PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches

Quick Overview

This question evaluates proficiency in linked-list pointer reasoning, cycle detection and shared-reference identification, as well as iterator design for round-robin merging, testing data-structure manipulation, iterator interfaces, and complexity analysis within the Coding & Algorithms domain.

  • Airbnb
  • Coding & Algorithms
  • Software Engineer

Solve Linked-List and Iterator Problems

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Interview Round: Onsite

You are asked to solve two coding problems. ## Problem 1: Detect shared nodes between possibly cyclic linked lists You are given the heads of two singly linked lists. Each list may be acyclic or may contain a cycle. A node is considered shared only if it is the exact same object/reference in memory, not merely a node with the same value. Implement: ```python def share_any_node(head_a: Optional[Node], head_b: Optional[Node]) -> bool: pass ``` Return `True` if the two lists share at least one node; otherwise return `False`. A `Node` has the following structure: ```python class Node: def __init__(self, value): self.value = value self.next = None ``` Consider all structural cases: - Both lists are acyclic. - One list is cyclic and the other is acyclic. - Both lists are cyclic but have completely separate cycles. - Both lists are cyclic and eventually enter the same cycle. - Both lists are cyclic and have the same cycle entry. - Both lists are cyclic and have different cycle entries but share the same cycle. Follow-up: ```python def find_shared_node(head_a: Optional[Node], head_b: Optional[Node]) -> Optional[Node]: pass ``` Return any shared node if one exists; otherwise return `None`. If the only shared nodes are inside a common cycle, returning any node in that shared cycle is acceptable. Discuss the expected time and space complexity. ## Problem 2: Implement a round-robin multi-stream iterator You are given multiple input streams. Each stream is an iterator over bytes or characters and supports: ```python has_next() -> bool next() -> value ``` Implement a `RoundRobinIterator` that merges these streams in round-robin order. Example: ```text stream 1: A B C stream 2: x y stream 3: 1 2 3 4 output: A x 1 B y 2 C 3 4 ``` Rules: - On each call to `next()`, return one element from the next available stream. - If a stream is exhausted, skip it for all future calls. - `has_next()` should return whether any stream still has data. - `has_next()` should be safe to call multiple times without consuming elements. - `next()` should raise an appropriate exception if no elements remain. - Do not read all stream contents into memory up front. - Preserve the provided interface and method signatures exactly if a base iterator class is supplied.

Quick Answer: This question evaluates proficiency in linked-list pointer reasoning, cycle detection and shared-reference identification, as well as iterator design for round-robin merging, testing data-structure manipulation, iterator interfaces, and complexity analysis within the Coding & Algorithms domain.

Part 1: Determine Whether Two Possibly Cyclic Linked Lists Share Any Node

You are given two heads into a shared pool of singly linked-list nodes. The pool is represented by an array named next_index, where node i points to node next_index[i], or to no node if next_index[i] is -1. Each head may start an acyclic list or a list with a cycle. Two lists share a node if both heads can reach the same node index. Return True if the two lists share at least one node; otherwise return False.

Constraints

  • 0 <= len(next_index) <= 200000
  • -1 <= head_a, head_b < len(next_index), unless len(next_index) is 0, in which case both heads must be -1
  • For every i, next_index[i] is either -1 or an integer in the range [0, len(next_index) - 1]
  • Each node has at most one outgoing edge, so each head defines a singly linked list that may contain a cycle

Examples

Input: ([1, 2, 3, -1, 5, 6, 3], 0, 4)

Expected Output: True

Explanation: List A is 0->1->2->3. List B is 4->5->6->3. They meet at node 3.

Input: ([1, 2, 0, 4, 5, 3], 0, 3)

Expected Output: False

Explanation: The lists are two separate cycles: 0->1->2->0 and 3->4->5->3.

Input: ([1, 2, 3, 4, 2, 6, 4], 0, 5)

Expected Output: True

Explanation: Both lists eventually enter the same cycle, but one enters at node 2 and the other at node 4.

Input: ([], -1, -1)

Expected Output: False

Explanation: Two empty lists share no node.

Input: ([1, 2, 1, 4, -1], 0, 3)

Expected Output: False

Explanation: One list is cyclic and the other is acyclic, and they never touch.

