First 1 in an Endless Sorted 0/1 Array
Updated
Problem statement
An endless list holds only 0s and 1s in sorted order: some number of 0s (possibly none), then 1s forever. You are given the start of the list as the array bits; every position past the end of bits holds 1.
Return the position (counting from 0) of the first 1. If bits holds only 0s, the first 1 is the position just past its end, bits.length.
Treat the list as endless: read it only through a small helper get(i) that returns bits[i], or 1 when i is past the end, and do not use the array's length as a search bound. Aim for O(log p) reads, where p is the answer. The judge only checks the answer.
Function
firstOne(bits: int[]) → intExamples
Example 1
bits = [0,0,0,1,1,1,1]return = 3Positions 0 to 2 hold 0 and position 3 holds the first 1, so the answer is 3.
Example 2
bits = [1,1]return = 0The very first value is already 1, so the answer is 0.
Example 3
bits = [0,0,0,0,0]return = 5All five stored values are 0. Every position past the stored part holds 1, so the first 1 is at position 5.
Constraints
1 <= bits.length <= 10^4- each
bits[i]is0or1, andbitsis sorted (all 0s come before all 1s)
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Track New Values in Sorted OrderBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Price at Query TimestampsGoogle · PHONE SCREENGoogle interview questions
- First Missing Number in a Consecutive ArrayArista Networks · OA · PHONE SCREENArista Networks interview questions
- Messages in an Inclusive Timestamp RangeAttentive · PHONE SCREEN · ONSITE INTERVIEWAttentive interview questions
- First Bad Version in a Monotone ArrayMeta · PHONE SCREENMeta interview questions
- Target Sum Across Two Sorted ArraysSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Leftmost Binary Search MatchByteDance · PHONE SCREENByteDance interview questions
- Find the First Target IndexSuperhuman · PHONE SCREENSuperhuman interview questions
- First Target IndexGrammarly · PHONE SCREEN
- Ceiling Value in a Sorted ArrayPeopleStrong · PHONE SCREENPeopleStrong interview questions
Interview reports that mention this question
Adobe interview experiences
- Adobe Web, QA, DevOps, ML Roles: 13 Experiences (Part 3 of 3)
- Adobe Interviews, Level Unknown: 38 Experiences (Part 1 of 3)
- Adobe New Grad MTS Interview Questions: 7 Experiences
- Adobe ML/Research Intern Interviews: 12 Experiences (Part 4 of 4)
- Adobe Product Intern Interviews: 15 Experiences (Part 3 of 4)