💻 Arrays & Hashing (Coding)
Day 2 | ⏱️ Part of 3.5-Hour Coding Block | TCS Interview Prep
📌 Subtopics
Arrays
- Subarrays: Contiguous subarrays, max subarray sum (Kadane’s algorithm)
- Sliding Window: Fixed-size and variable-size window problems
- Two Pointers: Sorted array problems, pair sum, container with most water
Hashing
- Hash Maps: Key-value storage, O(1) lookups
- Frequency Tables: Counting occurrences of elements
🌐 Learning Resources
| Resource | Link |
|---|---|
| GFG — Arrays | geeksforgeeks.org |
| GFG — Sliding Window | geeksforgeeks.org |
| GFG — Two Pointers | geeksforgeeks.org |
| GFG — Hashing | geeksforgeeks.org |
| NeetCode — Arrays & Hashing | neetcode.io |
| LeetCode — Array Problems | leetcode.com |
| TakeUForward — Arrays Playlist | takeuforward.org |
✅ Must-Practice Problems (LeetCode)
| Problem | Difficulty | Link |
|---|---|---|
| Two Sum | Easy | leetcode.com/problems/two-sum |
| Best Time to Buy & Sell Stock | Easy | leetcode.com/problems/best-time-to-buy-and-sell-stock |
| Maximum Subarray (Kadane’s) | Medium | leetcode.com/problems/maximum-subarray |
| Contains Duplicate | Easy | leetcode.com/problems/contains-duplicate |
| Longest Substring Without Repeating | Medium | leetcode.com/problems/longest-substring-without-repeating-characters |
| Subarray Sum Equals K | Medium | leetcode.com/problems/subarray-sum-equals-k |
| Group Anagrams | Medium | leetcode.com/problems/group-anagrams |
📝 Key Patterns
# Two Sum using HashMap
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
# Sliding Window Template
def sliding_window(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i-k]
max_sum = max(max_sum, window_sum)
return max_sum
# Kadane's Algorithm
def max_subarray(nums):
curr_max = global_max = nums[0]
for num in nums[1:]:
curr_max = max(num, curr_max + num)
global_max = max(global_max, curr_max)
return global_max🔗 Related Topics
- Strings — String problems heavily rely on array manipulation and hash maps for frequency counting
- Dynamic Programming — DP states are stored in 1D/2D arrays or hash tables
- Greedy Number Theory and Bit Manipulation — Greedy algorithm optimizations on arrays
- Patterns and Series — Patterns in number sequences are analyzed using arrays and hash maps
- Permutations Combinations and Probability — Generating arrays of combinations or permutations