1. Java data structures

When they ask how HashMap works I start from the table, not from “it is O(1).” Under the hood it is an array of bins, Node<K,V>[] table, and because capacity is always a power of two the index is mixed-hash & (n-1) instead of a slow modulo. Java first mixes with h ^ (h >>> 16) so the high sixteen bits still change which bin you land in; without that mix, keys whose hashes only differ in the high bits would pile into the same few low-bit buckets. After you land in a bin you walk the chain or tree and only then call equals, because two different keys can share a hash. You must override both equals and hashCode together or the key is broken: you will put with one instance and get with an “equal” instance and miss. Collisions start as a linked list; at length 8, if the table is already at least 64, Java 8 treeifies the bin into a red-black tree so a bad chain becomes O(log n) instead of O(n), and if the table is still small it resizes instead of treeifying. Load factor 0.75 is the resize trigger: when size exceeds 0.75 times capacity the table doubles and every entry rehashes, which is why average get, put, and remove stay O(1). HashSet is not a second data structure; it is a HashMap whose values are a dummy PRESENT object, so add and contains are put and get, and it allows one null the same way HashMap allows one null key. The map is not thread-safe and the iterator is fail-fast; if they ask whether I have used this, an in-process HashMap is one JVM, while Redis was the shared cache behind Ylogx’s −35% bot database latency.

Example: Keys "alice" and "Alice" are different strings, so they have different hashCodes and usually land in different bins; equals is false, so they are two map entries. If you write a User key whose equals lowercases the name but you forget hashCode, put(new User("alice"), 1) and get(new User("Alice")) can miss even when equals would have said they match, because they hash to different bins and the walk never compares them.

If they probe: average get/put/remove O(1); adversarial or broken hash O(n) until the bin treeifies, then O(log n). Do not mutate a key after it is in the map. ConcurrentHashMap only if they ask threads. Fail-fast iterator throws on structural change. Override equals and hashCode together.

I pick a PriorityQueue when I need repeated extract-min or extract-max, not a fully sorted snapshot sitting in memory. A binary heap gives offer and poll in O(log n) and peek in O(1), which is exactly Connect Ropes, the median stream, Merge k, and Top-K. If I sort the whole collection on every query I pay O(n log n) even when I only wanted the next smallest, so sort-every-time loses as soon as the set is live. Java’s PriorityQueue is an array-backed binary heap, not a TreeMap. TreeMap is a red-black tree: every insert, delete, and lookup is O(log n), and I can delete an arbitrary key, which the heap cannot. Heap remove(Object) scans in O(n), and there is no decrease-key, so I do not pretend Dijkstra can update a node in O(log n) without an extra map. I sort once when the input is static and I need the full order. I use TreeMap when I need ordered keys, ceiling or floor, or delete-by-key. On the word-count follow-up, HashMap counts plus a heap of size K is how I get top-K reviews without Arrays.sort of every review.

Example: Heap of ropes 2, 3, 4. The heap always merges the two currently smallest: poll 2 and 3, cost 5, offer 5; then poll 4 and 5, total cost 14. If I had merged 3 and 4 first I would pay 7 + 9 = 16, which is worse. After the first merge a new rope of length 1 can arrive; sort-once is then wrong because the two smallest have changed, and the heap still extracts them.

If they probe: peek O(1), offer/poll O(log n), remove(Object) O(n). The iterator is heap order, not sorted. Comparator is Integer.compare, not a-b. Lazy Dijkstra because there is no decrease-key. TreeMap if they need arbitrary delete.

They gave a dictionary of good words and a list of reviews, and the HashMap internals question came after this DSA. I put the dictionary in a HashSet so each token is average O(1) contains; scanning a list of the dictionary would be O(d) per word and they will call that out. I count how many tokens of each review hit the set, then sort the reviews by that count and break ties lexicographically. Total time is linear in the characters plus r log r for the sort. A HashSet is a HashMap with dummy PRESENT, so the same bin story applies if they pivot to internals. If they switch the ask from a full ranking to the top k reviews, I stop sorting all r and keep a min-heap of size k, which is why they asked PriorityQueue next. I do not invent a LeetCode id for this prompt.

Example: Dictionary {good, great}. Review A “good product” scores 1, review B “great good item” scores 2, review C “meh” scores 0. Sorted order is B, then A, then C. If they only want top 1, a size-1 min-heap keeps B and never sorts C versus A as a full array.

If they probe: tokenization, case, and punctuation. Complexity O(total chars + r log r). Top-k is O(r log k) after the counts. Same HashSet internals as the HashMap question. Do not invent an LC id.

