FastPrepDynamic Prefix Search Collection

Dynamic Prefix Search Collection

Amazon logoAmazon● MediumFULLTIMEONSITE INTERVIEW

Problem statement

Implement a dynamic collection of lowercase words. Process the finite array operations from left to right.

Each operation has one of these forms:

  • INSERT word: add word to the collection. Inserting a word that is already present does not create a duplicate.
  • SEARCH prefix: return up to three stored words that begin with prefix, ordered lexicographically.

The collection starts empty. Return one row for every SEARCH operation, in command order. INSERT operations do not produce output.

Function

processPrefixSearch(operations: String[]) → String[][]

Examples

Example 1

operations = ["INSERT mouse","INSERT mobile","INSERT moneypot","INSERT monitor","INSERT mousepad","SEARCH mo","SEARCH mou"]return = [["mobile","moneypot","monitor"],["mouse","mousepad"]]

The first search keeps the three lexicographically smallest matches for mo. The longer prefix mou has only two matches.

Example 2

operations = ["INSERT app","INSERT apple","SEARCH ap","INSERT apex","INSERT app","SEARCH ap","SEARCH z"]return = [["app","apple"],["apex","app","apple"],[]]

The second insertion of app is idempotent. After apex is added, it is first lexicographically. No stored word begins with z.

Constraints

  • 1 <= operations.length <= 100000.
  • Every operation is exactly one documented command with one separating space.
  • Every word and prefix contains 1 to 100 lowercase English letters.
  • The total number of characters across all operations is at most 1000000.
  • At least one operation is SEARCH.

More Amazon problems

See Amazon hiring insights
Saved
public String[][] processPrefixSearch(String[] operations) {
    // Write your code here.
}
operations["INSERT mouse","INSERT mobile","INSERT moneypot","INSERT monitor","INSERT mousepad","SEARCH mo","SEARCH mou"]
expected[["mobile", "moneypot", "monitor"], ["mouse", "mousepad"]]
Checking account…