Stokastik

Understanding class activation maps with product color classification In this post we are going to understand class activation maps or CAMs for visualising convolution neural nets by building a color classification model for e-commerce product images. The product images are tagged with the actual product color. Ideally a product image can have more than one color and it should be tagged with all the possible colors in the image, but to make the problem a bit simpler just […]

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

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

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

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

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

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

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

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

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