The unique lookup is roll number, so that is the HashMap key and the value is a Student holding name, marks, and a rank I recompute. Rank is not the map key: two students can share marks, and I still need get-by-roll in O(1) average. TreeMap would sort by roll, which does not rank by marks, and get would become O(log n) for no gain. On mutation I copy the values and sort by marks in O(n log n), or I leave rank until query time; either is fine in forty minutes. The internals sentence they want after the OOD is the same as the HashMap question: bins, mix h ^ (h >>> 16), treeify at 8, load 0.75, equals after hash. I do not put a HashMap inside Student. ConcurrentHashMap only if they bring threads, because HashMap has no structural sync. Integer as a key is fine; I do not use Student as a key unless equals and hashCode are defined on roll number only.

Example: Roll 101 Alice 90, roll 102 Bob 95, roll 103 Cara 90. The map has three keys. Sort values by marks descending: Bob rank 1, then Alice and Cara depending on the tie rule I clarified (dense 2,2 versus unique 2,3). Lookup of roll 103 is still one HashMap get, not a scan for rank.

If they probe: why not TreeMap keyed on marks (duplicate marks collide). Why not List-only (get-by-roll becomes O(n)). HashMap internals if they follow the 6653463 script. No structural sync on HashMap.

I always merge the two currently smallest ropes, because every time a length appears in a merge I pay that length again in later merges. That is the Huffman argument: a large partial sum should be created as late as possible so I do not keep re-adding it. After a merge the new rope goes back into the set, so the two smallest can change; sorting once and scanning left to right is the wrong algorithm as soon as a merge creates a length that sits between later originals. Java’s default PriorityQueue is a min-heap; I use Long because the hiring manager on that AUTA loop called out overflow. I poll two, add a+b to the running cost, offer a+b back, and stop when one rope remains. A single rope costs zero. Brute search of merge orders is factorial, which is why the heap is the whole solution. Time is O(n log n) and space is O(n). I do not treat this as a Job 10454435 prediction; it is the 8362604 AUTA APAC card, full write-up in Answer-BIBLE section 1.

Example: Heap of ropes 2, 3, 4. Poll 2 and 3, cost 5, offer 5; heap is now 4 and 5; poll 4 and 5, add 9, total cost 14. Merge 3+4 first: cost 7, then 7+2 = 9, total 16, which is worse because the large 7 is paid on top of the leftover 2. The heap keeps choosing the current mins so that does not happen.

If they probe: overflow → long, not int. n=1 returns 0. Proof sketch is Huffman / never pay a large partial extra times. O(n log n) time, O(n) space. Not a 10454435 prediction.

I keep the lower half in a max-heap lo and the upper half in a min-heap hi so the two middle values are always the two peeks. The sizes differ by at most one; I let lo be equal or one bigger so the odd median is lo.peek() and the even median is the average of both tops. Add is O(log n) because I offer and maybe move one element across; findMedian is O(1). Sorting an ArrayList on every find is O(n log n), and they asked time and space out loud on the 8362604 loop. In Java the max-heap is new PriorityQueue<>(Comparator.reverseOrder()); I refuse (a, b) -> b - a because large ints overflow, and I use Integer.compare(b, a) or reverseOrder instead. One TreeSet cannot hold duplicates, so it is the wrong “ordered set” shortcut. TreeMap of counts works as a sorted multiset but is slower to explain under time pressure. Sliding-window median needs delete, which a heap cannot do cheaply, so I switch to TreeMap or lazy deletion only if they ask.

Example: Stream 1, then 2, then 3. After 1, lo holds 1 and the median is 1. After 2, lo holds 1 and hi holds 2, median 1.5. After 3 I rebalance so lo holds 2 and 1 (max-heap peek 2) and hi holds 3, median 2. The invariant is: every value in lo is ≤ every value in hi, and the sizes stay within one.

If they probe: add O(log n), find O(1). Null is forbidden in PriorityQueue. Duplicates are fine with two heaps. Do not use b-a as a comparator. Sliding window needs TreeMap or lazy heap. Full card in Answer-BIBLE section 2.

Each list is already sorted, so the next global minimum is always among the k current heads. I put those heads in a min-heap keyed on val, poll the smallest, append it to a dummy tail, and if that node has a next I offer the next. That is N polls and at most N offers, each O(log k), so O(N log k) with only O(k) extra space. Dumping every value into an array and sorting is O(N log N) and throws away the fact that the lists were sorted. Pairwise merge-two from left to right is O(k N) extra pointer work because early lists get re-merged many times. Divide-and-conquer pairwise merge is also O(N log k) without a heap, and that is the follow-up if they dislike the PriorityQueue. I skip null heads or the comparator throws a NullPointerException. Dummy node avoids a special case for the first append.

