Autocoder

Google Coding Round Questions with Solutions in Python and Java

Last updated 2026-11-19

Google's coding interviews reward a clear approach, correct code and honest complexity analysis. These ten problems cover graph search, intervals, binary search, sliding windows and dynamic programming, with the reasoning you would say aloud.

Solve each one yourself first, then compare. Both Python and Java solutions are given and have been written to compile and run as shown.

Problems10, easy to hard
LanguagesPython and Java
Core topicsGraphs, intervals, binary search, DP, sliding window
Format Google describesLive coding in a shared document

Style of Google coding questions

Google's public guidance says interviews are live, in a shared document, and that reasoning is valued as much as the answer. The problems below lean on the topics Google lists (trees, hash tables, stacks, arrays, linked lists, priority queues) plus graph search, binary search variants and dynamic programming that medium and hard follow-ups often reach for.

These are practice problems in that style, not a record of any real paper. For the interview conversation itself see Google interview questions.

Habits that carry across all ten problems

Hiring status

For current Google roles and dates, see Google hiring, and apply only through Google's own careers site at google.com/about/careers/applications. Google has said its interviews run virtually or in person depending on role, and that using AI during its virtual interviews leads to disqualification.

Google Coding Round Questions with Solutions in Python and Java: questions with worked answers

  1. 1

    Number of Islands: count connected groups of '1' in a grid.

    medium

    Scan every cell; when you find an unvisited land cell, increment the count and flood-fill its component so it is never counted again. Use an explicit stack to avoid recursion limits on large grids. Time O(rows x cols), space O(rows x cols) worst case. Common mistakes: forgetting to mark cells visited before pushing (causing duplicates), and moving diagonally.

    python
    def num_islands(g):
        if not g: return 0
        R, C, n = len(g), len(g[0]), 0
        for i in range(R):
            for j in range(C):
                if g[i][j] == '1':
                    n += 1
                    g[i][j] = '0'
                    st = [(i, j)]
                    while st:
                        x, y = st.pop()
                        for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
                            a, b = x+dx, y+dy
                            if 0 <= a < R and 0 <= b < C and g[a][b] == '1':
                                g[a][b] = '0'
                                st.append((a, b))
        return n
    java
    import java.util.*;
    class Solution {
        int numIslands(char[][] g) {
            int R = g.length, C = R == 0 ? 0 : g[0].length, n = 0;
            int[][] d = {{1,0},{-1,0},{0,1},{0,-1}};
            for (int i = 0; i < R; i++)
                for (int j = 0; j < C; j++)
                    if (g[i][j] == '1') {
                        n++; g[i][j] = '0';
                        Deque<int[]> st = new ArrayDeque<>();
                        st.push(new int[]{i, j});
                        while (!st.isEmpty()) {
                            int[] p = st.pop();
                            for (int[] v : d) {
                                int a = p[0] + v[0], b = p[1] + v[1];
                                if (a >= 0 && a < R && b >= 0 && b < C && g[a][b] == '1') {
                                    g[a][b] = '0'; st.push(new int[]{a, b});
                                }
                            }
                        }
                    }
            return n;
        }
    }
  2. 2

    Word Ladder: shortest transformation length from beginWord to endWord, changing one letter at a time through a word list.

    hard

    Model words as graph nodes and run BFS from beginWord, since you need the minimum number of steps. For each word, try replacing each position with a to z and check membership in a set of the word list; remove words from the set when visited. Time O(N x L x 26) for N words of length L. Return 0 if endWord is not in the list. A common mistake is DFS, which does not give the shortest path, or comparing every pair of words, which is O(N squared x L).

    python
    from collections import deque
    def ladder(begin, end, words):
        ws = set(words)
        if end not in ws: return 0
        q, steps = deque([begin]), 1
        while q:
            for _ in range(len(q)):
                w = q.popleft()
                if w == end: return steps
                for i in range(len(w)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        nw = w[:i] + c + w[i+1:]
                        if nw in ws:
                            ws.remove(nw)
                            q.append(nw)
            steps += 1
        return 0
    java
    import java.util.*;
    class Solution {
        int ladder(String begin, String end, List<String> words) {
            Set<String> ws = new HashSet<>(words);
            if (!ws.contains(end)) return 0;
            Deque<String> q = new ArrayDeque<>();
            q.add(begin);
            int steps = 1;
            while (!q.isEmpty()) {
                for (int s = q.size(); s > 0; s--) {
                    String w = q.poll();
                    if (w.equals(end)) return steps;
                    char[] a = w.toCharArray();
                    for (int i = 0; i < a.length; i++) {
                        char o = a[i];
                        for (char c = 'a'; c <= 'z'; c++) {
                            a[i] = c;
                            String nw = new String(a);
                            if (ws.remove(nw)) q.add(nw);
                        }
                        a[i] = o;
                    }
                }
                steps++;
            }
            return 0;
        }
    }
  3. 3

    Merge Intervals: merge all overlapping intervals.

    medium

    Sort by start, then sweep: if the next interval starts at or before the end of the last merged one, extend the end with max(); otherwise start a new interval. Time O(n log n) for sorting, space O(n) for output. Mistakes: not sorting first, using the new end instead of the maximum when one interval contains another, and deciding touching intervals like [1,2],[2,3] incorrectly. Confirm with the interviewer that touching intervals merge.

    python
    def merge(iv):
        iv.sort()
        out = []
        for s, e in iv:
            if out and s <= out[-1][1]:
                out[-1][1] = max(out[-1][1], e)
            else:
                out.append([s, e])
        return out
    java
    import java.util.*;
    class Solution {
        int[][] merge(int[][] iv) {
            Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0]));
            List<int[]> out = new ArrayList<>();
            for (int[] x : iv) {
                if (!out.isEmpty() && x[0] <= out.get(out.size() - 1)[1])
                    out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], x[1]);
                else out.add(new int[]{x[0], x[1]});
            }
            return out.toArray(new int[0][]);
        }
    }
  4. 4

    Course Schedule: can all courses be finished given prerequisite pairs?

    medium

    This is cycle detection in a directed graph. Use Kahn's topological sort: compute in-degrees, queue every course with in-degree zero, and repeatedly remove one and decrease its neighbours. If you process all courses there is no cycle. Time O(V + E), space O(V + E). Mistake: building the edge in the wrong direction. For pair [a, b] (take b before a) the edge is b to a. See also graph interview questions.

    python
    from collections import deque
    def can_finish(n, pre):
        adj = [[] for _ in range(n)]
        deg = [0]*n
        for a, b in pre:
            adj[b].append(a)
            deg[a] += 1
        q = deque(i for i in range(n) if deg[i] == 0)
        done = 0
        while q:
            u = q.popleft(); done += 1
            for v in adj[u]:
                deg[v] -= 1
                if deg[v] == 0: q.append(v)
        return done == n
    java
    import java.util.*;
    class Solution {
        boolean canFinish(int n, int[][] pre) {
            List<List<Integer>> adj = new ArrayList<>();
            for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
            int[] deg = new int[n];
            for (int[] p : pre) { adj.get(p[1]).add(p[0]); deg[p[0]]++; }
            Deque<Integer> q = new ArrayDeque<>();
            for (int i = 0; i < n; i++) if (deg[i] == 0) q.add(i);
            int done = 0;
            while (!q.isEmpty()) {
                int u = q.poll(); done++;
                for (int v : adj.get(u)) if (--deg[v] == 0) q.add(v);
            }
            return done == n;
        }
    }
  5. 5

    Longest Increasing Subsequence in O(n log n).

    hard

    Keep an array tails where tails[i] is the smallest possible tail of an increasing subsequence of length i+1. For each number, binary-search the first tail that is greater than or equal to it and replace it, or append if none. The array length is the answer. Time O(n log n), space O(n). Note tails is not itself a valid subsequence. Using bisect_left (not right) is what makes the subsequence strictly increasing. Start from the O(n squared) DP and then optimise.

    python
    from bisect import bisect_left
    def lis(nums):
        tails = []
        for x in nums:
            i = bisect_left(tails, x)
            if i == len(tails): tails.append(x)
            else: tails[i] = x
        return len(tails)
    java
    class Solution {
        int lis(int[] nums) {
            int[] t = new int[nums.length];
            int len = 0;
            for (int x : nums) {
                int lo = 0, hi = len;
                while (lo < hi) {
                    int m = (lo + hi) >>> 1;
                    if (t[m] < x) lo = m + 1; else hi = m;
                }
                t[lo] = x;
                if (lo == len) len++;
            }
            return len;
        }
    }
  6. 6

    Trapping Rain Water: total water held between bars of given heights.

    hard

    Use two pointers with running maxima. Water above a bar equals min(left max, right max) minus its height. Move the pointer on the side with the smaller maximum, because that side's water level is fixed by its own maximum. Time O(n), space O(1). A prefix and suffix max array also works in O(n) space. Mistakes: moving the wrong pointer, or forgetting that bars on the smaller side are bounded by that side's max only.

    python
    def trap(h):
        l, r = 0, len(h) - 1
        lm = rm = water = 0
        while l < r:
            if h[l] < h[r]:
                lm = max(lm, h[l]); water += lm - h[l]; l += 1
            else:
                rm = max(rm, h[r]); water += rm - h[r]; r -= 1
        return water
    java
    class Solution {
        int trap(int[] h) {
            int l = 0, r = h.length - 1, lm = 0, rm = 0, w = 0;
            while (l < r) {
                if (h[l] < h[r]) { lm = Math.max(lm, h[l]); w += lm - h[l]; l++; }
                else { rm = Math.max(rm, h[r]); w += rm - h[r]; r--; }
            }
            return w;
        }
    }
  7. 7

    Serialize and Deserialize a binary tree.

    hard

    Use preorder with an explicit marker for null children, so the structure is unambiguous from one traversal. Serialise to tokens joined by commas; deserialise by consuming tokens in order and building recursively. Time and space O(n). Mistakes: omitting null markers (several trees share the same preorder), and splitting on a delimiter that can appear in values. Level-order works equally well.

    python
    def serialize(root):
        out = []
        def go(n):
            if not n: out.append('#'); return
            out.append(str(n.val)); go(n.left); go(n.right)
        go(root)
        return ','.join(out)
    
    def deserialize(s):
        it = iter(s.split(','))
        def build():
            t = next(it)
            if t == '#': return None
            n = TreeNode(int(t)); n.left = build(); n.right = build()
            return n
        return build()
    java
    import java.util.*;
    class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }
    class Codec {
        String serialize(TreeNode r) { StringBuilder sb = new StringBuilder(); go(r, sb); return sb.toString(); }
        private void go(TreeNode n, StringBuilder sb) {
            if (n == null) { sb.append("#,"); return; }
            sb.append(n.val).append(','); go(n.left, sb); go(n.right, sb);
        }
        TreeNode deserialize(String s) { return build(new ArrayDeque<>(Arrays.asList(s.split(",")))); }
        private TreeNode build(Deque<String> q) {
            String t = q.poll();
            if (t.equals("#")) return null;
            TreeNode n = new TreeNode(Integer.parseInt(t));
            n.left = build(q); n.right = build(q);
            return n;
        }
    }
  8. 8

    Search in Rotated Sorted Array (distinct values).

    medium

    At each step of binary search, at least one half is sorted. Compare nums[lo] with nums[mid] to find which, then check whether the target lies in that sorted half and discard the other. Time O(log n), space O(1). Mistakes: using strict comparison where lo equals mid (use <=), and checking the target against the wrong boundary. Duplicates break the argument and degrade the worst case to O(n).

    python
    def search(a, t):
        lo, hi = 0, len(a) - 1
        while lo <= hi:
            m = (lo + hi) // 2
            if a[m] == t: return m
            if a[lo] <= a[m]:
                if a[lo] <= t < a[m]: hi = m - 1
                else: lo = m + 1
            else:
                if a[m] < t <= a[hi]: lo = m + 1
                else: hi = m - 1
        return -1
    java
    class Solution {
        int search(int[] a, int t) {
            int lo = 0, hi = a.length - 1;
            while (lo <= hi) {
                int m = (lo + hi) >>> 1;
                if (a[m] == t) return m;
                if (a[lo] <= a[m]) {
                    if (a[lo] <= t && t < a[m]) hi = m - 1; else lo = m + 1;
                } else {
                    if (a[m] < t && t <= a[hi]) lo = m + 1; else hi = m - 1;
                }
            }
            return -1;
        }
    }
  9. 9

    Decode Ways: count ways to decode a digit string where 1 to 26 map to A to Z.

    medium

    A one-dimensional DP: ways[i] is the number of decodings of the first i characters. Add ways[i-1] if the single digit is not 0, and add ways[i-2] if the two-digit number is between 10 and 26. Only the last two values are needed, so space is O(1), time O(n). Mistakes: treating '0' as valid on its own, and accepting '06' as a two-digit code. See dynamic programming interview questions.

    python
    def num_decodings(s):
        prev2, prev1 = 1, 1 if s and s[0] != '0' else 0
        if not s: return 0
        for i in range(1, len(s)):
            cur = 0
            if s[i] != '0': cur += prev1
            if 10 <= int(s[i-1:i+1]) <= 26: cur += prev2
            prev2, prev1 = prev1, cur
        return prev1
    java
    class Solution {
        int numDecodings(String s) {
            if (s.isEmpty()) return 0;
            int p2 = 1, p1 = s.charAt(0) != '0' ? 1 : 0;
            for (int i = 1; i < s.length(); i++) {
                int cur = 0;
                if (s.charAt(i) != '0') cur += p1;
                int two = Integer.parseInt(s.substring(i - 1, i + 1));
                if (two >= 10 && two <= 26) cur += p2;
                p2 = p1; p1 = cur;
            }
            return p1;
        }
    }
  10. 10

    Top K Frequent Elements in better than O(n log n).

    medium

    Count with a hash map, then use bucket sort: index buckets by frequency (at most n), place each value in its frequency bucket, and read from the highest bucket down until you have k values. Time O(n), space O(n). A min-heap of size k gives O(n log k) and is the usual alternative to mention. Mistake: sorting all distinct values, which is O(n log n) when the question asks for better.

    python
    from collections import Counter
    def top_k(nums, k):
        cnt = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]
        for v, c in cnt.items(): buckets[c].append(v)
        out = []
        for c in range(len(nums), 0, -1):
            for v in buckets[c]:
                out.append(v)
                if len(out) == k: return out
        return out
    java
    import java.util.*;
    class Solution {
        int[] topK(int[] nums, int k) {
            Map<Integer, Integer> cnt = new HashMap<>();
            for (int x : nums) cnt.merge(x, 1, Integer::sum);
            List<Integer>[] b = new List[nums.length + 1];
            for (var e : cnt.entrySet()) {
                if (b[e.getValue()] == null) b[e.getValue()] = new ArrayList<>();
                b[e.getValue()].add(e.getKey());
            }
            int[] out = new int[k]; int i = 0;
            for (int c = nums.length; c > 0 && i < k; c--)
                if (b[c] != null) for (int v : b[c]) if (i < k) out[i++] = v;
            return out;
        }
    }
  11. 11

    Minimum Window Substring: smallest window of s containing all characters of t.

    hard

    Sliding window with counts. Expand the right end, tracking how many required characters are satisfied; when all are, shrink from the left while still satisfied and record the best window. Each index enters and leaves once, so time is O(|s| + |t|). Mistakes: counting satisfied characters by distinct letters but decrementing on duplicates incorrectly, and returning a window when t has letters s lacks.

    python
    from collections import Counter
    def min_window(s, t):
        need, missing = Counter(t), len(t)
        best, l = (0, 0), 0
        for r, ch in enumerate(s, 1):
            if need[ch] > 0: missing -= 1
            need[ch] -= 1
            if missing == 0:
                while need[s[l]] < 0:
                    need[s[l]] += 1; l += 1
                if best == (0, 0) or r - l < best[1] - best[0]: best = (l, r)
                need[s[l]] += 1; missing += 1; l += 1
        return s[best[0]:best[1]]
    java
    class Solution {
        String minWindow(String s, String t) {
            int[] need = new int[128];
            for (char c : t.toCharArray()) need[c]++;
            int missing = t.length(), l = 0, bs = 0, be = 0;
            for (int r = 1; r <= s.length(); r++) {
                char c = s.charAt(r - 1);
                if (need[c]-- > 0) missing--;
                if (missing == 0) {
                    while (need[s.charAt(l)] < 0) need[s.charAt(l++)]++;
                    if (be == 0 || r - l < be - bs) { bs = l; be = r; }
                    need[s.charAt(l++)]++; missing++;
                }
            }
            return s.substring(bs, be);
        }
    }

Frequently asked questions

Which language should I use for the Google coding round?

Google's internship guide lets you choose a language such as C, C++, Go, Java, JavaScript or Python. Pick the one you can write fastest without mistakes.

How hard are Google coding problems?

Commonly reported as medium to hard, often with follow-ups that change constraints. Practise explaining trade-offs, not just reaching a working solution.

Should I memorise these solutions?

No. Learn the pattern behind each one, such as BFS for shortest steps or two pointers with running maxima, so you can adapt when the constraints change.

Where can I read about the whole Google process?

See how to crack the Google interview and the topic guide on the DSA coding round.

Sources

Related guides

More in Company Interview Questions

See all in this section