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.

Answer 1

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.