Interview Q&A / Data Structures & Algorithms

1. How do you check if a string of brackets is valid (balanced parentheses)?

   Scan the string with a stack. Push every opening bracket. For every closing bracket, the stack must be non-empty and its top must be the matching opening bracket, which you then pop. The string is valid only if the stack is empty at the end. O(n) time, O(n) space.

   BeginnerIn-depthCoding3 min read
2. How do you implement binary search, and what are the common bugs?

   On a sorted array, keep two pointers low and high, check the middle element, and throw away the half that cannot contain the target. Repeat until found or low passes high. It runs in O(log n). The classic bugs are computing mid as (low + high) / 2, which can overflow in Java or C++, and off-by-one errors in the loop condition and pointer updates.

   BeginnerIn-depthCoding4 min read
3. How do you merge two sorted arrays into one sorted array?

   Use two pointers, one at the start of each array. Compare the two current elements, copy the smaller one to the result and move that pointer forward. When one array runs out, copy the rest of the other. This is O(n + m) time, much better than joining and sorting again.

   BeginnerIn-depthCoding3 min read
4. How do you reverse a singly linked list?

   Walk through the list once with three pointers (previous, current and next) and turn each arrow around so it points backwards. The last node you visit becomes the new head. O(n) time, O(1) extra space.

   BeginnerIn-depthCoding2 min read
5. Two Sum - find two numbers that add up to a target

   Walk through the array once and store each number's index in a hash map. For each number, check if target minus that number is already in the map. This takes O(n) time.

   BeginnerIn-depthCoding2 min read
6. How do you detect a cycle in a linked list?

   Use Floyd's tortoise and hare method. Move a slow pointer one step and a fast pointer two steps at a time. If the fast pointer reaches null, there is no cycle. If the two pointers ever meet, there is a cycle. It runs in O(n) time with O(1) extra space.

   IntermediateIn-depthCoding4 min read
7. What is the difference between BFS and DFS, and when would you use each?

   BFS (breadth-first search) explores a graph level by level using a queue, so it finds the shortest path in an unweighted graph. DFS (depth-first search) goes as deep as possible along one path before backtracking, using a stack or recursion, and suits cycle detection, topological sort and exploring all paths. Both take O(V + E) time.

   IntermediateIn-depthCoding4 min read
8. How do you find the longest substring without repeating characters?

   Use a sliding window. Expand the right end one character at a time and remember the last index where each character was seen. If the new character already appears inside the window, move the left end just past its previous position. Track the largest window size. This is O(n) time.

   AdvancedIn-depthCoding4 min read
9. How do you check if a string is a palindrome, ignoring spaces, punctuation and case?

   Use two pointers from both ends. Skip characters that are not letters or digits, compare the rest in lowercase, and move inward. If any pair differs, it is not a palindrome.

   BeginnerQuick answerCoding1 min read
10. How do you check if one string is a rotation of another?

    They must have the same length, and the second string must appear inside the first string written twice. For example, "waterbottle" doubled contains "erbottlewat".

    BeginnerQuick answerCoding1 min read
11. How do you check whether two strings are anagrams of each other?

    Two strings are anagrams if they have the same letters with the same counts. Count the characters of the first string, subtract using the second, and check that every count ends at zero.

    BeginnerQuick answerCoding1 min read
12. How do you evaluate a postfix (reverse Polish) expression?

    Scan tokens left to right. Push numbers onto a stack. When you see an operator, pop two numbers, apply the operator (the first popped is the right operand), and push the result. The final stack value is the answer.

    BeginnerQuick answerCoding1 min read
13. How do you find the first non-repeating character in a string?

    Count how often each character appears in one pass, then scan again and return the first character whose count is 1.

    BeginnerQuick answerCoding1 min read
14. How do you find the longest common prefix among an array of strings?

    Take the first string as the candidate prefix and shorten it until every other string starts with it. Return what is left, which may be an empty string.

    BeginnerQuick answerCoding1 min read
15. How do you find the maximum profit from buying and selling a stock once?

    Scan once while tracking the lowest price so far. At each day, the best profit if you sell today is price minus that lowest price. Keep the maximum of those.

    BeginnerQuick answerCoding1 min read
16. How do you find the middle node of a linked list in one pass?

    Use two pointers: slow moves one step, fast moves two. When fast reaches the end, slow is at the middle. For an even length it lands on the second of the two middle nodes.

    BeginnerQuick answerCoding1 min read
17. How do you implement merge sort in JavaScript?

    Recursively split the array into two halves until single elements remain, then merge the sorted halves by repeatedly taking the smaller front element. It runs in O(n log n) time with O(n) extra space.

    BeginnerQuick answerCoding1 min read
18. How do you merge two sorted linked lists into one sorted list?

    Use a dummy head and a tail pointer. Repeatedly attach the smaller of the two current nodes to the tail and advance that list. When one list ends, attach the rest of the other.

    BeginnerQuick answerCoding1 min read
19. How do you remove duplicates from a sorted array in place and return the new length?

    Keep a write index. Because the array is sorted, a value is new only if it differs from the last value written. Copy it forward and advance the write index; the final write index is the new length.

    BeginnerQuick answerCoding1 min read
20. How do you reverse the order of words in a sentence, ignoring extra spaces?

    Trim the string, split on one or more whitespace characters, reverse the array of words, and join with a single space.

    BeginnerQuick answerCoding1 min read
21. Why does [10, 9, 1].sort() return [1, 10, 9] in JavaScript?

    By default sort converts elements to strings and compares them in dictionary order, so "10" comes before "9". Pass a comparator such as (a, b) => a - b to sort numbers numerically.

    BeginnerQuick answerCoding1 min read
22. Write a function that moves all zeroes to the end of an array while keeping the order of the other elements.

    Use a write pointer: copy every non-zero value forward to the write position, then fill the remaining slots with zeroes. One pass, no extra array.

    BeginnerQuick answerCoding1 min read
23. How do you check if a linked list is a palindrome in O(1) extra space?

    Find the middle with slow and fast pointers, reverse the second half in place, then compare it with the first half node by node.

    IntermediateQuick answerCoding1 min read
24. How do you compute x to the power n efficiently with recursion?

    Use divide and conquer: x^n equals (x^(n/2)) squared, times x if n is odd. That halves n each time, so it needs only O(log n) multiplications instead of O(n).

    IntermediateQuick answerCoding1 min read
25. How do you count subarrays whose sum equals k using a prefix sum and hash map?

    Keep a running prefix sum and a map of how many times each prefix sum has occurred. At each step, the number of subarrays ending here with sum k equals the count of earlier prefix sums equal to current minus k.

    IntermediateQuick answerCoding1 min read
26. 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
27. 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
28. 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
29. 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
30. 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