Interview Q&A / Data Structures & Algorithms

1. 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
2. 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
3. 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
4. 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
5. 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
6. 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
7. What is the difference between an array and a linked list, and when would you choose each?

   An array stores items contiguously, so indexing is O(1) but inserting in the middle is O(n). A linked list stores nodes connected by pointers, so insertion at a known node is O(1) but reaching the kth item is O(n).

   BeginnerQuick answer1 min read
8. 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
9. 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
10. 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
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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