Quick Overview

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.

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] ```

Overview: 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.

Read the full ByteDance Site Reliability Engineer interview experience this question came from

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

  1. Maintain a search window [lo, hi] and repeatedly halve it by comparing the middle element with the target.
  2. 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).
  3. 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

  1. Process digits from the least significant end (the last index) toward the front.
  2. If the current digit is less than 9, increment it and you're done -- no further carry.
  3. 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

  1. Keep a write pointer (insert_pos) for the next slot that should hold a nonzero value.
  2. Scan left to right; each time you see a nonzero, copy it to insert_pos and advance insert_pos -- this preserves nonzero order.
  3. After the scan, every index from insert_pos to the end should be set to 0.

Loading coding console...