Example: Lists [1,4,5], [1,3,4], [2,6]. The heap starts with the three heads 1, 1, and 2. Poll 1 from the first list and offer 4; poll 1 from the second and offer 3; poll 2 and offer 6; continue until the merged list is [1,1,2,3,4,4,5,6]. At every step the heap holds at most three nodes, not all N values.

If they probe: O(N log k) time, O(k) space. Skip null heads or the comparator NPEs. Comparator.comparingInt(n -> n.val). Divide-and-conquer merge as the heap-free follow-up. Full card in Answer-BIBLE section 1.

I need get and put in average O(1) and I need to know which key is least recently used, so I pair a HashMap from key to node with a dummy-headed doubly linked list of those nodes. Most-recent sits immediately after head; the LRU node is tail.prev. Get looks up the map, returns -1 on miss, and on hit unlinks the node and splices it after head because a read counts as a use. Put updates an existing key by unlinking the old node, or inserts a new node after head; if size then exceeds capacity I unlink tail.prev and map.remove that key. LinkedHashMap constructed with access-order true plus removeEldestEntry is the one-sentence Java cheat they will accept, and then I still write the four pointer assignments, because that is the actual ask. TreeMap by timestamp is O(log n) and needs a clock; I refuse it. Thread-safety, Redis LRU, and TTL are production follow-ups, not the Bhavya pointer problem. Login Tracker with new_login and get_oldest_login is the same HashMap-plus-DLL shape as mentor practice, but I could not verify it as an SDE I Round 2 or Job 10454435 question, so I will not present it as our round; the closest public card is this LRU.

Example: Capacity 2. put(1,1), put(2,2), list is 2 then 1 with 2 most-recent. get(1) returns 1 and moves 1 after head, so 1 is most-recent and 2 is LRU. put(3,3) evicts 2, map.remove(2). get(2) returns -1. After that get(3) and get(1) both hit. LinkedHashMap access-order would have done the same move-to-end on get, which is why I mention it, then I still draw head and tail.

If they probe: get and put average O(1) because map lookup plus splice, not because the list is scanned. Dummy nodes so unlink never hits null. Must map.remove on eviction or the map leaks. Get must move to front. Login Tracker remains unverified; do not pitch it as 10454435 or our R2.

Uniform random needs an array because get(i) is O(1); a HashSet can tell me membership but cannot pick a uniform index without scanning. Delete in the middle of an ArrayList is O(n) because of the shift, so I swap the victim with the last element, pop the last slot, and fix the HashMap index of whoever moved. The map is value to index, so insert, delete, and search are expected O(1). HashMap alone cannot pick uniformly without walking the values. With duplicates, as in LC 6573582, the map becomes value to a Set of indices, or a list of indices, so one value can sit in several slots. get(i) is O(1) only because ArrayList is an array; a LinkedList get would destroy the bound. I do not use a deque here, because I need random access by index.

Example: List [10, 20, 30], map {10:0, 20:1, 30:2}. Delete 20: swap with 30, list becomes [10, 30], then pop, map becomes {10:0, 30:1}. getRandom is list.get(rand.nextInt(list.size())), which is equally likely 10 or 30. If duplicates were allowed and 10 appeared twice, the map would hold two indices for 10.

If they probe: expected O(1) each. ArrayList.remove(i) in the middle is O(n) — that is why swap-delete exists. HashSet cannot O(1) random. Duplicate follow-up uses a Set of indices. Random.nextInt(size); empty structure is a clarify.

I count frequencies with a HashMap in linear time, then I do not need a full sort of every unique key. A min-heap of size k keyed on frequency keeps the k largest: I offer each unique, and if the heap grows past k I poll the current smallest of those k. That is O(n + u log k), which beats sorting u keys when k is much smaller than the number of uniques. A max-heap of all uniques is extra work in that case. Bucket sort by count is O(n) when the values are ints and counts sit in 0 through n. This is the same skeleton as a Heap-plus-HashMap medium; Rudraksh’s round used a hashtag only, and I will not stamp a LeetCode id on it. If the earlier review-count problem switches to top-k reviews, this is the heap I already described.

Example: Array [1,1,1,2,2,3], k=2. Counts are 1→3, 2→2, 3→1. The size-2 min-heap sees 1 (freq 3), then 2 (freq 2), then 3 (freq 1) which loses to the heap minimum, so the answer is 1 and 2. If k had been 3 I would keep all three uniques and a full sort would have been similar work.

