How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Airbnb.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Detect overlap of two linked lists with cycles

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given the heads of two singly linked lists `headA` and `headB`. Each list may be: - A standard acyclic linked list, or - A cyclic linked list (contains a loop). Nodes are compared by **reference identity** (i.e., the same node object in memory), not by value. ### Task Determine whether the two lists **overlap** (share at least one common node). Return `true` if they overlap, otherwise return `false`. ### Follow-up If they do overlap, you may optionally return **any one** shared node. ### Constraints (typical) - `O(1)` extra space preferred. - Aim for `O(m + n)` time.

Quick Answer: This question evaluates understanding of linked list data structures, cycle detection techniques, pointer/reference identity, and algorithmic time/space complexity analysis within the Coding & Algorithms domain.

You are given two singly linked lists. Each list may be acyclic (ends at `None`) or cyclic (some node’s `next` pointer points back to an earlier node). Two lists **overlap** if they share **at least one node by identity** (i.e., the exact same node object). In this problem, nodes are represented by unique integer IDs. A `next_map` dictionary represents pointers: `next_map[u]` is the next node ID after `u`, or `None` if `u` is the tail. If two lists share a node, they will reference the same node ID. Return `True` if the two lists overlap (share any node), otherwise return `False`. Notes: - An empty list is represented by head `None`. - The input may contain cycles. - Assume `next_map` contains entries for every node ID that appears in the lists.

Constraints

0 <= number of nodes <= 1e5
Node IDs are integers and uniquely identify nodes (shared nodes use the same ID)
Each node has exactly one outgoing next pointer (to another node ID) or None
The structure may contain cycles
next_map contains all nodes reachable from headA or headB

Examples

Input: ({1: 2, 2: 3, 3: None, 4: 5, 5: None}, 1, 4)

Expected Output: False

Explanation: Two separate acyclic lists: 1->2->3 and 4->5 share no node IDs.

Input: ({1: 2, 2: 3, 3: 6, 6: 7, 7: None, 4: 5, 5: 6}, 1, 4)

Expected Output: True

Explanation: Lists share the tail starting at node 6: A: 1->2->3->6->7 and B: 4->5->6->7.

Input: ({1: 2, 2: 3, 3: 4, 4: 5, 5: 3, 6: 7, 7: 3}, 1, 6)

Expected Output: True

Explanation: Both lists enter the same cycle at node 3. They overlap at node 3 (and all nodes in the cycle).

Input: ({1: 2, 2: 3, 3: 4, 4: 5, 5: 3, 6: 7, 7: 4}, 1, 6)

Expected Output: True

Explanation: List A enters the cycle at node 3, list B enters the same cycle at node 4. Cycles are the same, so they overlap.

Input: ({1: 2, 2: 3, 3: 2, 4: 5, 5: None}, 1, 4)

Expected Output: False

Explanation: List A has a cycle (2<->3), list B is acyclic (4->5). They cannot overlap; otherwise B would also be cyclic.

Quick Overview

This question evaluates understanding of linked list data structures, cycle detection techniques, pointer/reference identity, and algorithmic time/space complexity analysis within the Coding & Algorithms domain.