🧩 Mastering Data Structures: From Challenging to Mind-Bending

"The art of programming is the skill of controlling complexity." — Marijn Haverbeke

Welcome to this deep dive into data structure problems that will challenge your problem-solving abilities and expand your coding toolkit. This collection features carefully selected problems that have appeared in technical interviews at top tech companies.

📚 Medium Challenges

1. 🌳 Construct Binary Tree from Traversals

Problem: Given inorder and preorder traversals of a binary tree, reconstruct the original binary tree.

Details:

• The inorder traversal visits left subtree, root, then right subtree
• The preorder traversal visits root, left subtree, then right subtree
• You may assume there are no duplicate values in the tree

Sample Input:

preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

Expected Output:

    3
   / \
  9   20
     /  \
    15   7

Explanation: The preorder starts with 3 (the root). From the inorder, we know 9 is in the left subtree of 3, while [15, 20, 7] are in the right subtree.

2. 🔄 LRU Cache Implementation

Problem: Design and implement a data structure for Least Recently Used (LRU) cache with O(1) time complexity for both get and put operations.

Details:

• Support get(key) - Get the value of the key if it exists, otherwise return -1
• Support put(key, value) - Set or insert the value if the key is not already present
• When the cache reaches its capacity, invalidate the least recently used item before inserting a new item
• Both operations should run in O(1) average time complexity

Sample Input:

capacity = 2
put(1, 1)
put(2, 2)
get(1)       // returns 1
put(3, 3)    // evicts key 2
get(2)       // returns -1 (not found)
put(4, 4)    // evicts key 1
get(1)       // returns -1 (not found)
get(3)       // returns 3
get(4)       // returns 4

Expected Output:

1
-1
-1
3
4

Explanation: The cache maintains most recently used items. When capacity is exceeded, the least recently used item is removed.

3. 🏝️ Number of Islands

Problem: Given a 2D binary grid which represents a map of '1's (land) and '0's (water), count the number of islands.

Details:

• An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically
• You may assume all four edges of the grid are surrounded by water
• Use DFS or BFS to explore connected components

Sample Input:

grid = [
  ["0","0","0","0","0"],
  ["0","1","1","1","0"],
  ["0","1","1","1","0"],
  ["0","1","0","0","0"],
  ["0","0","0","0","0"]
]

Expected Output:

1

Explanation: All the 1's are connected horizontally or vertically, forming one large island.

4. 📊 Top K Frequent Elements

Problem: Given an integer array and an integer k, return the k most frequent elements in any order.

Details:

• You may assume k is always valid (1 ≤ k ≤ number of unique elements)
• Your algorithm's time complexity must be better than O(n log n)
• Use a hash map for counting and a heap for finding top k elements

Sample Input:

nums = [1,1,1,2,2,3]
k = 2

Expected Output:

[1,2]

Explanation: Elements 1 and 2 are the two most frequent elements (frequencies 3 and 2 respectively).

5. 🔍 Valid Parentheses with Multiple Types

Problem: Given a string containing just the characters '(', ')', ', ', '[' and ']', determine if the input string has valid parentheses.

Details:

• Open brackets must be closed by the same type of brackets
• Open brackets must be closed in the correct order
• Every close bracket has a corresponding open bracket of the same type
• Use a stack data structure for efficient tracking

Sample Input:

s = "()[]{}"

Expected Output:

true

Explanation: All brackets are properly matched and closed in the correct order.

Sample Input 2:

s = "([)]"

Expected Output 2:

false

Explanation: The brackets are interleaved incorrectly - ')' closes '(' but '[' is still open.

🔥 Hard Challenges

1. 🧮 Serialize and Deserialize Binary Tree

Problem: Design an algorithm to serialize and deserialize a binary tree. Serialization is the process of converting a tree to a string, and deserialization is reconstructing the tree from the string.

Details:

• Your serialized string should be as compact as possible
• The deserialization should be able to reconstruct the exact same tree
• Handle null nodes appropriately in your serialization format
• Consider using preorder traversal with null markers

Sample Input:

Tree:
    1
   / \
  2   3
     / \
    4   5

Expected Serialization:

"1,2,null,null,3,4,null,null,5,null,null"

Expected Deserialization:

    1
   / \
  2   3
     / \
    4   5

Explanation: The serialization uses preorder traversal with "null" markers for empty nodes. Deserialization rebuilds the tree by processing the string in the same order.

2. 🎯 Merge k Sorted Lists

Problem: You are given an array of k linked-lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Details:

• Each individual linked list is already sorted
• The final result should be a single sorted linked list
• Optimize for time complexity using a min-heap or divide-and-conquer approach
• Handle edge cases like empty lists

Sample Input:

lists = [
  1->4->5,
  1->3->4,
  2->6
]

Expected Output:

1->1->2->3->4->4->5->6

Explanation: The merged list contains all elements from the input lists in sorted order.

Time Complexity: O(N log k) where N is the total number of nodes and k is the number of lists.

3. 🌊 Trapping Rain Water

Problem: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water can be trapped after raining.

Details:

• Water can only be trapped between higher elevations
• Calculate the total volume of trapped water
• Consider using two pointers or dynamic programming approach
• Each position can trap water equal to min(max_left, max_right) - current_height

Sample Input:

height = [0,1,0,2,1,0,1,3,2,1,2,1]

Expected Output:

6

Visual Representation:

    █
█   █ █   █
█ █ █████ ██
█████████████
0102101321201

Explanation: The trapped water (represented by spaces above) totals 6 units. Water is trapped at positions where there are higher bars on both sides.

💡 Problem-Solving Tips

1. Start with brute force: Understand the problem completely before optimizing
2. Identify patterns: Many problems follow common algorithmic patterns
3. Draw it out: Visualize the problem with examples and edge cases
4. Consider time/space tradeoffs: Sometimes using extra space can dramatically improve time complexity
5. Test edge cases: Empty inputs, single elements, and maximum constraints

🎯 Next Steps

Master these problems and you'll be well-equipped to tackle technical interviews at top tech companies. Remember, the key is not just to solve these problems, but to understand the underlying patterns and techniques that can be applied to similar challenges.

Happy coding! 🚀