Coding Problems

             Minimum number of rooms                                                       asked by Snapchat Ques. Given an array of time intervals (start, end) for classroom lectures (possibly overlapping), find the minimum number of rooms required.  For example - given [(30, 75), (0, 50), (60, 150)], you should return 2. Solution. To count the number of rooms we have to keep checking the ending time of first class and startinf time of other class. To understand the counting of rooms in given example first sort the array on the basis of starting time i.e. [(0, 50), (30, 75), (60, 150)]. So ending time of first class is greater than the starting time of second class then rooms required will be 2 and then starting time of third class is greater than ending time of first than that class can be done in first classroo...

                             Count Negative Numbers                                                        asked by Amazon Ques. Count the number of negative integers in the matrix. The matrix is given in such a way that the number of negative integers is one row is always greater than the next row. For example - [ [-3, -2, -1, 1],                                 [ -2,  2, 3, 4 ],                                  [ 4,  5,  7, 8 ]] should return 4 Solution. One naive way to solve this problem is to iterate the every row and columns and increment the count if found ...

                                Minimum Cost Required                                                        asked by Facebook Ques. A builder is looking to build a row of N houses that can be of K different colors. He has a goal of minimizing cost while ensuring that no two neighbouring houses are of same color. Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth color return the minimum cost which achieves this goal. Solution.   Suppose we have cost matrix like this - [ [2, 1, 1],   [1, 10, 3],   [1, 2, 100]  ] Each row represents the house and each column represents the color so the values are the cost of painting the color for a house. Since we know that indexes starts from 0 so cost of pain...

                                    Maximum in Subarray                                                          asked by Google Ques. Given an array of integers and a number k, where 1<= k <= length of array, compute the maximum values of each subarray of length k. For example - given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get [10, 7, 8, 8], since  10 = max(10, 5, 2) 7 = max(5, 2, 7) 8 = max(2, 7, 8) 8 = max(7, 8, 7) Solution. This question has a simple solution. In array we will create a window which consist of number of elements equal to k and can find the maximum among them and append that in output list. But while traversing the array we have to keep something very important in mind. We will not traverse from index 0 to nth index...

              First Recurring Character                                                        asked by Google Ques. From a given string return the first recurring character of the string. For example - if string is "ABCDBA" then return B and if string is "ABCD" then return None because no character is recurring. Solution. The first solution that come to our mind is that while traversing each character of string keep track of already occured character and if any character occured again then return that character. So to keep track of characters we can use dictionary or list. Lets see this -  def first_rec_char(s):     char_list = []     for i in s:          if i in char_list:               return i        ...

                  Longest Substring                                                    asked by Amazon Ques. Given an integer K and string S, find the length of the longest substring that contains at most K distinct characters. For example, given S = "abcba" and  K = 2 , the longest substring with K distinct characters is "bcb". Solution. This problem can be solved by many methods but time complexity will be high. There is a solution of O(n) time complexity. We can use the method of sliding window here. In the window it will contain the substring and it will be stable if it contains K distinct characters at any point. If window contains less than K charcaters then we expand the windw by adding more characters from the right side otherwise if window contains more than K distinct charcaters we will shrink the wi...