← Google Interview Insights

Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Google SWE coding round with a graph/scheduling problem that looks deceptively simple until you realize the time-feasibility constraint changes everything. No behavioral stuff, just the one problem with a few test cases to work through.

Questions Asked (1)

Q1

Given a list of flights each with an origin, destination, departure time, and arrival time, determine whether a time-feasible itinerary exists from a start airport to an end airport. A connection is only valid if the next flight departs no earlier than the previous flight's arrival time.

Algorithms & Data StructuresSystem Design
Author's notes

My first instinct was BFS and I went with it, but the tricky part is that the same airport can be visited at different times and you can't just track visited nodes like a normal graph problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the flights as a directed graph where each flight is a node, and add edges between flights if the destination of one matches the origin of the next and the departure time of the next is >= the arrival time of the previous. Then perform a search (BFS/DFS) from all flights departing the start airport to see if any flight arriving at the end airport is reachable. Alternatively, sort flights by departure time and use dynamic programming or a priority queue to track reachable airports over time.

Pro tip: Clarify edge cases upfront: what if start equals end? Are there multiple flights with same route but different times? Also, mention that the graph can be built in O(E^2) naively but can be optimized to O(E log E) by sorting flights by departure time and using binary search or a sweep line.

1. Clarify requirements and edge cases

Ask about input size, whether times are in a consistent format, if multiple flights can have the same origin/destination, and if start and end can be the same. Confirm that connections require departure >= arrival.

2. Model as a graph problem

Represent each flight as a node. Add a directed edge from flight A to flight B if A.destination == B.origin and B.departure >= A.arrival. Also consider adding a virtual start node connected to all flights from the start airport, and a virtual end node from all flights to the end airport.

3. Choose an efficient search strategy

Use BFS/DFS from the start node to see if the end node is reachable. For large inputs, sort flights by departure time and use a priority queue (Dijkstra-like) to track the earliest arrival time at each airport, or use dynamic programming over sorted flights.

4. Analyze time and space complexity

Naive graph construction is O(E^2) time and space. Optimize by sorting flights by departure time and using binary search to find valid connections, reducing to O(E log E). Space can be O(E) for the graph or O(A) for airport-based DP.

5. Test with examples and edge cases

Walk through a simple example, then test cases like no flights, start unreachable, cycles, and multiple paths. Verify that the algorithm correctly handles time constraints.

Key Points to Mention

  • Graph modeling: flights as nodes, edges for valid connections, virtual start/end nodes.
  • Time constraint: departure >= arrival for connections.
  • Search algorithm: BFS/DFS for reachability, or Dijkstra/DP for earliest arrival.
  • Optimization: sorting flights by departure time and binary search to avoid O(E^2) edges.
  • Complexity analysis: O(E log E) time with sorting, O(E) space.
  • Edge cases: start == end, no flights, multiple flights same route, time zones (if applicable).

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