← Airbnb Interview InsightsSoftware Engineer

Airbnb·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Airbnb coding round, 45 minutes, one main problem on linked lists with cycles and intersection. The time pressure is brutal when you factor in writing test cases AND a follow-up, and I left feeling like the interviewer herself wasn't fully sure how to handle the harder variant.

Questions Asked (2)

Q1

Given two linked lists, each of which may or may not contain a cycle, determine whether they share at least one common node.

Algorithms & Data Structures
Author's notes

My linked list fundamentals are solid so the main problem went fine.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, detect cycles in both lists using Floyd's cycle-finding algorithm. Then, based on the presence of cycles, determine if they intersect by comparing the entry points of cycles or by traversing to the end if no cycles exist.

Pro tip: Clarify with the interviewer whether the lists are singly linked and if modifying them is allowed; this shows attention to detail and avoids assumptions that could lead to incorrect solutions.

1. Detect cycles in each list

Use Floyd's tortoise and hare algorithm to determine if each list has a cycle and find the starting node of the cycle if present.

2. Handle cases based on cycle presence

If neither list has a cycle, find the intersection by comparing lengths and traversing to the intersection point. If one has a cycle and the other doesn't, they cannot intersect.

3. If both have cycles, check for intersection

If both have cycles, check if they share the same cycle by comparing the cycle entry points or by traversing one cycle to see if the other's entry point is encountered.

4. Return the result

Based on the checks, return true if they share at least one common node, otherwise false.

Key Points to Mention

  • Floyd's cycle-finding algorithm (tortoise and hare) for cycle detection
  • Finding the start of the cycle using the meeting point and resetting one pointer to head
  • Handling the case where one list has a cycle and the other does not
  • Comparing lengths and using two-pointer technique for acyclic lists
  • Time complexity O(m+n) and space complexity O(1)
  • Edge cases: empty lists, single node lists, cycles that include the head

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

Q2

Follow-up: modify your solution to return the actual intersecting node, not just whether one exists.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

This is where things fell apart.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem: are we finding the intersection of two singly linked lists? If so, the goal is to return the node where they merge. Use a two-pointer technique: traverse both lists, and when one pointer reaches the end, redirect it to the other list's head. If they intersect, the pointers will meet at the intersection node after at most two passes; if not, both will become null simultaneously.

Pro tip: Mention that this approach uses O(1) extra space and O(m+n) time, which is optimal. Also, note that if the lists might have cycles, you need to handle that separately, but for typical interview questions, assume acyclic.

1. Clarify the problem

Confirm that the input consists of two singly linked lists and that we need to return the intersecting node (or null if none). Ask if the lists are guaranteed to be acyclic.

2. Choose the two-pointer approach

Explain that you'll use two pointers, one for each list. When a pointer reaches the end, redirect it to the head of the other list. This equalizes the path lengths.

3. Walk through the algorithm

Describe the loop: while pointerA != pointerB, advance both. If pointerA becomes null, set it to headB; similarly for pointerB. When they meet, that's the intersection node (or null if no intersection).

4. Analyze complexity

State that time complexity is O(m+n) and space complexity is O(1). Mention that each pointer traverses at most m+n nodes.

5. Handle edge cases

Discuss cases: one or both lists empty, no intersection, intersection at head, etc. Ensure the algorithm returns null correctly when no intersection exists.

Key Points to Mention

  • Two-pointer technique with pointer redirection
  • Time complexity O(m+n) and space complexity O(1)
  • Handling of no intersection (both pointers become null)
  • Assumption of acyclic lists; mention cycle detection if needed
  • Comparison of node references, not values
  • Edge cases: empty lists, intersection at head or tail

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