Code Through the Looking Glass — All You Need is a Dictionary (and O(N) )

DZone 's Guide to

Code Through the Looking Glass — All You Need is a Dictionary (and O(N) )

Continuing with his series, Code Through the Looking Glass, Ayende Rahien discusses how a Dictionary class and an EmailSearcher method obtained the desired results, in a very unexpecting way.

· Web Dev Zone ·
Free Resource

The first question that I ask in the coding task goes something like this:

"Given a CSV file containing users' data, which is large, but can fully fit into memory, we want to be able to search by email address very quickly and get all the matching user ids. Optimize for fast queries over fast startup".

The intent is basically that you'll read the file and load that into a dictionary, then use that to perform queries.

This candidate has done just that, although things started being strange pretty much from the get-go:

Dictionary<int, string> emails = new Dictionary<int, string>();

That seemed like a pretty strange way to set things up, but we have seen crazier. At this point, I thought that they are probably storing the hash code of the email in the dictionary, and the string value is the concatenated list of all the matching ids.

The truth was far more interesting. Here is the code for querying:

public Dictionary<int, int> EmailSearcher(string email)
    Dictionary<int, int> answer = new Dictionary<int, int>();
    int count = 0;
    foreach (var entry in emails)
        if (entry.Value.ToString().Equals(email, StringComparison.OrdinalIgnoreCase))
            answer.Add(count, entry.Key);

    return answer;

This code actually has multiple levels of strangeness. The obvious one is that this is doing a linear search on the dictionary, but look at the return type as well.

The candidate was well aware that this code is not able to handle large amounts of information, so the candidate sent us an alternative implementation. But I'll talk about that in my next post.

c#, development, dictionary class

Published at DZone with permission of Oren Eini , DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}