← Atlassian Interview InsightsSoftware Engineer

Atlassian·Software Engineer·Onsite - System Design / Architecture·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Atlassian system design round for a software engineer role. The core problem was designing a data structure that handles four operations all in constant average time, which sounds manageable until you actually try to make getMaxKey and getMinKey work without scanning everything.

Questions Asked (1)

Q1

Design a data structure that supports inc(key), dec(key), getMaxKey(), and getMinKey() all in O(1) average time. Keys with a count of zero should be removed automatically.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs
Author's notes

My first instinct was a heap and a hashmap, which is wrong the moment you think about dec() and removal.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and constraints, then propose a design using a hash map for O(1) key lookup and a doubly linked list of buckets to group keys by count, enabling O(1) access to min and max. Walk through each operation, explaining how you maintain the bucket list sorted by count and handle key removal when count reaches zero.

Pro tip: Emphasize that the bucket list is sorted by count, so getMaxKey and getMinKey are O(1) by checking the tail and head respectively; this shows you understand the invariant that makes the design work.

1. Clarify requirements and constraints

Confirm that keys are strings, counts are integers, and operations should be O(1) average. Ask about concurrency or memory constraints if relevant.

2. Propose the core data structures

Use a hash map from key to its bucket, and a doubly linked list of buckets where each bucket holds a set of keys with the same count. Buckets are ordered by count.

3. Explain inc and dec operations

For inc, move the key to the next bucket (or create one) and update the hash map; for dec, move to the previous bucket, and if count becomes zero, remove the key entirely.

4. Explain getMaxKey and getMinKey

Return any key from the last bucket for max and from the first bucket for min, both in O(1) by accessing the head or tail of the bucket list.

5. Discuss edge cases and complexity

Cover empty structure, single key, and bucket merging/removal. Confirm all operations are O(1) average and mention space complexity O(n).

Key Points to Mention

  • Hash map for O(1) key lookup and bucket association
  • Doubly linked list of buckets sorted by count
  • Each bucket contains a set of keys with the same count
  • Moving keys between buckets on inc/dec, creating/removing buckets as needed
  • Removing keys with count zero automatically
  • O(1) average time for all operations and O(n) space

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