Problem Statement Solution : One approach that uses O(n) extra space, is to store for each node N, the pointer to the nodes with minimum and maximum values in the sub-tree rooted at N. Let's denote the minimum node rooted at N by N.min and the maximum node by N.max. Then for a sub-tree rooted at N, the sub-tree has a "defect", if : N.val < N.left.max.val and/or N.val > N.right.min.val […]
Problem Statement Solution : Observe that one can switch from one route to another route, if both the routes have at-least one stop in common. Starting with the source stop S, there could be multiple possible bus routes R that includes this stop. Thus for every possible route R that include the stop S, do a Breadth First Search to all possible routes R' reachable from this route. R' can […]
This post is motivated from trying to find better unsupervised vector representations for questions pertaining to the queries from customers to our agents. Earlier, in a series of posts, we have seen how to design and implement a clustering framework for customer questions, so that we can efficiently find the most appropriate answer and at the same time find out most similar questions to recommend to the customer.
In this series of posts we will be looking to design a cab hailing service similar to Uber or Ola (in India). We will be mainly concerned about the technical design and challenges and not get into the logistics such as signup and recruitment of drivers, training drivers for customer satisfaction, number of cabs on street and so on. Even for the technical design, we will omit some of the […]
Problem Statement Solution : A simple brute force approach would require for each pair of points in the matrix, whether the points form the top left and bottom right corner of a rectangle (all 1's) and compute its area. Since there are O(N2) points, thus there are O(N4) pairs of points. Checking whether there is a rectangle between them and computing its area takes O(N2) comparisons. Thus the total run-time is O(N6), […]
In continuation of my earlier posts on designing an automated question-answering system, in part three of the series we look into how to incorporate feedback into our system. Note that since getting labelled data is an expensive operation from the perspective of our company resources, the amount of feedback from human agents is very low (~ 2-3% of the total number of questions). So obviously with such less labelled data, […]
This post is branched from my earlier posts on designing a question-question similarity system. In the first of those posts, I discussed the importance of speed of retrieval of most similar questions from the training data, given a question asked by a user in an online system. We designed few strategies, such as the HashMap based retrieval mechanism. The HashMap based retrieval assumes that at-least one word between the most […]
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 […]
In this post we will look at the offline implementation architecture. Assuming that, 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 5 question-answer rounds including statements, greetings, contextual and personal questions. Thus on average we generate 40K client-agent response pairs […]
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.