Facebook Interview Question for Software Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

void merge(vector<pair<int,int> > &res, const pair<int,int> &toMerge){
    if(res.empty() || toMerge.first > res.back().second){
        res.push_back(toMerge);
    }else{
        res.back().first = min(res.back().first,toMerge.first);
        res.back().second = max(res.back().second,toMerge.second);
    }
}

vector<pair<int,int> > mergeIntervals(const vector<pair<int,int> > &l1, const vector<pair<int,int> > &l2){
    vector<pair<int,int> > result;
    for(int i = 0,j = 0; i < l1.size() || j < l2.size();){
        if(i == l1.size()){
            merge(result,l2[j++]);
        }else if(j == l2.size()){
            merge(result,l1[i++]);
        }else{
            if(l1[i].second < l2[j].first){
                merge(result,l1[i++]);
            }else if(l2[j].second < l1[i].first){
                merge(result,l2[j++]);
            }else{
                merge(result,{min(l1[i].first,l2[j].first),max(l1[i].second,l2[j].second)});
                i++;
                j++;
            }
        }
    }

    return result;
}

- Guy November 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private List<int[]> mergeIntervals(List<List<int[]>> list) {
        List<int[]> result = new ArrayList<>();
        List<int[]> intervals = new ArrayList<>();
        for(List<int[]> item : list) {
            for(int[] i : item) {
                intervals.add(i);
            }
        }
        Collections.sort(intervals, new Comparator<int[]>(){
           public int compare(int[] a, int[] b) {
               return a[0] - b[0];
           } 
        });
        int[] period = new int[]{intervals.get(0)[0], intervals.get(0)[1]};
        for(int i=1; i<intervals.size(); ++i) {
            if(period[1] >= intervals.get(i)[0]) {
                if (intervals.get(i)[1] > period[1])
                    period[1] = intervals.get(i)[1];
            } else {
                result.add(period);
                period = new int[]{intervals.get(i)[0], intervals.get(i)[1]};
            }
        }
        result.add(period);
        return result;
    }

- Popeye November 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is quite clever and is elegant in its simplicity and robustness: it can handle not just two lists as inputs, but arbitrarily many.

The caveat may be for larger lists. Since it makes an additional copy of the inputs and then performs a preliminary sort, there's additional memory overhead and the performance is constrained by the sorting step which is generally limited to O(n log(n)). For smaller datasets this is not a problem.

Making use of the fact that the inputs are sorted, we can achieve O(n) performance since we can traverse the inputs in-order and do a single pass and also perform a O(n) comparisons (with a slightly larger coefficient). Again, this would only matter for larger inputs.

Also, while this can be done with arbitrarily many input lists, so long as all are sorted, there's more effort involved in doing the comparisons and internal "bookkeeping" so, to keep it simple, I opted for the two-list input as stated. Finally, the problem doesn't explicitly state it, but I assume that each individual input list does not contain any overlapping intervals - that is, each list's intervals are already disjoint and we're merging to create a single list with any cross-list overlapping ranges merged, but no need to merge ranges within a single list. (We could add a pre-processing step to handle the case of overlapping intervals in the inputs.)

In Java this is:

package com.ezraepstein.careercup.fb;


import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
import java.util.StringJoiner;

public class MergeIntervals {

  private static boolean isInRangeInclusive(int[] r, int x) {
    return r[0] <= x && x<= r[1];
  }

  /**
   * Extends the range (r) based on the ranges in the takeFrom list.
   * @param r the current range
   * @param takeFrom sorted list of ranges to examine
   * @param idx current index into the list of ranges being examined
   * @return the new index value.
   */
  private static int coalesceIntervals(int[] r, List<int[]> takeFrom, int idx) {
    while (idx < takeFrom.size() && isInRangeInclusive(r, takeFrom.get(idx)[0])) {
      r[1] = Math.max(r[1], takeFrom.get(idx)[1]);
      ++idx;
    }

    return idx;
  }

  /**
   * Merge two lists of ordered (sorted) disjoint ranges to create a single such list.
   * <p>
   *   The input lists must be sorted ascending with only disjoint ranges.  This function does not
   *   check and so no guarantees are made if invalid data are provided.
   * </p>
   *
   * @param lh the first input list (aka, the "left-hand" list to be merged)
   * @param rh the secong input list (aka, the "right-hand" one)
   * @return the combined list of contiguous ranges.
   */
  public static List<int[]> mergeIntervals(final List<int[]> lh, List<int[]> rh) {
    List<int[]> result = new ArrayList<int[]>(Math.max(32, lh.size()));

    int i = 0, j = 0;                     // indices into lh and rh, respectively
    int[] r;                  // the current range, will be assigned in the loop
    // move along both lists, taking from whichever has the smaller starting range at the current indices.
    while (i<lh.size() && j<rh.size()) {
      if (lh.get(i)[0] <= rh.get(j)[0]) {
        r = lh.get(i++);
        j = coalesceIntervals(r, rh, j);
      } else {
        r = rh.get(j++);
        i = coalesceIntervals(r, lh, j);
      }

      result.add(r);
    }

    // may have only finished taking items from one list, so check that and copy as needed
    if (i < lh.size()) {
      result.addAll(lh.subList(i, lh.size()));
    } else if (j < rh.size()) {
      result.addAll(rh.subList(j, rh.size()));
    }

    return result;
  }

