Sector file // dsa

DATA STRUCTURES & ALGORITHMSDECODED.

Q: How do you reverse a linked list?

Iterate with three pointers — `prev`, `curr`, `next` — and at each step point `curr.next` back to `prev`, then advance all three. Returns the new head in O(n) time, O(1) space. It can also be done recursively.

Q: How do you solve the climbing stairs problem?

Ways to reach step n = ways(n-1) + ways(n-2) (take 1 or 2 steps), which is **Fibonacci**. Compute iteratively with two variables in O(n) time, O(1) space.

Q: What is the difference between an array and a linked list?

An **array** stores elements contiguously: O(1) index access but O(n) insert/delete in the middle and fixed/expensive resizing. A **linked list** stores nodes with pointers: O(1) insert/delete given a node but O(n) access and extra memory for pointers. Choose based on access vs mutation patterns.

Q: What is the difference between a stack and a queue?

A **stack** is LIFO (last-in, first-out) — push/pop at one end; used for recursion, undo, and DFS. A **queue** is FIFO (first-in, first-out) — enqueue at the back, dequeue at the front; used for scheduling and BFS.

Q: Maximum subarray (Kadane) vs divide-and-conquer — proof of correctness?

**Core concept.** Maximum subarray (Kadane) vs divide-and-conquer is a classic interview signal. Input n steps <text class="d-text" x="410" y="55" text

Q: What is Big-O notation?

**Big-O** describes how an algorithm's running time or space grows relative to input size n in the worst case, ignoring constants — e.g. O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic. It lets you compare algorithms independent of hardware.

Q: How do you find the intersection node of two linked lists?

Advance two pointers, one per list; when a pointer hits the end, redirect it to the **other list's head**. After at most one switch each, they align and meet at the intersection (or both reach null). O(m+n) time, O(1) space.

Q: How do you find the missing number in 0..n?

Sum 0..n with `n(n+1)/2` and subtract the actual array sum — the difference is the missing number, O(n) time / O(1) space. **XOR** of indices and values also works and avoids overflow risk.

Q: How do you find the best time to buy and sell a stock?

Track the **minimum price** seen so far and, at each day, compute `price - minSoFar` to update the best profit. One pass updates both, giving O(n) time and O(1) space. The trick is realizing you only need the lowest price to the left of each selling day.

Q: How do you merge two sorted linked lists?

Use a **dummy head** and a tail pointer; repeatedly attach the smaller of the two list heads and advance it. When one list runs out, append the rest of the other. O(m+n) time, O(1) extra space. The dummy node avoids special-casing the head.

Algorithms & data structures

127 Questions78.5k Views5.3k Upvotes

27 easy71 med29 hard

Filter

Transmission log

// 127 visible

DATA STRUCTURES & ALGORITHMSDECODED.

Transmission log

How do you reverse a linked list?

How do you solve the climbing stairs problem?

What is the difference between an array and a linked list?

What is the difference between a stack and a queue?

Maximum subarray (Kadane) vs divide-and-conquer — proof of correctness?

What is Big-O notation?

How do you find the intersection node of two linked lists?

How do you find the missing number in 0..n?

How do you find the best time to buy and sell a stock?

How do you merge two sorted linked lists?

How do you add one to a number represented as a digit array?

What is the time complexity of common operations on arrays, hash maps, and balanced trees?

How do you move all zeroes to the end of an array in place?

How do you check for valid/balanced parentheses?

How do you compute the GCD of two numbers?

How do you check if a root-to-leaf path sums to a target?

What is a stable sorting algorithm?

Number of islands with DFS vs BFS vs Union-Find — trade-offs?

How do you check if two strings are anagrams?

How do you check if a binary tree is symmetric?

How do you find the single number where every other element appears twice?

How do you find the majority element?

How do you check if a linked list is a palindrome?

Longest consecutive sequence in O(n) with hash set — why not sort?

How do you find a duplicate in an array?

How do you find the maximum depth of a binary tree?

How do you solve the Two Sum problem efficiently?

What is a trie and when is it useful?

How do you find the lowest common ancestor in a binary tree?

How do you find the k closest points to the origin?

How do you solve the 0/1 knapsack problem?

How does binary search work and what are its requirements?

How do you solve the course schedule (prerequisites) problem?

How do you add two numbers stored as linked lists?

How does Quickselect find the kth smallest/largest element?

How do you implement a queue using two stacks?

How do you check if a binary tree is balanced?

How do you check if a graph is bipartite?

How do you remove the nth node from the end of a linked list?

Implement Trie for autocomplete — how do you handle wildcards (.)?

How do you search in a rotated sorted array?

How do you rotate an array by k positions?

How does a hash table work?

How do you validate that a binary tree is a BST?

How do you sort an array of 0s, 1s, and 2s?

How do you find the maximum subarray sum?

Find the kth largest element in an array

How do you get the right-side view of a binary tree?

What is a monotonic stack and when do you use it?

How do you find the middle of a linked list?

How do you compute the diameter of a binary tree?

How do you count the number of set bits in an integer?

How do you count connected components in an undirected graph?

What is a heap / priority queue?

How do you rotate an N×N matrix by 90 degrees in place?

How do you find the kth smallest element in a BST?

What is recursion and what is a base case?

What is a binary search tree (BST)?

How do you do a level-order (BFS) traversal of a tree?

How do you count unique paths in a grid?

Decode ways DP: how do you handle 0 and 06 edge cases?

What is binary search on the answer?

How do you find the node where a linked list cycle begins?

How do you merge overlapping intervals?

How do you group anagrams together?

How do you find the longest substring without repeating characters?

What is the difference between BFS and DFS?

How do you find the maximum product subarray?

How do you solve the house robber problem?

How do you solve the word break problem?

How do you detect a cycle in a linked list?

How do you traverse a matrix in spiral order?

How do you compute the product of an array except self without division?

How do you solve the container with most water problem?

How do you find the minimum number of meeting rooms required?

Trapping Rain Water with two pointers — why does leftMax/rightMax work in O(1) space?

How do you solve the coin change problem?

How do you find the longest common subsequence?