Count Passing Car Pairs
In this week’s blog, let’s talk about a Bloomberg first-round interview question. Recently a friend of mine got an offer from Bloomberg as a software engineer; therefore, I want it to test my technical skill and write a blog about it. In this blog, let’s focus on the first round, and for the later rounds of the interview questions, we can do it other times for other blogs.
Here is the question:
Intuition
The most simple/naive way to solve this question is to check each of the ‘0’ cars that pass through ‘1’ cars from the left to right index of the array. However, this is not efficient at all. The better/efficient way of approaching this question is a greedy method. Instead of looking from left to right, we can check from the opposite side from right to left. Let’s say we are in cars of ‘0’ traveling to the east. We can check each of our cars ‘0’ that passes through car ‘1’. On the other hand, we can also traverse from right to left with the same approach, but with the perspective that we are in car ‘1’. If this sounds confusing, let’s look into the implementation.
Implementation
The naive way of solving this question would have two nested loops. The first loop searches for a ‘0’ and the second for loop searches for ‘1’s after ‘0. Count how many cars that meet the condition and return the total count of those cars.
The better way (greedy approach), we can traverse the array once with two counters. Let’s start from right to left, traversing the array; we can track how many 1s from right to left. Whenever we meet a 0, we increment the count of cars by the count of 1s.
Vice Versa
Time & Space Complexity
The naive solution of time complexity is O(n²) and the greedy approach of time complexity is O(n). Both space complexity is O(1).
Thanks for reading my article. If you enjoyed what you read, consider connecting or dropping me a line at osgood1024@gmail.com.
