FastPrepInsert Delete GetRandom O(1)
Problems/Insert Delete GetRandom O(1)

Insert Delete GetRandom O(1)

Charta Health logoCharta Health● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This was the first virtual coding round for a Senior Software Engineer role at Charta Health. The task was the well-known Insert Delete GetRandom O(1) problem, named only by a link. The interviewer gave a few hints along the way.

The report gives no rules, limits or examples. This version uses the usual rules. Insert and remove return whether they changed the set, and getRandom picks fairly. You get the calls as a list of commands instead of a class. Every getRandom in the tests comes when one value is left, so its answer is fixed. There are up to 2,000 commands.

Our version is about 85% the same as the reported question.

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": add x if it is not in the set. Record "true" if it was added, or "false" if x was already there.
  • "remove x": take x out if it is in the set. Record "true" if it was removed, or "false" if x was 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 before x.
  • x is 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

  • Design Hit CounterPHONE SCREEN · Seen Nov 2026
  • Integers With Multiple Sum of Two CubesPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Concurrent Token-Bucket Rate LimiterPHONE SCREEN · Seen Sep 2026
  • Inorder Successor in a Binary Search TreeONSITE INTERVIEW · Seen Sep 2026

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
All Charta Health interview questionsSee Charta Health hiring insights
Saved
class Solution {
    public String[] processRandomizedSet(String[] operations) {
        // Write your code here.
    }
}
Checking account…