  static String intListArrayAsString(List<int[]> l) {
    final StringJoiner sj = new StringJoiner(", ");
    l.forEach(x -> sj.add(Arrays.toString(x)));
    return sj.toString();
  }

}

tested via:

package com.ezraepstein.careercup.fb;


import org.junit.Test;

import java.util.Arrays;
import java.util.List;

public class MergeIntervalsTest {
  
  @Test
  public void coalesceIntervals() {
    List<int[]> lh = Arrays.asList(new int[]{1,2}, new int[]{3,9});
    List<int[]> rh = Arrays.asList(new int[]{4,5}, new int[]{8,10}, new int[]{11, 12});

    System.out.println("List 1: " + MergeIntervals.intListArrayAsString(lh));
    System.out.println("List 2: " + MergeIntervals.intListArrayAsString(rh));


    final List<int[]> result = MergeIntervals.mergeIntervals(lh, rh);

    System.out.println("O/P:    " + MergeIntervals.intListArrayAsString(result));
  }
}

with output:

List 1: [1, 2], [3, 9]
List 2: [4, 5], [8, 10], [11, 12]
O/P:    [1, 2], [3, 10], [11, 12]

Process finished with exit code 0

- ezra.epstein November 13, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The assignments to the local variable "r" should be via copy to avoid modifying the inputs:

r = Arrays.copyOf(lh.get(i++), 2);

- ezra.epstein November 13, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

solution in C
1. build sorted array of all starting points and another array for all ending points then
2. use following algorithm to build result array
// create sorted array first

while(i<array_size && j<array_size)
	{
		result[cnt][0] = start_point[i++];
		
		while(end_point[j] > start_point[i])
		{
			i++; j++;				
		}
		result[cnt][1] = end_point[j++];
		cnt++;			
	}

- ssonsue1 November 13, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[][] mergeInterval(int[][] list1, int[][] list2) {
        int maxLen = (list1.length >= list2.length ? list1.length : list2.length);

        int[][] result = new int[maxLen][2];
        for(int i = 0; i < maxLen; i++) {
            if(list1.length <= i){
                result[i] = list2[i];

            } else if(list2.length <= i) {
                result[i] = list1[i];
            } else {
                int startA = list1[i][0];
                int startB = list2[i][0];
                int endA = list1[i][1];
                int endB = list2[i][1];

                result[i][0] = (startA < startB ? startA : startB);
                result[i][1] = (endA > endB ? endA : endB);
            }
        }

        return result;
    }

- Anonymous November 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[][] mergeInterval(int[][] list1, int[][] list2) {
        int maxLen = (list1.length >= list2.length ? list1.length : list2.length);

        int[][] result = new int[maxLen][2];
        for(int i = 0; i < maxLen; i++) {
            if(list1.length <= i){
                result[i] = list2[i];

            } else if(list2.length <= i) {
                result[i] = list1[i];
            } else {
                int startA = list1[i][0];
                int startB = list2[i][0];
                int endA = list1[i][1];
                int endB = list2[i][1];

                result[i][0] = (startA < startB ? startA : startB);
                result[i][1] = (endA > endB ? endA : endB);
            }
        }

        return result;
    }

- Kevin Chun November 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[][] mergeInterval(int[][] list1, int[][] list2) {
        int maxLen = (list1.length >= list2.length ? list1.length : list2.length);

        int[][] result = new int[maxLen][2];
        for(int i = 0; i < maxLen; i++) {
            if(list1.length <= i){
                result[i] = list2[i];

            } else if(list2.length <= i) {
                result[i] = list1[i];
            } else {
                int startA = list1[i][0];
                int startB = list2[i][0];
                int endA = list1[i][1];
                int endB = list2[i][1];

                result[i][0] = (startA < startB ? startA : startB);
                result[i][1] = (endA > endB ? endA : endB);
            }
        }

        return result;
    }

Test code is below

@Test
    public void test_mergeArrayInterval() {
        int[][] list1 = new int[][] {{1,2}, {3,9}};
        int[][] list2 = new int[][] {{4,5}, {8, 10}, {11, 12}};

        int[][] result = new ArrayIntervalMerge().mergeInterval(list1, list2);
        for(int i = 0; i < result.length; i++) {
            System.out.println(Arrays.toString(result[i]));
        }
    }

