Sorted Distinct-Integer Class: add() Reports New or Old, Then Cut Its Memory

Quick 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.

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

Bloomberg logo
Bloomberg
Oct 29, 2026
mediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals
1
0

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:

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 Guidance

  • 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.

What This Part Should Cover Guidance

  • 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.

What This Part Should Cover Guidance

  • 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.

What This Part Should Cover Guidance

  • 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 Guidance

  • 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 Guidance

  • 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?