Interview Question | Senior SDE | Given a search term, find all occurrences of similar words

notaprogrammer 0
Viewed 55

I was recently asked this in one of my technical coding interview and I am really struggling to find a solution/similar problem on leetcode and elsewhere. If any of you know a good solution or can point me to a link where a similar problem/solution exists, please do so. Appreciate the help I can receive on this forum!

Here's the question:

When you’re typing too fast you might press the wrong key. For example if you want to press G you might press its neighbors T, F, B or H (all with distance 1 from G) or even worse by pressing further letters like R (at distance 2) or Z(at distance 5).

The keyboard layout looks like this:

q  w  e  r  t  y  u  i  o  p
a  s  d  f  g  h  j  k  l
z  x  c  v  b  n  m

Given a word as search_term, search among all entries in the database and find every occurrence of that word with the distance of at most maximum_distance

Example Input:
{ "maximum_distance": 3, "search_term": “taj”},

Example Database:
[
"The King David Jerusalem Hotel, Jerusalem",
"Burj Al Arab Jumeirah, Dubai",
"The Plaza, New York City",
"Fairmont Le Chateau Frontenac, Quebec City",
"Old Faithful Inn, Yellowstone National Park",
"Grand Hotel Europe, St. Petersburg",
"Disney's Contemporary Resort, Florida",
"The Beverly Hills Hotel, Beverly Hills",
"Taj Mahal, Mumbai"
]
Example output:
Found: rab, Distance: 3, Hotel: Burj Al Arab Jumeirah, Dubai
Found: rah, Distance: 1, Hotel: Burj Al Arab Jumeirah, Dubai
Found: Fai, Distance: 2, Hotel: Fairmont Le Chateau Frontenac, Quebec City
Found: ten, Distance: 3, Hotel: Fairmont Le Chateau Frontenac, Quebec City
Found: Fai, Distance: 2, Hotel: Old Faithful Inn, Yellowstone National Park
Found: Taj, Distance: 0, Hotel: Taj Mahal, Mumbai
interview data-structures algorithm
1 Answers

So what you have here is a four-connected lattice (at the core, it is not a full rectangle), representable as an undirected graph where each node is labelled by its letter.

On this graph you can pre-define, for each node, all neighbors of distance N. You could do this manually, as it only needs to be done once, initially, and N is constraint by the keyboard layout.

Alternatively, you can calculate all neighbors of max. distance N on the fly given the constructed graph, e.g. by taking the adjacency matrix to the N-th power (see https://math.stackexchange.com/questions/736863/power-of-an-adjacency-matrix).

Now the processing is rather straight forward. You do a substring search with the twist, that for each letter of the search term, you accept all letters in the set of this letter (the pre-defined set of letters with distance <= N). You could also do it the other way round as you have an undirected graph at hands.

You can implement a naïve substring search with two cascaded for-loops or adapt a more efficient algorithm, which would become relevant for long strings and especially for long search terms. (For a discussion of these algorithms see What is the fastest substring search algorithm?)

ypnos0
Related