At first he introduced himself to me, he asked me whether I had any internships before.
Next he asked me about why Bloomberg. I replied saying that I want to improve my skills with C++ and dealing with that amount of data in Bloomberg will be a great challenge for me.
We then started the technical part where he had given me this problem.
Find the number of occurences of a target string in a source string
int indexOf("ABABA", "A") --> returns 3
At first, I was surprised by the question as it was the first interview and I didn't expect a KMP question here. I told him that there is a liner a solution via KMP and also mentioned the other O(n^2) approach where we iterate over the source string and keeps comparing the substring ending at the length of the target with the target string.
He asked me to implement the KMP, so I started explaining it to him hoping that I will remember how it works. However I got stuck trying to calculate the fail array and asked him that I prefer to do the hashing solution and also I mentioned him again the O(n^2) solution but he prefered the linear time one.
He was okay with it and he let me implement it, but before I did, he told me that the hashing will be an O(n^2) since he assumed that the hash function has a linear time. I told him that I wouldn't calculate the hash function in a linear time and that I will precompute the prefix hashing of the source string which is a linear time then I will compute hash(i,j) by subtracting the prefix hash of j from the prefix hash of i
hash(i,j) = pfxHash[j] - pfxHash[i-1] //O(1) time
then we compare if (hash(i,j) == hash(target) * pow1[i])
He let me continue the coding then after I finished I went to case handling where I handled of the target string is empty only. He asked me about why not handle if the source string is empty. I told him my code won't through any errors and the return value will be 0 as it wasn't mentioned in the problem discription. He agreed with me and then asked me if there is more test cases. I mentioned the case when the target string is larger than the source string and handled it by returning 0.
At the end he asked me if there are any questions to ask him. I asked him about how would he teach interns in his team and whether Bloomberg really consider intern projects into production. He told me he hadn't any interns in his team before and also that not all intern projects make it into production but they try to make it reaches that stage.