Why Data Structures and Algorithms Matter
Data structures and algorithms form the foundation of computer science and are the primary focus of technical interviews at top tech companies. Understanding them isn't just about passing interviews—it's about writing efficient, scalable code that can handle real-world problems.
Time and Space Complexity
Before diving into specific data structures, you must understand Big O notation. It describes the upper bound of an algorithm's growth rate.
Common Time Complexities (best to worst):
O(1) - Constant: Array access, hash table lookup
O(log n) - Logarithmic: Binary search
O(n) - Linear: Simple search, single loop
O(n log n) - Linearithmic: Efficient sorting (merge, quick)
O(n²) - Quadratic: Nested loops, bubble sort
O(2ⁿ) - Exponential: Recursive Fibonacci
O(n!) - Factorial: Generating permutations
// O(1) - Constant time
function getFirst(arr) {
return arr[0];
}
// O(n) - Linear time
function findMax(arr) {
let max = arr[0];
for (let num of arr) {
if (num > max) max = num;
}
return max;
}
// O(n²) - Quadratic time
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length-i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
// O(log n) - Logarithmic time
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
Arrays and Strings
Arrays are the most fundamental data structure. Many interview problems involve array manipulation.
Common Array Patterns
Two Pointers: Use two indices to traverse the array, often from opposite ends.
// Two Sum with sorted array-O(n)
function twoSumSorted(nums, target) {
let left = 0, right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) return [left, right];
if (sum < target) left++;
else right--;
}
return [-1, -1];
}
// Remove duplicates in-place-O(n)
function removeDuplicates(nums) {
if (nums.length === 0) return 0;
let writeIndex = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i]!== nums[i - 1]) {
nums[writeIndex] = nums[i];
writeIndex++;
}
}
return writeIndex;
}
Sliding Window: Maintain a window of elements as you traverse.
// Maximum sum subarray of size k-O(n)
function maxSumSubarray(arr, k) {
let windowSum = 0;
let maxSum = 0;
// Calculate sum of first window
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
// Slide the window
for (let i = k; i < arr.length; i++) {
windowSum = windowSum-arr[i-k] + arr[i];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// Longest substring without repeating characters-O(n)
function lengthOfLongestSubstring(s) {
const seen = new Map();
let maxLength = 0;
let start = 0;
for (let end = 0; end < s.length; end++) {
if (seen.has(s[end])) {
start = Math.max(start, seen.get(s[end]) + 1);
}
seen.set(s[end], end);
maxLength = Math.max(maxLength, end-start + 1);
}
return maxLength;
}
Prefix Sum: Precompute cumulative sums for range queries.
// Range sum query-O(1) after O(n) preprocessing
class RangeSumQuery {
constructor(nums) {
this.prefix = [0];
for (let num of nums) {
this.prefix.push(this.prefix[this.prefix.length - 1] + num);
}
}
sumRange(left, right) {
return this.prefix[right + 1] - this.prefix[left];
}
}
Hash Tables
Hash tables provide O(1) average-case lookup, insertion, and deletion. They're invaluable for solving many interview problems.
// Two Sum (unsorted) - O(n)
function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target-nums[i];
if (seen.has(complement)) {
return [seen.get(complement), i];
}
seen.set(nums[i], i);
}
return [];
}
// Group Anagrams-O(n * k log k) where k is max string length
function groupAnagrams(strs) {
const groups = new Map();
for (let str of strs) {
const sorted = str.split('').sort().join('');
if (!groups.has(sorted)) {
groups.set(sorted, []);
}
groups.get(sorted).push(str);
}
return Array.from(groups.values());
}
// First non-repeating character-O(n)
function firstUniqChar(s) {
const count = new Map();
for (let char of s) {
count.set(char, (count.get(char) || 0) + 1);
}
for (let i = 0; i < s.length; i++) {
if (count.get(s[i]) === 1) return i;
}
return -1;
}
Linked Lists
Linked lists are fundamental for understanding pointers and memory management.
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
// Reverse a linked list-O(n)
function reverseList(head) {
let prev = null;
let current = head;
while (current) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
// Detect cycle-O(n) time, O(1) space
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
// Merge two sorted lists-O(n + m)
function mergeTwoLists(l1, l2) {
const dummy = new ListNode();
let current = dummy;
while (l1 && l2) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 || l2;
return dummy.next;
}
// Find middle node-O(n)
function middleNode(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
Trees and Graphs
Trees and graphs are essential for modeling hierarchical and networked data.
Binary Trees
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
// Tree traversals
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;
}
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;
}
// Maximum depth-O(n)
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
// Level order traversal (BFS) - O(n)
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length) {
const level = [];
const levelSize = queue.length;
for (let i = 0; i < levelSize; 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;
}
// Validate BST-O(n)
function isValidBST(root) {
function validate(node, min, max) {
if (!node) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}
return validate(root, -Infinity, Infinity);
}
Graphs
// Graph representation-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);
}
}
// BFS-O(V + E)
function bfs(graph, start) {
const visited = new Set();
const queue = [start];
const result = [];
visited.add(start);
while (queue.length) {
const vertex = queue.shift();
result.push(vertex);
for (let neighbor of graph.adjacencyList.get(vertex)) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return result;
}
// DFS-O(V + E)
function dfs(graph, start) {
const visited = new Set();
const result = [];
function traverse(vertex) {
visited.add(vertex);
result.push(vertex);
for (let neighbor of graph.adjacencyList.get(vertex)) {
if (!visited.has(neighbor)) {
traverse(neighbor);
}
}
}
traverse(start);
return result;
}
// Number of islands-O(m * n)
function numIslands(grid) {
if (!grid.length) 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;
}
Dynamic Programming
Dynamic programming solves complex problems by breaking them into overlapping subproblems.
// Fibonacci-O(n) with memoization
function fibonacci(n, memo = {}) {
if (n in memo) return memo[n];
if (n <= 1) return n;
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
// Climbing stairs-O(n)
function climbStairs(n) {
if (n <= 2) return n;
let prev1 = 1, prev2 = 2;
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2;
prev1 = prev2;
prev2 = current;
}
return prev2;
}
// Longest increasing subsequence-O(n²)
function lengthOfLIS(nums) {
const dp = new Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}
// Coin change-O(amount * coins.length)
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (let coin of coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i-coin] + 1);
}
}
}
return dp[amount] === Infinity? -1: dp[amount];
}
Interview Problem-Solving Framework
When approaching any DSA problem in an interview, follow this framework:
Understand the problem: Ask clarifying questions about input constraints, edge cases, and expected output format.
Work through examples: Trace through the problem with simple examples before coding.
Identify the pattern: Is it a two-pointer problem? Dynamic programming? Graph traversal?
Plan your approach: Explain your algorithm before writing code.
Implement the solution: Write clean, readable code with meaningful variable names.
Test and optimize: Walk through your solution with test cases and discuss potential optimizations.
Consistent practice with these patterns will prepare you for success in any coding interview.