Open the Lock
Updated
Problem statement
A lock has four wheels. Each wheel shows one digit from 0 to 9, and the lock shows the four digits as a code such as "0000". In one move you turn one wheel by one step, either up or down. The wheels wrap around: turning 9 up gives 0, and turning 0 down gives 9.
The lock starts at "0000". The list deadends holds dead codes. If the lock ever shows a dead code, the wheels jam and you cannot move again, so a valid sequence of moves must never show a dead code, including the starting code.
Return the fewest moves needed to make the lock show target, or -1 if it cannot be done. If the lock already shows target at the start, the answer is 0.
Function
openLock(deadends: String[], target: String) → intExamples
Example 1
deadends = ["1000","0100","9000","0900"]target = "1100"return = 4Without dead codes, "1100" is two moves away. But both ways of making the first of those two moves land on a dead code: "1000" and "0100". A shortest detour turns another wheel first and undoes it at the end: "0000" → "0010" → "1010" → "1110" → "1100", which is 4 moves.
Three moves are impossible. Every move changes the sum of the four digits from even to odd or back, because a wheel changes by 1 or wraps between 9 and 0. "0000" and "1100" both have an even digit sum, so the number of moves must be even.
Example 2
deadends = ["9000","0090"]target = "9009"return = 2Turning a wheel down from 0 gives 9. The first and last wheels each need one such turn. Turning the first wheel first lands on the dead code "9000", so turn the last wheel first: "0000" → "0009" → "9009". That is 2 moves, the fewest possible since two wheels must change.
Example 3
deadends = ["0001","0009","0010","0090","0100","0900","1000","9000"]target = "4321"return = -1Every code one move away from "0000" is dead, so no first move is allowed and the target can never be reached. The answer is -1.
Constraints
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4deadends[i]andtargetcontain only the digits0to9.targetis not indeadends.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Word LadderGoogle · ONSITE INTERVIEWGoogle interview questions
- Find Duplicate Files in a FilesystemHarvey · PHONE SCREEN · ONSITE INTERVIEWHarvey interview questions
- Word LadderGoldman Sachs · PHONE SCREEN · ONSITE INTERVIEWGoldman Sachs interview questions
- Word Ladder IIBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Linked Merchants Within Two HopsStripe · PHONE SCREENStripe interview questions
- Find Minimum City HopsAmazon · OA
- Insert an Employee into an Organization HierarchyWaymo · PHONE SCREENWaymo interview questions
- Shortest Path from Encoded Graph EdgesBitGo · OABitGo interview questions
- Fewest Turns to Open a Wheel LockC3.ai · PHONE SCREENC3.ai interview questions
- Minimum Genetic MutationBenchling · OABenchling interview questions