Stokastik

Machine Learning, AI and Programming

Leetcode : Longest Duplicate Substring

Problem Statement Solution: The brute force approach for this problem would be to scan for all substrings of length L for each possible value of L from 1 to N-1. Store the substrings in a set() and whenever we encounter a substring which is already present in the set then it is a duplicated substring of length L. Repeat this for all L until we find some L' for which […]

Continue Reading →

Leetcode : Redundant Connections 2

Problem Statement Solution: The brute force approach for this problem would be to do a DFS or BFS starting from each node after removing edge Ei in the input 'edges' array. At each position i from right to left, after removing Ei, do BFS from each node in the graph. If for BFS from any node, we cover all the nodes from 1 to N without any cycle, then return […]

Continue Reading →

Leetcode : Course Schedule 3

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 […]

Continue Reading →

Leetcode : Design O(1) data structure for insertion, deletion and get random

Problem Statement Solution: It is pretty obvious that O(1) insertion and removal can be designed using a Set or Hash-Map or a Doubly Linked List. When duplicates are prohibited, using a Set() data structure is very convenient, but when duplicates are allowed we cannot use Set. Instead we can use Hash-Map. The key of the Hash-Map are the unique integers while the values are the count of each integer. While […]

Continue Reading →

Fast Nearest Neighbour Search - Product Quantization

In this on-going series of fast nearest neighbor search algorithms, we are going to look at Product Quantization technique in this post. In the last post, we had looked at KD-Trees, which are effecient data structures for low dimensional embeddings and also in higher dimensions provided that the nearest neighbor search radius is small enough to prevent backtracking. Product Quantization or PQ does not create any tree indexing data structure […]

Continue Reading →

Leetcode : Cutoff Trees for Golf

Problem Statement Solution : There is no trick that reduces the worst case run-time complexity for this problem. The brute-force approach is to first sort the tree heights from lowest to highest (ignoring the tree heights with height < 1) and then for each successive pair (A, B) of sorted tree heights, do a BFS from A to B and compute the minimum length path required to travel from A […]

Continue Reading →

Leetcode : Self Crossing

Problem Statement Solution: The brute force approach would be to store the starting and the ending co-ordinates for each line segment in an array A and then for the current segment, check if it intersects or "touches" any one of the previous line segments present in the array A. The run-time and space complexity of this approach is O(N2) where N is the number of line segments. Can we do […]

Continue Reading →

Leetcode : Number of digit one

Problem Statement Solution: The brute force approach would be iterate through all numbers from 0 to N and then for each number count the number of 1's and add them up. For a number N, the number of digits it contains is O(log10N). Thus the brute force approach has a time complexity of O(N*log10N). Can we do better than this ? The proposed solution achieves a O(log10N) run-time complexity. The […]

Continue Reading →

Fast Nearest Neighbour Search - KD Trees

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 […]

Continue Reading →

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 […]

Continue Reading →