Meta·Software Engineer·Technical Phone Screen·Senior

Senior

Apr 2026

Summary

Coding screen for a Research Scientist role at Meta. One algorithmic problem, graph-based, cleaner than expected once you see the structure.

Questions Asked (1)

You have a list of photo pairs where each pair records two consecutively visited locations, but the order within each pair is unknown. Reconstruct the full trip as an ordered path of locations, given that every location was visited exactly once and the trip is not a cycle.

Algorithms & Data Structures

Author's notes

Took me a minute to see it as a graph problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph where each location is a node and each photo pair is an undirected edge. The trip corresponds to a Hamiltonian path in this graph, which can be found by identifying the two endpoints (nodes with degree 1) and then traversing the path using DFS or by reconstructing the sequence from the edges.

Pro tip: Clarify that the graph is a simple path (each node degree ≤ 2) and that the endpoints are the only nodes with degree 1; this simplifies the solution and avoids unnecessary complexity.

1. Understand the problem

Restate the problem: given unordered pairs of consecutive locations, reconstruct the unique ordered path where each location appears exactly once and the path is not a cycle.

2. Model as a graph

Treat each location as a node and each pair as an undirected edge. The trip is a Hamiltonian path in this graph.

3. Identify endpoints

Count the degree of each node. The two nodes with degree 1 are the start and end of the trip; all others should have degree 2.

4. Reconstruct the path

Start from one endpoint and follow edges to the next unvisited node until all nodes are visited. Alternatively, use DFS to find the Hamiltonian path.

5. Validate and handle edge cases

Check that the path includes all locations exactly once and that no cycles exist. Discuss handling of invalid inputs or multiple components.

Key Points to Mention

Graph representation: nodes as locations, edges as photo pairs.
Degree analysis: endpoints have degree 1, internal nodes degree 2.
Hamiltonian path: the trip is a Hamiltonian path in the graph.
Algorithm choice: DFS or iterative traversal from an endpoint.
Time and space complexity: O(N) time and space with N locations.
Edge cases: empty input, single pair, disconnected graph, cycle detection.

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