And result is

1, 5]
[3, 10]
[11, 12]

- Kevin Chun November 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This obviously doesn't work

- Levi November 15, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It's trickier than it seems:
Swift

class Sequence {
    let a: [[Int]]
    let b: [[Int]]
    
    var ia = 0
    var ib = 0
    init(a: [[Int]], b: [[Int]]) {
        self.a = a
        self.b = b
    }
    
    func getNext() -> [Int]? {
        let r1 = ia < a.count ? a[ia] : nil
        let r2 = ib < b.count ? b[ib] : nil
        if let r1 = r1, let r2 = r2 {
            if r1[0] <= r2[0] {
                ia += 1
                return r1
            } else {
                ib += 1
                return r2
            }
        } else {
            if let r1 = r1 {
                ia += 1
                return r1
            }
            if let r2 = r2 {
                ib += 1
                return r2
            }
        }
        return nil
    }
    
}

func isIntersect(a:[Int], b:[Int]) -> Bool {
    if a[0] < b[0] {
        return a[1] >= b[0]
    } else {
        return b[1] >= a[0]
    }
}

func mergeSequences(a: [[Int]], b: [[Int]]) -> [[Int]] {
    var result: [[Int]] = []
    let s = Sequence(a: a, b: b)
    var woking = s.getNext()
    if woking != nil {
        while woking != nil {
            let next = s.getNext()
            if let next = next {
                if isIntersect(a: woking!, b: next) {
                    woking = [min(woking![0],next[0]), max(woking![1], next[1])]
                } else {
                    result.append(woking!)
                    woking = next
                }
            } else {
                result.append(woking!)
                woking = nil
            }
        }
    }
    return result
}

print(mergeSequences(a: [[1, 2], [3,9]], b: [[4,5], [8,10], [11, 12]])) // [[1, 2], [3, 10], [11, 12]]

print(mergeSequences(a: [[1, 2], [7,9]], b: [[4,5], [8,10], [11, 12]])) // [[1, 2], [4, 5], [7, 10], [11, 12]]

print(mergeSequences(a: [[1, 4], [7,9], [8,11]], b: [[4,5], [11, 12]])) // [[1, 5], [7, 12]]

- eugene.kazaev November 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java 8 solution:

List<List<Integer>> exo(List<List<Integer>> a, List<List<Integer>> b) {
        a.addAll(b);
        Collections.sort(a, (l1, l2) -> l1.get(0).compareTo(l2.get(0)));

        for (int i = 0; i < a.size(); i++) {
            for (int j = i + 1; j < a.size(); j++) {
                if (a.get(i).get(1) < a.get(j).get(0)) {
                    continue;
                }
                if (a.get(i).get(1) > a.get(j).get(1)) {
                    a.remove(j);
                } else {
                    a.get(i).set(1, a.get(j).get(1));
                    a.remove(j);
                }
                j--;
            }
        }

        return a;
    }

- Benyoucef.Hakim November 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int[][] merge2(int[][] a1, int[][] a2){
		Integer[][] combined = combine(a1, a2);
		List<Integer[]> ret = new ArrayList<>();
		ret.add(combined[0]);
		Integer[] lastInsert = ret.get(0);
		for(int i=1; i< combined.length; i++) {
			if(combined[i][0] <= lastInsert[1]
					&& combined[i][1] > lastInsert[1]) {
				lastInsert[1] = combined[i][1];
			}else if(combined[i][1] < lastInsert[1]) {
				continue;
			}else {
				ret.add(combined[i]);
			}
			lastInsert = ret.get(ret.size()-1);
		}
		int[][] y = new int[ret.size()][];
		for(int n=0; n<ret.size(); n++) {
			int[] m = {ret.get(n)[0], ret.get(n)[1]};
			y[n] = m;
		}
		return y;
	}
	
	private static Integer[][] combine(int[][] a1, int[][] a2){
		Integer[][] combined = new Integer[a1.length + a2.length][];
		int c_idx = 0;
		int i1 = 0, i2 = 0;
		
		while(i1 < a1.length && i2 < a2.length) {
			if(a1[i1][0] <= a2[i2][0]) {
				Integer[] x = {a1[i1][0], a1[i1][1]};
				combined[c_idx] = x;
				i1++;
			}else {
				Integer[] x = {a2[i2][0], a2[i2][1]};
				combined[c_idx] = x;
				i2++;
			}
			c_idx++;
		}
		
		if(i1 < a1.length) {
			for(int k=i1; k<a1.length; k++) {
				Integer[] x = {a1[k][0], a1[k][1]};
				combined[c_idx] = x;
				c_idx++;
			}
		}
		if(i2 < a2.length) {
			for(int k=i2; k<a2.length; k++) {
				Integer[] x = {a2[k][0], a2[k][1]};
				combined[c_idx] = x;
				c_idx++;
			}
		}
		return combined;
	}

