PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

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.

  • medium
  • Bytedance
  • Coding & Algorithms
  • Site Reliability Engineer

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.

Input: ([1, 3, 5, 7, 9], 9)

Expected Output: 4

Explanation: Last element matches.

Input: ([1, 3, 5, 7, 9], 4)

Expected Output: -1

Explanation: 4 is not present, so return -1.

Input: ([], 5)

Expected Output: -1

Explanation: Empty array contains nothing.

Input: ([42], 42)

Expected Output: 0

Explanation: Single-element array, target found at index 0.

Input: ([-5, -3, -1, 0, 2, 8], -3)

Expected Output: 1

Explanation: Works with negative values.

Input: ([1, 1, 1, 1], 1)

Expected Output: 1

Explanation: With duplicates, any valid index (here the midpoint) is acceptable.

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.

Input: ([0],)

Expected Output: [1]

Explanation: 0 + 1 = 1.

Input: ([9],)

Expected Output: [1, 0]

Explanation: 9 + 1 = 10; single digit overflows to two digits.

Input: ([1, 9, 9],)

Expected Output: [2, 0, 0]

Explanation: 199 + 1 = 200; carry stops at the leading digit.

Input: ([4, 3, 2, 1],)

Expected Output: [4, 3, 2, 2]

Explanation: 4321 + 1 = 4322.

Input: ([8, 9],)

Expected Output: [9, 0]

Explanation: 89 + 1 = 90; carry into the second digit only.

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.

Input: ([1, 2, 3],)

Expected Output: [1, 2, 3]

Explanation: No zeros, array unchanged.

Input: ([],)

Expected Output: []

Explanation: Empty array stays empty.

Input: ([0],)

Expected Output: [0]

Explanation: Single zero.

Input: ([5],)

Expected Output: [5]

Explanation: Single nonzero.

Input: ([0, 0, 1],)

Expected Output: [1, 0, 0]

Explanation: Leading zeros move behind the nonzero.

Input: ([4, 0, 5, 0, 0, 6, -7],)

Expected Output: [4, 5, 6, -7, 0, 0, 0]

Explanation: Negative values are treated as nonzero and keep their relative order.

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.
Last updated: Jun 21, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Reverse Nodes in K-Sized Groups - Bytedance
  • Solve Bracket Matching and Tree Width - Bytedance (hard)
  • Reverse Linked List Groups - Bytedance (medium)
  • Solve Stack and String Shift Problems - Bytedance (medium)
  • Find LCA With Parent Pointers - Bytedance (medium)