Q1: A single processor system has some process scheduled, with some startTime and Duration. given a new process can we schedule it with out removing some pre-scheduled process. I shared BS based approach Interviewer asked me to implement it I did, she asked me to use lower_bound instead of actually implementing BS. She asked me to find some bugs in the code. I found and fixed one. Then she pointed another one, i fixed that too. Then she asked me to write the time and space complexity. Q2. After that she asked a follow up saying that now the computer has 4 processors, how will we check if a new process can be scheduled to any of the processsor? I shared an approach involving cordinate compressing the start and end time, then making an array and intializing it with 0, then for each process doing arr[start]++, arr[end+1]--. where start and end are the compressed representation of original values. then it told that i would build a segment tree to find the range. And finally I told her that i'll find the smalles interval containing our process from the compressed co-ordinates using Binary Seach then i'll find the range max in that range if it is 4 then we can't schedule the process else we can. She didn't ask me to code this But told me to write the time and space complexity of my solution. Overall the round went pretty well. 2nd: Coding He told me a bit about himself and asked me to describe my thesis project. After that he told me to open the coding doc and started asking questions. Q1: The interview told me to find no. of ways to make 'K' non-empty set from 'N' unique objects. He gave some sample like 1, 1 -> 1; 3, 2 -> 1; 4, 2 -> 2. Seeing the samples it was pretty clear that the objects are not unique. When i pointed that out and asked the interview that is this problem equivalent to the no. of ways we can fill N identical balls into K identical bags such that each has atleast one ball? To which he replied yes, He was not thorough with the problem himself. I asked him about the range of N to which he replied 1 < N <= 1e6, K <= N I dropped the idea of any DP based solution and started focusing on solving this using PnC. But the interview told me to come up with a reccurence relation, I was really drawing blank at that point and told him that even if we find a relation in terms of N, K we would have N x K states. I failed to find any correct recurrence relation. and the interviewer also told me to forget this and moved on to the next question. After the round i found the relation online. Q2: There's a directed graph find the shortest cycle from a source node. I told a dfs based solution using the standard cycle finding algorithm and storing length of cycle whenever we encounter one and returning the min value. He told me do write the time and space complexity of my solution He told me to imporve my complexity, i was drawing blank. He suggested to use BFS. I agreed and wrote the time complexity for that as well The he asked me to code the solution but now i have to return the nodes of the shortest cycle starting from the source. I coded the BFS and kept parent array to retrive the nodes of the cycle when we found it. After this he asked me to ask any question that i had, i did, he answered. interview ended. Overall this round could have gone better, I thought 1st question was really hard. The HR called me and said that i have a 3rd round and it is a deal breaker. 3rd: Coding The interviewer told me about himself, his work. and asked me to introduce myself, after which we moved staraight to the interview. Q1: Given a 2D matrix, The cost to move to an adjacent cell(4 direction, up, left, down, right) is defined as the absolute difference between the values in the cell. A path's cost is defined as the maximum cost of any step taken to traverse that path. Given a cost find if we can move from top-left to bottom-right in cost less or equal to that. I told and implemented a BFS based solution, he asked me to write the time and space complexity. Q2: Follow up to the first question find the least cost to go from top left to bottom right. I told him that if we plot a graph of cost vs is_possible in the last problem, it would be like step funtion's graph and the inflection point would be our answer. And we can find the inflection point using Binary Search. He agreed. I coded the solution using the function in the previous question as the check function. He asked me to do the TC, Space analysis, I did. I solved these 2 questions pretty quickly so he decided to ask another one.