# is hash table a magic?

I have no cs background (algorithm and data structure), but need to find a data analysis related job since my major is math / statistics. However, (I am trying to avoid software engineering related jobs) no matter which position I applied, from finance to bioinformatics, almost every technical interview involves hash table. I feel very frustrated that if I don't know this, I cannot find a job. If I know this, then I have to study algorithm and data structure (then solve all the problems in Leetcode, etc), which is equivalent to a SDE job seeker .

For example, I got an interview question: $a=(3,2,5,6,1,3,2)$, $b=(4,3,6,2,3)$ ( generally, length of $a$ is N, length of $b$ is N). And there is a program to output all matched pairs (just a pseudocode in whatever language):

for i in 1:N
for j in 1:M
if a[i]=b[j]:
print(a[i])


Then the program outputs $(3,3,2,6,3,3,2)$. The time complexity of this is $O(MN)$, and the interview question I did not figured out is, to get the same output, how to improve this program?

They finally told me that it takes $O(N)$ to make a hash table (search table) for $b$, and then use $O(M)$ time to loop $a$. So the total time is $O(M+N)$.

My question is: is this just that simple? (they said they do not care space complexity at the beginning)

I know nothing about hash table except the only fact that it takes $O(1)$ to search the keyword. So assume this is true, I can understand his answer. However, I am just curious, is this just this simple? I mean, it seems there is no algorithm in this solution but just "hash it". Are all the core intelligence to solve this problem is hidden in the hash table property and how hash table is created in $O(N)$? Is this a usual way for a cs student/SDEer, who knows hash, to solve this problem, that comes first in their mind? (To me, I think his example code is exactly what I will write if I meet this problem in my research work.)

If it is so straightforward to think in this hash way for those know hash, then I think I should also learn algorithm and data structure. Otherwise I think I won't get a job. Is there any suggested book or tutorial that can help me to solve this kind of problem algorithmly or hashly?

• It is not that simple, amortised / expected time... did you look at our answered questions about hash tables? What is your question? (There are several of them and context does matter a lot. For everyday programming tasks, yes. For somewhat stricter analysis, pesymistic case for look up is $\mathcal O(n)$...). It is nice to put a background, but I think, that question would fit in 3 lines. Nice one: cs.stackexchange.com/questions/249/when-is-hash-table-lookup-o1 – Evil Mar 29 '18 at 22:21
• I'm not sure the question is appropriate for this site, or indeed anywhere on the network. You are basically asking for tips about how to find a job. – Yuval Filmus Mar 29 '18 at 22:30
• If you want to work in computer science (programming or not), it's a terrific idea to study some computer science. – Yuval Filmus Mar 29 '18 at 22:31
• It sounds like you should read an undergraduate-level textbook on data structures and algorithms. That will describe how hash tables work, and many other things that will be helpful to you in this sort of interview. The interview is probably testing your knowledge of computer science, so if you don't know much computer science, it's no surprise that you are having difficulty with the interview question. – D.W. Mar 29 '18 at 22:39
• Thanks for your comments and suggestion! @Evil an others. I will study the basic algo and DS textbook. After a second thought, I think my actual question is "Given this problem, does the example $O(MN)$ code looks very stupid for cs people, and if their first thought is to use hash table to solve the problem like the interviewer?" – breezeintopl Mar 30 '18 at 0:10