Problem Statement Solution: An obvious brute force approach is to enumerate all possible scenarios i.e. all possible valid sequence of courses and take the answer as the sequence with the maximum length. For an input size of N and a sequence of length M, the number of possible sequences is exponential in N i.e. NM. Obviously this is a bad choice, but can we think of a better solution. We […]
Tag: Max Heap
In a few of my earlier posts "designing Q&A retrieval system" and "designing e-commerce system for similar products using deep learning", one of the primary goals was to retrieve the most similar answers (responses) and the most similar e-commerce products respectively in a fast and scalable way. The later post was pretty much generic i.e. find dense representations for each item (questions, product images etc.) using un-supervised and supervised learning […]
Problem Statement Solution: The brute force approach to solve this problem is to sort the numbers in each window and then compute the median for each window. Since there are K numbers in each window, thus the run-time complexity of the brute force approach is O(N*K*logK) because, there are N-K windows and sorting each window is O(K*logK).
Problem Statement Solution: At first, this looks like a classic graph traversal problem. For example, I might be tempted to use BFS approach to find the minimum number of steps to reach the target. But one important distinction this problem has from a standard BFS is that in a standard BFS problem, the car can either directly reach a station Y from station X or they cannot depending whether there […]