At first, he introduced himself and asked me if I had any previous internships.

Next, he asked me why I was interested in Bloomberg. I replied that I want to improve my skills with C++ and that dealing with the amount of data at Bloomberg would be a great challenge for me.

We then started the technical part, where he presented me with the following problem:

Find the number of occurrences 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 algorithm question. I told him there is a linear solution using KMP and also mentioned the O(n^2) approach, where we iterate over the source string and compare the substring ending at the length of the target with the target string.

He asked me to implement KMP, so I started explaining it, hoping I would remember how it works. However, I got stuck trying to calculate the fail array and asked if I could instead do the hashing solution. I also reiterated the O(n^2) solution, but he preferred the linear time one.

He was okay with that and let me implement it. Before I did, he told me that the hashing solution would be O(n^2) since he assumed the hash function itself took linear time. I explained that I would precompute the prefix hashing of the source string, which takes linear time, and then compute hash(i,j) by subtracting the prefix hash of j from the prefix hash of i-1:

hash(i,j) = pfxHash[j] - pfxHash[i-1] // O(1) time then compare if (hash(i,j) == hash(target) * pow1[i]).

He let me continue coding. After I finished, I moved on to case handling, where I addressed the case of an empty target string. He then asked why I hadn't handled an empty source string. I told him my code wouldn't throw any errors and would return 0, as it wasn't specified in the problem description. He agreed and then asked if there were more test cases. I mentioned the case where the target string is larger than the source string, which I handled by returning 0.

At the end, he asked if I had any questions for him. I asked how he would teach interns on his team and whether Bloomberg truly considers intern projects for production. He told me he hadn't had any interns on his team before and that not all intern projects make it into production, but they try to reach that stage.

Why Bloomberg?

Did you have any internships before?