TikTok·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Jun 2026

Summary

TikTok coding round focused entirely on one data structure problem that sounds straightforward until you actually try to implement it correctly under pressure. The duplicate-handling requirement is where things get interesting.

Questions Asked (1)

Design a data structure that supports add(x), remove(x), and getRandom() all in average O(1) time, where duplicate values are allowed and getRandom must return each element with probability proportional to how many times it appears.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with a hashmap and felt pretty good about it until they asked about getRandom.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a dynamic array to store all elements (including duplicates) and a hash map from value to a set of indices in the array. For add, append the value and add its index to the map; for remove, swap the target element with the last element, update the map for both, and pop the last element; for getRandom, pick a random index from the array. This ensures average O(1) time for all operations and correct probability proportional to frequency.

Pro tip: Mention that using a set of indices per value allows O(1) removal even with duplicates, and discuss the trade-off between using a set versus a list for indices (e.g., set gives O(1) removal but higher constant factors).

1. Clarify requirements and constraints

Confirm that duplicates are allowed, getRandom must be weighted by frequency, and all operations should be average O(1). Ask about memory constraints and whether values can be any type.

2. Design the core data structures

Propose a dynamic array (list) to store all elements in order, and a hash map mapping each value to a set of indices where it appears in the array.

3. Implement add and remove operations

For add: append to array, add index to map. For remove: get an index from the map, swap with last element, update map for swapped element, remove last element, and remove index from map.

4. Implement getRandom

Generate a random integer between 0 and array length - 1 and return the element at that index. This gives each occurrence equal probability, hence weighted by frequency.

5. Analyze complexity and edge cases

Discuss average O(1) time for all operations, handle edge cases like removing the last element, removing when only one occurrence, and empty structure.

Key Points to Mention

Use of a dynamic array to store all elements, enabling O(1) random access for getRandom.
Hash map from value to a set of indices for O(1) average-time add and remove.
Swap-with-last technique to achieve O(1) removal from the array.
Updating the index set for the swapped element during removal.
Probability proportional to frequency is naturally achieved by uniform random selection over the array of all occurrences.
Trade-offs: using a set for indices gives O(1) removal but may have higher constant factors; alternative is a list with lazy deletion but that complicates getRandom.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.