Interview Q&A / Data Structures & Algorithms

31. How do you design a stack that returns the minimum element in O(1)?

    Keep a second stack of minimums. On each push, also push the smaller of the new value and the current minimum. Pop from both together, and the top of the second stack is always the minimum.

    IntermediateQuick answerCoding1 min read
32. How do you find all unique triplets in an array that sum to zero?

    Sort the array, fix one number, and use two pointers on the rest to find pairs that cancel it. Skip equal values to avoid duplicate triplets. It runs in O(n squared).

    IntermediateQuick answerCoding1 min read
33. How do you find the length of the longest consecutive sequence in an unsorted array in O(n)?

    Put all numbers in a set. Only start counting from a number whose predecessor is not in the set, then walk upward while the next number exists. Each number is visited at most twice.

    IntermediateQuick answerCoding1 min read
34. How do you find the longest palindromic substring in a string?

    Every palindrome has a centre. Try each index as an odd-length centre and each gap between letters as an even-length centre, expand outward while the ends match, and keep the longest.

    IntermediateQuick answerCoding1 min read
35. How do you find the next greater element for every item in an array?

    Use a monotonic stack of indices. Walk left to right; while the current value is greater than the value at the stack top, that top has found its next greater element. Then push the current index.

    IntermediateQuick answerCoding1 min read
36. How do you find the node where two linked lists intersect?

    Walk two pointers, one from each head. When a pointer reaches the end, redirect it to the head of the other list. After at most two passes they meet at the intersection node, or both become null if there is none.

    IntermediateQuick answerCoding1 min read
37. How do you generate all permutations of an array using backtracking?

    Build the permutation one position at a time. Try every unused element at the current position, mark it used, recurse, then unmark it. A complete path of length n is one permutation; there are n! of them.

    IntermediateQuick answerCoding1 min read
38. How do you generate all subsets of an array using backtracking?

    At each step, record the current path as a subset, then try adding each remaining element, recurse, and remove it again. An array of n items has 2^n subsets.

    IntermediateQuick answerCoding1 min read
39. How do you generate all valid combinations of n pairs of parentheses?

    Build the string character by character. You may add an opening bracket while fewer than n have been used, and a closing bracket only when it would not exceed the number of openings. A string of length 2n is valid.

    IntermediateQuick answerCoding1 min read
40. How do you group anagrams together from a list of words?

    Anagrams share the same sorted letters, so use the sorted word as a hash map key and collect each word under its key. The map values are the groups.

    IntermediateQuick answerCoding1 min read
41. How do you implement a queue using two stacks?

    Push new items onto an input stack. When you need to dequeue and the output stack is empty, pour everything from the input stack into the output stack, which reverses the order, then pop from the output stack.

    IntermediateQuick answerCoding1 min read
42. How do you implement quick sort, and when does it become slow?

    Pick a pivot, partition so smaller elements go left and larger go right, then recursively sort both sides. It averages O(n log n) but becomes O(n squared) when the pivot is always the smallest or largest element.

    IntermediateQuick answerCoding1 min read
43. How do you remove the nth node from the end of a linked list in one pass?

    Move a fast pointer n steps ahead of a slow pointer, then move both until fast reaches the last node. The slow pointer is then just before the node to delete. A dummy head handles removing the first node.

    IntermediateQuick answerCoding1 min read
44. How do you rotate an array to the right by k steps in place?

    Reverse the whole array, then reverse the first k elements, then reverse the rest. Take k modulo the length first. It runs in O(n) time with O(1) extra space.

    IntermediateQuick answerCoding1 min read
45. How do you solve Combination Sum, finding all combinations that add up to a target when numbers can be reused?

    Sort the candidates and backtrack with a start index. Add a candidate, recurse with the reduced target (same start index so it can be reused), and stop a branch when the target is zero or the candidate exceeds it.

    IntermediateQuick answerCoding1 min read
46. How do you solve the Container With Most Water problem using two pointers?

    Start with pointers at both ends. The area is the shorter height times the distance. Move the pointer at the shorter line inward, because moving the taller one can never increase the area.

    IntermediateQuick answerCoding1 min read
47. How do you sort an array of 0s, 1s and 2s in a single pass?

    Use the Dutch national flag method with three pointers: low for the next 0 position, high for the next 2 position, and mid scanning. Swap 0s to the front and 2s to the back; leave 1s in the middle.

    IntermediateQuick answerCoding1 min read
48. What is a stable sort and why does it matter?

    A stable sort keeps items with equal keys in their original relative order. It matters when you sort by one field after another, such as by marks first and then keep the earlier name order for ties.

    IntermediateQuick answerCoding1 min read
49. What is counting sort and when can it beat O(n log n)?

    Counting sort counts how many times each value appears in a small integer range, then rebuilds the array from those counts. It runs in O(n + k) time for values in 0..k, so it beats comparison sorts when k is small.

    IntermediateQuick answerCoding1 min read
50. What is Kadane's algorithm for the maximum subarray sum?

    At each element decide: extend the running subarray or start fresh from this element. Track the best sum seen. It finds the largest contiguous sum in one pass.

    IntermediateQuick answerCoding1 min read
51. What is the difference between merge sort and quick sort?

    Merge sort splits the array in half, sorts each half and merges them; it is always O(n log n) and stable but needs O(n) extra space. Quick sort partitions around a pivot in place; it averages O(n log n) but can degrade to O(n squared) with bad pivots.

    IntermediateQuick answer1 min read
52. How do you design an LRU cache with O(1) get and put?

    Combine a hash map for instant lookup with an ordering of recent use. In JavaScript a Map remembers insertion order, so deleting and re-inserting a key on each access moves it to the newest end; the oldest key is evicted when full.

    AdvancedQuick answerCoding1 min read
53. How do you find the maximum in every sliding window of size k?

    Keep a deque of indices whose values are in decreasing order. Drop indices that left the window from the front, drop smaller values from the back before adding the new index, and the front is always the window maximum.

    AdvancedQuick answerCoding1 min read
54. How do you find the node where a cycle begins in a linked list?

    Detect the cycle with slow and fast pointers. When they meet, reset one pointer to the head and move both one step at a time. They meet again exactly at the start of the cycle.

    AdvancedQuick answerCoding1 min read
55. How do you solve the N-Queens problem with backtracking?

    Place one queen per row. For each column in the row, check that no earlier queen shares the column or a diagonal. If safe, place it and recurse to the next row; otherwise skip. Undo and try the next column.

    AdvancedQuick answerCoding1 min read