Implement Sorted Search and Array Updates
Company: Bytedance
Role: Site Reliability Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement the following independent array functions.
### Part 1: Search a sorted array
Given a sorted array of integers `nums` in nondecreasing order and an integer `target`, return the index of `target` if it exists. If `target` does not exist, return `-1`.
Requirements:
- The algorithm should run in `O(log n)` time.
- If there are duplicate values equal to `target`, returning any valid index is acceptable.
Example:
```text
nums = [1, 3, 5, 7, 9], target = 7
Output: 3
```
### Part 2: Add one to an integer represented as digits
You are given an array `digits` representing a nonnegative integer. Each element is one decimal digit, and the most significant digit is at index `0`. Add `1` to the integer and return the resulting digit array.
Requirements:
- Do not convert the entire array into a built-in integer type.
- Correctly handle carry propagation.
Examples:
```text
digits = [1, 2, 3]
Output: [1, 2, 4]
digits = [9, 9, 9]
Output: [1, 0, 0, 0]
```
### Part 3: Move all zero values to the end
Given an integer array `nums`, rearrange it in place so that all nonzero elements appear first in their original relative order, followed by all zero values.
Requirements:
- Modify the input array in place.
- Preserve the relative order of nonzero elements.
- Use `O(1)` extra space.
Example:
```text
nums = [0, 1, 0, 3, 12]
After modification: [1, 3, 12, 0, 0]
```
Quick Answer: This question evaluates proficiency in array manipulation and fundamental algorithmic techniques—specifically binary search for sorted arrays, digit-wise arithmetic with carry handling, and in-place stable reordering—within the Coding & Algorithms domain and with attention to time and space complexity.
Search a Sorted Array
Given a sorted array of integers `nums` in nondecreasing order and an integer `target`, return the index of `target` if it exists in the array. If `target` does not exist, return `-1`.
The algorithm must run in `O(log n)` time. If there are duplicate values equal to `target`, returning any valid index is acceptable.
Example:
```
nums = [1, 3, 5, 7, 9], target = 7
Output: 3
```
Constraints
- 0 <= len(nums) <= 10^5
- nums is sorted in nondecreasing order
- -10^9 <= nums[i], target <= 10^9
Examples
Input: ([1, 3, 5, 7, 9], 7)
Expected Output: 3
Explanation: Target 7 sits at index 3.
Input: ([1, 3, 5, 7, 9], 1)
Expected Output: 0
Explanation: First element matches.
Hints
- Maintain a search window [lo, hi] and repeatedly halve it by comparing the middle element with the target.
- If nums[mid] < target, the answer must be to the right (lo = mid + 1); if nums[mid] > target, it's to the left (hi = mid - 1).
- Return mid as soon as nums[mid] == target; if the window empties (lo > hi), return -1.
Plus One (Digit Array)
You are given an array `digits` representing a nonnegative integer, where each element is one decimal digit and the most significant digit is at index `0`. Add `1` to the integer and return the resulting digit array.
Do not convert the entire array into a built-in integer type. Handle carry propagation correctly, including the case where a new leading digit is needed.
Examples:
```
digits = [1, 2, 3] -> [1, 2, 4]
digits = [9, 9, 9] -> [1, 0, 0, 0]
```
Constraints
- 1 <= len(digits) <= 10^4
- 0 <= digits[i] <= 9
- digits has no leading zeros except the number 0 itself (i.e. [0])
Examples
Input: ([1, 2, 3],)
Expected Output: [1, 2, 4]
Explanation: 123 + 1 = 124, no carry.
Input: ([9, 9, 9],)
Expected Output: [1, 0, 0, 0]
Explanation: 999 + 1 = 1000; carry propagates and a new leading digit is added.
Hints
- Process digits from the least significant end (the last index) toward the front.
- If the current digit is less than 9, increment it and you're done -- no further carry.
- If it's 9, set it to 0 and carry into the next digit. If the carry survives past index 0, prepend a 1 (e.g. [9,9,9] -> [1,0,0,0]).
Move Zeroes
Given an integer array `nums`, rearrange it in place so that all nonzero elements appear first in their original relative order, followed by all zero values.
Modify the input array in place, preserve the relative order of the nonzero elements, and use `O(1)` extra space. (Return the array so its final state can be checked.)
Example:
```
nums = [0, 1, 0, 3, 12]
After modification: [1, 3, 12, 0, 0]
```
Constraints
- 0 <= len(nums) <= 10^4
- -2^31 <= nums[i] <= 2^31 - 1
- The rearrangement must happen in place with O(1) extra space
Examples
Input: ([0, 1, 0, 3, 12],)
Expected Output: [1, 3, 12, 0, 0]
Explanation: Nonzeros 1,3,12 keep order; two zeros pushed to the end.
Input: ([0, 0, 0],)
Expected Output: [0, 0, 0]
Explanation: All zeros stay as all zeros.
Hints
- Keep a write pointer (insert_pos) for the next slot that should hold a nonzero value.
- Scan left to right; each time you see a nonzero, copy it to insert_pos and advance insert_pos -- this preserves nonzero order.
- After the scan, every index from insert_pos to the end should be set to 0.