google logo
Google· SWE Intern

Google SWE Intern 2026 OA questions

Posted
5 Jul 2025
515 reads

Summary

This post details the two algorithmic problems encountered during my Google SWE Intern 2026 Online Assessment.

How it went

Problem 1: You have an array A of length n, where each element is either 1, 2 or 3. You will be given q queries. In the i‑th query you’re given two integers x and y:

x (1 ≤ x ≤ n): the index in the array to update

y ∈ {1, 2, 3}: the new value to assign

After performing the update A[x] ← y, you must compute and print the minimum number of swaps (each swap exchanges two elements at arbitrary positions) required to sort the entire array in non‑decreasing order. Constraint 1 <= n <= 1e5 1 <= q <= 1e5 A[i]∈ {1, 2, 3} Problem 2:

You’re given an integer array A of length n. A subsequence is any sequence you get by deleting zero or more elements (without reordering). We want to count how many subsequences of A satisfy both of these parity‑run constraints:

No three evens in a row: You never pick three consecutive elements in your subsequence that are all even numbers.

No three odds in a row: You never pick three consecutive elements in your subsequence that are all odd numbers.

Compute the total number of non‑empty valid subsequences.

Constraint 1 <= n <= 1e5 1 <= A[i] <= 1e9

Questions asked (2)

  1. 01

    Minimum Swaps to Sort Array of 1s, 2s, 3s After Updates

    Data Structures & Algorithms

    You have an array A of length n, where each element is either 1, 2 or 3. You will be given q queries. In the i‑th query you’re given two integers x and y:

    x (1 ≤ x ≤ n): the index in the array to update

    y ∈ {1, 2, 3}: the new value to assign

    After performing the update A[x] ← y, you must compute and print the minimum number of swaps (each swap exchanges two elements at arbitrary positions) required to sort the entire array in non‑decreasing order. Constraint 1 <= n <= 1e5 1 <= q <= 1e5 A[i]∈ {1, 2, 3}

  2. 02

    Count Valid Subsequences with Parity-Run Constraints

    Data Structures & Algorithms

    You’re given an integer array A of length n. A subsequence is any sequence you get by deleting zero or more elements (without reordering). We want to count how many subsequences of A satisfy both of these parity‑run constraints:

    No three evens in a row: You never pick three consecutive elements in your subsequence that are all even numbers.

    No three odds in a row: You never pick three consecutive elements in your subsequence that are all odd numbers.

    Compute the total number of non‑empty valid subsequences.

    Constraint 1 <= n <= 1e5 1 <= A[i] <= 1e9

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!