Google SWE Intern 2026 OA questions
Summary
This post details the two algorithmic problems encountered during my Google SWE Intern 2026 Online Assessment.
Full Experience
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
Interview Questions (2)
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}
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