- silas.kaggwa November 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public ArrayList mergeIntervals(List list1, List list2){
		
		
		int len1 = 0;
		int len2 = 0;
		int max = 0;
		
		ArrayList<int[]> finalArray = new ArrayList<int[]>();
		
		while(max < list1.size()+list2.size()){
			
			
		if(len1 ==  list1.size() ||  len2 == list2.size()){
			
			for(int i = len1; i < list1.size() ; i ++){
				finalArray.add((int[])list1.get(len1));
				len1++;
			}
			
			for(int i = len2; i < list2.size() ; i ++){
				finalArray.add((int[])list2.get(len2));
				len2++;
			}
		} else{
			
			
		int[] array1 = (int[])list1.get(len1);
		int[] array2 = (int[])list2.get(len2);
		int[] result = new int[2];
		
		if(array1[0] <= array2[0]){
			result[0] = array1[0];
			
			if(array2[0] >= array1[0] && array2[0] <= array1[1] ){
				
				if(array1[1] >= array2[1]  ){
					result[1] = array1[1];
					
				}else{
					result[1] = array2[1];
				}
				
				
				len2++;
			}else{
				result[1] = array1[1];
			}
			len1++;
			finalArray.add(result);
		}else {
			result[0] = array2[0];
			
			if(array1[0] >= array2[0] && array1[0] <= array2[1] ){
				
				if(array1[1] >= array2[1]  ){
					result[1] = array1[1];
					
				}else{
					result[1] = array2[1];
				}
				
				
				len1++;
			}else{
				result[1] = array2[1];
			}
			len2++;
			finalArray.add(result);
			
		}
			
		}
		max = len1+len2;
		}
		
		
		return finalArray;
	}

- kamal.hasanjk November 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One kind of easy solution is check all numbers which within between minimum and maximum.

for(int i=1; i<=max; i++) {

if inside any interval
if out side of all interval



}

- adiya.tb November 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

and

boolean canMerge(int[] arr1, int[] arr2){
return arr1[1] >= arr2[0];
}

int[] mergeLocal(int[] arr1, int[] arr2){

int[] merged = new int[2];
// Determine first element [1,2] [2,3] .... [2,8] [3,6]
if(arr1[0] < arr2[0]){
merged[0] = arr1[0];
}

// Determins second element [1,2] [2,3] .... [2,8] [3,6]
if(arr1[1] > arr2[1]){
merged[1] = arr1[1];
}else{
merged[1] = arr2[1];
}
return merged;
}

List<int[]> mergeArrays(List<int[]> arr1, List<int[]> arr2){

List<int[]> mergedArray = new ArrayList<>();

// Merge array 1

int i = 1;
mergedArray.add(arr1.get(0));
int j = 0;

while(i < arr1.size()){

if(canMerge(mergedArray.get(j),arr1.get(i))){
mergedArray.set(j,mergeLocal(mergedArray.get(j),arr1.get(i)));
}else{
mergedArray.add(arr1.get(i));
j++;
}
i++;
}

// Merge Array 2
int k = 0 ;
while(k < arr2.size()){
if(canMerge(mergedArray.get(j),arr2.get(k))){
mergedArray.set(j,mergeLocal(mergedArray.get(j),arr2.get(k)));
}else{
mergedArray.add(arr2.get(k));
j++;
}
k++;

}
return mergedArray;
}

and

- Dinesh C November 25, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[][] mergeInterval(int[][] list1, int[][] list2) {

        LinkedList<int[]> result = new LinkedList<>();

        result.add(list1[0]);
        int i =1;
        int j =0;
        while(i < list1.length && j < list2.length) {

            int[] secondInterval;
            int[] a = i < list1.length ? list1[i] : null;
            int[] b = j < list2.length ? list2[j] : null;

            if(a[0] < b[0]) {
               secondInterval = a;
                i++;
            } else {
                secondInterval = b;
                j++;
            }

            mergeWithResult(result, secondInterval);
        }

        while(i < list1.length) {
            mergeWithResult(result, list1[i++]);

        }

        while(j < list2.length) {
            mergeWithResult(result, list2[j++]);
        }

        int[][] resultArray = new int[result.size()][2];

        int k =0;
        for(int[] element: result) {
            resultArray[k++] = element;
        }

        return resultArray;
    }

    private static void mergeWithResult(LinkedList<int[]> result, int[] secondInterval) {
        int[] lastInterval = result.getLast();

        if(lastInterval[1] < secondInterval[0]) {
            result.add(secondInterval);
        } else {
            result.getLast()[1] = Math.max(result.getLast()[1], secondInterval[1]);
        }
    }

- Anonymous December 02, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More