Merge two sorted lists
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Given two **sorted** lists (arrays) of integers `A` and `B` in non-decreasing order, merge them into a single sorted list.
## Requirements
- Output must be sorted in non-decreasing order.
- Aim for linear time in the total number of elements.
## Example
- `A = [1, 3, 5]`, `B = [1, 2, 6]` → `[1, 1, 2, 3, 5, 6]`
Quick Answer: This question evaluates a candidate's competency in array manipulation and merging algorithms, emphasizing understanding of ordered data and time complexity. Commonly asked in Coding & Algorithms interviews for Data Scientist roles, it assesses practical application-level skills in implementing efficient (linear-time) merges and algorithmic efficiency awareness.
Merge two non-decreasing integer arrays into one sorted array.
Constraints
- Inputs are sorted non-decreasing
Examples
Input: ([1, 3, 5], [1, 2, 6])
Expected Output: [1, 1, 2, 3, 5, 6]
Input: ([], [1])
Expected Output: [1]
Input: ([2], [])
Expected Output: [2]
Hints
- Use two pointers.