Katkat
Back

Find the Closest Candidate String by Edit Distance

TargetBackend Engineer · Online Assessment
MediumBackend EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests the implementation of the Levenshtein distance algorithm (Edit Distance) and the ability to manage tie-breaking logic when comparing multiple strings against a query.

Problem Statement

You are given a list of candidates (strings) and a list of queries (strings). For each query, you must find the candidate string that has the smallest Levenshtein edit distance to that query.

If two or more candidates result in the same minimum edit distance, select the candidate that appears earliest in the original candidates list (the deterministic tie-break).

Levenshtein distance between two strings s1 and s2 is defined as the minimum number of operations (insertions, deletions, or substitutions) required to transform s1 into s2.

Function Signature

def find_closest_candidates(candidates: list[str], queries: list[str]) -> list[str]:
    # ...

Constraints

  • 1 <= len(candidates) <= 500
  • 1 <= len(queries) <= 100
  • String lengths range from 0 to 100
  • All strings consist of lowercase English letters.

Examples

Example 1:

  • candidates: ["apple", "apply", "apricot"]
  • queries: ["aple"]
  • Output: ["apple"]
  • Explanation: Edit distance between "aple" and "apple" is 1 (insert 'p'). Distance to "apply" is 2. Distance to "apricot" is 4.

Example 2:

  • candidates: ["cat", "bat", "rat"]
  • queries: ["hat"]
  • Output: ["cat"]
  • Explanation: All have distance 1. "cat" appears first, so it is the tie-break winner.

Hints

Hint 1

Implement a helper function that uses a 2D dynamic programming table of size (len(s1)+1) x (len(s2)+1) to calculate the Levenshtein distance.

Hint 2

For each query, iterate through the list of candidates and keep track of the current minimum distance and the corresponding candidate index.

Hint 3

Since you only need the previous row to compute the current row in the DP table, you can optimize space complexity from O(N*M) to O(min(N, M)).

Follow-up questions

  • How would you optimize the search if the number of candidates increased to 1,000,000?
  • Can you explain the time complexity of your solution and why it is dependent on the string lengths?
  • What changes are needed if the cost of an 'insertion' is higher than a 'substitution'?