Phone Screen: Lean Hire
DSA 1: No Hire
DSA 2: Strong Hire
Domain Round(Android) : Strong Hire
Googliness: Pending Interview. Now Done with the interview feedback is Lean Hire
I'm confused about the DSA 1 interview feedback. I solved the given question using bitmasking and backtracking, resulting in a time complexity of n^5, which is the best achievable for that question. There's an alternative approach using a Trie, but it also results in the same time complexity. I couldn't present the Trie approach during the interview, and the interviewer agreed that n^5 is the best possible. Despite this, I received a No Hire, which I feel is unfair.
Q1: What are your thoughts on this DSA1? Shall i ask to re-evaluate?
Q2: Also, what do you think about my chances of being hired at Google for L4?
.
.
======================= DSA 1 Question ==========================
We are given a list of Strings each string is size 5 exact, we need to combine 5 word to make a sentence in which should not have any duplicate characters.
Input:
werty uiopa sdfgh jklzx cvbnm aasdg sdfjk lzxcv bnmgh
Output:
werty uiopa sdfgh jklzx cvbnm
werty uiopa sdfjk lzxcv bnmgh
Solution:
record Pair(String word, int mask) {
}
List<List<String>> findValidWords(List<String> words) {
List<Pair> unique = new ArrayList<>();
for (String word : words) {
int mask = 0;
boolean isGoodWord = true;
for (int i = 0; i < 5; i++) {
int c = word.charAt(i) - 'a';
if ((mask & (1 << c)) == 1) {
isGoodWord = false;
break;
}
mask = mask | (1 << c);
}
if (isGoodWord)
unique.add(new Pair(word, mask));
}
find(unique, 0, 0, new LinkedList<>());
return ans;
}
List<List<String>> ans = new ArrayList<>();
void find(List<Pair> words, int idx, int mask, LinkedList<String> res) {
if (res.size() == 5) {
ans.add(new ArrayList<>(res));
return;
}
for (int i = idx; i < words.size(); i++) {
Pair cur = words.get(i);
if ((mask & cur.mask) == 0) {
res.add(cur.word);
find(words, i + 1, mask | cur.mask, res);
res.removeLast();
}
}
}