1.2 ★ core [I][J] 15 interview Q's

Linear structures — when to reach for each

Arrays, dynamic arrays, linked lists, stacks, queues, deques — know the access/insert/delete costs and the one-sentence “use it when” for each.

Linear structures store elements in a sequence; the differences between them are entirely about what’s cheap. Pick one by asking three questions — where do I add, where do I remove, and how do I look things up? — then let the Big-O fall out of the answer. Every structure below is a different bet on which of those operations you’ll do most.

Arrays vs linked lists — the core split

The fundamental divide is contiguous memory versus linked nodes. An array packs elements side by side, so indexing is pure arithmetic — base + i × size — which is O(1), and the CPU cache loves the locality. The cost is rigidity: inserting or deleting in the middle means shifting everything after it, O(n). A dynamic array (JS Array, ArrayList, vector) adds growable size on top, giving amortized O(1) append while keeping O(1) indexing; it’s the default “list” you should reach for unless something specific argues otherwise.

A linked list stores each element in its own node with a pointer to the next. That makes insert/delete at a known position O(1) — just relink pointers, no shifting — but there’s no index arithmetic, so finding anything is O(n), and the scattered nodes thrash the cache. Reach for it only when you constantly add or remove at the ends and rarely index; in practice that niche is narrow, and a dynamic array or deque usually wins.

FIG 1 · memory layout The array is one contiguous block (index = arithmetic); the list is scattered nodes joined by pointers (index = a walk).

Picking a structure

Structure	Reach for it when	Avoid when	Costs
Static array	size is fixed and known; you index heavily	the collection grows/shrinks	index `O(1)`, insert `O(n)`
Dynamic array	the default list; append + index a lot	you insert/delete in the middle constantly	append amortized `O(1)`, index `O(1)`, mid `O(n)`
Linked list	constant add/remove at the ends, rare indexing	you need random access or cache locality	ends `O(1)`, search/index `O(n)`
Stack (LIFO)	undo, DFS, call stack, expression parsing	you need first-in order	push/pop `O(1)`
Queue (FIFO)	task/work queues, BFS, fair ordering	you need last-in order	enqueue/dequeue `O(1)`
Deque	sliding windows; pushing/popping both ends	you only ever use one end (use stack/queue)	both ends `O(1)`

Match the structure to where you add, remove, and look up.

Stack, queue, deque — the one-sentence distinctions

These three are access disciplines layered on an array or linked list, not new storage. A stack is LIFO — last in, first out, like a stack of plates; it powers undo, DFS, and the call stack. A queue is FIFO — first in, first out, like a checkout line; it powers work queues and BFS. A deque is both: O(1) push and pop at either end, which is what makes it the right tool for sliding-window problems where you add on one side and evict on the other.

FIG 2 · LIFO vs FIFO A stack returns the most recent item; a queue returns the oldest. Same data, opposite discipline.

Why a deque beats array.unshift

A common trap is using the front of a dynamic array as a queue. array.shift() / array.unshift() remove or add at index 0 — which forces every other element to slide over, making each call O(n).

// O(n) per dequeue: every element shifts left
const q = [];
q.push(task);          // O(1) amortized
const next = q.shift(); // O(n) — re-indexes the whole array!

// A deque pops the front in O(1) by relinking, not shifting.
// (In JS, use a ring buffer / index pointer, or a library deque.)

For a real queue, use a structure with O(1) ends — a deque, a linked list, or a dynamic array with a moving head index. Repeatedly shift()-ing a large array turns an O(n) job into an O(n^2) one — the same accidentally-quadratic trap from Chapter 1.1, wearing a different hat.

Stack: balanced-brackets in one pass

The stack is the natural fit for any “match the most recent open thing” problem — bracket matching, undo history, the call stack itself. Push openers; on a closer, the top of the stack must be its partner.

function isBalanced(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);                 // remember the most recent opener — O(1)
    } else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;  // top must match — O(1)
    }
  }
  return stack.length === 0;          // O(n) total, O(n) space
}

LIFO is exactly right here: the bracket you must close next is always the one you opened most recently, which is what pop() returns.

The O(n²) hiding in array.shift() V8 / Node

The “use a dynamic array as a queue” trap is so common it has bitten the Node ecosystem repeatedly. A worker that does queue.push(job) to enqueue and queue.shift() to dequeue looks O(1) per operation — but shift() re-indexes the entire backing array, so draining a queue of n jobs is O(n²). On a 50-job test queue it’s invisible; under a production burst of tens of thousands of jobs, the event loop stalls for seconds and latency graphs spike, with profilers pointing at a single Array.prototype.shift.

