Quick Overview

This question evaluates proficiency in mutable data structure operations, specifically linked list node removal and binary tree node replacement/deletion, requiring knowledge of traversal, pointer/reference manipulation, and edge-case handling.

Delete nodes in linked list and binary tree

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are asked to solve **two short coding tasks**. You may assume standard node definitions: - **Singly linked list node:** `val`, `next` - **Binary tree node:** `val`, `left`, `right` ## Task A — Remove the Nth node from the end of a linked list Given the head of a singly linked list and an integer `n`, remove the **n-th node from the end** of the list and return the new head. **Requirements** - `1 <= n <= length(list)` - Aim for `O(L)` time where `L` is the list length, and `O(1)` extra space. ## Task B — Delete a node from a binary tree and reconnect Given the root of a **binary tree (not necessarily a BST)** and an integer `key`, delete **one** node whose value equals `key` and return the (possibly new) root. To keep the tree structure valid after deletion, perform deletion using this rule: 1. Find the node `X` with value `key`. 2. Find the **deepest, rightmost** node in the tree `D`. 3. Replace `X.val` with `D.val`. 4. Delete node `D` from its parent by setting the corresponding child pointer to `null`. **Edge cases** - If `key` is not found, return the original root. - If the tree has only one node and it matches `key`, return `null`. **Complexity target:** `O(N)` time, `O(N)` space is acceptable (e.g., BFS queue), where `N` is the number of nodes.

Quick Answer: This question evaluates proficiency in mutable data structure operations, specifically linked list node removal and binary tree node replacement/deletion, requiring knowledge of traversal, pointer/reference manipulation, and edge-case handling.

Part 1: Remove the Nth Node from the End of an Encoded Linked List

A singly linked list is encoded as nested Python tuples of the form `(value, next_node)`, where `next_node` is either another tuple or `None`. For example, `(1, (2, (3, None)))` represents the linked list `1 -> 2 -> 3`. Given the encoded head of a linked list and an integer `n`, remove the `n`-th node from the end of the list and return the new encoded head. Your algorithm should follow linked-list logic rather than relying on random access.

Constraints

  • Let `L` be the number of nodes in the list.
  • `1 <= L <= 10^5`
  • `1 <= n <= L`
  • Node values are integers in the range `[-10^9, 10^9]`

Examples

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

Expected Output: (1, (2, (3, (5, None))))

Explanation: The 2nd node from the end is `4`, so the result is `1 -> 2 -> 3 -> 5`.

Input: ((1, None), 1)

Expected Output: None

Explanation: Single-node list: deleting the 1st node from the end removes the only node.

Hints

  1. A dummy node before the head makes deleting the first real node much easier.
  2. Use two pointers: move one pointer `n` steps ahead, then move both pointers together until the front pointer reaches the end.

Part 2: Delete a Node from a Binary Tree Using Deepest-Rightmost Replacement

A binary tree is encoded as a level-order Python list, where missing children are represented by `None`. For example, `[1, 2, 3, None, 4]` means node `2` has no left child and has right child `4`. Given the encoded root of a binary tree and an integer `key`, delete one node whose value equals `key` using this exact rule: 1. Find the target node `X`. 2. Find the deepest, rightmost node `D` in the tree. 3. Copy `D.val` into `X.val`. 4. Remove the original deepest-rightmost node `D` from its parent. If `key` does not exist, return the original tree. If the tree has one node and it matches `key`, return an empty list. For deterministic behavior, if multiple nodes contain `key`, delete the first one found in level-order traversal. Return the resulting tree in trimmed level-order form, with unnecessary trailing `None` values removed.

Constraints

  • `0 <= N <= 10^4`, where `N` is the number of non-`None` nodes in the tree
  • Tree values are integers in the range `[-10^9, 10^9]`
  • The tree is not necessarily a BST
  • An `O(N)` time solution is expected
  • `O(N)` auxiliary space is allowed

Examples

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

Expected Output: [1, 2, 6, 4, 5]

Explanation: Node `3` is replaced by deepest-rightmost node `6`, and the original `6` is removed.

Input: ([1], 1)

Expected Output: []

Explanation: The tree has one node and it matches `key`, so the result is an empty tree.

Hints

  1. A breadth-first search can simultaneously find the target node, the deepest-rightmost node, and each node's parent.
  2. After replacing the target value, be careful to delete the original deepest-rightmost node from its parent, not the target node itself.

Loading coding console...