Coding Problems

                      Find subsets                                                    asked by Facebook Ques. Given a list of given numbers return all the possible subsets of those numbers. For example - if given numbers are [1, 2] then its subsets are [None], [1], [2], [1, 2]. Total number of subsets can be found as 2^n  where n is number of items given in the list. Solution. We know the length of given list and number of subsets are the (2^n). What we can do is that we can make lists equal to (2^n)  and length of each list will be equal to n. Now in the list we can initially set each value to 0 and for each element we traverse in the input list one time we can set the value at index equal to current element index set to current element and another time we can set it to None. In short it can b...

             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...

                                      Sum of non-adjacent                                                                               asked by Airbnb                              Ques. Given a list of integers, write a function that returns the largest sum of non-adjacent number. Numbers can be 0 or negative.  For example - [2, 4, 6, 2, 5] should return 13 since we pick 2, 6 and 5. Another list [5, 1, 1, 5] should return 10 since we pick 5 and 5. Solution.  In this problem we can not take the two contniuous inetgers means adjacents. Think about it like this if we have 1 element in ...

        Lowest Missing Positive Integer                                                                           asked by Stripe Ques. Given an array of integers, find the first missing positive integer in the linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well. For example - the input [3, 4, -1, 1] should give 2 and input [1, 2, 0] should give 3. Solution.   This problem can be solved by many ways but here we have to keep in mind about the contraints of complexity. We can not use extra space and time can not be more than O(n).  What we can do here ? Well there is an idea. Firstly we separate out positive and negative integers in the array and we can ...

           Product of elements of Array                                                           asked by Uber Ques. Given an array of integers, return a new array such that each element at index i of new array is the product of all the numbers in the original array except that one at i. For example, if our input was [1, 2, 3, 4, 5] then the expected output would be [120, 60, 40, 30, 24]. If input is [3, 2, 1] then the expected output would be [2, 3, 6]. Solution. We need to multiply all the elements of array except the one on the index at which we are currently. At index one we will multiply all the elements except the one at index 1. There can be many ways to solve this and different complexities. We can traverse the array two times using nested for loops. Lets see how- inp = [1, 2, 3, 4, 5]      ...

             Sum of Numbers in List                                                      asked by Google Ques. Given a list of numbers and a integer K return whether any two numbers from the list will add upto K or not. For example - Given list is [10, 15, 3, 7] and K = 17, then return True because 10 + 7 = 17. Solution.   So basically we have to find the two numbers that are present in the list and sum of both is equal to K. So we can simply run two loops on the list and check each pair of number if they are equal to K or not. This method is Brute-force and complexity is O(n^2). What we can do here is run the loop over the list and then subtract that number from the target and check whether the remaining number is present in the list or not. Lets see the code  def find_numbers(inp_list, K):    ...