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?
