DSA for Data Engineers
Blind 75 — Python Edition | Curated for Data Engineering Interviews
1. ARRAYS & STRINGS
Q1. Two Sum
Tags: HashMap | Frequency | Lookup
DE Use: Deduplication, finding matching keys across datasets
def two_sum(nums, target):
seen = {}
for i, n in enumerate(nums):
if target - n in seen:
return [seen[target - n], i]
seen[n] = i
Q2. Best Time to Buy and Sell Stock
Tags: Sliding Window | Min Tracking
DE Use: Time-series max/min tracking in streaming pipelines
def max_profit(prices):
min_p, max_p = float('inf'), 0
for p in prices:
min_p = min(min_p, p)
max_p = max(max_p, p - min_p)
return max_p
Q3. Contains Duplicate
Tags: HashSet | Dedup
DE Use: Detecting duplicate records in ETL pipelines
def contains_duplicate(nums):
return len(nums) != len(set(nums))
Q4. Product of Array Except Self
Tags: Prefix/Suffix | No Division
DE Use: Running calculations across partitioned data
def product_except_self(nums):
res = [1] * len(nums)
prefix = 1
for i in range(len(nums)):
res[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(len(nums)-1, -1, -1):
res[i] *= suffix
suffix *= nums[i]
return res
Q5. Maximum Subarray (Kadane's)
Tags: Dynamic Programming | Streaming
DE Use: Max value window in time-series data
def max_subarray(nums):
cur = best = nums[0]
for n in nums[1:]:
cur = max(n, cur + n)
best = max(best, cur)
return best
2. HASHMAPS & FREQUENCY
Q6. Group Anagrams
Tags: HashMap | Sorting | Grouping
DE Use: Grouping similar records, bucketing by key pattern
from collections import defaultdict
def group_anagrams(strs):
d = defaultdict(list)
for s in strs:
d[tuple(sorted(s))].append(s)
return list([Link]())
Q7. Top K Frequent Elements
Tags: Heap | Counter | Bucket Sort
DE Use: Top N customers, top N products in aggregation pipelines
from collections import Counter
import heapq
def top_k_frequent(nums, k):
count = Counter(nums)
return [Link](k, [Link](), key=[Link])
Q8. Valid Anagram
Tags: Counter | Frequency Map
DE Use: Schema validation, column name matching
from collections import Counter
def is_anagram(s, t):
return Counter(s) == Counter(t)
Q9. Longest Consecutive Sequence
Tags: HashSet | O(n)
DE Use: Finding gaps in sequence IDs, detecting missing records
def longest_consecutive(nums):
s = set(nums)
best = 0
for n in s:
if n - 1 not in s:
cur = n
streak = 1
while cur + 1 in s:
cur += 1
streak += 1
best = max(best, streak)
return best
3. SLIDING WINDOW
Q10. Longest Substring Without Repeating Characters
Tags: Sliding Window | HashMap
DE Use: Rolling window deduplication in streaming data
def length_of_longest_substring(s):
seen = {}
l = best = 0
for r, c in enumerate(s):
if c in seen and seen[c] >= l:
l = seen[c] + 1
seen[c] = r
best = max(best, r - l + 1)
return best
Q11. Minimum Window Substring
Tags: Sliding Window | Two Pointer
DE Use: Finding minimum data range satisfying conditions
from collections import Counter
def min_window(s, t):
need = Counter(t)
missing = len(t)
best = ""
l = 0
for r, c in enumerate(s, 1):
missing -= need[c] > 0
need[c] -= 1
if not missing:
while need[s[l]] < 0:
need[s[l]] += 1
l += 1
if not best or r - l < len(best):
best = s[l:r]
need[s[l]] += 1
missing += 1
l += 1
return best
4. TWO POINTERS
Q12. Three Sum
Tags: Two Pointer | Sorting
DE Use: Finding matching record combinations across datasets
def three_sum(nums):
[Link]()
res = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s == 0:
[Link]([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]: l += 1
while l < r and nums[r] == nums[r-1]: r -= 1
l += 1; r -= 1
elif s < 0: l += 1
else: r -= 1
return res
Q13. Valid Palindrome
Tags: Two Pointer | String
DE Use: Data validation, string normalization checks
def is_palindrome(s):
s = ''.join([Link]() for c in s if [Link]())
return s == s[::-1]
5. STACKS & QUEUES
Q14. Valid Parentheses
Tags: Stack | Matching
DE Use: Validating nested JSON/XML structures in pipelines
def is_valid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for c in s:
if c in mapping:
if not stack or stack[-1] != mapping[c]:
return False
[Link]()
else:
[Link](c)
return not stack
Q15. Daily Temperatures
Tags: Monotonic Stack
DE Use: Next greater value problems in time-series
def daily_temperatures(temps):
res = [0] * len(temps)
stack = []
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = [Link]()
res[j] = i - j
[Link](i)
return res
6. BINARY SEARCH
Q16. Binary Search
Tags: Binary Search | O(log n)
DE Use: Searching sorted partition keys, index lookups
def search(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target: return mid
elif nums[mid] < target: l = mid + 1
else: r = mid - 1
return -1
Q17. Find Minimum in Rotated Sorted Array
Tags: Binary Search | Rotated
DE Use: Partition boundary detection in distributed data
def find_min(nums):
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) // 2
if nums[mid] > nums[r]: l = mid + 1
else: r = mid
return nums[l]
7. TREES & GRAPHS (DATA LINEAGE)
Q18. Maximum Depth of Binary Tree
Tags: DFS | Recursion
DE Use: Measuring data lineage depth, dependency trees
def max_depth(root):
if not root: return 0
return 1 + max(max_depth([Link]), max_depth([Link]))
Q19. Number of Islands
Tags: BFS/DFS | Graph
DE Use: Finding connected components in data dependency graphs
def num_islands(grid):
count = 0
def dfs(i, j):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '0'
for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(i+di, j+dj)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count
Q20. Course Schedule (Cycle Detection)
Tags: Topological Sort | DAG
DE Use: Detecting circular dependencies in pipeline DAGs
from collections import defaultdict, deque
def can_finish(n, prerequisites):
graph = defaultdict(list)
indegree = [0] * n
for a, b in prerequisites:
graph[b].append(a)
indegree[a] += 1
q = deque([i for i in range(n) if indegree[i] == 0])
count = 0
while q:
node = [Link]()
count += 1
for nei in graph[node]:
indegree[nei] -= 1
if indegree[nei] == 0:
[Link](nei)
return count == n
8. DYNAMIC PROGRAMMING
Q21. Climbing Stairs
Tags: DP | Fibonacci
DE Use: Counting pipeline execution paths
def climb_stairs(n):
a, b = 1, 1
for _ in range(n - 1):
a, b = b, a + b
return b
Q22. Longest Common Subsequence
Tags: DP | String Matching
DE Use: Schema diff, data reconciliation between two datasets
def lcs(text1, text2):
dp = [[0] * (len(text2)+1) for _ in range(len(text1)+1)]
for i in range(1, len(text1)+1):
for j in range(1, len(text2)+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
Q23. Coin Change
Tags: DP | BFS
DE Use: Minimum steps to transform data between formats
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if c <= i:
dp[i] = min(dp[i], dp[i-c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
9. SORTING & INTERVALS
Q24. Merge Intervals
Tags: Sorting | Intervals
DE Use: Merging overlapping time windows in event data
def merge(intervals):
[Link]()
res = [intervals[0]]
for start, end in intervals[1:]:
if start <= res[-1][1]:
res[-1][1] = max(res[-1][1], end)
else:
[Link]([start, end])
return res
Q25. Meeting Rooms II
Tags: Heap | Greedy | Scheduling
DE Use: Resource allocation in parallel pipeline scheduling
import heapq
def min_meeting_rooms(intervals):
[Link]()
heap = []
for start, end in intervals:
if heap and heap[0] <= start:
[Link](heap, end)
else:
[Link](heap, end)
return len(heap)
10. PYTHON DATA ENGINEERING SPECIFIC
Q26. Find duplicates in a list of dicts (records)
Tags: HashMap | Dedup | ETL
DE Use: Direct ETL deduplication logic
def find_duplicates(records, key):
seen = set()
dupes = []
for r in records:
val = r[key]
if val in seen:
[Link](r)
[Link](val)
return dupes
Q27. Flatten nested JSON
Tags: Recursion | JSON | Schema
DE Use: Flattening Kafka JSON messages in pipelines
def flatten(d, parent='', sep='_'):
items = {}
for k, v in [Link]():
new_key = f"{parent}{sep}{k}" if parent else k
if isinstance(v, dict):
[Link](flatten(v, new_key, sep))
else:
items[new_key] = v
return items
Q28. Group records by key (like SQL GROUP BY)
Tags: defaultdict | Aggregation
DE Use: In-memory aggregation before DB write
from collections import defaultdict
def group_by(records, key):
result = defaultdict(list)
for r in records:
result[r[key]].append(r)
return dict(result)
Q29. Sliding window average (streaming)
Tags: Deque | Streaming | Window
DE Use: Rolling average in real-time Kafka streams
from collections import deque
def sliding_average(nums, k):
window = deque()
result = []
total = 0
for n in nums:
[Link](n)
total += n
if len(window) > k:
total -= [Link]()
if len(window) == k:
[Link](total / k)
return result
Q30. LRU Cache
Tags: OrderedDict | Cache | O(1)
DE Use: Caching lookup tables in ETL graph components
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
[Link] = capacity
[Link] = OrderedDict()
def get(self, key):
if key not in [Link]: return -1
[Link].move_to_end(key)
return [Link][key]
def put(self, key, value):
if key in [Link]:
[Link].move_to_end(key)
[Link][key] = value
if len([Link]) > [Link]:
[Link](last=False)
Total: 30 Questions | Focus: Arrays, HashMap, Sliding Window, Trees, Graphs, DP, DE-specific
Python