If they probe: O(n + u log k) versus O(u log u) sort versus O(n) bucket. Tie-break on equal frequency: I ask. Comparator on freq with Integer.compare. If k is larger than uniques, return everything.

A Trie node is a children map, or a TrieNode[26] for lowercase English, plus an isWord flag or a payload. Insert, search, and prefix walk one character at a time, so they are O(L) in the string length. Exact whole-word lookup does not need a Trie; a HashMap of the strings is simpler because you only ever ask “is this exact key present.” The Trie wins when they ask startsWith, autocomplete, or shared prefixes, because a HashMap would have to scan every key. Kushank’s round named Trie only as a partial; the two Binary Search titles stayed unnamed, and I will not stamp LC 208 or 211. Word Ladder on the AUTA loop is a HashSet dictionary plus BFS, not a Trie, unless they ask to speed the twenty-six letter edges. Aditya’s Searchable Collection is HashMap for exact and Trie if prefix, and that loop was not UTA. Prefix into top-K is Trie plus heap; I could not verify the full 6282609 ask this pass.

Example: Insert “app” and “apple”. The nodes share a-p-p. startsWith("app") is true after three steps. search("app") is true only if that node’s isWord is set. search("ap") is false. A HashMap would hold the two full strings and could not answer “starts with ap” without iterating both keys.

If they probe: time O(L), space O(total characters times alphabet) or HashMap children. Delete is O(L) if you prune empty nodes; I often skip delete in Live Code. Do not force a Trie onto Word Ladder unless they ask. Do not stamp LC 208/211 on Kushank.

The title stays unnamed; I do not invent a problem statement for Shiwangi’s easy hashmap or Taanya’s maps-plus-heaps. I prepare the operations out loud: HashMap is average O(1) for counts and ids, a heap is peek O(1) and offer or poll O(log n) when I must repeatedly extract a min after counting. That pair is either count-then-top-k or a stream plus extract-min. If they poke HashMap internals I give bins, the mix, treeify at 8, and load 0.75, same as LC 6570344. A bookstore word-count OOD is a frequency map of words, which is the same map. This is not a Job 10454435 named question.

Example: Count words in a sentence with a HashMap, then if they ask the three most common words I build a size-3 min-heap on frequency instead of sorting the whole map. If they only ask whether a word appeared, the map alone is enough and a heap would be theatre.

If they probe: unnamed stays unnamed. Why that pair (count then extract-min). Same HashMap internals if they follow the bookstore path. Not 10454435.

LFU is not the UTA default two-DSA; Bhavya’s onsite card was LRU, and this is not Login Tracker. I keep a map from key to node, a map from frequency to a doubly linked list of keys with that frequency in LRU order, and an integer minFreq. Get increments frequency, moves the node to the next frequency list, and updates minFreq if the old list emptied. Put inserts at frequency one; on overflow I evict from the list of minFreq, the least recently used among that frequency unless they specify another tie-break. Get and put stay O(1) because every splice is on a known node. The LLD follow-up was an EvictionPolicy strategy so LRU versus LFU is a plug-in; I do not open with LFU on a UTA two-DSA unless they named it.

Example: Capacity 2. put(1,1), put(2,2), then get(1) so key 1 has frequency 2 and key 2 still has frequency 1. put(3,3) evicts 2, not 1, because minFreq is 1 and 2 is the LRU at that freq. If both had frequency 1, the tie-break would be LRU among that list.

If they probe: O(1) get/put. Tie-break is LRU among the same frequency. Not Bhavya LRU. Not Login Tracker. Not UTA-default. Strategy pattern if they want extensible.

HashMap from song name to node plus a doubly linked list gives insert, delete, and search by name in average O(1), which is the same pointer machine as LRU without a capacity eviction. I splice on known nodes the way I would in the cache: four pointer assignments to unlink, four to insert after a neighbor. If they mean insert at an integer index in an array, that cannot be O(1), so I ask whether playlist position matters. A random-access ArrayList would make index insert O(n). Dummy head and tail keep those splices from hitting null, same as the LRU sketch later in this chapter. This was Prince Medium Round 2 in a loop that also had Locker in Round 1; it is a real IE and it is not UTA-default and not Job 10454435.

Example: Songs A–B–C in a DLL, map "B" to that node. Delete B: relink A.next to C and C.prev to A, then map.remove("B"). Search for B after that is a map miss. Insert D after A is a map put plus splicing D between A and C, still O(1) because we already hold A.

