Katkat
Back

Solve three coding problems

GoogleSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

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).

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.
  1. 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.
  1. 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.