How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Solve three coding problems | Google Coding Question

Quick Overview

This set of problems evaluates algorithmic problem-solving across combinatorics and enumeration (finding the N-th lexicographic license plate), constrained geometric and graph traversal reasoning (counting Android-style 3x3 unlock patterns), and interval-processing algorithms (computing intersections of sorted, non-overlapping intervals) within the domain of algorithms and data structures. These questions are commonly asked because they reveal ability to reason about discrete enumeration, constraint handling, and efficient time/space implementations for edge-case-heavy inputs, and the level of abstraction spans both conceptual understanding (combinatorial and geometric constraints) and practical application (efficient algorithm and data-structure implementation).

Solve three coding problems

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

The interview note described the following coding questions: 1. **Find the N-th license plate in lexicographic order** - A license plate has exactly 6 characters: the first 3 are uppercase letters `A-Z`, and the last 3 are digits `0-9`. - Example format: `AAA000`. - Consider all valid license plates sorted in lexicographic order as strings. - Given an integer `N` (1-indexed), return the `N`-th license plate. 2. **Count Android-style 3x3 unlock patterns** - You have a 3x3 grid of dots, like the standard Android lock screen. - A valid pattern is a sequence of distinct dots. - Moving from one dot to another is allowed unless the straight line between them passes through another dot that has not been visited yet. - Count the total number of valid unlock patterns that use between 4 and 9 dots, inclusive. 3. **Return intersections of two interval lists** - You are given two lists of closed intervals. - Within each list, intervals are sorted by start time and do not overlap with each other. - Return all intervals where the two lists overlap.

Quick Answer: This set of problems evaluates algorithmic problem-solving across combinatorics and enumeration (finding the N-th lexicographic license plate), constrained geometric and graph traversal reasoning (counting Android-style 3x3 unlock patterns), and interval-processing algorithms (computing intersections of sorted, non-overlapping intervals) within the domain of algorithms and data structures. These questions are commonly asked because they reveal ability to reason about discrete enumeration, constraint handling, and efficient time/space implementations for edge-case-heavy inputs, and the level of abstraction spans both conceptual understanding (combinatorial and geometric constraints) and practical application (efficient algorithm and data-structure implementation).

Part 1: Find the N-th license plate in lexicographic order

A valid license plate has exactly 6 characters. The first 3 characters are uppercase letters from A to Z, and the last 3 characters are digits from 0 to 9. Examples include AAA000 and BCD123. Consider all valid license plates sorted in lexicographic order as strings. Given a 1-indexed integer n, return the n-th license plate.

Constraints

1 <= n <= 17_576_000
Each plate has the fixed format LLLDDD, where L is A-Z and D is 0-9.

Examples

Input: (1,)

Expected Output: "AAA000"

Explanation: The first plate is the smallest possible one.

Input: (1000,)

Expected Output: "AAA999"

Explanation: The first 1000 plates all begin with AAA, from AAA000 through AAA999.

Input: (1001,)

Expected Output: "AAB000"

Explanation: After AAA999, the next lexicographic plate is AAB000.

Input: (17576000,)

Expected Output: "ZZZ999"

Explanation: This is the last possible valid plate.

Hints

There are exactly 1000 possible numeric suffixes for each 3-letter prefix.
Use n - 1 to get a zero-based index, then split it into a letter-part index and a digit-part index.

Part 2: Count Android-style 3x3 unlock patterns

On a standard 3x3 Android unlock screen, a pattern is a sequence of distinct dots. A move from one dot to another is allowed unless the straight line between them passes through a middle dot that has not been visited yet. For example, moving from 1 to 3 requires 2 to have already been visited. Given min_length and max_length, count how many valid patterns use between min_length and max_length dots, inclusive. The original interview question is the special case min_length = 4 and max_length = 9.

Constraints

1 <= min_length <= max_length <= 9
Each dot may be used at most once in a pattern.

Examples

Input: (1, 1)

Expected Output: 9

Explanation: Each single dot is a valid pattern, so there are 9 patterns.

Input: (2, 2)

Expected Output: 56

Explanation: This counts only patterns of exact length 2.

Input: (1, 2)

Expected Output: 65

Explanation: There are 9 patterns of length 1 and 56 of length 2.

Input: (4, 9)

Expected Output: 389112

Explanation: This is the total requested by the original interview question.

Input: (9, 9)

Expected Output: 140704

Explanation: This counts only patterns that visit all 9 dots exactly once.

Hints

Some moves require an intermediate dot: for example 1 -> 3 needs 2, 1 -> 9 needs 5, and 7 -> 9 needs 8.
The grid has symmetry: all 4 corners behave the same, all 4 edge-centers behave the same, and the center is unique.

