# Stokastik

## Leetcode : Remove Duplicate Letters Problem Statement Solution: The problem looks to be easy on the outside but gets 'tricky' when we have to find the smallest possible string (alphabetically) with all unique letters. Removing duplicates is a very common problem that we usually encounter in our day to day software engineering. But in most use-cases it is sufficient to remove any one of the duplicates (first, last or randomly picked). Let's analyze the brute […]

## Leetcode : Minimum Cost To Merge Stones Problem Statement Solution: It might be 'tempting' to think that the problem can be solved using a greedy approach, i.e. merge the K consecutive stones with the minimum cost in each step. But the greedy approach is not optimal, for e.g. if the stones array is [6,4,4,6] and K=2, then the greedy approach would result in a minimum cost of 42 whereas the optimal cost is 40. The greedy approach […]

## Designing large scale similarity models using deep learning Finding similar texts or images is a very common problem in machine learning used extensively for search and recommendation. Although the problem is very common and has high business value to some organisations, but still this has remained one of the most challenging problems when the database size is very large such as >50GB and we do not want to lose on precision and recall much by retrieving only 'approximately' […]

## Leetcode : The Skyline Problem 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 […]

## Leetcode : Sliding Window Median 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).

## Leetcode : Consecutive Numbers Sum Problem Statement Solution: The brute force approach is to evaluate all possible sequence of consecutive numbers less than N, whose sum gives N. The number of all possible sequences of consecutive numbers less than N is O(N2), because we can select pair of indices i and j (i <= j) such that the sequence lies between i and j. The number of such pairs is O(N2). We can definitely improve […]

## Leetcode : Non-negative Integers without Consecutive Ones Problem Statement Solution: The brute force approach is to scan all the integers less than equals to N, compute their binary representation and check if the binary representation has consecutive ones or not. The run-time complexity of this approach is O(N*logN) because scanning all the integers less than N is O(N) and scanning the binary representation for each integer is O(logN), because binary representation of an integer M is of […]

## Leetcode : K-Similar Strings Problem Statement Solution: The brute force approach is to evaluate all possible swaps. Given the string is of length N, the number of possible pairs is U=0.5*N*(N-1). But observe that not just the swaps but the sequence of swaps also matters. The number of possible sequence of swaps is U!. Thus the run-time complexity is O(U!). For moderately sized value of N such as 20 as given by the problem […]

## Leetcode : Reverse Pairs Problem Statement Solution: The brute force approach is to consider all pairs (i, j) such that i < j and check whether they satisfy the condition that nums[i] > 2*nums[j]. The time complexity for this approach is definitely O(N2) where N is the number of elements in the array 'nums'. We can improve this time complexity by reducing the number of comparisons required for each element. For e.g. if we […]

## Detecting placeholder images in e-Commerce product listings Many times we trust sellers to upload correct product images for online products on our e-commerce platform, but due to checks in place that a product shall always accompany an image, 3rd party sellers upload stock or placeholder image in case there is no image for the product available. Problem is that although we do not want to show products without images on our website, but due to zero validation […]