Problem Statement Solution: It was actually difficult for me to come up with the brute force approach to solve the skyline problem. But that does not mean that getting to the efficient solution was easy. I struggled a lot in order to come to the efficient solution because there were so many scenarios that I was missing out on initially. Coming to think of it, the brute force approach would […]
Tag: Min Heap
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: Most of us must have encountered a similar problem of finding the maximum number of valid parentheses pairs, which is pretty straightforward and quite commonly asked in many programming interviews. This is one variant where we need to find the longest sub-string which is a valid parentheses. The sub-string may contain any number of parenthesis pairs. One naive approach is to check for all pair of indices […]
In the last post we saw how we can use Cython programming language to boost speed of Python programs. For a simple program like finding primes upto a certain N, we obtained a gain of around 50-60x with Cython as compared to a naive Python implementation. This is significant when we are going to deploy our codes in production. A complex system will have multiple such programs calling each other […]