Big Fish Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

//Algorithm. Sort the input intervals by from and then doing a linear scan on the sorted list
// to merge intervals Time complexity: NLOGN + N ~ NLOGN

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class IntervalMerge {

	public static void main(String[] str) {
		List<Interval> inputIntervals = new ArrayList<Interval>();
		//{-10,-5}{-1,5}{2,4}{5,10}{20,35}{12,17}{17,21} 

		inputIntervals.add(new Interval(-10,-5));
		inputIntervals.add(new Interval(-1,5));
		inputIntervals.add(new Interval(2,4));
		inputIntervals.add(new Interval(5,10));
		inputIntervals.add(new Interval(20,35));
		inputIntervals.add(new Interval(12,17));
		inputIntervals.add(new Interval(17,21));
		
		Collections.sort(inputIntervals);
		List<Interval> outputIntervals = new ArrayList<Interval>();
		//linear scan through the list
		for (Interval currentInterval:inputIntervals) {
			Interval lastInterval = null;
			
			if(outputIntervals.size() > 0)
				lastInterval = outputIntervals.get(outputIntervals.size()-1);
			if(lastInterval == null) {
				outputIntervals.add(currentInterval);
				continue;
			}
			//Compare the lastInterval to with the current intervals from
			//last.to < current.from
			if(lastInterval.to < currentInterval.from) {
				outputIntervals.add(currentInterval);
				continue;
			}
			//last.to > current.from
			if(lastInterval.to >= currentInterval.from) {
				//Check the last interval to with the currentInterval to
				lastInterval.to = Math.max(lastInterval.to, currentInterval.to);
				continue;
			}
		}
		System.out.println(outputIntervals);
		
	}
}
 class Interval implements Comparable<Interval>{
	int from;
	int to;
	public Interval(int from, int to) {
		this.from = from;
		this.to = to;
	}
	@Override
	public int compareTo(Interval o) {
		// TODO Auto-generated method stub
		if(from > o.from) return 1;
		if(from == o.from) return 0;
		return -1;
	}
	@Override
	public String toString() {
		return "{" + from +"," + to +  "}";
	}
}

- naren November 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am not from Java background. Can you please list the sorted result of?

Collections.sort(inputIntervals);

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

It will be sorted based on the "from" of the interval. Sorted result will be
{-10,-5}{-1,5}{2,4}{5,10}{12,17}{17,21}{20,35}

linear scan through this list does the following to the output
pass1 {-10,-5} //There is nothing else in the output
pass 2 {-10,-5} {-1,5} //because -5 < -1
pass 3 {-10,-5} {-1,5} //because 2 <5 and 5 >4
pass 4 {-10,-5} {-1,10} //because 5 <=5 and 10 >5
pass 5 {-10,-5} {-1,10}{12,17} //because 10<12
pass 6 {-10,-5} {-1,10}{12,21} //because 17<=17 and 21 > 17
pass 7 {-10,-5} {-1,10}{12,35} //because 20<=21 and 35 > 21

Final answer:
{-10,-5} {-1,10}{12,35}

- naren November 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I originally had a tree-based solution, and it was a mess. : )

Props to naren for the clean solution; I cleaned up the main loop a bit.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;



public class Main{
	
	
	public static void main(String[] args){
		Set<Set<Point>> testCases = new HashSet<Set<Point>>();
		Set<Point> testCase0 = new HashSet<Point>(){{
			add(new Point(-10, -5));
			add(new Point(-1, 5));
			add(new Point(2, 4));
			add(new Point(5, 10));
			add(new Point(20, 35));
			add(new Point(12, 17));
			add(new Point(13, 21));
		}};
		testCases.add(testCase0);
		Set<Point> testCase1 = new HashSet<Point>(){{
			add(new Point(-1, 1));
			add(new Point(-5, -4));
			add(new Point(2, 5));
			add(new Point(1, 7));
			add(new Point(-7, -6));
			add(new Point(-3, -2));
			add(new Point(-6, 0));
		}};
		testCases.add(testCase1);
		
		for(Set<Point> testCase : testCases){
			mergeIntersection(testCase);
		}
		
	}
	
