Solve Linked-List and Iterator Problems
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
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.
Hints
- If you record every distinct node reachable from one head, the second traversal becomes a membership check.
- 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.
Hints
- Store all distinct nodes reachable from the first head, then walk the second list until you either hit one of them or stop.
- 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.
Hints
- Keep a queue of the stream indices that still have remaining characters.
- Store the current read position for each stream so that 'has_next' can stay O(1) and never consumes data.