Facebook Interview Question: given a list of tuples of mov... | Glassdoor

Interview Question

Data Engineer Interview Menlo Park, CA

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.
Tags:
de interview q
Answer

Interview Answer

9 Answers

1

Looking 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;
    }

aonecode.com on Aug 23, 2017
0

Can you forward the questions asked onsite. I have an onsite in 2 weeks. sudheernew1234@gmail.com

Sudh on Sep 11, 2017
0

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)

Ish on Sep 27, 2017
1

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

Face Book on Nov 5, 2017
0

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)

Sam on Jun 19, 2018
0

Ignore my previous answer. I wasn't paying attention to the cases where two tuples overlap in terms of the time range.

Sam on Jun 19, 2018
0

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!

Anonymous on Jul 26, 2018
0

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

Anonymous on Oct 1, 2018
0

input=[(0,9),(0,10),(1,9)]

l=[]
for i in input:
 l.append(i[0])
 l.append(i[1])

print(len(set(l)))

Anonymous on Oct 1, 2018

Add Answers or Comments

To comment on this, Sign In or Sign Up.