Big Fish Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
I am not from Java background. Can you please list the sorted result of?
Collections.sort(inputIntervals);
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}
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;
}
}
}
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)
#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;
}
}
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;
}
- naren November 11, 2014