एक बात है जिसके लिए शीर्ष इंटरव्यू कोच आपसे $500 नहीं लेने चाहिए: कोडिंग इंटरव्यू की लगभग 90% समस्याएँ सिर्फ सात डेटा स्ट्रक्चर के आसपास घूमती हैं। अगर आप गहराई से समझते हैं कि कब और क्यों किस स्ट्रक्चर का उपयोग करना है, तो आधी लड़ाई आप पहले ही जीत चुके हैं। बाकी आधी अभ्यास है, लेकिन सही मानसिक मॉडल के बिना अभ्यास सिर्फ रटने जैसा हो जाता है। यह पाठ आपको वह नक्शा देता है, जिससे हर नई समस्या पहचाने हुए इलाके जैसी लगे।
हर तकनीकी इंटरव्यू उसी स्रोत से सवाल लेता है। ये वे स्ट्रक्चर हैं जो आपको मिलेंगे, आवृत्ति के क्रम में:
| डेटा स्ट्रक्चर | इंटरव्यू आवृत्ति | मुख्य ऑपरेशन | इंटरव्यूअर कब इसकी अपेक्षा करते हैं | |---|---|---|---| | ऐरे / स्ट्रिंग | ★★★★★ | एक्सेस O(1), खोज O(n), इन्सर्ट O(n) | लगभग हर समस्या यहीं से शुरू होती है | | हैश मैप / सेट | ★★★★★ | इन्सर्ट O(1), खोज O(1), डिलीट O(1) | "इसे O(n²) से O(n) में ऑप्टिमाइज़ करें" | | लिंक्ड लिस्ट | ★★★★☆ | इन्सर्ट O(1), डिलीट O(1), एक्सेस O(n) | पॉइंटर मैनिपुलेशन, साइकल डिटेक्शन | | स्टैक और क्यू | ★★★★☆ | पुश/पॉप O(1), एनक्यू/डीक्यू O(1) | पार्सिंग, BFS, अनडू ऑपरेशन | | ट्री (बाइनरी, BST) | ★★★★☆ | खोज O(log n), इन्सर्ट O(log n) | पदानुक्रमित डेटा, सॉर्टेड ऑपरेशन | | ग्राफ़ | ★★★☆☆ | निरूपण पर निर्भर | संबंध, पाथ, कनेक्टिविटी | | हीप | ★★★☆☆ | इन्सर्ट O(log n), एक्सट्रैक्ट-मिन O(log n) | "सबसे बड़े/छोटे k खोजें" |
लगभग हर इंटरव्यू समस्या की शुरुआत ऐरे से होती है। मुख्य समझ यह है कि अधिकतर ऐरे समस्याएँ सच में ऐरे के बारे में नहीं होतीं। वे दो पॉइंटर, स्लाइडिंग विंडो या प्रीफ़िक्स सम जैसे पैटर्न पहचानने के बारे में होती हैं।
# Two Sum — the most classic interview problem
# "Given an array and target, find two numbers that add to target"
def two_sum(nums, target):
seen = {} # Hash map to store complement
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# Time: O(n), Space: O(n) — trading space for time
ध्यान दें कि यह "ऐरे" समस्या भी सच में हैश मैप समस्या है। यह पैटर्न बार-बार दिखता है: ब्रूट फ़ोर्स ऐरे पर नेस्टेड लूप लगाता है, और ऑप्टिमल समाधान हैश मैप जोड़ता है।
अगर आप किसी समस्या में अटके हैं और ब्रूट फ़ोर्स O(n²) है, तो खुद से पूछें: "क्या हैश मैप इसे O(n) कर सकता है?" हैरानी की बात है कि उत्तर अक्सर हाँ होता है।
हैश मैप तब बहुत काम आते हैं जब आपको यह करना हो:
साइन इन करें चर्चा में शामिल होने के लिए
// Group Anagrams — a classic hash map problem
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
लिंक्ड लिस्ट समस्याएँ जाँचती हैं कि आप नोड खोए बिना पॉइंटर बदल सकते हैं या नहीं। आपको तीन तकनीकें आनी चाहिए:
# Detect a cycle in a linked list (Floyd's Algorithm)
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
स्टैक (LIFO) और क्यू (FIFO) सरल स्ट्रक्चर हैं, लेकिन वे पूरी समस्या श्रेणियाँ खोल देते हैं:
# Valid Parentheses — classic stack problem
def is_valid(s: str) -> bool:
stack = []
matching = {')': '(', '}': '{', ']': '['}
for char in s:
if char in matching:
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0
ट्री समस्याओं में आम तौर पर रिकर्शन और तीन ट्रैवर्सल क्रमों में से एक शामिल होता है: इन-ऑर्डर, प्री-ऑर्डर, पोस्ट-ऑर्डर। विकसित करने वाला मानसिक मॉडल है: "मुझे बाएँ सबट्री से क्या चाहिए, दाएँ सबट्री से क्या चाहिए, और मौजूदा नोड पर उन्हें कैसे मिलाना है?"
# Maximum depth of a binary tree — the template for tree recursion
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
BST (Binary Search Tree) समस्याएँ एक अहम गुण जोड़ती हैं: इन-ऑर्डर ट्रैवर्सल सॉर्टेड तत्व देता है। अगर एक ही समस्या में "सॉर्टेड" और "ट्री" दिखें, तो तुरंत BST सोचें।
ग्राफ़ समस्याएँ डरावनी लग सकती हैं, लेकिन adjacency list बनाने के बाद अधिकतर BFS या DFS में बदल जाती हैं। मुख्य कौशल ये हैं:
# BFS shortest path in an unweighted graph
from collections import deque
def shortest_path(graph, start, end):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, distance = queue.popleft()
if node == end:
return distance
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append((neighbour, distance + 1))
return -1 # Not reachable
जब भी समस्या में "K largest", "K closest" या "merge K sorted lists" कहा जाए, तो heap (priority queue) लगभग निश्चित रूप से सही उत्तर है। Python में heapq min-heap देता है। max-heap के लिए मानों को negate करें।
import heapq
# Find the K largest elements in an array
def k_largest(nums, k):
return heapq.nlargest(k, nums) # Uses a min-heap of size k internally
आपको संख्याओं की stream का median हर insertion पर O(log n) में खोजना है। कौन सा data structure combination सबसे उपयुक्त है?
| स्ट्रक्चर | एक्सेस | खोज | इन्सर्ट | डिलीट | स्पेस | |---|---|---|---|---|---| | ऐरे | O(1) | O(n) | O(n) | O(n) | O(n) | | हैश मैप | - | O(1)* | O(1)* | O(1)* | O(n) | | लिंक्ड लिस्ट | O(n) | O(n) | O(1) | O(1) | O(n) | | स्टैक/क्यू | O(n) | O(n) | O(1) | O(1) | O(n) | | BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | | हीप | - | O(n) | O(log n) | O(log n) | O(n) |
* औसत केस। हैश collisions के कारण worst case O(n) है।
समस्या पढ़ते समय यह मानसिक चेकलिस्ट विकसित करें: