Bloomberg lets you interview with 2 teams at the same time, and the results don't affect each other. They require you to finish both coding problems.
First, a rant: their recruiter is extremely irresponsible. The night before my first team's interview it was rescheduled, with no formal email notice. For the second team, when the interview time came, nobody showed up and I got ghosted. Both were rescheduled to a week later, and in the end I failed both. Moving on.
Team 1: the interviewer was the tech lead.
15 minutes on my resume, where they ask about some details. The last 5 minutes are for my questions.
Coding 1:
Given 5 coin denominations, I think it was [1,5,10,15,20], each coin can be used an unlimited number of times. Given an amount n, output the combination that makes up the amount with the fewest coins. For example: n=3 outputs [3X1 coin], n=5 outputs [1X5 coin].
It's a DP knapsack problem, plus keeping track of the best combination for each amount.
Coding 2:
Given a user-film list, like 1:[a,b,c,d,e] 2:[a,c,d] 3:[]
This means user 1 watched films a, b, c, d, e.
Then given a new person's film list, like [a,c], recommend films to this person. The rule is to look through other people's watch histories: if the new person's films are a subset of someone else's, keep that person's watch history, otherwise skip them. Finally, recommend new films based on the total watch counts across everyone kept, sorted by number of viewers from high to low.
In the example above, users 1 and 2 are kept. b was watched by 1 person, d by 2 people, e by 1 person. Sorted by number of viewers, return [d,b,e].
I used a subset check to decide whether to skip a person, then computed the set difference of films, counted how many times each film appears, and finally sorted by count.
I finished both problems and ran the test cases, and two days later I got rejected, with no reason given.
Team 2: the interviewer was a senior engineer.
15 minutes on my resume, where they ask about some details. The last 5 minutes are for my questions.
Coding 1:
Design a class with an add function. Each call to add writes in an int and returns whether it is a duplicate, and also returns all the data entered so far in sorted order.
For example: add(2)->[new, 2] add(1)->[new, 1, 2] add(2)->[old, 1, 2]
add(3)->[new, 1, 2, 3] add(1)->[old, 1, 2, 3]
I said that in Java you could use a TreeSet, which is something like a balanced BST. In Python I didn't know there was a built-in SortedList, so I said I could implement it myself by maintaining a sorted list. I'd use bisect.bisect_left to find the insert position, check whether the element is already there, and output the sorted list after insertion. Lookup is O(log n), but insertion is O(n) in the worst case, and space is O(n), where n is the number of distinct elements.
After I finished writing, the interviewer kept saying the number of calls would be very large and questioned whether this space complexity was acceptable. I couldn't think of how to optimize it, since at minimum you have to keep the data already written. In the end I thought of using a bitmask: store it in 32 or 64 bits, where the first number like 11001... says whether 1-32 have appeared, the second number covers 33-64, and so on. But if the data written is too sparse that wouldn't necessarily be good either. The interviewer didn't say whether it was right, and in the end there was no time left to write it. I don't understand what they were actually asking for.
Discussion
Loading comments…