Interview Q&A / Data Structures & Algorithms

1. 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
2. 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
3. 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
4. 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
5. 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
6. 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
7. 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
8. 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