FastPrepOpen the Lock
Problems/Open the Lock

Open the Lock

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Open the Lock, a known practice puzzle, was one of several data-structure questions in the technical round of a March 2025 Microsoft SWE intern interview (off-campus, India). The candidate went over solution ideas of increasing speed, breadth-first search among them. There were also edge-case variants that the report does not describe.

With no statement given, this version uses the familiar rules. There are four wrapping digit wheels starting at 0000, a list of dead codes to avoid, and you find the fewest single-step turns to reach the target, or -1. Our choices: no extra edge-case variant is added (the editorial covers a dead start, a target of 0000 and an unreachable target), and the limits are 1 to 500 dead codes of four digits each.

Our version is about 85% the same as the reported question.

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) → int

Examples

Example 1

deadends = ["1000","0100","9000","0900"]target = "1100"return = 4

Without 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 = 2

Turning 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 = -1

Every 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 <= 500
  • deadends[i].length == 4
  • target.length == 4
  • deadends[i] and target contain only the digits 0 to 9.
  • target is not in deadends.

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

Interview reports that mention this question

  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int openLock(String[] deadends, String target) {
        // Write your code here.
    }
}
Checking account…