Comprehensive coverage of fundamental data structures, their operations, implementation trade offs, and algorithmic uses. Candidates should know arrays and strings including dynamic array amortized behavior and memory layout differences, linked lists, stacks, queues, hash tables and collision handling, sets, trees including binary search trees and balanced trees, tries, heaps as priority queues, and graph representations such as adjacency lists and adjacency matrices. Understand typical operations and costs for access, insertion, deletion, lookup, and traversal and be able to analyze asymptotic time and auxiliary space complexity using Big O notation including constant, logarithmic, linear, linearithmic, quadratic, and exponential classes as well as average case, worst case, and amortized behaviors. Be able to read code or pseudocode and derive time and space complexity, identify performance bottlenecks, and propose alternative data structures or algorithmic approaches to improve performance. Know common algorithmic patterns that interact with these structures such as traversal strategies, searching and sorting, two pointer and sliding window techniques, divide and conquer, recursion, dynamic programming, greedy methods, and priority processing, and when to combine structures for efficiency for example using a heap with a hash map for index tracking. Implementation focused skills include writing or partially implementing core operations, discussing language specific considerations such as contiguous versus non contiguous memory and pointer or manual memory management when applicable, and explaining space time trade offs and cache or memory behavior. Interview expectations vary by level from selecting and implementing appropriate structures for routine problems at junior levels to optimizing naive solutions, designing custom structures for constraints, and reasoning about amortized, average case, and concurrency implications at senior levels.
EasyTechnical
77 practiced
Describe the typical time complexity of lookup, insertion, and deletion for JavaScript Map, Object (property access), and Set. Include average and worst-case behavior in your answer, mention how hash collisions or prototype chain lookups can affect Object, and explain any engine guarantees (like insertion-order preservation) that matter for frontend code.
Sample Answer
**Answer (frontend developer perspective)****Summary of typical complexity**- JavaScript Map - Average: lookup/insert/delete = O(1) - Worst-case: O(n) if many hash collisions or a pathological engine implementation - Engine note: preserves insertion order (important for predictable iteration, e.g., rendering lists)- JavaScript Set - Average: has/add/delete = O(1) - Worst-case: O(n) for collision/pathological cases - Engine note: preserves insertion order for iteration- Plain Object (property access) - Average: property read/write/delete = O(1) in modern engines (they use hash tables / hidden classes) - Worst-case: - O(n) if a hash collision or if the engine degrades representation - Property lookup can be O(k) where k is prototype chain depth (if property is inherited and not found on the object) - Caveat: enumeration order for Object keys follows the ES spec (integer indices in ascending order, then insertion order for string keys, then symbols) — generally stable in modern browsers but Maps give clearer insertion-order semantics.**Practical guidance for frontend**- Use Map when keys are non-strings (objects) or you need guaranteed insertion-order iteration.- Use Object for simple keyed data and JSON-like shapes; be mindful of prototype lookups (use Object.create(null) for a pure map) and integer-key ordering quirks.- Use Set for unique collections with fast membership checks.These complexities reflect typical engine implementations (V8/SpiderMonkey/JavaScriptCore); average O(1) is what you should expect for UI code performance, but choose data structures to avoid prototype pitfalls and to rely on insertion-order behavior when iteration order matters.
EasyTechnical
132 practiced
Describe binary search and its time complexity. Include practical front-end scenarios where binary search is applicable (for example, searching sorted data, finding an insertion point for virtualized lists, or mapping pixel offset to item index). Also discuss typical pitfalls and preconditions required for correctness.
Sample Answer
**Definition & approach** Binary search repeatedly halves a sorted range to find a target: compare target to middle element, then search left or right half until found or range is empty. I typically implement it iteratively in JS to avoid recursion overhead.**Time & space complexity** - Time: O(log n) comparisons. - Space: O(1) iterative, O(log n) recursive call stack.**Frontend practical scenarios** - Searching sorted arrays (e.g., sorted list of timestamps). - Finding insertion point for virtualized lists: binary search on cumulative heights to locate first item whose prefix sum ≥ scroll offset. - Mapping pixel offset to item index: maintain array of item heights (or prefix sums) and binary-search offset → index for fast scroll-to-item. - Debounced lookup in autocomplete when data is pre-sorted.**Preconditions & pitfalls** - Array must be sorted by the same comparator used in comparisons. Unsorted input breaks correctness. - Watch integer mid computation to avoid overflow in some languages (use left + ((right - left) >> 1)); JS safe but follow pattern. - Off-by-one errors: choose inclusive/exclusive boundaries consistently. - Stable behavior when duplicates: decide whether you need first/last occurrence and adapt comparisons. - For variable-height virtualization, keep prefix-sum updates efficient; stale sums cause wrong mapping.**Quick tip** Write tests for edge cases: empty array, single element, all-equal elements, target smaller/larger than all items, and duplicate targets.
EasyTechnical
81 practiced
Compare quicksort, mergesort, and TimSort with respect to time and space complexity and stability. Explain why modern JS engines often employ TimSort for sorting arrays of objects and what implications this has for frontend developers when sorting large datasets.
Sample Answer
**Time / Space / Stability (brief comparison)**- Quicksort - Time: average O(n log n), worst-case O(n^2) - Space: O(log n) extra (stack), in-place - Stability: unstable (unless specially implemented)- Mergesort - Time: O(n log n) worst/average - Space: O(n) extra (needs temporary arrays) - Stability: stable- TimSort (hybrid used in many modern runtimes) - Time: O(n log n) worst, O(n) best for nearly-sorted data - Space: O(n) worst-case but often less (uses runs + small temp buffers) - Stability: stable**Why JS engines often use TimSort**- Adaptive: detects and exploits existing ordered runs in real-world data (e.g., nearly-sorted arrays from UI changes), giving near-linear performance.- Stable: preserves relative order of equal elements — important when sorting arrays of objects by one key while relying on prior ordering by another key.- Robust: avoids quicksort’s pathological worst-case while being practical and fast across varied input.**Implications for frontend developers**- Stability matters: you can do multi-key sorts safely (sort by secondary key first, then primary) without losing previous order.- Performance: TimSort is excellent for mostly-sorted UI datasets (e.g., incremental updates), but sorting very large arrays on the main thread can still block UI—use pagination, virtual lists, Web Workers, or incremental sorting.- Memory/GC: sorts that allocate many temporaries can increase GC pressure—avoid unnecessary object churn in comparator functions.- Practical tips: keep comparator fast and pure, pre-map objects to sortable keys when possible, and prefer stable sorts for predictable UI behavior.
EasyTechnical
129 practiced
Compare JavaScript arrays and linked lists for common frontend use cases. For both structures discuss access, insertion (beginning/middle/end), deletion, memory layout (contiguous vs non-contiguous), and typical engine behavior. Describe scenarios on the client where a linked list would be preferable to a JS Array and when it would not be worth the added complexity.
Sample Answer
**Direct answer — high level**JavaScript Arrays are the go-to collection for frontend work; linked lists are rarely needed but can fit niche cases.**Access**- Array: O(1) random access (integer index). JS engines optimize dense arrays to contiguous memory or fast elements hidden classes.- Linked list: O(n) random access — must traverse nodes.**Insertion**- Beginning: - Array: unshift is O(n) (shifts elements). - Linked list: O(1) (if you have head pointer).- Middle: - Array: splice is O(n) (move tail). - Linked list: O(n) to find spot, O(1) to link.- End: - Array: push is amortized O(1) in optimized engines. - Linked list: O(1) if tail pointer present.**Deletion**- Array: pop O(1); shift/splice O(n) due to element moves; sparse arrays and deletions can deoptimize engine internal representations.- Linked list: O(1) to remove known node (with prev pointer for doubly linked), but O(n) to locate it.**Memory layout & engine behavior**- Array: logically contiguous, compact storage when dense — typed as "fast elements" in V8; better cache locality and fewer GC allocations.- Linked list: non-contiguous nodes, each node is an object -> more allocations, worse cache locality, more GC pressure.**When to prefer a linked list (frontend)**- You need many constant-time insertions/deletions at known node positions and can maintain node references (e.g., implementing an LRU cache, an undo/redo history with frequent middle removals, or a custom rope/text buffer where slicing/inserting is heavy).- When you want stable iterators (remove current node during iteration without index adjustments).**When it’s not worth it**- Typical UI lists: filtering, mapping, indexing, rendering — Arrays are simpler, faster, and integrate with frameworks (React diffing, .map). DOM operations are best batched (DocumentFragment) rather than using linked lists.- For occasional head removals or inserts, use array methods or deque-like libraries; complexity and GC cost of linked lists rarely pay off.Takeaway: use Arrays by default; consider a linked list only for real, measured hotspots where O(1) node ops outweigh allocation and traversal costs.
HardTechnical
72 practiced
Design and implement in JavaScript a data structure that supports insert(value), remove(value), and getRandom() returning a uniformly random element, all in average O(1) time. Explain how you handle duplicates, memory overhead, and how each operation achieves the required complexities. Provide code for core operations or pseudocode.
Sample Answer
**Approach (brief)** Use an array for O(1) random access and a Map from value -> Set of indices to handle duplicates. Insert appends to array and records index; remove swaps target with last element, updates indices in Map, then pops. getRandom picks a random index.**Code (JavaScript)**
javascript
class RandomizedCollection {
constructor() {
this.arr = []; // values
this.idxMap = new Map(); // value -> Set of indices in arr
}
insert(val) {
const i = this.arr.length;
this.arr.push(val);
if (!this.idxMap.has(val)) this.idxMap.set(val, new Set());
this.idxMap.get(val).add(i);
return true; // could return whether it was new
}
remove(val) {
if (!this.idxMap.has(val) || this.idxMap.get(val).size === 0) return false;
// get any index of val
const valIdx = this.idxMap.get(val).values().next().value;
const lastIdx = this.arr.length - 1;
const lastVal = this.arr[lastIdx];
// overwrite valIdx with lastVal
this.arr[valIdx] = lastVal;
// update sets
this.idxMap.get(val).delete(valIdx);
this.idxMap.get(lastVal).delete(lastIdx);
if (valIdx !== lastIdx) this.idxMap.get(lastVal).add(valIdx);
this.arr.pop();
if (this.idxMap.get(val).size === 0) this.idxMap.delete(val);
return true;
}
getRandom() {
if (this.arr.length === 0) return null;
const i = Math.floor(Math.random() * this.arr.length);
return this.arr[i];
}
}
**Complexity & reasoning** - insert: O(1) average — push and Set add. - remove: O(1) average — swap, Set deletions/adds, pop. Using Set permits O(1) removal of an index when you have the element. - getRandom: O(1) — index access.**Duplicates & memory overhead** - Duplicates supported by storing multiple indices in idxMap's Set for a value. - Memory: O(n) for array + O(n) integers in total across all Sets. Overhead reasonable for frontend usage; if memory constrained, consider weak index compression or limiting duplicates. This implementation is practical for frontend features requiring random sampling (e.g., randomized UI elements, A/B test buckets) while keeping operations fast.
Unlock Full Question Bank
Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.