If they probe: index insert is O(n) in an array — ask if position matters. Same unlink as LRU. No eviction unless they add a cap. Not UTA default. Not 10454435.

At Ylogx we cut bot database latency 35 percent with caching in front of Postgres, with RLS and RBAC across three organizational tiers, and the BI path is 40 percent faster reports, 99.9 percent uptime, and sub-210 ms. Inside one JVM, ConcurrentHashMap or a HashMap plus a lock is an exact cache with no TTL story and no sharing across ECS tasks. Across instances, with TTL and eviction, that cache is Redis, which is on the resume, and I will not claim I shipped Java LinkedHashMap access-order at Ylogx. Redis LRU is a maxmemory-policy on the server, which is not the Bhavya pointer problem. If they ask me to code O(1) LRU I write HashMap plus a doubly linked list and say production was Redis in front of Postgres. Row-level security stays in Postgres; the cache key must include tenant and role, or a user in one of the three tiers can read a cached row that belongs to another. A HashMap keyed only on the SQL text would leak across those tiers the moment two tenants run the same question. Rate limiter LLD is a different card: live-round count is one, not a UTA two-DSA, and I do not drag it into this cache answer.

Example: Two tenants, Acme and Globex, both ask “open invoices.” If the Redis key is only the query hash, Globex can get Acme’s rows from cache. The key must be tenantId + role + queryHash, and the Postgres query still enforces the three-tier RLS. An in-process HashMap has the same bug if it is a static map shared by every request thread without the tenant in the key.

If they probe: ConcurrentHashMap is not a distributed cache. Do not cache RLS-stripped rows under a global key. Redis eviction is not the Live Code LRU. Do not claim LinkedHashMap in production at Ylogx. Rate limiter count=1, not UTA.

Ranking sources from 200-plus websites is a HashMap of scores plus either a full sort in O(n log n) or a size-k min-heap if I only need the top k. That is the same Top-K skeleton as the AUTA heap question; I say that as computer science, not that IQVIA asked Amazon’s question. When k is much smaller than n the heap wins; when n is already 200 and k is near 200, sort is honest and simpler. Hybrid RAG on 200-plus page BRDs is retrieval, not a heap, unless they ask how I rank chunks. Implementation language on the resume is Python and FastAPI; Live Code is still a Java PriorityQueue. I do not invent a Job 10454435 coding question out of this metric.

Example: Two hundred site scores, k=10. I offer each (score, url) into a size-10 min-heap on score and poll when the heap grows past 10, same as Top K frequent but the payload is a URL. A full Arrays.sort of 200 pairs is also fine if they want the complete ranking for the research report.

If they probe: heap versus sort when n is 200 is almost a wash; say heap when k is much smaller than n. Live Code remains Java PQ even though the project is Python. Do not claim IQVIA asked Amazon’s Top-K question.

Each camera is a FIFO of frames, so the Java structure is ArrayDeque or a bounded blocking queue, one queue per feed. LinkedList as a random-access List is the wrong default because get-by-index walks; Stack is legacy and synchronized. If the consumer lags at 24 FPS across 20-plus cameras I drop the oldest frame, which is a ring buffer, LRU-adjacent in spirit but not Bhavya’s cache. The resume fact if they ask why queues mattered is YOLOv9 from 73 to 89 mAP on 15,000-plus images at 24 FPS. I do not volunteer InstaRecon. If they ask about that work I give a public-data ethics one-liner and redirect to Argus or Ylogx.

Example: Bounded deque of capacity 8 frames per camera. Offer last; if size exceeds 8, poll first. Camera 3 does not share camera 7’s queue, because a stall on one feed must not drop the other. A PriorityQueue would reorder by some score and break FIFO, which is wrong unless they asked for a priority stream.

If they probe: ArrayDeque has no nulls and no get(i). Backpressure versus drop-oldest: I ask which they want. Not LinkedList-as-List. Not Bhavya LRU. InstaRecon: ethics one-liner, then Argus or Ylogx.

Exact id to record is a HashMap in process or a Redis hash across processes, because I have a key and I want the value. Approximate nearest neighbor is FAISS, not a TreeMap, because TreeMap orders keys, not embedding distance. Graph hops and relationships are Neo4j or an adjacency list, not a heap. I pick one sentence and stop; I do not dump the whole skills list. Postgres indexes are B-plus flavored; I only connect that to Ylogx if they go query planning or DNS, not as a resume brag on B-trees. Linear scan of all vectors in a HashMap is only honest when n is tiny.

