Insert Delete GetRandom O(1)
Updated
Problem statement
Build a set of integers where adding a value, removing a value, and picking a random value each take O(1) time on average.
The set starts empty. Handle the commands in operations in order, and record one result for each command:
"insert x": addxif it is not in the set. Record"true"if it was added, or"false"ifxwas already there."remove x": takexout if it is in the set. Record"true"if it was removed, or"false"ifxwas not there."getRandom": pick one value from the set, where every value has the same chance of being picked. Record that value as a decimal string.
So that every answer can be checked, a "getRandom" command only comes when the set holds exactly one value, and the only correct pick is that value. Your set should still pick fairly from a set of any size in O(1) time.
Return the list of results.
Function
processRandomizedSet(operations: String[]) → String[]Examples
Example 1
operations = ["insert 4","insert 9","insert 4","remove 4","getRandom"]return = ["true","true","false","true","9"]The set gets 4 and then 9. The second insert 4 fails because 4 is already there. Removing 4 works and leaves only 9, so getRandom must return 9.
Example 2
operations = ["remove 7","insert -3","getRandom","remove -3","insert -3"]return = ["false","true","-3","true","true"]7 was never added, so removing it fails. After insert -3, the set is just -3, so getRandom returns it. Then -3 is removed, so adding it again works.
Example 3
operations = ["insert 2147483647","insert -2147483648","remove 2147483647","getRandom"]return = ["true","true","true","-2147483648"]Both ends of the value range can be stored. After the largest value is removed, only -2147483648 is left.
Constraints
1 <= operations.length <= 2000- Each command is
"insert x","remove x"or"getRandom", with exactly one space beforex. xis an integer written in decimal with no leading zeros or plus sign, and-2^31 <= x <= 2^31 - 1.- A
"getRandom"command only comes when the set holds exactly one value.
More Charta Health interview questions
Similar questions at other companies
- Portfolio Tickers with Constant-Time Random PickCitadel · PHONE SCREENCitadel interview questions
- Build a Pivot Table with TotalsSigma Computing · PHONE SCREEN
- Process On-Call Routing OperationsOpenAI · PHONE SCREENOpenAI interview questions
- Stateful Paginated Fetch NLyft · PHONE SCREENLyft interview questions
- Linear-Probing Key-Value StoreEase · PHONE SCREEN
- Escape Room LeaderboardPinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Role-Based Network Access ControlOkta · PHONE SCREENOkta interview questions
- Track Package Receipt GapsAmazon · PHONE SCREEN
- Transformer KV Cache OperationsNVIDIA · PHONE SCREENNVIDIA interview questions
- Rate Limiter with Hourly and Daily Effort QuotasZscaler · PHONE SCREENZscaler interview questions