Skip List
Updated
Problem statement
You get a script of calls to run on a collection of whole numbers. Run the calls in order and collect their answers.
The collection starts empty. A number can be stored many times, once for each add call. There are three kinds of call:
add stores one more copy of the number and answers nothing.
search answers true when the number is stored at least once, and false when it is not stored.
erase takes away one stored copy of the number and answers true. When the number is not stored, it changes nothing and answers false.
The script is two arrays of the same length. Call i uses the name operations[i] and the number numbers[i]. Return the answers of the search and erase calls as a boolean[], in the order the calls were made. If the script has no such call, return an empty array.
The name comes from the structure this exercise is about. A skip list keeps the numbers sorted in a linked list and adds higher lanes that link only some of the nodes, so a search can jump ahead on a high lane and step down to the lower lanes. Do not use a built-in sorted container. Only the answers are checked, so any correct approach passes, but try to build a real skip list, where each call takes about O(log n) expected time when n numbers are stored.
Function
skipListCalls(operations: String[], numbers: int[]) → boolean[]Examples
Example 1
operations = ["add","add","search","search","erase","search"]numbers = [5,10,10,7,5,5]return = [true,false,true,false]Add 5 and 10. Searching 10 gives true and searching 7 gives false, because 7 was never added. Erasing 5 gives true because a 5 is there, and then searching 5 gives false.
Example 2
operations = ["add","add","add","erase","search","erase","add","search","search"]numbers = [40,20,30,25,30,20,25,25,20]return = [false,true,true,true,false]Store 40, 20 and 30. Erasing 25 gives false, because 25 is not stored, and the stored numbers stay as they are, so searching 30 gives true. Erasing 20 gives true. After adding 25, searching 25 gives true, and searching 20 gives false because its only copy is gone.
Example 3
operations = ["add","add","search","erase","erase","search"]numbers = [50000,0,50000,50000,50000,0]return = [true,true,false,true]The largest allowed number and the smallest one are both stored. Searching 50000 gives true. The first erase of 50000 removes it and gives true, the second finds nothing and gives false. The number 0 is still there, so the last search gives true.
Example 4
operations = ["add","add","add"]numbers = [1,2,3]return = []Add calls do not produce a result. With only add calls, the answer is an empty array.
Constraints
- Every
operations[i]is exactly one of the words"add","search"and"erase". - Every
numbers[i]is a whole number with0 <= numbers[i] <= 5 * 10^4. - A script has at least one call and at most 2000 calls:
1 <= operations.length <= 2000. - The two arrays have the same length:
numbers.length == operations.length.
More Bloomberg LP Phone Screen questions
- N-ary Index-Path Encoder and DecoderPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Trapping Rain WaterPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Word SearchOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Fewest Coins CombinationPHONE SCREEN · Seen Nov 2026
- Recommend Films from Viewers Who Watched Everything You DidPHONE SCREEN · Seen Nov 2026
- Track New Values in Sorted OrderPHONE SCREEN · Seen Nov 2026
- Design Browser HistoryPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Mutable Stock Price Top KPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Sparse Vector and Matrix OperationsPHONE SCREEN · Seen Oct 2026
- Add Two Numbers IIPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Least Frequently Used CacheNVIDIA · PHONE SCREENNVIDIA interview questions
- Checkpointed Dynamic SequenceOpenAI · PHONE SCREENOpenAI interview questions
- LFU CacheFreshworks · PHONE SCREENFreshworks interview questions
- LFU Cache with LRU Tie-BreakingRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
- LFU CacheGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Least Frequently Used Cache SimulatorAdobe · PHONE SCREENAdobe interview questions
- Windowed Key-Value MapConfluent · PHONE SCREEN · ONSITE INTERVIEWConfluent interview questions
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- LRU CacheServiceNow · PHONE SCREEN · ONSITE INTERVIEWServiceNow interview questions
- LRU CacheGimlet Labs · PHONE SCREEN
Interview reports that mention this question
Bloomberg LP interview experiences
- Bloomberg AI-Assisted Coding Round, All Levels: 14 Experiences
- Bloomberg SWE Intern Interview Questions: 68 Questions
- Bloomberg Interview Questions, Level Not Reported: 65 Questions
- Bloomberg Experienced Design & More: 126 Questions (Part 2 of 2)
- Bloomberg Experienced SWE Interviews: 167 Questions (Part 1 of 2)