An Algorithm for Passing Programming Interviews (2020)

> XAND does not exist?

XAND being a convenient way to mean binary AND. I thought it was easy to infer. Taking the binary encodings, you can do a binary AND to determine if a set is an anagram subset (or full anagram) with more flexibility.

^Create a hashmap (any searchable K/V will do, redis, postgres, etc). For each word, check to see if encoding exists in set. If not, add key of encoding and value of word. If it exists, you have a match on the search word and the found key's value. Aggregate on a hashmap there for your final output, to avoid adding the same words multiple times.

- Some Leetcode questions require tricks/complex algorithm that you absolutely won't find in the span of 45 mins. If you do, either you are ultra genius, that able to find and modify a variation of Kadane's algorithm in 45 mins (even though it is a simple one), or you just have seen the question before and you just somewhat memorized it. Obviously the answer is the latter. In this case, what do actually FAANG companies really looking for? Is it the proof that a candidate has been finishing hundreds of questions?

- I've seen videos on interview example on Youtube, and they all present medium to easy Leetcode questions. The onsite interview at FAANG is mostly hard questions. So that means there are disconnect from how FAANG actually interviews and how these interview samples are conducted. And again, solving a hard question that you've never seen before optimally require way more than 45 mins, unless you've seen the question before, which goes back to no. 1

- Hiring managers or recruiters that gave advice. Saying stuff like "talk a lot, talk to the interviewer, interview is a 2 way street" and other feel-good self-help stuff that has nothing to do with the actual interview and don't help at all. Claimed that what the companies are looking are your thought process. Nope, lies. What companies are looking is whether you can solve this problem optimally in 45 mins. If you have thought process, speaking during the interview, etc, and you couldn't even finish the question in brute force, then you fail. If you able to finish the question with brute force, but not optimal, you also fail.

- Experienced senior engineers that definitely rusty on Leetcode and just did basic DS&A brushup and definitely couldn't pass Leetcode hard, got offered with TC way higher than these fresh grads.

So, I'm quite confused on what are the companies really looking for? I think I concluded that FAANG companies are indeed practicing what they say "eliminating false positives and have a really high false negatives". Therefore the whole interview Leetcode fiasco is just a number's game.

A few things:

- If you are senior engineers and have track record at other companies, then you don't need Leetcode to prove your worth. Since statistically, you are already worthy and can perform in your job.

- If you are not a senior engineer from other FAANG companies, then you just have to play the number's game. I.e, keep interviewing (and Leetcoding) until somehow the combination of your studies and the mood of the interviewer and the questions that come up during that interview day rolls in your favor.

OK, first, I'm not sure your original post presents the right reading of the blog post. Sorting and using a dictionary are given in the blog post as two separate solutions, not two components of one solution. (Sorry if I'm mistaken – but it seems to read this way to me?)

Regarding your concerns about dictionary generation: I might be missing something, but this doesn't seem so hard? The first thought that comes to mind is to associate to each word a 26-tuple of integers that counts the number of appearances of each letter of the alphabet. This can be done in O(N) time, since it's an O(1) operation for each word (length of words is assumed to be bounded above by some constant). Then

1) Create a (multi)-dictionary with these tuples as keys. Insert is O(1) in the average case, you're doing it N times, so this step is O(N).

2) Go through the dictionary by key and delete all singletons. Again O(N).

3) Print the dictionary by key to get the groups of anagrams.

This is O(N) on average. It's not immediately clear to me whether one can do O(N) in the worst case – are you claiming that your way does that?

[Of course, this is not so far off from what you're doing. But it illustrates the claim that bit arrays are not necessary.]