Airbnb·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jul 2026

Summary

Two coding problems at Airbnb for a software engineer role. The linked list one was deceptively deep and the round-robin iterator felt more straightforward but had some gotchas around exhausted streams.

Questions Asked (2)

Given the heads of two singly linked lists that may each be acyclic or contain a cycle, determine whether the two lists share any node by reference. Follow up: return the actual shared node if one exists.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one wrecked me a little.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, detect and locate cycles in each list using Floyd's cycle-finding algorithm. Then, determine if the lists intersect by comparing the entry points of cycles or by aligning lengths if acyclic. Finally, find the first common node by advancing pointers appropriately.

Pro tip: Clarify upfront that 'shared node' means same node reference, not same value. Also, discuss edge cases like one list cyclic and the other acyclic, which cannot intersect.

1. Detect cycles and find cycle entry points

Use Floyd's tortoise and hare to detect if each list has a cycle. If a cycle exists, find the entry node by resetting one pointer to head and moving both at same speed.

2. Handle cases based on cycle presence

If one list has a cycle and the other doesn't, they cannot intersect. If both have cycles, check if they share the same cycle by comparing cycle entry points or traversing one cycle to see if the other's entry is present.

3. Find intersection for acyclic lists

If both lists are acyclic, compute their lengths, advance the pointer of the longer list by the length difference, then move both pointers until they meet or reach null.

4. Find intersection when both have cycles

If both have cycles and share the same cycle, treat the problem as finding the intersection of two acyclic lists ending at the cycle entry point. Compute lengths from heads to cycle entry, align, and find the first common node.

5. Return the shared node or null

If a common node is found, return it; otherwise, return null. Verify with edge cases like empty lists or single-node cycles.

Key Points to Mention

Floyd's cycle detection algorithm (tortoise and hare) for O(1) space complexity.
Difference between node value equality and node reference equality.
Handling of edge cases: one list cyclic, both cyclic but different cycles, no intersection.
Time complexity O(m+n) and space complexity O(1) for the optimal solution.
Trade-offs: using a hash set for O(m+n) space but simpler implementation.
Importance of clarifying assumptions with the interviewer before coding.

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

Implement a round-robin iterator that merges multiple input streams, cycling through them in order and skipping any stream that's been exhausted, without loading all data into memory upfront.

Algorithms & Data StructuresSystem Design

Author's notes

Cleaner than the first problem but the has_next idempotency requirement caught me.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the interface and constraints, then design an iterator that maintains a list of active stream iterators and an index for the next stream to read. On each next() call, attempt to read from the current stream; if exhausted, remove it and move to the next, cycling until a value is found or all streams are exhausted.

Pro tip: Discuss how to handle edge cases like empty streams, duplicate values, and thread safety, and mention that the iterator should be lazy to avoid loading all data into memory.

1. Clarify requirements and constraints

Ask about the stream interface (e.g., hasNext/next), whether streams can be added dynamically, and if thread safety is required. Confirm that memory usage should be O(k) where k is the number of streams.

2. Design the data structures

Use a list of iterators for the streams and an index to track the current position. Optionally, use a queue to efficiently skip exhausted streams.

3. Implement the next() method

Loop through the streams starting from the current index, skipping exhausted ones. When a value is found, advance the index for the next call and return the value. If all streams are exhausted, throw an exception or return a sentinel.

4. Implement hasNext() and handle edge cases

Ensure hasNext() correctly checks if any stream has remaining elements without consuming them. Handle cases like empty input list, all streams empty, and streams that become exhausted during iteration.

5. Analyze complexity and discuss optimizations

Explain that each next() call may skip exhausted streams, leading to O(k) worst-case time per call, but amortized O(1) if streams are removed. Discuss using a circular buffer or linked list for efficiency.

Key Points to Mention

Lazy evaluation: only read from streams as needed, never load all data into memory.
Maintain a list of active stream iterators and an index to cycle through them.
Skip exhausted streams by removing them from the active list or advancing the index.
Handle edge cases: empty input, all streams exhausted, streams with no elements.
Time complexity: O(k) worst-case per next() call, but amortized O(1) if exhausted streams are removed.
Thread safety: if required, use synchronization or concurrent data structures.

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