Interview Question

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
of 1 vote

Take a hit up front and build a hash table mapping characters to an array of dictionary strings that contain that character, i.e: 'r ==> "mary", "yygr"'

When you search for a string, you take the intersection of the dictionary strings for each character in the input string. You are looking for strings from the dictionary that show up for *every* character in the input string.

Python example (doesn't read from file or stdin):

def dictionary_to_database(dict):
    database = {}
    for line in dict.split("\n"):
        for char in sorted(list(set(line))):
            if char not in database:
                database[char] = []
    return database

def find_entries(database, string):
    intersection = database[string[0]]
    for char in string[1:]:
        intersection = set(intersection) & set(database[char])
    return list(intersection)

d = dictionary_to_database("""mary
print find_entries(d, "ry")
print find_entries(d, "dd")

- mrmekon November 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 votes

I was thinking the same thing but with following difference:
. Put all the string in an array ARR
. Create a HashMap that holds key-value pair as 'character'->'index of the string in the ARR array'
. Then whenever 2nd string is entered, we check each character of this string and try to identify the list of indexes that match that character.
. For each such character, we have to identify the intersection of the indexes.
. Since we need to identify the intersection between the list of indexes(integers), it would be easy compared to identifying intersection between string.
. For optimization purpose, we can remove the duplicate characters from the 2nd input string

- Mario November 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
of 0 votes


The difference between our solutions just comes down to specifics of the language. In Python, the strings will all have the same object IDs. I'm not sure how the set's "intersection" function does comparisons, but if it just compares object IDs then my solution is already doing integer comparison instead of string comparison. But it might not be -- definitely something to keep in mind.

- mrmekon November 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
of 0 vote

If storage is not a concern then we can use suffix tree.
It will provide best searching solutions in such cases.

- ashu November 20, 2012 | Flag Reply

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More


CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More