Example: userId to session is Redis or HashMap. “Find similar BRD chunks” is FAISS on embeddings. “Who reports to whom in the org” is Neo4j or an adjacency list. Putting those three problems on one TreeMap would be the wrong tool for two of them.

If they probe: exact versus ANN versus graph versus B-plus — pick one sentence. Do not claim TreeMap does cosine similarity. Redis versus HashMap is process boundary, same as the Ylogx cache talk.

Hot catalog and session need a HashMap or Redis to stay under sub-300 ms with 99.5 percent uptime. Prefix search over topics would be a Trie in standard CS, or a database LIKE or tsvector in production. I did not ship a Java Trie on GiftedBooks and I will not invent one. Doubt resolution from hours down to 3–10 minutes is a product metric, not a data-structure claim. If they connect RAG Q-and-A to retrieval I talk about the hot cache in front of the store, not a Live Code LRU unless they ask to code one. I keep the talk to maps and caches unless they explicitly ask for a prefix tree, because claiming a Trie I did not ship is worse than saying the database handled search.

Example: courseId to Course in a map for the hot path. Autocomplete for the prefix “alg” would be a Trie or Postgres; I say I used the database, not that I wrote a 26-way Trie in that service.

If they probe: do not invent a Trie on this project. In-memory map versus Redis is the same one-JVM versus shared-cache split as Ylogx. sub-300 ms is the latency number if they ask for a metric.

A binary heap is a complete tree packed in an Object array so parent i has children 2i+1 and 2i+2 in zero-based indexing. Sift-up and sift-down are O(log n); Floyd’s build-heap is O(n), which is why constructing a PriorityQueue from a collection is linear. Min-heap means parent is less than or equal to children so peek is the minimum; max-heap flips the compare so peek is the maximum; it is the same code. Java PriorityQueue is a min-heap by default using Comparable or a comparator; max is Comparator.reverseOrder(). It is not synchronized. The iterator is heap order, not sorted, which is the trap if they print the queue and expect ascending values. Peek is O(1), offer and poll are O(log n), contains and remove of an arbitrary object are O(n), and there is no decrease-key, so Dijkstra offers a new pair and skips stale pops. Nulls are forbidden, and the comparator must be Integer.compare, not a minus b, because subtraction overflows.

Example: Offer 3, then 1, then 2 into a default PriorityQueue. Peek is 1. Iterating the queue might print 1, 3, 2, which is heap order, not a sorted list. Reverse-order peek is 3. A TreeMap of the same three keys would iterate 1, 2, 3 and could delete 2 in O(log n); the heap cannot.

If they probe: remove(Object) O(n). Iterator not sorted. Lazy Dijkstra. Overflow in a-b. Null forbidden. Build-heap O(n) from a collection.

Live Code list is ArrayList because get by index is O(1) and add at the end is amortized O(1). Stack, queue, deque, BFS, and monotonic stacks are ArrayDeque because both ends are O(1) and it is a circular buffer. I never use java.util.Stack or Vector; they are legacy and synchronized. ArrayDeque has no get(i) and does not allow nulls, which is why it is the wrong structure for GetRandom. LinkedList as a List is a trap because get(i) walks O(n); as a Deque it is correct but heavier than ArrayDeque because every node has two pointers. ArrayList grows by old plus old shifted right by one, about 1.5 times. GetRandom and swap-delete need ArrayList, not a deque, because I need index i. A raw array is tightest memory but does not grow; I use it when the length is known.

Example: BFS: Queue<int[]> q = new ArrayDeque<>(), never a LinkedList unless they force List. Swap-delete for GetRandom cannot be a deque because I need a.get(i) and a.set(i, last). Adding at index 0 on an ArrayList shifts everyone and is O(n); ArrayDeque offerFirst is O(1).

If they probe: add(0) on ArrayList is O(n). ArrayDeque grow is 2× circular. LinkedList get(i) is O(n). No nulls in ArrayDeque. Stack/Vector are wrong defaults.

HashMap and HashSet are unordered average O(1); worst case is O(n) until a bin treeifies, then O(log n). LinkedHashMap keeps insertion order, or access order if you pass true as the third constructor argument, and that plus removeEldestEntry is LRU in one class; I still write HashMap plus a doubly linked list in Live Code because they want the pointers. TreeMap and TreeSet are red-black trees, O(log n) for get, put, and remove, with sorted keys and ceiling, floor, and subMap. TreeMap needs a Comparable or a Comparator and does not allow a null key; HashMap allows one null key. I use TreeMap when I need ordered keys or delete-arbitrary in O(log n), for example a sorted multiset of counts. IdentityHashMap and WeakHashMap I skip unless they name them.