Hints

  1. If you record every distinct node reachable from one head, the second traversal becomes a membership check.
  2. Because cycles are possible, stop traversing a list when you revisit a node.

Part 2: Return a Shared Node in Two Possibly Cyclic Linked Lists

You are given two heads into a shared pool of singly linked-list nodes. The pool is represented by next_index, where node i points to next_index[i], or to no node if next_index[i] is -1. Each head may start an acyclic list or a cyclic list. Return the index of any node reachable from both heads. If no shared node exists, return -1. If multiple answers are possible, any valid shared node is acceptable. The reference solution used for the sample outputs returns the first shared node encountered while traversing list B.

Constraints

  • 0 <= len(next_index) <= 200000
  • -1 <= head_a, head_b < len(next_index), unless len(next_index) is 0, in which case both heads must be -1
  • For every i, next_index[i] is either -1 or an integer in the range [0, len(next_index) - 1]
  • Each node has at most one outgoing edge, so each head defines a singly linked list that may contain a cycle

Examples

Input: ([1, 2, 3, -1, 5, 6, 3], 0, 4)

Expected Output: 3

Explanation: The two lists first meet at node 3.

Input: ([1, 2, 0, 4, 5, 3], 0, 3)

Expected Output: -1

Explanation: The two cycles are completely separate.

Input: ([1, 2, 3, 4, 2, 6, 4], 0, 5)

Expected Output: 4

Explanation: Both lists share the same cycle. The reference solution returns the first shared node seen while traversing list B, which is 4.

Input: ([0], 0, 0)

Expected Output: 0

Explanation: Both heads already point to the same single-node cycle.

Input: ([1, -1], 0, -1)

Expected Output: -1

Explanation: An empty second list cannot share a node.

Hints

  1. Store all distinct nodes reachable from the first head, then walk the second list until you either hit one of them or stop.
  2. To avoid infinite loops in cyclic lists, remember which nodes you have already visited during each traversal.

Part 3: Simulate a Round-Robin Multi-Stream Iterator

You are given several input streams, each represented as a list of single-character strings, and a list of operations to perform on a conceptual round-robin iterator built from those streams. On each 'next' call, the iterator should return one character from the next available stream in round-robin order. Exhausted streams are skipped forever. 'has_next' must not consume data. For this function version of the problem, return a list of results for the operations: append 'true' or 'false' for each 'has_next', append the returned character for each successful 'next', and append 'EXCEPTION' for a 'next' call when no characters remain.

Constraints

  • 0 <= len(streams) <= 100000
  • 0 <= sum(len(stream) for stream in streams) <= 200000
  • 0 <= len(operations) <= 200000
  • Each stream element is a single-character string
  • Every operation is either 'has_next' or 'next'

Examples

Input: ([['A', 'B', 'C'], ['x', 'y'], ['1', '2', '3', '4']], ['has_next', 'next', 'next', 'next', 'next', 'next', 'next', 'next', 'next', 'next', 'has_next'])

Expected Output: ['true', 'A', 'x', '1', 'B', 'y', '2', 'C', '3', '4', 'false']

Explanation: The iterator alternates among non-empty streams and skips exhausted ones.

Input: ([], ['has_next', 'next'])

Expected Output: ['false', 'EXCEPTION']

Explanation: With no streams, nothing can be read.

Input: ([[], ['a'], [], ['b', 'c']], ['has_next', 'has_next', 'next', 'has_next', 'next', 'next', 'has_next', 'next'])

Expected Output: ['true', 'true', 'a', 'true', 'b', 'c', 'false', 'EXCEPTION']

Explanation: Empty streams are ignored, and repeated 'has_next' calls do not consume anything.

Input: ([['z']], ['next', 'has_next', 'next'])

Expected Output: ['z', 'false', 'EXCEPTION']

Explanation: After reading the only character, the iterator is exhausted.

Hints

  1. Keep a queue of the stream indices that still have remaining characters.
  2. Store the current read position for each stream so that 'has_next' can stay O(1) and never consumes data.
Last updated: May 23, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Determine Exact Layover Booking - Airbnb (medium)
  • Implement Text Layout and Query Parsing - Airbnb (easy)
  • Parse Query Parameters Into a Map - Airbnb (medium)
  • Compute board-game score from regions - Airbnb (medium)
  • Find smallest permutation under constraints - Airbnb (medium)