Solve three array/string/graph coding tasks
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given three separate coding tasks. Implement each as a function.
## 1) Merge three sorted arrays
**Input:** Three integer arrays `A`, `B`, `C`, each sorted in non-decreasing order (may contain duplicates, may be empty).
**Output:** A single array containing all elements from `A`, `B`, and `C` in non-decreasing order.
**Constraints (typical):** Total length up to ~1e5.
**Example:**
- `A = [1, 4, 4]`, `B = [2, 6]`, `C = [0, 4, 10]`
Output: `[0, 1, 2, 4, 4, 4, 6, 10]`
---
## 2) Sort characters by a given custom order
You are given a string `order` that defines a custom ordering of (some) characters, and a string `s` to sort.
**Rules:**
- Characters that appear in `order` must appear in the output in the same relative order as in `order`.
- If a character appears multiple times in `s`, all its occurrences should be grouped together.
- Characters in `s` that do **not** appear in `order` should appear at the end (you may keep their relative order from `s`, or specify/implement a consistent rule).
**Input:** `order` (string), `s` (string)
**Output:** A reordered string.
**Example:**
- `order = "cba"`, `s = "abcdabc"`
Output: `"ccbb aa dd"` without spaces → e.g. `"ccbbaad"` (all `c` first, then `b`, then `a`, then the remaining characters like `d`).
---
## 3) Deep copy (clone) a graph
Given a reference to a node in a connected, undirected graph, return a **deep copy** (clone) of the entire graph.
Assume each node has:
- an integer `val`
- a list of neighbor node references `neighbors`
**Requirements:**
- The cloned graph must contain entirely new nodes (no pointer/reference sharing with the original).
- Adjacency (edges) must be preserved.
- Handle cycles correctly.
**Input:** A node reference `node` (or `null`).
**Output:** A node reference to the cloned node corresponding to the input `node` (or `null`).
**Edge cases to consider:** `null` input, single-node graph, cycles, self-loops.
Quick Answer: This set of three coding tasks evaluates proficiency in fundamental data structures and algorithms, covering multi-way array merging, custom character ordering and grouping, and graph cloning with correct handling of cycles and references.
Merge Three Sorted Arrays
Return one sorted array containing all elements from A, B, and C.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,4,4], [2,6], [0,4,10])
Expected Output: [0, 1, 2, 4, 4, 4, 6, 10]
Explanation: Merge all three sorted arrays.
Input: ([], [], [1])
Expected Output: [1]
Explanation: Empty inputs are allowed.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.
Sort Characters By Custom Order
Sort characters that appear in order according to that order; remaining characters keep original order.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('cba','abcdabc')
Expected Output: 'ccbbaad'
Explanation: Characters in order are grouped first, others keep original order.
Input: ('x','abc')
Expected Output: 'abc'
Explanation: All unordered chars keep original order.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.
Deep Copy Graph Representation
Clone a nested [value, neighbors] graph representation, preserving shared nodes by value.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1, [[2, []], [3, []]]],)
Expected Output: [1, [[2, []], [3, []]]]
Explanation: Clone a small graph/tree-like nested representation.
Input: (None,)
Expected Output: None
Explanation: Empty graph returns None.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.