## Google Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 3 vote

This is a De Bruijn sequence problem.
See https://en.wikipedia.org/wiki/De_Bruijn_sequence#Algorithm

Comment hidden because of low score. Click to expand.
0
of 0 vote

public String digits(Integer n, String input){
Integer k=0;
String digits=null;
if(input!=null&&!input.isEmpty()) { k = input.length();}
if((k>n||k==n)&&input.matches("[0-9]+")){
digits=input.substring((k-n), input.length()); }
else{ digits="not a valid password"; }
return digits;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public String digits(Integer n, String input){
Integer k=0;
String digits=null;
if(input!=null&&!input.isEmpty()) {
k = input.length();
}
if((k>n||k==n)&&input.matches("[0-9]+")){
digits=input.substring((k-n), input.length());
}
else{
}
return digits;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

n-actual password, input-how many ever characters you enter
my code checks if the entered password is not null and it contains all digits only, and, trims to last n-digits that is meant for password and returns the same.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we do it with pattern matching algorithm?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solved by finding a Hamiltonian path of size K^N

``````unordered_set<string> visited;

bool crackSafeHelp(const string &start,string &res,int k,int pow){
if(visited.size() == pow){
return true;
}

string newNode = start.substr(1);

for(int i = 0; i < k; ++i){
string digit = to_string(i);
string temp = newNode + digit;

if(visited.find(temp) == visited.end()){
res += digit;
visited.insert(temp);
if(crackSafeHelp(temp,res,k,pow)){
return true;
}

visited.erase(temp);
res.pop_back();
}
}

return false;
}

string crackSafe(int n, int k) {
int power = pow(k,n);
string start(n,'0');
string res(n,'0');
visited.insert(start);
crackSafeHelp(start,res,k,power);
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

it is exactly same as leetcode 753.. copy and paste?

Comment hidden because of low score. Click to expand.
0
of 0 vote

slightly modified leetcode solution so that it works on both num and alphabet.

``````class Solution(object):
# n: length
# k: alphabet
def DeBruijn(self, n, k):
seen = set()
try:
alphabet = list(map(str, range(k)))
except(ValueError, TypeError):
alphabet = k
def dfs(node):
for x in alphabet:
neighbor = node + x
if neighbor not in seen:
dfs(neighbor[1:])
dfs(alphabet[0] * (n-1))
# print(seen)
return "".join(answer) + alphabet[0] * (n-1)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.