Google Interview Question for SDE1s


Country: United States




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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class MinIntervalCountToCoverInterval {
	static class Interval implements Comparable<Interval>{
		Integer sT;
		Integer eT;
		Interval(int sT, int eT){
			this.sT = sT;
			this.eT = eT;
		}

		@Override
		public int compareTo(Interval o) {
			return eT.compareTo(o.eT);
		}

		@Override
		public String toString() {
			return "[" + sT +  ", " + eT + "]";
		}
	}

	static ArrayList<Interval> FindMinInterval(ArrayList<Interval> list, Interval reqInterval){
		Set<Integer> set = new HashSet<Integer>();
		for (int i=0; i< list.size(); i++){
			set.add(list.get(i).sT);
			set.add(list.get(i).eT);
		}
		set.add(reqInterval.sT);
		set.add(reqInterval.eT);

		Integer arr[] = set.toArray(new Integer[set.size()]);
		Arrays.sort(arr);

		HashMap<Integer, Interval> bestIntervalMap = new HashMap<Integer, Interval>();
		for (int i=0; i< list.size(); i++){
			Interval interval = list.get(i);

			int startIndex = Arrays.binarySearch(arr, interval.sT);
			if (startIndex < 0){
				startIndex = -startIndex -1;
			}
			int endIndex = Arrays.binarySearch(arr, interval.eT);
			if (endIndex < 0){
				endIndex = -endIndex -1;
			}
			endIndex--;

			for (int j=startIndex; j<=endIndex; j++){
				if (!bestIntervalMap.containsKey(arr[j])){
					bestIntervalMap.put(arr[j], interval);
				} else {
					if (bestIntervalMap.get(arr[j]).eT < interval.eT){
						bestIntervalMap.put(arr[j], interval);
					}
				}
			}
		}
		int startTime = reqInterval.sT;
		ArrayList<Interval> intervalList = new ArrayList<Interval>();
		while (startTime < reqInterval.eT){
			Interval interval = bestIntervalMap.get(startTime);
			if (interval == null){
				return null;
			}
			intervalList.add(interval);
			startTime = interval.eT;
		}

		return intervalList;
	}

	static void PrintList(ArrayList<Interval> list){
		if (list!=null){
			for (int i=0; i<list.size(); i++){
				System.out.print(list.get(i).toString() + ((i == list.size()-1) ? "" : ", "));
			}
			System.out.println();
		}else{
			System.out.println("Not possible");
		}
	}

	public static void main(String[] args){
		ArrayList<Interval> list = new ArrayList<Interval>();
		list.add(new Interval(-1, 9));
		list.add(new Interval(1, 10));
		list.add(new Interval(0, 3));
		list.add(new Interval(9, 10));
		list.add(new Interval(3, 14));
		list.add(new Interval(2, 9));
		list.add(new Interval(10, 16));
		PrintList(FindMinInterval(list, new Interval(2, 15)));
	}
}

- havefun March 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

1. Consider all intervals which start before the target start time
2. Among those pick the interval with max end time
3. Update the target start time to the previous max end time and repeat

public static int minimumMerge(Interval[] intervals, Interval target) {
    int result = 0;
    Arrays.sort(intervals);

    int targetStart = target.start;
    int maxEndtime = Integer.MIN_VALUE;
    int mergedIntervals = 0;
    int i=0;
    while (i < intervals.length) {
      if (intervals[i].start <= targetStart) {
        maxEndtime = Math.max(maxEndtime, intervals[i].end);
        i++;
      } else {
        targetStart = maxEndtime+1;
        mergedIntervals++;
      }
    }

    if (maxEndtime >= target.end) return ++mergedIntervals;
    return 0;
  }

  public static class Interval implements Comparable<Interval>{
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }

    public int compareTo(Interval i) {
      return start-i.start;
    }
  }

- challapallirahul March 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This would fail for // (-1,9), (0,3), (1,10), (2,9), (3,14),(9,12), (12,16)

- sri November 07, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findMinInterval(Interval[] intervals, Interval target){
        if(intervals.length==0)
            return Integer.MAX_VALUE;
        int min=Integer.MAX_VALUE;
          Arrays.sort(intervals,new Comparator<Interval>(){
              public int compare(Interval a,Interval b){
                  return a.start-b.start;
              }
          });
        
        
        for(int i=0;i<intervals.length;i++){
            if(intervals[i].start>target.start)
                break;
            if(intervals[i].start<=target.start && intervals[i].end>= target.end ){
                min=1;
                break;
            }
            int temp_min=1;
           Interval curInterval= intervals[i];
            Interval prevInterval= null;
            for(int j=i+1;j<intervals.length;j++){
                 if(intervals[j].start<= curInterval.end && intervals[j].end>= target.end){
                     if(prevInterval==null || (prevInterval!=null && intervals[j].start>prevInterval.end))
                  temp_min+=1;  
              
                     if(min>temp_min)
                         min=temp_min;
                  break;   
                 }
              else if(intervals[j].start> curInterval.start && intervals[j].start<=curInterval.end && intervals[j].end> curInterval.end){
                  if(prevInterval==null || (prevInterval!=null && intervals[j].start>prevInterval.end)){
                  temp_min+=1;
                      prevInterval= curInterval;   
              }
               curInterval=intervals[j];  
            }
        }
    }
         return min;
    }