Part 3: Return intersections of two interval lists

You are given two lists of closed intervals. Within each list, intervals are sorted by start time and do not overlap with each other. Return every interval where the two lists intersect. Because the intervals are closed, touching at an endpoint counts as an intersection.

Constraints

0 <= len(first_list), len(second_list) <= 100000
0 <= start <= end <= 10^9
Within each input list, intervals are sorted by start and do not overlap.

Examples

Input: ([[0, 2], [5, 10], [13, 23], [24, 25]], [[1, 5], [8, 12], [15, 24], [25, 26]])

Expected Output: [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]

Explanation: This example contains several overlapping ranges, including point intersections like [5, 5].

Input: ([], [[1, 3]])

Expected Output: []

Explanation: If either list is empty, there are no intersections.

Input: ([[1, 2], [5, 7]], [[2, 3], [7, 9]])

Expected Output: [[2, 2], [7, 7]]

Explanation: Because the intervals are closed, touching at 2 and 7 counts.

Input: ([[1, 7]], [[3, 5]])

Expected Output: [[3, 5]]

Explanation: One interval can be fully contained inside another.

Input: ([[1, 2], [5, 6]], [[3, 4], [7, 8]])

Expected Output: []

Explanation: Disjoint interval lists produce no overlaps.

Hints

If two current intervals overlap, the intersection is [max(start1, start2), min(end1, end2)].
After processing the current pair, move forward in the list whose current interval ends first.

Last updated: May 21, 2026

Loading coding console...

Quick Overview

Solve three coding problems

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

Part 1: Find the N-th license plate in lexicographic order

Constraints

1 <= n <= 17_576_000
Each plate has the fixed format LLLDDD, where L is A-Z and D is 0-9.

Examples

Input: (1,)

Expected Output: "AAA000"

Explanation: The first plate is the smallest possible one.

Input: (1000,)

Expected Output: "AAA999"

Explanation: The first 1000 plates all begin with AAA, from AAA000 through AAA999.

Input: (1001,)

Expected Output: "AAB000"

Explanation: After AAA999, the next lexicographic plate is AAB000.

Input: (17576000,)

Expected Output: "ZZZ999"

Explanation: This is the last possible valid plate.

Hints

There are exactly 1000 possible numeric suffixes for each 3-letter prefix.
Use n - 1 to get a zero-based index, then split it into a letter-part index and a digit-part index.

Part 2: Count Android-style 3x3 unlock patterns

Constraints

1 <= min_length <= max_length <= 9
Each dot may be used at most once in a pattern.

Examples

Input: (1, 1)

Expected Output: 9

Explanation: Each single dot is a valid pattern, so there are 9 patterns.

Input: (2, 2)

Expected Output: 56

Explanation: This counts only patterns of exact length 2.

Input: (1, 2)

Expected Output: 65

Explanation: There are 9 patterns of length 1 and 56 of length 2.

Input: (4, 9)

Expected Output: 389112

Explanation: This is the total requested by the original interview question.

Input: (9, 9)

Expected Output: 140704

Explanation: This counts only patterns that visit all 9 dots exactly once.

Hints

Some moves require an intermediate dot: for example 1 -> 3 needs 2, 1 -> 9 needs 5, and 7 -> 9 needs 8.
The grid has symmetry: all 4 corners behave the same, all 4 edge-centers behave the same, and the center is unique.

Part 3: Return intersections of two interval lists

Constraints

0 <= len(first_list), len(second_list) <= 100000
0 <= start <= end <= 10^9
Within each input list, intervals are sorted by start and do not overlap.

Examples

Input: ([[0, 2], [5, 10], [13, 23], [24, 25]], [[1, 5], [8, 12], [15, 24], [25, 26]])

Expected Output: [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]

Explanation: This example contains several overlapping ranges, including point intersections like [5, 5].

Input: ([], [[1, 3]])

Expected Output: []

Explanation: If either list is empty, there are no intersections.

Input: ([[1, 2], [5, 7]], [[2, 3], [7, 9]])

Expected Output: [[2, 2], [7, 7]]

Explanation: Because the intervals are closed, touching at 2 and 7 counts.

Input: ([[1, 7]], [[3, 5]])

Expected Output: [[3, 5]]

Explanation: One interval can be fully contained inside another.

Input: ([[1, 2], [5, 6]], [[3, 4], [7, 8]])

Expected Output: []

Explanation: Disjoint interval lists produce no overlaps.

Hints

If two current intervals overlap, the intersection is [max(start1, start2), min(end1, end2)].
After processing the current pair, move forward in the list whose current interval ends first.

Last updated: May 21, 2026

Loading coding console...