Interview Q&A / Data Structures & Algorithms

1. 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
2. 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
3. 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
4. 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
5. 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
6. 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
7. 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
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 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
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 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
12. 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
13. 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
14. 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
15. 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
16. 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