Problem Solving (Code) Flashcards
(15 cards)
Write a Sliding Window solution to find the maximum sum of k consecutive elements in an array.
```javascript
function maxSum(arr, k) {
let max = 0, sum = 0;
for (let i = 0; i < k; i++) sum += arr[i];
max = sum;
for (let i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k];
max = Math.max(max, sum);
}
return max;
}
// Example: maxSum([1, 4, 2, 10, 2], 3) → 16 (4+2+10)
// Explanation: Uses a window of size k, sliding by adding new element and removing oldest, tracking max sum (O(n)).
~~~
Implement Two Pointers to find two numbers in a sorted array that sum to a target.
```javascript
function twoSum(arr, target) {
let left = 0, right = arr.length - 1;
while (left < right) {
let sum = arr[left] + arr[right];
if (sum === target) return [left, right];
if (sum < target) left++;
else right–;
}
return [];
}
// Example: twoSum([2, 7, 11, 15], 9) → [0, 1] (2+7=9)
// Explanation: Two pointers move toward each other in sorted array, adjusting based on sum (O(n)).
~~~
Use Fast and Slow Pointers to detect a cycle in a linked list.
```javascript
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
// Example: List 1->2->3->2 (cycle) → true
// Explanation: Slow moves one step, fast moves two; meeting indicates a cycle (O(n)).
~~~
Implement Binary Search to find an element in a sorted array.
```javascript
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;
}
// Example: binarySearch([1, 2, 3, 4, 5], 3) → 2
// Explanation: Halves search space each step, returns index or -1 if not found (O(log n)).
~~~
Write a Depth-First Search (DFS) to find if a path exists in a graph.
```javascript
function hasPath(graph, start, end, visited = new Set()) {
if (start === end) return true;
visited.add(start);
for (let neighbor of graph[start]) {
if (!visited.has(neighbor)) {
if (hasPath(graph, neighbor, end, visited)) return true;
}
}
return false;
}
// Example: graph = {0:[1,2], 1:[2], 2:[]} → hasPath(graph, 0, 2) → true
// Explanation: Recursively explores each node’s neighbors, tracking visited nodes (O(V + E)).
~~~
Use Breadth-First Search (BFS) to find the shortest path in an unweighted graph.
```javascript
function shortestPath(graph, start, end) {
let queue = [[start]], visited = new Set([start]), paths = [];
while (queue.length) {
let path = queue.shift(), node = path[path.length - 1];
if (node === end) return path;
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([…path, neighbor]);
}
}
}
return [];
}
// Example: graph = {0:[1,2], 1:[2], 2:[]} → shortestPath(graph, 0, 2) → [0, 2]
// Explanation: Explores nodes level by level, returns shortest path (O(V + E)).
~~~
Implement Two Heaps to find the median of a data stream.
```javascript
class MedianFinder {
constructor() {
this.minHeap = []; // Stores larger half
this.maxHeap = []; // Stores smaller half
}
addNum(num) {
if (this.maxHeap.length === 0 || num < this.maxHeap[0]) {
this.maxHeap.push(num);
this.maxHeap.sort((a, b) => b - a);
} else {
this.minHeap.push(num);
this.minHeap.sort((a, b) => a - b);
}
if (this.maxHeap.length > this.minHeap.length + 1) {
this.minHeap.push(this.maxHeap.shift());
this.minHeap.sort((a, b) => a - b);
} else if (this.minHeap.length > this.maxHeap.length) {
this.maxHeap.push(this.minHeap.shift());
this.maxHeap.sort((a, b) => b - a);
}
}
findMedian() {
if (this.maxHeap.length > this.minHeap.length) return this.maxHeap[0];
return (this.maxHeap[0] + this.minHeap[0]) / 2;
}
}
// Example: addNum(1), addNum(2), findMedian() → 1.5
// Explanation: Balances two heaps to keep median accessible (O(log n) per add).
~~~
Use Backtracking to solve the N-Queens problem.
```javascript
function solveNQueens(n) {
let result = [];
function backtrack(board, row) {
if (row === n) {
result.push(board.map(r => ‘.’.repeat(r) + ‘Q’ + ‘.’.repeat(n-1-r)));
return;
}
for (let col = 0; col < n; col++) {
if (isSafe(board, row, col)) {
board[row] = col;
backtrack(board.slice(), row + 1);
}
}
}
function isSafe(board, row, col) {
for (let i = 0; i < row; i++) {
if (board[i] === col || Math.abs(board[i] - col) === row - i) return false;
}
return true;
}
backtrack([], 0);
return result;
}
// Example: solveNQueens(4) → [[‘.Q..’, ‘…Q’, ‘Q…’, ‘..Q.’], [’..Q.’, ‘Q…’, ‘…Q’, ‘.Q..’]]
// Explanation: Places queens recursively, pruning invalid placements (O(n!)).
~~~
Implement Dynamic Programming to compute the nth Fibonacci number.
```javascript
function fibonacci(n) {
let dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Example: fibonacci(5) → 5 (0,1,1,2,3,5)
// Explanation: Stores subproblem results in array to avoid recomputation (O(n)).
~~~
Use Topological Sort to order tasks with dependencies.
```javascript
function topologicalSort(graph) {
let result = [], visited = new Set(), temp = new Set();
function dfs(node) {
if (temp.has(node)) return false; // Cycle detected
if (visited.has(node)) return true;
temp.add(node);
for (let neighbor of graph[node]) {
if (!dfs(neighbor)) return false;
}
temp.delete(node);
visited.add(node);
result.unshift(node);
return true;
}
for (let node in graph) {
if (!visited.has(node)) dfs(node);
}
return result;
}
// Example: graph = {0:[1,2], 1:[3], 2:[3], 3:[]} → [0, 2, 1, 3]
// Explanation: Orders nodes so dependencies come first (O(V + E)).
~~~
Implement Greedy to find minimum coins for a target amount.
```javascript
function minCoins(coins, amount) {
coins.sort((a, b) => b - a);
let count = 0;
for (let coin of coins) {
while (amount >= coin) {
amount -= coin;
count++;
}
}
return amount === 0 ? count : -1;
}
// Example: minCoins([1, 5, 10, 25], 30) → 3 (25+5)
// Explanation: Chooses largest coins first, may not always be optimal (O(n)).
~~~
Use Merge Intervals to combine overlapping intervals.
```javascript
function mergeIntervals(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
let result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
let last = result[result.length - 1];
if (intervals[i][0] <= last[1]) {
last[1] = Math.max(last[1], intervals[i][1]);
} else {
result.push(intervals[i]);
}
}
return result;
}
// Example: mergeIntervals([[1,3], [2,6], [8,10]]) → [[1,6], [8,10]]
// Explanation: Merges overlapping intervals after sorting by start time (O(n log n)).
~~~
Implement Subsets pattern to generate all subsets of a set.
```javascript
function subsets(nums) {
let result = [[]];
for (let num of nums) {
let newSubsets = result.map(subset => […subset, num]);
result.push(…newSubsets);
}
return result;
}
// Example: subsets([1,2]) → [[], [1], [2], [1,2]]
// Explanation: Builds subsets iteratively by adding each element (O(2ⁿ)).
~~~
Use Monotonic Stack to find the next greater element in an array.
```javascript
function nextGreaterElement(nums) {
let stack = [], result = new Array(nums.length).fill(-1);
for (let i = 0; i < nums.length; i++) {
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result;
}
// Example: nextGreaterElement([4, 5, 2, 25]) → [5, 25, 25, -1]
// Explanation: Maintains a stack of indices, popping when a larger element is found (O(n)).
~~~
Implement Kadane’s Algorithm to find the maximum subarray sum.
```javascript
function maxSubArray(nums) {
let max = nums[0], current = nums[0];
for (let i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
max = Math.max(max, current);
}
return max;
}
// Example: maxSubArray([-2,1,-3,4,-1,2,1]) → 6 (4,-1,2,1)
// Explanation: Tracks local and global max sum, resetting if sum becomes negative (O(n)).
~~~
