Sorted Distinct-Integer Class: add() Reports New or Old, Then Cut Its Memory
Company: Bloomberg
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
Design a class with a method `add(x)` that records one integer per call. Each call returns whether `x` is new (never added before) or old (already added), together with all distinct values added so far in ascending order. For example:
```text
add(2) -> [new, 2]
add(1) -> [new, 1, 2]
add(2) -> [old, 1, 2]
add(3) -> [new, 1, 2, 3]
add(1) -> [old, 1, 2, 3]
```
After a first version, the interviewer stressed that `add` is called a very large number of times and questioned whether its space usage was acceptable, without saying what they were looking for.
### Clarifying Questions
- What is the range of the integers (32-bit, 64-bit, small and nonnegative)? Can they be negative?
- Must every call return a fresh copy of the full sorted list, or may it return a read-only view, an iterator, or only the change?
- Roughly how many calls, and how many distinct values, are expected? Do callers keep the lists returned by earlier calls?
- Is the class used from several threads?
- Will removals ever be needed?
### Part 1 — Implement the class
Write the class and its `add` method.
```hint Two questions per call
Each call asks "have I seen this value?" and "what is the sorted order now?"; consider whether one structure can answer both.
```
#### What This Part Should Cover
- Correct new and old detection and correctly sorted output
- A structure suited to the language (a balanced tree set, a sorted container, or binary search over a sorted array)
- Behavior on the first call and on repeated values
### Part 2 — Analyze time and space
State the cost of one call and of many calls.
```hint Count the output too
Include the cost of building the returned list in each call, not only the cost of finding the position.
```
#### What This Part Should Cover
- Per-call cost of lookup, insertion and building the returned list
- Total cost over many calls
- Space as a function of the number of distinct values versus the number of calls
### Part 3 — Reduce the space for a very large number of calls
The interviewer says the call count is huge and the space is not acceptable. Propose how to reduce it.
```hint Know the range
Ask what is known about the range and density of the integers; the best representation changes with the answer.
```
#### What This Part Should Cover
- Compact representations and when each one wins (packed arrays, bitmaps over a known range, compressed bitmaps, runs)
- Concrete memory figures for the options
- Whether the return contract itself is the real cost, and how to change it
### What a Strong Answer Covers
- A correct implementation with new and old detection and sorted output
- Honest complexity, including the linear cost of returning the sorted list on every call
- The observation that memory grows with distinct values, not with calls, unless callers keep every returned list
- Space options matched to range and density, with numbers, including the weakness of a plain bitmap for sparse values
- Clarifying the return contract as a possible source of the problem
### Follow-up Questions
- The values are sparse 64-bit integers. What does a bitmap cost, and what would you use instead?
- How would you also support `remove(x)`?
- Callers only ever need the k smallest values after each call. How does the design change?
- How would you persist the set so that it survives a restart?
Overview: Design a class whose add method records an integer, reports whether it was new or already seen, and returns all distinct values in sorted order. It tests choosing a sorted structure, honest per-call complexity including the returned list, and reducing memory when the method is called a huge number of times.
Read the full Bloomberg Software Engineer interview experience this question came from