Interview Question
Country: United States
Interview Type: Phone Interview
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
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.
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):
- mrmekon November 20, 2012def 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] = [] database[char].append(line) 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 brad pitt yygr""") print find_entries(d, "ry") print find_entries(d, "dd")