	private static void mergeIntersection(Set<Point> points){
		List<Point> l = new ArrayList<Point>();
		for(Point p : points){
			l.add(p);
		}
		
		Collections.sort(l);
		
		int left = 0, right = 1;
		while(right < points.size()){
			if(l.get(left).intersect(l.get(right))){
				l.get(left).setB(Math.max(l.get(left).getB(), l.get(right).getB()));
				l.set(right, null);
				right++;
			}
			else{
				left = right;
				right++;
			}
		}
		for(Point p : l){
			if(p != null){
				System.out.println(p);
			}
		}
		System.out.println();
	}

	public static class Point implements Comparable<Point>{
		int a;
		int b;
		
		public Point(int a, int b){
			this.a = a;
			this.b = b;
		}
		
		public int getA(){
			return a;
		}
		
		public int getB(){
			return b;
		}
		
		public void setA(int a){
			this.a = a;
		}
		
		public void setB(int b){
			this.b = b;
		}
		
		public boolean intersect(Point p){
			return !(p.getB() < a || p.getA() > b);
		}
		
		public String toString(){
			return " [" + a + " , " + b + "] ";
		}

		@Override
		public int compareTo(Point p) {
			if(a < p.getA()) return -1;
			return 1;
		}
	}

}

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

Sort the intervals based on the start time. initialize ans=1.
Take ending time= ending time of first interval. Now, traverse this sorted array from the second interval till the end. . When you encounter a new interval, there are two cases:-
1. the start time of this interval is less than or equal to the previous ending time - in this case, ending time=max(ending time, new end time)
2. The start time of this interval is greater than the previous ending time. In this case,
ending time= new ending time; ans++;

Order= O(nlogn) (for sorting)

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

#include <iostream>
#include<stdlib.h>
#include<string.h>

#define ARR_SZ 1001;
/*Assuming numbers are in range of -500 to 500*/

void AddSet(int x, int y, int *Temp);
void PrintSet(int * ptr, int N);

int *Array = NULL;
int main()
{
int i,N,x,y, T, *Temp = NULL;
N = ARR_SZ;
Array = (int *)malloc(sizeof(int)* N);
if(!Array){
printf("Memory Error : Can not Alloacte memory\n");
return -1;
}
for(i= 0;i<N;i++)
Array[i] = 0;
Temp = Array + (N/2);
printf("Enter number of Entries and followed by pairs : 3 -1 3 3 56 78 90 \n");
scanf("%d", &T);
for(i = 1;i<=T;i++){
scanf("%d", &x);
scanf("%d", &y);
AddSet(x, y, Temp);
}
PrintSet(Temp, N);
return 0;
}

void AddSet(int x, int y, int *Temp){
int i;
for(i=x;i<=y;i++){
Temp[i] = 1;
}
}

void PrintSet(int * Temp, int N){
int i, j;
i = j = -N/2;
while(i != N && j != N){
while(Temp[i] != 1){
i++;
j++;
}
while(Temp[j] == 1 )
j++;
printf("%d %d\n",i,j-1);
i = j;
}
}

- acts November 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This can be accomplished in O(n) where n is the number of pairs of number:

public static ArrayList<int[]> getOverlaps(ArrayList<int[]> ranges){
	//handle easy cases
	if(ranges == null){
		throw new NullPointerException();
	}
	if(ranges.size() < 2){
		return ranges;
	}

	//sort the ranges on the first index
	Collections.sort(ranges, new Comparator<int[]>(){
		public int compare(int[] o1, int[] o2){
			return o1[0] - o2[0];
		}
	});

	//setup global tracking variables
	ArrayList<int[]> results = new ArrayList<int[]>();
	//get the start and end of the first output range
	int[] trackedRange = new int[]{ ranges.get(0)[0], ranges.get(0)[1]};
	//for each range
	for(int i = 1; i < ranges.size(); i++){
		int[] range = ranges.get(i);
		//if the new range does not overlap with the old one, 
		//then this is a new range and the old one should be put in the results
		if(range[0] > trackedRange[1]){
			results.add(trackedRange);
			trackedRange = new int[]{range[0], range[1]};
		}
		//otherwise, the endpoint of the range could be extended by the new range
		else if(range[1] > trackedRange[1]){
			trackedRange[1] = range[1];
		}
	}
	//there will be an additional range that is not captured by the for loop
	results.add(trackedRange);
	return results;
}

- zortlord November 12, 2014 | 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