How should I practice Search for an Element in a Stream?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon phone screen problems in FastPrep.

Is Search for an Element in a Stream associated with Amazon?

FastPrep tags this as a Amazon phone screen coding practice problem when the problem catalog has that company and stage context.

Search for an Element in a Stream

Amazon● MediumINTERNPHONE SCREEN

Problem statement

Values arrive one at a time in a stream. At any moment, you may be asked whether a given value has already arrived.

You are given two arrays of the same length, operations and values. Process them from left to right. At index i:

If operations[i] is "add", the value values[i] arrives in the stream.
If operations[i] is "search", check whether values[i] arrived at an earlier index.

Return a boolean array with one entry for each "search", in the order the searches appear. An entry is true if that value arrived before the search, and false otherwise. A value may arrive more than once; a repeat arrival changes nothing. If there are no searches, return an empty array.

Follow-up

Can you solve it without a hash set or hash map? Keeping the values in a list makes each search take O(n) time, and a plain binary search tree can turn into a long chain. Use a self-balancing binary search tree, such as an AVL tree, so that every operation takes O(log n) time in the worst case, and write the rotation code that keeps the tree balanced.

Function

searchStream(operations: String[], values: int[]) → boolean[]

Examples

Example 1

operations = ["add","add","search","search","add","search"]values = [5,3,3,7,7,7]return = [true,false,true]

The values 5 and 3 arrive first, so the search for 3 returns true. The value 7 has not arrived yet, so the next search returns false. After 7 arrives, searching for it again returns true.

Example 2

operations = ["search","add","add","search","search"]values = [4,4,4,4,-4]return = [false,true,false]

The first search for 4 happens before anything arrives, so it returns false. Then 4 arrives twice, and the search for 4 returns true. The value -4 never arrives, so the last search returns false.

Example 3

operations = ["add","add","add"]values = [10,20,30]return = []

There are no "search" operations, so the result is an empty array.

Constraints

1 <= operations.length <= 10^4
values.length == operations.length
Each operations[i] is either "add" or "search".
-10^9 <= values[i] <= 10^9