- deep March 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive approach in Scala

object CoverIntervals {

  case class Interval(start: Int, end: Int)

  def findOneCoveringInterval(intervals: Set[Interval], target: Interval): Boolean =
    intervals.exists(interval => interval.start <= target.start && interval.end >= target.end)

  def partlyCovers(el: Interval, target: Interval): Boolean =
    (el.start < target.start && el.end >= target.start) || (el.start < target.end && el.end >= target.end)

  def cutTarget(interval: Interval, target: Interval): Interval =
    if (interval.start < target.start && interval.end >= target.start)
      Interval(interval.end, target.end)
    else if (interval.start < target.end && interval.end >= target.end)
      Interval(target.start, interval.start)
    else throw new RuntimeException("unexpected arg: " + interval + " " + target)

  def findMinInterval(intervals :Set[Interval], target: Interval): Option[Int] = {
    if (findOneCoveringInterval(intervals, target))
      Some(1)
    else {
      val partlyCovered = intervals.filter(el => partlyCovers(el, target))
      if (partlyCovered.size == 0)
        Option.empty
      else {
        val res = for {
          interval <- partlyCovered
          number <- findMinInterval(intervals - interval, cutTarget(interval, target))
        } yield (number)

        if (res.isEmpty)
          Option.empty
        else
          Option(res.min + 1)
      }
    }
  }
}

- kryzoo.m March 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is straight out of Leetcode

- Max Steel March 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_min_intervals(intervals, target):
    intervals.sort()
    ct = target[0]
    i = 0
    max_step = 0
    res = 0
    while i < len(intervals):
        while i < len(intervals) and intervals[i][0] <= ct:
            max_step = max(max_step, intervals[i][1])
            i += 1
        ct = max_step
        res += 1
    return res

print find_min_intervals([[-1, 9], [1, 10], [0, 3], [9,10], [3, 14], [2, 9], [10, 16]], [2,15])

- prathji June 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this method should be right, basical idea is using TreeMap, and the time complexity is O(nLog(n)):

public static int minMerge(List<Interval> intervals,Interval target){
          TreeMap<Integer,Integer> treemap = new TreeMap<>();
          for(int i=0;i<intervals.size();i++){
              Interval temp = intervals.get(i);
              if(treemap.containsKey(temp.start)){
                  treemap.put(temp.start,Math.max(temp.end,treemap.get(temp.start)));
              }else{
                  treemap.put(temp.start,temp.end);
              }
          }
        
          int count = 0;
          int cur_end = target.start;
          while(treemap.size()!=0){
              count++;
              Integer next_start = treemap.floorKey(cur_end);
              if(next_start==null){
                  return 0;
              }
              Integer next_end = treemap.get(next_start);
              treemap.remove(next_start);
              while(!treemap.isEmpty()){
                  next_start = treemap.floorKey(cur_end);
                  if(next_start==null){
                      break;
                  }
                  
                  next_end = Math.max(next_end,treemap.get(next_start));
                  treemap.remove(next_start);
              }
              if(next_end>=target.end){
                  return count;
              }
              cur_end = next_end;
          }
        
          return 0;
    }

- tiandiao123 September 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Copy pasting here:
here's my explanation and well-commented code, hope it will help :)
Greedy: choose furthest range
0. sort by start, upon same, by end(not necessary)

find eligible intervals for start: base start = target.start
definition of eligible intervals: x is eligible if x.start <= start && x.end > start
special case: if the earliest start > start, no ans, break!!!
Among all eligible intervals, choose the one that has the furthest range
count++;
if(furthest range >= target.end) -> ans found
update start to furthest range
repeat the iteration
public static int leastMerge(List<Interval> list, Interval interval) {
//0. sort by start
Collections.sort(list, (o1, o2) -> o1.start - o2.start);
int i = 0;
int start = interval.start;
int count = 0;
while (i < list.size()) {
//special case, no way to cover
if (list.get(i).start > start) {
break;
}
int furthest = Integer.MIN_VALUE;
//1. find eligible intervals
while (i < list.size() && list.get(i).start <= start) {
if (list.get(i).end > start) { //eligible
//2. choose the one that has the furthest range
if (list.get(i).end > furthest) {
furthest = list.get(i).end;
}
}
i++;
}
count++;

if (furthest >= interval.end) return count;
//3. update start to furthest range
start = furthest;
}
return 0;
}

- Rajat.nitp July 21, 2020 | 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