The reported fixes are always the same shape: swap the array for a real queue with O(1) ends — a linked list, a ring buffer, or a dynamic array with a moving head index (libraries like denque exist precisely for this). It is the linear-structures version of the same accidentally-quadratic lesson from Chapter 1.1: an O(n) operation inside a loop is an O(n²) outage waiting for scale.

read the writeup ↗ github.com

01 Learning objectives

0 / 7 done

02 Curated reading

MDN — JavaScript Array
optional 15m — How the “default list” actually behaves.

03 Knowledge check

knowledge check3 questions · pass ≥ 70%

01easy
You repeatedly add and remove from the FRONT of a sequence. Best choice?
02easy
A stack is:
03medium
BFS over a graph naturally uses which structure to track the frontier?

04 Interview questions

browse all ↗

What gets asked on this topic — tap a card for how to approach it, the follow-ups, and the trap. Company tags are best-effort & sourced.

Commonly asked junior concept very common Array vs linked list: compare index access, insert/delete, and memory. When would you choose each?
Arrays are contiguous: O(1) random index access but O(n) to insert/delete in the middle (shifting). Linked lists give O(1) insert/delete at a known node or the ends, but O(n) to find or index because you must walk the pointers. Reach for an array when you index a lot and the size is roughly known; reach for a linked list when you constantly add/remove at the front (or splice known nodes) and rarely index.
Follow-ups they push on
- Why is array access cache-friendly but linked-list traversal often isn't?
- What does a dynamic array (ArrayList/vector) change about this comparison?
Red flag Saying linked lists are 'faster for inserts' without the 'at a known position' caveat — finding the position is still O(n).
source: Tech Interview Handbook — Linked List cheatsheet ↗
Commonly asked junior concept common Explain a stack vs a queue vs a deque in one sentence each, and give a real use for each.
A stack is LIFO — last in, first out — used for undo, call stacks, DFS, and expression parsing. A queue is FIFO — first in, first out — used for task/work queues and BFS. A deque is double-ended, O(1) push/pop at both ends, used when you need front-and-back access (and as a faster substitute for inserting at index 0 of an array).
Follow-ups they push on
- Which would you use for BFS, and why not the other?
Red flag Mixing up which end stays open, or claiming a stack is good for FIFO ordering.
source: Tech Interview Handbook — Stack cheatsheet ↗
AmazonMicrosoftAppleMeta junior coding very common Reverse a singly linked list.
Iterate with three pointers — prev, curr, next — and on each step reverse the link (curr.next = prev) then advance all three; return prev at the end. This is O(n) time, O(1) space. The recursive version is O(n) space due to the call stack, so mention the iterative one first.
Follow-ups they push on
- Now reverse only nodes between positions m and n.
- Reverse the list in groups of k.
Red flag Losing the rest of the list by overwriting `curr.next` before saving `next`.
source: LeetCode 206 — Reverse Linked List (company tags) ↗
AmazonMicrosoftBloomberg mid coding common Detect whether a singly linked list has a cycle, using O(1) extra space.
Use Floyd's tortoise-and-hare: a slow pointer moves one step and a fast pointer two steps; if they ever meet there's a cycle, and if fast reaches null there isn't. O(n) time, O(1) space. A hash set of visited nodes also works but costs O(n) space, so lead with Floyd's.
Follow-ups they push on
- Return the node where the cycle begins.
- How do you find the cycle's length?
Red flag Advancing the fast pointer without null-checking both `fast` and `fast.next`, causing a crash on even-length lists.
source: LeetCode 141 — Linked List Cycle (company tags) ↗
AmazonMetaGoogleMicrosoftBloomberg junior coding very common Determine if a string of brackets ()[]{} is validly matched.
Push each opening bracket onto a stack; on a closing bracket, pop and check it matches the expected opener, failing fast on mismatch or empty stack. At the end the string is valid only if the stack is empty. O(n) time, O(n) space — the classic motivating example for why stacks exist.
Follow-ups they push on
- Handle the longest valid-parentheses substring.
- What if other characters are interleaved with the brackets?
Red flag Forgetting to check the stack is empty at the end, so unmatched openers like `(((` are wrongly accepted.
source: LeetCode 20 — Valid Parentheses (company tags) ↗
AmazonBloombergGoogle mid coding common Design a stack that returns its minimum element in O(1) alongside push/pop/top.
Keep a second 'min stack' that records the running minimum in parallel with the main stack; on push you store min(value, currentMin), and on pop you pop both. Every operation stays O(1) time and the structure uses O(n) extra space. The key idea is that each level remembers the min as of when it was pushed, so popping restores the previous min for free.
Follow-ups they push on
- Reduce the extra space when many pushed values repeat.
Red flag Storing only a single min variable, which can't recover the previous minimum after the current min is popped.
source: LeetCode 155 — Min Stack (company tags) ↗
Commonly asked mid concept occasional Why is inserting at the front of a dynamic array O(n), and what should you use instead?
Inserting at index 0 forces every existing element to shift one slot right, which is O(n) per insert. If you frequently add/remove at the front, use a deque (or a linked list), which gives O(1) push/pop at both ends. This is a common hidden-quadratic bug: building a result by repeatedly inserting at the front of an array turns an O(n) loop into O(n^2).
Follow-ups they push on
- When is appending to the end of a dynamic array still cheap?
Red flag Reaching for `arr.unshift(...)`/insert-at-0 in a loop and not noticing it makes the whole loop quadratic.
source: MDN — JavaScript Array ↗
AmazonMicrosoftGoogle mid coding common Implement a FIFO queue using two LIFO stacks.
Keep an in stack for pushes and an out stack for pops; when out is empty, pour everything from in into out, which reverses the order and exposes the oldest element. Each element is moved at most once between stacks, so dequeue is amortized O(1) even though a single transfer is O(n). This is a clean test of whether a candidate understands LIFO-vs-FIFO and amortized cost.
Follow-ups they push on
- What's the worst-case (not amortized) cost of a single pop?
Red flag Transferring on every dequeue instead of only when `out` is empty, which makes it O(n) per op.
source: LeetCode 232 — Implement Queue using Stacks (company tags) ↗
AmazonMicrosoftGoogle junior coding common Find the middle node of a singly linked list in one pass.
Use the fast/slow pointer trick: advance slow by one and fast by two each step; when fast reaches the end, slow sits at the middle. It's O(n) time, O(1) space, and finishes in a single pass — no need to first count the length and then walk halfway. For an even-length list, decide up front whether you return the first or second middle (the fast/fast.next loop condition controls this).
What a strong answer covers
- Two pointers, speeds 1 and 2 ⇒ slow lands at the middle in one pass.
- O(n) time, O(1) space; no length precomputation.
- Even length: loop condition picks first vs second middle.
- Same tortoise/hare machinery as cycle detection.
Follow-ups they push on
- For even length, how do you choose between the two middles?
- How does this generalize to finding the node n/k of the way through?
Red flag Looping while `fast != null` instead of checking `fast && fast.next`, dereferencing null on even-length lists.
source: LeetCode 876 — Middle of the Linked List (company tags) ↗
AmazonMetaMicrosoftGoogle mid coding common Remove the nth node from the end of a singly linked list in one pass.
Advance a fast pointer n nodes ahead, then move fast and slow together until fast hits the end — now slow is just before the node to remove, so you splice it out. Use a dummy head in front of the real head so removing the first node needs no special case. One pass, O(n) time, O(1) space.
What a strong answer covers
- Gap of n between fast and slow locates the target in one pass.
- Dummy node before head removes the edge case of deleting the head.
- O(n) time, O(1) space.
- Stop fast at the last node so slow lands on the predecessor.
Follow-ups they push on
- Why does the dummy node matter when n equals the list length?
- How would you do it in two passes, and why prefer one?
Red flag Skipping the dummy node and crashing (or returning the wrong head) when the node to remove is the head itself.
source: LeetCode 19 — Remove Nth Node From End of List (company tags) ↗
AmazonMicrosoftAppleMeta junior coding very common Merge two sorted linked lists into one sorted list.
Walk both lists with a dummy head and a tail pointer: at each step append the smaller of the two current nodes and advance that list; when one list runs out, append the remainder of the other. O(n + m) time, O(1) extra space because you splice existing nodes rather than allocate new ones. The dummy node removes the special case for choosing the very first node.
What a strong answer covers
- Dummy head + tail pointer avoids first-node special-casing.
- Splice existing nodes ⇒ O(1) extra space.
- O(n + m) time, one comparison per node.
- Attach the leftover tail wholesale once one list empties.
Follow-ups they push on
- How does this become the merge step of merge sort on a list?
- Extend to merging k sorted lists efficiently.
Red flag Forgetting to attach the remaining nodes of the non-empty list after the loop ends.
source: LeetCode 21 — Merge Two Sorted Lists (company tags) ↗
★ must-know AmazonMicrosoftBloomberg mid concept common Why is a doubly linked list often paired with a hash map (e.g. in an LRU cache), and what does each part provide?
The hash map gives O(1) lookup from key to its node; the doubly linked list gives O(1) reordering — unlink a node from anywhere and move it to the front/back using its prev/next pointers. Neither alone suffices: a hash map has no order, and a list alone needs O(n) to find a node. Together they back an LRU cache where both get and put (including evicting the least-recently-used entry) are O(1). The doubly-linked part is essential because unlinking an interior node in O(1) requires knowing its predecessor, which only a backward pointer provides.
What a strong answer covers
- Hash map: O(1) find key → node. Doubly linked list: O(1) reorder/evict.
- Map stores pointers to list nodes, not values, so manipulation is direct.
- prev pointer is what makes interior unlink O(1) (a singly list can't).
- Move-to-front on access; evict from the tail (the LRU end).
Quick self-check
In an LRU cache, why a doubly linked list rather than a singly linked one?
Follow-ups they push on
- Why a doubly (not singly) linked list specifically?
- What stale-reference bug appears if you evict from the list but not the map?
Red flag Removing the evicted node from the list but leaving its key in the hash map, leaving a dangling stale reference.
source: LeetCode 146 — LRU Cache (company tags) ↗
Commonly asked mid concept occasional How does a circular buffer (ring buffer) work, and where is it the right choice?
A ring buffer is a fixed-size array with head and tail indices that wrap around using modulo; you enqueue at tail and dequeue at head, both O(1), reusing slots instead of shifting. It's ideal for bounded producer/consumer streams — audio/IO buffering, recent-event logs, fixed-window rate limiting — where memory must be capped and old data can be overwritten. The classic subtlety is distinguishing full from empty when head == tail (track a size/count or leave one slot unused).
What a strong answer covers
- Fixed array + wrapping head/tail via modulo ⇒ O(1) enqueue/dequeue.
- No element shifting and no dynamic allocation after setup.
- Best for bounded streaming buffers (audio, logs, IO).
- full-vs-empty ambiguity at head == tail needs a count or a sacrificed slot.
Follow-ups they push on
- How do you tell a full buffer from an empty one?
- What happens to the oldest data when the buffer is full and you write?
Red flag Failing to disambiguate full from empty (both have head == tail), corrupting reads/writes.
source: GeeksforGeeks — Circular Queue ↗
AmazonGoogleMeta mid coding common Given daily temperatures, for each day return how many days until a warmer one (a monotonic-stack problem).
Use a monotonic decreasing stack of indices: scan left to right, and while the current temperature exceeds the temperature at the stack's top index, pop it and record the gap (current index − popped index) as its answer. Push the current index. Each index is pushed and popped at most once, so it's O(n) time, O(n) space — far better than the O(n^2) double loop. The stack pattern answers 'next greater element' style questions generally.
What a strong answer covers
- Stack holds indices awaiting a warmer day, kept decreasing by temperature.
- Pop and resolve each index when a warmer day arrives.
- Each index pushed/popped once ⇒ O(n) time.
- Generalizes to 'next greater/smaller element' problems.
Follow-ups they push on
- How does this generalize to 'next greater element' on a circular array?
- Why is the amortized cost O(n) despite the inner while-loop?
Red flag Storing temperatures instead of indices on the stack, losing the distance needed for the answer.
source: LeetCode 739 — Daily Temperatures (company tags) ↗
Commonly asked junior concept occasional What's the difference between a singly and a doubly linked list, and what does the second pointer cost and buy you?
A singly linked list has only a next pointer per node (forward traversal only); a doubly linked list adds a prev pointer, enabling backward traversal and O(1) deletion of a node given only a reference to it. The cost is one extra pointer of memory per node plus more bookkeeping on every insert/delete (you must fix two links, not one). Choose doubly when you need to walk backward or splice out arbitrary nodes cheaply (LRU caches, browser history); choose singly to save memory when forward-only suffices.
What a strong answer covers
- Singly: next only, forward traversal; Doubly: prev + next.
- Doubly enables O(1) delete given just the node and backward walks.
- Cost: extra pointer per node + dual-link maintenance on every edit.
- Use doubly for LRU/history; singly when forward-only and memory-tight.
Quick self-check
What does the `prev` pointer in a doubly linked list primarily buy you?
Follow-ups they push on
- Can you delete a known node in O(1) in a singly linked list (with a trick)?
- Why do LRU caches specifically need the doubly-linked variant?
Red flag Updating only `next` (or only `prev`) on insert/delete and corrupting one direction of the list.
source: GeeksforGeeks — Doubly Linked List ↗