given a list of tuples of movie watched times, find how many unique minutes of the movie did the viewer watch e.g. [(0,15),(10,25)]. The viewer watched 25 minutes of the movie. 10 AnswersLooking for interview experience sharing and coaching? Visit aonecode.com for private lessons by FB, Google and Uber engineers Our ONE TO ONE class offers SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U) ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding), latest interview questions sorted by companies, mock interviews. Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training. Feel free to email us aonecoding@gmail.com with any questions. Thanks! Two solutions: O(1) Space O(NlogN) time Method: Sort the intervals by start time and merge intervals public int mergeIntervals(int[][] array) { Arrays.sort(array, (int[] o1,int[] o2)-> (o1[0] - o2[0])); int start = 0, end = 0, sum = 0; for(int[] interval: array) { if(interval[0] > end) { sum += end - start; start = interval[0]; end = interval[1]; } else { end = Math.max(interval[1], end); } } sum += end - start; return sum; } O(X) Space O(N) time Solution: Create array of size MAX(time) - MIN(time) to keep track of whether someone watched the movie at the ith unit of time. This only works if the intervals are not in a huge time span. public int sumIntervals(int[][] array) { int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; for(int[] interval: array) { if(min > interval[0]) min = interval[0]; if(max < interval[1]) max = interval[1]; } boolean[] inUse = new boolean[max - min + 1]; int sum = 0; for(int[] interval: array) { int end = interval[1] - min; for(int i = interval[0] - min; i <= interval[1] - min; i++) { if(!inUse[i]) { inUse[i] = true; sum++; } } } return sum; } Can you forward the questions asked onsite. I have an onsite in 2 weeks. sudheernew1234@gmail.com t = [(0, 10), (15, 25), (12, 20), (30, 48)] t = sorted(t) tol = t[0][1] - t[0][0] for i in range(len(t) - 1): if t[i+1][0] > t[i][1]: tol += t[i+1][1] - t[i+1][0] else: tol += t[i+1][1] - t[i][1] print(tol) Show More Responses Hello Dear, It will be a great help if you could share more details on the onsite interview experience to following email address: facebook.data.engineering@gmail.com Regards, An aspirant looking for your help t = [(0, 10), (15, 25), (12, 20), (30, 48)] total = 0 for i in t: total = total + i[1]-i[0] print("total time watched:" , total) Ignore my previous answer. I wasn't paying attention to the cases where two tuples overlap in terms of the time range. Can you please share your onsite or type of ETL/Design que on - meggieanderson1992@gmail.com. Much appreciated in advance as it would be really helpful for my prep in 2 weeks! input=[(0,9),(0,10),(1,9)] l=[] for i in input: l=l.append(i[0]) l=l.append(i[1]) print(len(set(l))) input=[(0,9),(0,10),(1,9)] l=[] for i in input: l.append(i[0]) l.append(i[1]) print(len(set(l))) Could you please send some onsite questions or preparation experience to: jamesnikess@gmail.com I have a DE onsite in 2 weeks. Hugely appreciate your help! |