Airbnb·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Airbnb coding round, linked list problem that sounds manageable until you realize there are three separate cases to handle. Took me a bit to work through the cyclic-plus-cyclic scenario without fumbling.

Questions Asked (1)

Given two singly linked lists that may each independently contain a cycle, determine whether the two lists share any node in common.

Algorithms & Data Structures

Author's notes

I got the acyclic case pretty fast, tail comparison or the length-difference two-pointer thing.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, detect and locate the cycle entry point in each list using Floyd's cycle-finding algorithm. Then, if both lists have cycles, check if they share the same cycle by comparing the cycle entry nodes; if only one has a cycle, they cannot intersect; if neither has a cycle, find the intersection by aligning lengths or using two pointers.

Pro tip: Clarify with the interviewer whether the lists are allowed to have cycles and whether they share nodes by reference or value. Also, mention that if both have cycles, you can break the cycle temporarily to treat them as acyclic, but remember to restore it.

1. Detect cycles in each list

Use Floyd's tortoise and hare algorithm to determine if each list contains a cycle. If a cycle exists, find the entry node of the cycle.

2. Analyze cycle presence

If exactly one list has a cycle, they cannot intersect. If neither has a cycle, proceed to step 3. If both have cycles, proceed to step 4.

3. Find intersection for acyclic lists

Compute the lengths of both lists, advance the pointer of the longer list by the length difference, then move both pointers in tandem until they meet or reach the end.

4. Check intersection for cyclic lists

If both lists have cycles, check if they share the same cycle by comparing the cycle entry nodes. If the entry nodes are the same, they intersect; otherwise, traverse one cycle to see if the other's entry node is reachable.

5. Return the intersection node

If an intersection is found, return the first common node. Otherwise, return null to indicate no intersection.

Key Points to Mention

Floyd's cycle detection algorithm (tortoise and hare) and how to find the cycle entry point.
Handling cases: both acyclic, one cyclic, both cyclic.
Time and space complexity: O(n) time, O(1) space.
Edge cases: empty lists, single-node lists, self-cycles.
Comparison by node reference, not value.
Potential follow-up: how to handle if the lists are immutable or if cycles cannot be broken.

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