When preparing for technical interviews, understanding basic data structures like arrays and objects isn't enough. Modern JavaScript provides powerful built-in data structures, and implementing custom structures like trees and graphs is essential for solving complex problems efficiently.
Sets: Unique Collections Made Simple
A Set is a collection of values where each value must be unique. JavaScript's built-in Set object provides O(1) time complexity for add, delete, and has operations.
Basic Set Operations
javascript
// Creating and using Sets
const set = new Set();
set.add(1);
set.add(2);
set.add(3);
set.add(1); // Duplicate, will be ignored
console.log(set); // Set {1, 2, 3}
// Check if value exists
console.log(set.has(2)); // true
// Delete a value
set.delete(2);
console.log(set.has(2)); // false
// Get size
console.log(set.size); // 2
// Convert to array
const arr = [...set]; // [1, 3]Practical Interview Examples
1. Remove Duplicates from Array
javascript
function removeDuplicates(arr) {
return [...new Set(arr)];
}
// Usage
const nums = [1, 2, 2, 3, 4, 4, 5];
console.log(removeDuplicates(nums)); // [1, 2, 3, 4, 5]2. Find Intersection of Two Arrays
javascript
function intersection(nums1, nums2) {
const set1 = new Set(nums1);
const set2 = new Set(nums2);
const result = [];
for (const num of set1) {
if (set2.has(num)) {
result.push(num);
}
}
return result;
}
// Usage
console.log(intersection([1, 2, 2, 1], [2, 2])); // [2]
console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [9, 4]3. Check for Valid Sudoku
javascript
function isValidSudoku(board) {
const rows = new Set();
const cols = new Set();
const boxes = new Set();
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
const num = board[i][j];
if (num === '.') continue;
const rowKey = `row-${i}-${num}`;
const colKey = `col-${j}-${num}`;
const boxKey = `box-${Math.floor(i/3)}-${Math.floor(j/3)}-${num}`;
if (rows.has(rowKey) || cols.has(colKey) || boxes.has(boxKey)) {
return false;
}
rows.add(rowKey);
cols.add(colKey);
boxes.add(boxKey);
}
}
return true;
}Maps: Key-Value Powerhouse
Maps are collections of key-value pairs where keys can be any type (objects, functions, or primitives). They maintain insertion order and provide efficient lookups.
Basic Map Operations
javascript
// Creating and using Maps
const map = new Map();
// Setting values
map.set('name', 'John');
map.set(42, 'answer');
map.set(true, 'boolean key');
// Objects as keys
const objKey = { id: 1 };
map.set(objKey, 'object key');
// Getting values
console.log(map.get('name')); // 'John'
console.log(map.get(42)); // 'answer'
console.log(map.get(objKey)); // 'object key'
// Check if key exists
console.log(map.has('name')); // true
// Delete a key
map.delete('name');
// Get size
console.log(map.size); // 3
// Clear all entries
map.clear();Practical Interview Examples
1. Two Sum Problem (Optimized)
javascript
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
return [];
}
// Usage
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6)); // [1, 2]2. Group Anagrams
javascript
function groupAnagrams(strs) {
const map = new Map();
for (const str of strs) {
const sorted = str.split('').sort().join('');
if (!map.has(sorted)) {
map.set(sorted, []);
}
map.get(sorted).push(str);
}
return [...map.values()];
}
// Usage
console.log(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));
// [["eat","tea","ate"], ["tan","nat"], ["bat"]]3. Subarray Sum Equals K
javascript
function subarraySum(nums, k) {
const map = new Map();
map.set(0, 1); // Initialize with prefix sum 0
let count = 0;
let sum = 0;
for (const num of nums) {
sum += num;
const complement = sum - k;
if (map.has(complement)) {
count += map.get(complement);
}
map.set(sum, (map.get(sum) || 0) + 1);
}
return count;
}
// Usage
console.log(subarraySum([1, 1, 1], 2)); // 2
console.log(subarraySum([1, 2, 3], 3)); // 2Trees: Hierarchical Data Structures
Trees are hierarchical structures with a root node and child nodes. Binary trees are the most common type in interviews.
Binary Tree Implementation
javascript
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
// Create a binary tree
// 1
// / \
// 2 3
// / \
// 4 5
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);Tree Traversals
1. Inorder Traversal (Left, Root, Right)
javascript
function inorderTraversal(root) {
const result = [];
function traverse(node) {
if (!node) return;
traverse(node.left);
result.push(node.val);
traverse(node.right);
}
traverse(root);
return result;
}
// Iterative approach
function inorderTraversalIterative(root) {
const result = [];
const stack = [];
let current = root;
while (current || stack.length > 0) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.push(current.val);
current = current.right;
}
return result;
}2. Preorder Traversal (Root, Left, Right)
javascript
function preorderTraversal(root) {
const result = [];
function traverse(node) {
if (!node) return;
result.push(node.val);
traverse(node.left);
traverse(node.right);
}
traverse(root);
return result;
}3. Postorder Traversal (Left, Right, Root)
javascript
function postorderTraversal(root) {
const result = [];
function traverse(node) {
if (!node) return;
traverse(node.left);
traverse(node.right);
result.push(node.val);
}
traverse(root);
return result;
}4. Level Order Traversal (BFS)
javascript
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const level = [];
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}Common Tree Problems
1. Maximum Depth of Binary Tree
javascript
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
// Iterative approach using BFS
function maxDepthBFS(root) {
if (!root) return 0;
const queue = [root];
let depth = 0;
while (queue.length > 0) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
depth++;
}
return depth;
}2. Validate Binary Search Tree
javascript
function isValidBST(root, min = -Infinity, max = Infinity) {
if (!root) return true;
if (root.val <= min || root.val >= max) {
return false;
}
return (
isValidBST(root.left, min, root.val) &&
isValidBST(root.right, root.val, max)
);
}3. Lowest Common Ancestor
javascript
function lowestCommonAncestor(root, p, q) {
if (!root || root === p || root === q) {
return root;
}
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (left && right) return root;
return left || right;
}4. Serialize and Deserialize Binary Tree
javascript
function serialize(root) {
const result = [];
function preorder(node) {
if (!node) {
result.push('null');
return;
}
result.push(node.val.toString());
preorder(node.left);
preorder(node.right);
}
preorder(root);
return result.join(',');
}
function deserialize(data) {
const values = data.split(',');
let index = 0;
function build() {
if (values[index] === 'null') {
index++;
return null;
}
const node = new TreeNode(parseInt(values[index]));
index++;
node.left = build();
node.right = build();
return node;
}
return build();
}Graphs: Complex Relationships
Graphs represent relationships between entities. They consist of vertices (nodes) and edges (connections).
Graph Representations
Adjacency List
javascript
// Using Map for adjacency list
class Graph {
constructor() {
this.adjacencyList = new Map();
}
addVertex(vertex) {
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, []);
}
}
addEdge(v1, v2) {
this.adjacencyList.get(v1).push(v2);
this.adjacencyList.get(v2).push(v1); // For undirected graph
}
getNeighbors(vertex) {
return this.adjacencyList.get(vertex) || [];
}
}
// Usage
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');Graph Traversals
1. Breadth-First Search (BFS)
javascript
function bfs(graph, start) {
const visited = new Set();
const queue = [start];
const result = [];
visited.add(start);
while (queue.length > 0) {
const vertex = queue.shift();
result.push(vertex);
for (const neighbor of graph.getNeighbors(vertex)) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return result;
}2. Depth-First Search (DFS)
javascript
function dfs(graph, start, visited = new Set()) {
if (visited.has(start)) return [];
visited.add(start);
const result = [start];
for (const neighbor of graph.getNeighbors(start)) {
result.push(...dfs(graph, neighbor, visited));
}
return result;
}
// Iterative DFS
function dfsIterative(graph, start) {
const visited = new Set();
const stack = [start];
const result = [];
while (stack.length > 0) {
const vertex = stack.pop();
if (!visited.has(vertex)) {
visited.add(vertex);
result.push(vertex);
for (const neighbor of graph.getNeighbors(vertex)) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
}
return result;
}Common Graph Problems
1. Clone Graph
javascript
function cloneGraph(node, visited = new Map()) {
if (!node) return null;
if (visited.has(node)) {
return visited.get(node);
}
const newNode = { val: node.val, neighbors: [] };
visited.set(node, newNode);
for (const neighbor of node.neighbors) {
newNode.neighbors.push(cloneGraph(neighbor, visited));
}
return newNode;
}2. Course Schedule (Detect Cycle)
javascript
function canFinish(numCourses, prerequisites) {
const graph = new Map();
const visited = new Set();
// Build adjacency list
for (let i = 0; i < numCourses; i++) {
graph.set(i, []);
}
for (const [course, prereq] of prerequisites) {
graph.get(course).push(prereq);
}
function hasCycle(course, path = new Set()) {
if (path.has(course)) return true;
if (visited.has(course)) return false;
visited.add(course);
path.add(course);
for (const prereq of graph.get(course)) {
if (hasCycle(prereq, path)) {
return true;
}
}
path.delete(course);
return false;
}
for (let i = 0; i < numCourses; i++) {
if (hasCycle(i)) {
return false;
}
}
return true;
}
// Usage
console.log(canFinish(2, [[1, 0]])); // true
console.log(canFinish(2, [[1, 0], [0, 1]])); // false3. Number of Islands
javascript
function numIslands(grid) {
if (!grid || grid.length === 0) return 0;
let count = 0;
const rows = grid.length;
const cols = grid[0].length;
function dfs(r, c) {
if (
r < 0 || r >= rows ||
c < 0 || c >= cols ||
grid[r][c] === '0'
) {
return;
}
grid[r][c] = '0'; // Mark as visited
dfs(r + 1, c);
dfs(r - 1, c);
dfs(r, c + 1);
dfs(r, c - 1);
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') {
count++;
dfs(r, c);
}
}
}
return count;
}Time and Space Complexity Reference
| Data Structure | Access | Search | Insertion | Deletion | Space | |---------------|--------|--------|-----------|----------|-------| | Set | O(1) | O(1) | O(1) | O(1) | O(n) | | Map | O(1) | O(1) | O(1) | O(1) | O(n) | | Binary Tree | O(log n)* | O(log n)* | O(log n)* | O(log n)* | O(n) | | Graph (Adjacency List) | O(1) | O(V + E) | O(1) | O(E) | O(V + E) |
*Average case for balanced trees
Interview Tips
- 1Know when to use Sets: Duplicate removal, membership testing
- 2Master Map operations: Frequency counting, caching, relationship mapping
- 3Practice tree traversals: Memorize recursive and iterative approaches
- 4Graph fundamentals: BFS for shortest path, DFS for path finding
- 5Edge cases: Empty structures, single nodes, cycles in graphs
Practice Problems
Easy:
- Contains Duplicate
- Single Number
- Maximum Depth of Binary Tree
- Symmetric Tree
Medium:
- Group Anagrams
- Subarray Sum Equals K
- Validate Binary Search Tree
- Course Schedule
Hard:
- Binary Tree Maximum Path Sum
- Serialize and Deserialize Binary Tree
- Word Ladder
- Critical Connections in a Network
Remember: Understanding these data structures deeply will give you a significant advantage in technical interviews. Practice implementing them from scratch until they become second nature!