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 Technical Screen rounds at Two Sigma.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Two Sigma during technical interviews.

Merge two sorted linked lists | Two Sigma Coding Question

Merge two sorted linked lists

Company: Two Sigma

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Given two singly linked lists sorted in ascending order, merge them into one singly linked list that is also sorted in ascending order. Requirements: - Each input list may be empty. - Node values are integers. - Reuse the existing nodes if possible. - Return the head of the merged list. - Target time complexity: O(n + m), where n and m are the lengths of the two lists.

Quick Answer: This question evaluates proficiency with linked list data structures, pointer manipulation, in-place merging concepts, and algorithmic efficiency within the Coding & Algorithms domain.

You are given the heads of two singly linked lists sorted in ascending order. Merge them into one singly linked list that is also sorted in ascending order, and return the head of the merged list. For this problem environment, a linked list is represented as a nested Python list of the form [value, next_node], where next_node is either another node or None. Examples: - The list 1 -> 2 -> 4 is represented as [1, [2, [4, None]]] - An empty list is represented as None Requirements: - Either input list may be empty. - Node values are integers. - Reuse the existing nodes if possible instead of creating a brand new list. - Return the head of the merged list in the same nested format.

Constraints

0 <= n, m <= 100000, where n and m are the lengths of the two lists
-10^9 <= node value <= 10^9
Both input lists are sorted in non-decreasing order

Examples

Input: ([1, [2, [4, None]]], [1, [3, [4, None]]])

Expected Output: [1, [1, [2, [3, [4, [4, None]]]]]]

Explanation: Merge by repeatedly taking the smaller front node: 1, 1, 2, 3, 4, 4.

Input: (None, [0, [2, None]])

Expected Output: [0, [2, None]]

Explanation: If one list is empty, the result is simply the other list.

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

Expected Output: [-4, [-3, [1, [2, [5, [6, None]]]]]]

Explanation: Merging the sorted lists produces -4 -> -3 -> 1 -> 2 -> 5 -> 6.

Input: (None, None)

Expected Output: None

Explanation: Both lists are empty, so the merged list is also empty.

Input: ([1, [1, [2, None]]], [1, [3, None]])

Expected Output: [1, [1, [1, [2, [3, None]]]]]

Explanation: Duplicates must be preserved in sorted order.

Input: ([5, None], [1, None])

Expected Output: [1, [5, None]]

Explanation: A single-node list can be merged with another single-node list by choosing the smaller head first.

Hints

Keep one pointer on each list and always attach the smaller current node to the merged list.
A dummy head node can simplify edge cases like when one list is empty or when the first node comes from the second list.

Quick Overview

This question evaluates proficiency with linked list data structures, pointer manipulation, in-place merging concepts, and algorithmic efficiency within the Coding & Algorithms domain.