Example: LinkedHashMap access-order: put alice, put bob, get alice, and alice moves to the most-recent end, which is the LRU sentence. TreeMap of timestamps answers “next event after t” with ceilingKey; a HashMap cannot ceiling. HashSet of names is HashMap to PRESENT, so “alice” and “Alice” are two elements unless I normalize case.

If they probe: TreeMap null key NPE. LinkedHashMap still average O(1) but extra pointers. Access-order true is LRU, then still write the DLL. Delete-arbitrary is TreeMap, not PriorityQueue.

I keep a parent array and a rank or size array. Find with path compression flattens the tree so the next find is almost a single hop; union by rank keeps the trees shallow. Amortized cost is almost O(α(n)) per operation, inverse Ackermann, which is a constant for interview sizes, so n unions are about O(n). I use it for components, undirected cycle detection when union returns false, and Kruskal. FTE UTA Rank A generally did not name DSU; an intern IE used union-find for grouping strings one swap apart, unnamed, in the family of LC 839, and I do not say they asked 839. The 8362604 students-and-enemies graph wanted BFS or DFS in O(V+E), not a union-find gadget unless I already know the bipartite trick. Without path compression a degenerate chain is O(n) per find, which is why I mention compression out loud.

Example: Unions 0-1, 1-2, 3-4. find(0) equals find(2), find(0) does not equal find(3). union(2,3) links the two components; a later union(0,4) returns false because they are already connected, which is the undirected-cycle test.

If they probe: almost O(α(n)). Path compression plus union by rank together. Not a drop-in for directed graphs. Not the default for 8362604 bipartite. Intern grouping was unnamed, not LC 839.

Insert or search of a word of length L is O(L) in both a Trie and a HashMap, because the map still hashes and equals the whole string. The Trie wins on shared prefixes, autocomplete, and startsWith, because a HashMap would iterate every key. Children are TrieNode[26] when the alphabet is lowercase English, or a HashMap of character to node otherwise, and the end marker or a count lives on the node. Delete is O(L) if I walk back and prune empty nodes; I often skip delete in Live Code. Space is proportional to total characters times alphabet for the array children, or to actual branches for HashMap children. Exact dictionary membership with no prefix is HashMap or HashSet, which is why Word Ladder starts as a set plus BFS.

Example: Keys “app”, “apple”, “apply”. The HashMap stores three full strings. The Trie shares a-p-p, then branches l-e versus l-y. startsWith(“appl”) is a walk of four nodes, not a scan of the map. search(“app”) depends on isWord on that shared node.

If they probe: both O(L) for exact search; Trie wins on prefix. HashMap prefix requires iterating all keys. Array[26] versus HashMap children. Delete often skipped in Live Code.

If I already hold the node, insert or delete is O(1) because I relink four pointers, independent of list length. Finding by key without a map is O(n) on the list, which is why LRU and playlist both add a HashMap from key to node. With the map, find is average O(1) and then splice is O(1), so get and put of a cache become average O(1). A singly linked list delete needs the previous node, so it is O(n) unless I already hold prev; that is why the cache is doubly linked. Merge k, reverse, and cycle problems stay on a singly list because those algorithms never need to splice out of the middle by key. Dummy head and tail mean unlink never sees null.

Example: LRU unlink is n.prev.next = n.next and n.next.prev = n.prev. Insert after head is four assignments: n.next = head.next, n.prev = head, head.next.prev = n, head.next = n. Without dummy nodes, deleting the real head is a special case I would rather not debug live.

If they probe: known node O(1); find without map O(n); with map O(1) average. Singly list delete needs prev. Forgetting map.remove when you unlink leaks the key. Dummy head and tail avoid null.

The one-sentence pick is: repeated minimum with no arbitrary delete is a PriorityQueue; need delete-arbitrary or ceiling is TreeMap; full order once is Arrays.sort in O(n log n); window maximum is a monotonic ArrayDeque in O(n). I say it that way because the four tools solve four different operator sets, and mixing them is how people write O(n log n) when O(n) was enough. A heap of the sliding window still needs delete or lazy invalidation, so it is O(n log k) and I only use it if n is small or they already have a heap. TreeMap as a sorted multiset of counts is how I delete a value from a “heap-like” structure in O(log n). Sort is not incremental: if the set keeps changing I do not re-sort from scratch. The Java PriorityQueue iterator will not give me the sorted order I would get from TreeMap, so I do not print a heap and call it sorted.

