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