Shortest string to try all 3 digit lock

Question

I was asked this question in one of my recent interviews. A three digit lock can have its key value between range "000" - "999". So basically 1000 combinations have to be tried to open the lock. So I had to generate the shortest string such that all possible combinations (i.e between "000"-"999") would be checked. So for example if we had string "01234" then it would check the combinations "012", "123" and "234". So I had to generate a string which would check all combination. I tried to use a hashset to implement this, where I started with "000" and then took the last two character in string i.e "00" and then appended a new number from 0 to 9 and checked if it existed in hashset. If not I appended that number to output string and repeated the process. Is there any other efficient and clean way to solve this problem.

en.wikipedia.org/wiki/De_Bruijn_sequence (A python program appears at the end of the article.) — rici
Unless that job was in a very specific environment, that seems like an odd interview question to me. It's not an easy algorithm to come up with in a few minutes, so the question is simply testing to see if you've stumbled upon the concept at some point in your education. Of course, there are practical applications in combinatorics, so if the job involves that field I guess it might be interesting to see if the applicant recognizes the pattern. (Although you could just ask directly :) ) — rici
Yeah De_Bruijn-sequence does look similar to the problem statement. Thanks — Ram Swami

sve sve · Accepted Answer · 2015-10-13T21:24:35

The procedure you described is based on the assumption that the shortest string has every code exactly once. It turns out that this assumption is correct. Here's a simple backtracking implementation (C++):

#include <stdio.h>

bool used[1000];
int digits[33333];

bool backtrack(int index, int total)
{
    if (total == 1000)
    {
        printf("%d\n", index);
        for (int i = 0; i < index; ++i) {
            printf("%d", digits[i]);
        }
        printf("\n");
        return true;
    }

    for (int d = 0; d < 10; ++d)
    {
        int prev = 100*digits[index-2]+10*digits[index-1]+d;
        if (!used[prev]) {
            digits[index] = d;
            used[prev] = true;
            if (backtrack(index+1, total+1))
                return true;
            used[prev] = false;
        }
    }
}

int main(void) {
    digits[0] = 0;
    backtrack(2, 0);
    return 0;
}

Output:

1002
00010020030040050060070080090110120130140150160170\
18019021022023024025026027028029031032033034035036\
03703803904104204304404504604704804905105205305405\
50560570580590610620630640650660670680690710720730\
74075076077078079081082083084085086087088089091092\
09309409509609709809911121131141151161171181191221\
23124125126127128129132133134135136137138139142143\
14414514614714814915215315415515615715815916216316\
41651661671681691721731741751761771781791821831841\
85186187188189192193194195196197198199222322422522\
62272282292332342352362372382392432442452462472482\
49253254255256257258259263264265266267268269273274\
27527627727827928328428528628728828929329429529629\
72982993334335336337338339344345346347348349354355\
35635735835936436536636736836937437537637737837938\
43853863873883893943953963973983994445446447448449\
45545645745845946546646746846947547647747847948548\
64874884894954964974984995556557558559566567568569\
57657757857958658758858959659759859966676686696776\
78679687688689697698699777877978878979879988898999\
00

The procedure is efficient.

Shortest string to try all 3 digit lock

1 Answers