Stokastik

Machine Learning, AI and Programming

LeetCode : Maximum Gap

Problem Statement Solution : There were many different approaches that were coming to my mind while beginning to solve the problem, but all of them were non-linear space/time complexities. One thing that I realized was that, if there was some generic O(N) approach that enables us to find difference between any two consecutive numbers in the sorted array, then sorting the numbers itself would be linear. But that is not […]

Continue Reading →

Designing a Question-Question Similarity Framework - Part II

In this post we will look at the offline implementation. In our company, there are currently about a 100 manual agents, each serving somewhere around 60-80 customers (non-unique) a day, i.e. a total of about 8K customer queries each day for our agents. And each customer session has an average of 3 question-answer rounds including statements, greetings, contextual and personal questions. Thus on average we generate 24K QA pairs each […]

Continue Reading →

Designing a Question-Question Similarity Framework - Part I

Natural Language Question Answering system such as chatbots and AI conversational agents requires answering customer queries in an intelligent fashion. Many companies employ manual resources to answer customer queries and complaints. Apart from the high cost factor with employing people, many of the customer queries are repetitive in nature and most of the time same intents are asked in different tones.

Continue Reading →

LeetCode : Cutoff Trees for Golf

Problem Statement Solution : My solution in Python for this problem is not accepted as of yet due to "Time Limit Exceeded". There is no trick that reduces the worst case time complexity for this problem. The straightforward approach is to first sort the tree heights smallest to largest (ignoring the tree heights with height < 1) and then for each successive pair (A, B) of sorted tree heights, do […]

Continue Reading →

LeetCode : Largest Rectangle in Histogram

Problem Statement Solution : At first glance, one can say that a brute force approach would take time complexity. That is correct. Let me begin first with the brute force approach explanation. In order to find the largest rectangle possible, scan each of the unit one rectangle (i.e. the heights given in the input array) and then for each such rectangle i compute the maximum possible width it can be […]

Continue Reading →

LeetCode : Smallest Rotation with Highest Score

Problem Statement Solution : As we can see that, we can easily come up with a solution. Rotate the array each time and compute the score. There are N possible rotations for an array of size N, and for each rotated position, computing the score for the array takes O(N) time complexity. Since the approach is very easy, we will not code this approach but will explore whether we can […]

Continue Reading →

LeetCode : Dungeon Game

Problem Statement Solution : This problem is probably towards high medium difficulty level but below the hard level of problems. At one glance, one can conclude that we can solve this problem using the dynamic programming technique and it is correct. The only difficulty is in identifying what value to memoize at each step during the King's journey towards the Princess. So this is how it works. The initial health […]

Continue Reading →

LeetCode : K Inverse Pairs Array

Problem Statement Solution : One of the strong heuristics that I generally use for solving counting problems in programming is that it is most likely a dynamic programming problem and most of the cases it is true, since most such counting problems can be defined recursively. In this problem, of counting the number of k-inverse pairs in an array of size 'n' (from 1 to n) can be defined recursively. […]

Continue Reading →

Dynamic Programming in NLP - Longest Common Subsequence

In this second part of the series on my posts on Dynamic Programming in NLP, I will be showing how to solve the Longest Common Subsequence problem using DP and then use modified versions of the algorithm to find out the similarity between two strings. LCS is a common programming question asked in many technical interviews. Given two strings (sequence of words, characters etc.) S1 and S2, return the number […]

Continue Reading →

Dynamic Programming in NLP - Skip Grams

In this series of posts, I will be exploring and showing how dynamic programming technique is used in machine learning and natural language processing. Dynamic programming is very popular in programming interviews. DP technique is used mainly in problems which has optimal substructure and can be defined recursively, which means that a problem of size N can be solved by solving smaller sub-problems of size m < N. Such problems […]

Continue Reading →