Example: Sliding window maximum of [1, 3, -1, -3, 5] with k=3: a decreasing ArrayDeque of indices yields 3, 3, 5 in linear time. A heap of each window would work but pays log k per index and needs to drop the element that left the window. Connect Ropes stays a heap; “next timestamp ≥ t” stays TreeMap.ceilingKey.

If they probe: PQ remove is O(n). Sort is not incremental. Monotonic deque is O(n) for window max. TreeMap for delete-arbitrary. Iterator of PQ is not sorted.

HashMap/HashSet get/put/remove     avg O(1)   worst O(n) [tree bin O(log n)]
TreeMap/TreeSet all                O(log n)
PriorityQueue peek                 O(1)
PriorityQueue offer/poll           O(log n)
PriorityQueue remove(Object)       O(n)
ArrayList get / add-end            O(1) / amort. O(1)
ArrayList add/remove at i          O(n)
ArrayDeque offer/poll both ends    O(1)
LinkedList get(i)                  O(n)     — do not
DSU find/union                     O(α(n))
Trie insert/search                 O(L)
DLL+map get/put (LRU)              O(1) avg
String + in a loop                 O(n²)    — StringBuilder

PriorityQueue<Integer> minH = new PriorityQueue<>();
PriorityQueue<Integer> maxH = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<int[]> byFirst =
        new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
minH.offer(x);           // O(log n)
int lo = minH.peek();    // O(1)
int x = minH.poll();     // O(log n)

1. table[ (h ^ (h >>> 16)) & (n-1) ]
2. walk list / tree; equals after hash
3. bin length ≥ 8 and n ≥ 64 → red-black; else resize
4. size > 0.75n → new table 2n, transfer
HashSet = HashMap(key → PRESENT)

Deque<Integer> st = new ArrayDeque<>(); // stack: push/pop/peek
Queue<int[]> q = new ArrayDeque<>();    // BFS: offer/poll/peek
List<Integer> a = new ArrayList<>();    // random access + swap-delete

TreeMap<Integer, Integer> freq = new TreeMap<>(); // val → count
freq.merge(x, 1, Integer::sum);
if (freq.get(x) == 0) freq.remove(x);
int min = freq.firstKey();           // O(log n)
int ceil = freq.ceilingKey(t);       // O(log n) or NPE if none — null-check

class DSU {
    int[] p, r;
    DSU(int n) {
        p = new int[n]; r = new int[n];
        for (int i = 0; i < n; i++) p[i] = i;
    }
    int find(int x) { return p[x] == x ? x : (p[x] = find(p[x])); }
    boolean union(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (r[a] < r[b]) { int t = a; a = b; b = t; }
        p[b] = a;
        if (r[a] == r[b]) r[a]++;
        return true;
    }
}

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    boolean end;
}
void insert(TrieNode root, String w) {
    TrieNode cur = root;
    for (int i = 0; i < w.length(); i++) {
        int c = w.charAt(i) - 'a';
        if (cur.next[c] == null) cur.next[c] = new TrieNode();
        cur = cur.next[c];
    }
    cur.end = true;
}
boolean startsWith(TrieNode root, String p) {
    TrieNode cur = root;
    for (int i = 0; i < p.length(); i++) {
        int c = p.charAt(i) - 'a';
        if (cur.next[c] == null) return false;
        cur = cur.next[c];
    }
    return true;
}

class LRUCache {
    static class N { int k, v; N prev, next; N(int k, int v) { this.k = k; this.v = v; } }
    int cap;
    Map<Integer, N> map = new HashMap<>();
    N head = new N(0, 0), tail = new N(0, 0);
    LRUCache(int cap) { this.cap = cap; head.next = tail; tail.prev = head; }
    void unlink(N n) { n.prev.next = n.next; n.next.prev = n.prev; }
    void afterHead(N n) {
        n.next = head.next; n.prev = head;
        head.next.prev = n; head.next = n;
    }
    int get(int k) {
        N n = map.get(k);
        if (n == null) return -1;
        unlink(n); afterHead(n);
        return n.v;
    }
    void put(int k, int v) {
        if (map.containsKey(k)) { unlink(map.get(k)); }
        N n = new N(k, v);
        map.put(k, n); afterHead(n);
        if (map.size() > cap) {
            N lru = tail.prev;
            unlink(lru); map.remove(lru.k);
        }
    }
}

PriorityQueue<ListNode> pq =
        new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
for (ListNode h : lists) if (h != null) pq.offer(h);