← Upstart Interview Insights

Upstart·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Had a technical phone screen for a software engineer role at Upstart. One algorithmic problem, fairly well-defined but with a sneaky constraint that makes it less obvious than it looks at first glance.

Questions Asked (1)

Q1

You're given a list of cities and their longitudes. Traveling west to east, find the maximum number of cities you can visit such that each subsequent city is both further east (higher longitude) and lexicographically greater in name than the previous one.

Algorithms & Data Structures
Author's notes

The longitude constraint alone would just be longest increasing subsequence, which I spotted pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as a 2D longest increasing subsequence (LIS) problem where each city is a point (longitude, name). Sort cities by longitude, then find the longest strictly increasing subsequence of names using an O(n log n) patience sorting approach with binary search on the tails array.

Pro tip: Clarify whether 'lexicographically greater' uses standard string comparison (e.g., 'apple' < 'banana') and whether case matters; also confirm if longitudes are unique, as duplicates would require careful handling to avoid invalid sequences.

1. Clarify the problem

Restate the problem in your own words and ask clarifying questions about lexicographic order, case sensitivity, and duplicate longitudes.

2. Model as 2D LIS

Explain that each city is a point (longitude, name) and we need the longest chain where both coordinates strictly increase.

3. Sort by longitude

Sort the cities by longitude ascending. If longitudes can be equal, handle ties by sorting names descending to prevent invalid sequences in the LIS step.

4. Apply LIS on names

Use the O(n log n) patience sorting algorithm: maintain a tails array and for each name, binary search for the first tail >= name and replace it, or append if none.

5. Return the length

The size of the tails array is the maximum number of cities visitable. Optionally, reconstruct the sequence if needed.

Key Points to Mention

  • This is a 2D longest increasing subsequence (LIS) problem.
  • Sorting by longitude reduces it to a 1D LIS on names.
  • Use patience sorting with binary search for O(n log n) time.
  • Handle duplicate longitudes by sorting names in descending order for ties.
  • Lexicographic comparison uses standard string ordering (e.g., 'apple' < 'banana').
  • Edge cases: empty list, all cities same longitude, names with different cases.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.