Katkat
Back

Implement Sorted Search and Array Updates

ByteDanceSite Reliability Engineer · Technical Screen
MediumSite Reliability EngineerTechnical ScreenCoding & Algorithms

Last updated

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

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:

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:

nums = [0, 1, 0, 3, 12]
After modification: [1, 3, 12, 0, 0]