Fewest Turns to Open a Wheel Lock
Updated
Problem statement
A lock has four wheels. Each wheel shows one digit from 0 to 9, so the lock always shows a four-digit code. It starts at "0000".
One turn moves one wheel one step up or down. Going up from 9 gives 0, and going down from 0 gives 9.
Some codes are listed in blocked. If the lock ever shows a blocked code, it jams and can no longer be turned. This includes the starting code: if "0000" is blocked, the lock is jammed from the start.
Return the fewest turns needed to make the lock show target without ever showing a blocked code. Return 0 if the lock already shows target and "0000" is not blocked. Return -1 if it cannot be done, including whenever "0000" or target is blocked. A blocked code can be listed more than once.
Function
fewestTurns(blocked: String[], target: String) → intExamples
Example 1
blocked = []target = "8091"return = 4Nothing is blocked, so each wheel can take its shortest way. The first wheel goes down from 0 to 9 to 8 (2 turns), the third wheel goes down from 0 to 9 (1 turn) and the last wheel goes up from 0 to 1 (1 turn). That is 4 turns.
Example 2
blocked = ["0001","0009"]target = "0002"return = 4The last wheel must go from 0 to 2, but both of its neighbors, 0001 and 0009, are blocked while the other wheels show 0. So first turn another wheel: 0000 to 1000 to 1001 to 1002 to 0002. That is 4 turns, and no path with fewer turns avoids the blocked codes.
Example 3
blocked = ["0000","4321"]target = "1234"return = -1The starting code 0000 is blocked, so the lock is jammed before the first turn. The answer is -1.
Constraints
0 <= blocked.length <= 1000blocked[i].length == 4andtarget.length == 4- Every code in
blockedandtargetis made of the digits0to9only.
More C3.ai interview questions
- Days Until a Warmer DayPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Longest Run of Ones After Flipping k ZerosPHONE SCREEN · Seen Mar 2022
- Top K Frequent ElementsPHONE SCREEN · Seen Feb 2021
- Item Prices From Material CostsPHONE SCREEN · Seen Dec 2020
- Adjacent-Key Lock PatternsPHONE SCREEN · Seen Feb 2014
- Drop Recent Duplicate MessagesOA · Seen Oct 2026
- Maximum K-Star SumOA · Seen Oct 2026
- Every Result of Grouping an ExpressionONSITE INTERVIEW · Seen Jan 2023
- Fewest Jumps to the Last IndexONSITE INTERVIEW · Seen Jan 2023
- Rotate a Square Grid ClockwiseONSITE INTERVIEW · Seen Jan 2023
Similar questions at other companies
- Linked Merchants Within Two HopsStripe · PHONE SCREENStripe interview questions
- Insert an Employee into an Organization HierarchyWaymo · PHONE SCREENWaymo interview questions
- Find Duplicate Files in a FilesystemHarvey · PHONE SCREEN · ONSITE INTERVIEWHarvey interview questions
- Shortest Word Transformation SequenceReddit · PHONE SCREENReddit interview questions
- Word LadderGoldman Sachs · PHONE SCREEN · ONSITE INTERVIEWGoldman Sachs interview questions
- Word Ladder IIBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Find Minimum City HopsAmazon · OA
- Shortest Path from Encoded Graph EdgesBitGo · OABitGo interview questions
- Open the LockMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Minimum Genetic MutationBenchling · OABenchling interview questions