Coding Problem 12

-
             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 classroom so number of rooms required are 2.
So to solve this problem the main idea is to take two array first one will store the starting time only and second one will store the ending time. Now we will sort both of them and then keeo checking the value which one is greater. If ending time is more than we will increse the number of rooms and go to the next starting time otherwise we will reduce the number of rooms and go to the next ending time. Lets see how-

input = [(30, 75), (0, 50), (60, 150)]
start = [30, 0, 60]   --> after sorting , start = [0, 30, 60]
end = [75, 50, 150]   ---> after sorting, end = [50, 75, 150]

we will start from the first indexes of both lists let i = 0 and j = 0 and count = 0
i=0, j=0, count=0
start[i] < end[j]    ,then count = 1, i = 1

i=1, j=0, count=1
start[i] < end[j]    ,then count = 2, i = 2

i=2, j=0, count=2
start[i] > end[j]    ,then count = 1, j = 1

i=2, j=1, count=1
start[i] < end[j]    ,then count = 2, i = 3 (greater than list length and loop finishes here)

so maximum rooms are = 2

Now lets code this - 

input_list = [(30, 75), (0, 50), (60, 150)]

start = []
end = []

for i in input_list:
    start.append(i[0])
    end.append(i[1])

start.sort()
end.sort()

i = j = 0
temp_room = room = 0
n = len(input_list)

while i < n and j < n:
    if start[i] < end[j]:
        temp_room += 1
        room = max(room, temp_room)
        i += 1
    else:
        temp_room -= 1
        j += 1

print("Rooms required are: {0}".format(room))

Output: Rooms required are: 2

Comments

Post a Comment

Popular posts from this blog

Coding Problem 10

-
Image
                                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...
Read more

Coding Problem 3

-
             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):    ...
Read more

Coding Problem 9

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