Senior-Level DSA Topics for Google

📖 Concept

Google's coding interviews test DSA at a higher bar for senior candidates. You're expected to identify the optimal approach quickly and implement it cleanly in Kotlin.

Essential topic areas ranked by Google frequency:

Arrays & Strings — Two pointers, sliding window, prefix sums, binary search
Trees & Graphs — BFS/DFS, shortest path, topological sort, tree traversals
Dynamic Programming — State definition, transitions, optimization
Hash Maps & Sets — Frequency counting, grouping, caching
Stacks & Queues — Monotonic stack, BFS, parentheses matching
Heaps (Priority Queues) — Top-K, median, merge K sorted lists
Linked Lists — Reversal, cycle detection, merge
Greedy — Interval scheduling, minimum operations
Tries — Autocomplete, word search, longest prefix
Union-Find — Connected components, cycle detection

Senior-level expectations:

Identify the pattern within 2-3 minutes
Discuss time/space complexity BEFORE coding
Write clean, idiomatic Kotlin (not Java translated to Kotlin)
Handle edge cases without prompting
Optimize from brute force to optimal proactively

Problem-solving framework:

1. Understand — Restate the problem, ask clarifying questions
2. Plan — Identify pattern, discuss approach, state complexity
3. Code — Write clean solution with good variable names
4. Test — Walk through 2 examples + 1 edge case
5. Optimize — If not optimal, discuss how to improve

💻 Code Example

codeTap to expand ⛶

1// Google-frequency coding patterns in Kotlin
2
3// 1. Sliding Window — Max sum of subarray of size K
4fun maxSumSubarray(arr: IntArray, k: Int): Int {
5    var windowSum = arr.slice(0 until k).sum()
6    var maxSum = windowSum
7    for (i in k until arr.size) {
8        windowSum += arr[i] - arr[i - k]
9        maxSum = maxOf(maxSum, windowSum)
10    }
11    return maxSum
12}
13
14// 2. Two Pointers — Container with most water
15fun maxArea(height: IntArray): Int {
16    var left = 0
17    var right = height.lastIndex
18    var maxWater = 0
19    while (left < right) {
20        val water = minOf(height[left], height[right]) * (right - left)
21        maxWater = maxOf(maxWater, water)
22        if (height[left] < height[right]) left++ else right--
23    }
24    return maxWater
25}
26
27// 3. BFS — Shortest path in unweighted graph
28fun shortestPath(graph: Map<Int, List<Int>>, start: Int, end: Int): Int {
29    val queue: Queue<Pair<Int, Int>> = LinkedList()
30    val visited = mutableSetOf(start)
31    queue.add(start to 0)
32    while (queue.isNotEmpty()) {
33        val (node, dist) = queue.poll()
34        if (node == end) return dist
35        for (neighbor in graph[node] ?: emptyList()) {
36            if (neighbor !in visited) {
37                visited.add(neighbor)
38                queue.add(neighbor to dist + 1)
39            }
40        }
41    }
42    return -1
43}
44
45// 4. Dynamic Programming — Longest Increasing Subsequence
46fun lengthOfLIS(nums: IntArray): Int {
47    // Patience sorting — O(n log n)
48    val tails = mutableListOf<Int>()
49    for (num in nums) {
50        val pos = tails.binarySearch(num).let { if (it < 0) -(it + 1) else it }
51        if (pos == tails.size) tails.add(num) else tails[pos] = num
52    }
53    return tails.size
54}
55
56// 5. Monotonic Stack — Next greater element
57fun nextGreaterElements(nums: IntArray): IntArray {
58    val result = IntArray(nums.size) { -1 }
59    val stack = ArrayDeque<Int>() // indices
60    for (i in nums.indices) {
61        while (stack.isNotEmpty() && nums[stack.last()] < nums[i]) {
62            result[stack.removeLast()] = nums[i]
63        }
64        stack.addLast(i)
65    }
66    return result
67}

🏋️ Practice Exercise

50 Must-Practice Problems for Google:

Arrays & Strings (10):

Two Sum (Easy) — HashMap
Best Time to Buy/Sell Stock (Easy) — Kadane's
Container With Most Water (Medium) — Two pointers
3Sum (Medium) — Sort + two pointers
Minimum Window Substring (Hard) — Sliding window
Longest Substring Without Repeating (Medium) — Sliding window
Product of Array Except Self (Medium) — Prefix/suffix
Merge Intervals (Medium) — Sort + greedy
Trapping Rain Water (Hard) — Two pointers
Longest Consecutive Sequence (Medium) — HashSet

Trees & Graphs (10): 11. Binary Tree Level Order Traversal (Medium) — BFS 12. Validate BST (Medium) — Inorder 13. Lowest Common Ancestor (Medium) — Recursion 14. Serialize/Deserialize Binary Tree (Hard) — BFS/preorder 15. Number of Islands (Medium) — BFS/DFS 16. Course Schedule (Medium) — Topological sort 17. Word Ladder (Hard) — BFS 18. Clone Graph (Medium) — BFS + HashMap 19. Alien Dictionary (Hard) — Topological sort 20. Binary Tree Max Path Sum (Hard) — DFS

Dynamic Programming (10): 21. Climbing Stairs (Easy) — Fibonacci pattern 22. Coin Change (Medium) — Bottom-up DP 23. Longest Increasing Subsequence (Medium) — Patience sorting 24. Word Break (Medium) — DP + Trie 25. Edit Distance (Medium) — 2D DP 26. Unique Paths (Medium) — 2D DP 27. House Robber (Medium) — Linear DP 28. Decode Ways (Medium) — Linear DP 29. Partition Equal Subset Sum (Medium) — 0/1 Knapsack 30. Regular Expression Matching (Hard) — 2D DP

Remaining (20): LRU Cache, Merge K Sorted Lists, Design Hit Counter, Implement Trie, Find Median from Data Stream, Task Scheduler, Min Stack, Valid Parentheses, Daily Temperatures, Top K Frequent Elements, Kth Largest Element, Meeting Rooms II, Number of Connected Components, Redundant Connection, Design Twitter, Max Frequency Stack, Sliding Window Maximum, Palindrome Partitioning, Word Search II, Accounts Merge

⚠️ Common Mistakes

Jumping into coding without discussing the approach — Google evaluates your thought process, not just the answer
Not considering all edge cases — empty input, single element, all duplicates, overflow
Writing verbose Java-style Kotlin — use Kotlin idioms (let, apply, destructuring, extension functions)
Not optimizing proactively — if you write O(n²), immediately discuss how to reach O(n) or O(n log n)
Forgetting to test your code — walk through at least 2 examples after writing

💼 Interview Questions

🎤 Mock Interview

Mock interview is powered by AI for Senior-Level DSA Topics for Google. Login to unlock this feature.

Was this topic helpful?

← PreviousCI/CD Strategies for Android Next →Pattern Recognition & Problem-Solving Strategy