## Amazon Interview Question for SDE1s

• 0

Country: United States
Interview Type: In-Person

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

This one a tricky question, it does seem easy at first but when you try with values like [0,6] , [1,2],[3,5] you will notice what goes wrong,

so this is the solution,
0. we should store the old indices of ranges in a map.
1. then we should sort the intervals according to start then according to end
2. we will keep track of the latest merged range and compare it with the new range, its a dynamic programming solution, where we will assume the first merged range is range number zero in the sorted ranges array.

3. we will iterate through the sorted range array from index 1 to end, and check
if( current range intersect with latest merged range ) {
latest marge range = { min( current range.start , mergedRange.start ) ,
max( current range.end , mergedRange.end )
}

if( i -1 == 0) // to consider the first element that we put in the range

add current range *Original* index ( before the sort ) to the result vector
}else{
latest merged range = current range;
}

5. sort the result vector

6. return the result vector;

here is the code, this solution is O(nlogN) , since the sort takes the most of the time.

``````template<>
class hash< pair<int, int> >
{
public:
bool operator()(const pair<int, int>& p)const {
return hash<int>()(p.first) ^ hash<int>()(p.second);
}
};

bool isInRange(int index, pair<int, int> range) {
return index >= range.first && index <= range.second;
}

vector<int> findOverlapps(vector<pair<int, int> > & jobs) {

if (jobs.size() <= 1)
return{};

unordered_map<pair<int, int>, int > rangeOrgIndexMap;

for (int i = 0; i < jobs.size(); i++) {
rangeOrgIndexMap[jobs[i]] = i;
}

vector<int> overlappIndex;

vector<pair<int, int> > sortedJobs = jobs;

sort(sortedJobs.begin(), sortedJobs.end());

pair<int, int> mergedRange = sortedJobs;

for (int i = 1; i < sortedJobs.size() ; i++) {

if( isInRange(sortedJobs[i].first, mergedRange) || isInRange(sortedJobs[i].second, mergedRange) ) {

mergedRange = { min(sortedJobs[i].first , mergedRange.first) , max(sortedJobs[i].second , mergedRange.second) };

if (i - 1 == 0)
overlappIndex.push_back(rangeOrgIndexMap[sortedJobs[i-1]]);

overlappIndex.push_back(rangeOrgIndexMap[sortedJobs[i]]);
}
else {
mergedRange = sortedJobs[i];
}
}

sort(overlappIndex.begin(), overlappIndex.end());

return overlappIndex;
}``````

Comment hidden because of low score. Click to expand.
2
of 4 vote

My solution is similar to LaithBasilDotNet's, whose code is already very nice under the assumption that the times are hours between 0 and 24: the code is simple and clear and the algorithm is in linear time and constant memory.

I use bit masks instead of the dayTime vector, which allows me to dispense with the inner loops: dup_mask is the bit mask of all hours which appear in at least two job schedules.

``````#include <vector>
#include <utility>

std::vector<int> find_overlaps(const std::vector<std::pair<int, int>> jobs)
{
std::vector<int> result;

for (const auto &job : jobs) {
uint32_t mask = (1ul << job.second) - (1ul << job.first);
}
for (int i = 0; i != jobs.size(); i++) {
uint32_t mask = (1ul << jobs[i].second) - (1ul << jobs[i].first);
result.push_back(i);
}

return result;
}``````

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

Interesting solution of using the integer a your "array" for counting (true/false) sort and using bit-wise operations to fill without the loop to populate it. Very nice.

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

not an answer for the given problem

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

Agree with pc, not a solution for this problem. Does not work for this input:
{ (1,2) (1,2) (3,5) }

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

I think we need to take into consideration both the starting time and the larger value of execution time for a given start time.
eg : - let us take all the jobs started at time 1

[1,2][1,5][1,6]
the largest time for which any job starting at 1 executed = 5
at this point we have to consider all the jobs whose starting time lies between 1 to 5
i.e any job that starts at 2, 3, 4 ,5, 6 also overlaps.

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

does your solution works with [1,2][3,5][0,6] ?

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

yes it will. i intend to store the starting time in a set and will use a multimap to store starting and ending time.

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

I don't understand how it should work, but what your code execution time is it N^2 or NLogN or N

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

``````#include "iostream"
#include "map"
#include "set"
#include "vector"

using namespace std;

vector<int>& findOverLappingJobs(multimap<int,int>& jobs, set<int>& startTime)
{
vector<int>* overLappingPairs = new vector<int>;

for(set<int>::iterator itrSet = startTime.begin(); itrSet!= startTime.end(); ++itrSet)
{
auto itrRange = jobs.equal_range(*itrSet);
int max = 0;
int temp = 0;
for(auto itrMap = itrRange.first; itrMap != itrRange.second; ++itrMap)
{
overLappingPairs->push_back(itrMap->first);
overLappingPairs->push_back(itrMap->second);
temp = itrMap->second - itrMap->first;
if(temp > max)
{
max = temp;
}
}
max += *itrSet;
for(int i = *itrSet + 1; i <= max; ++i)
{
startTime.erase(i);
auto itrRange = jobs.equal_range(i);
for(auto itrMap = itrRange.first; itrMap != itrRange.second; ++itrMap)
{
overLappingPairs->push_back(itrMap->first);
overLappingPairs->push_back(itrMap->second);
}
}
overLappingPairs->push_back(-1);
}
return *overLappingPairs;
}

int _tmain(int argc, _TCHAR* argv[])
{
int numberOfJobs = 0;

cin >> numberOfJobs;

multimap<int, int> jobs;
set<int> startTime;

int start;
int end;

for(int i = 0; i < numberOfJobs; ++i)
{
cin >> start;
cin >> end;
jobs.insert(make_pair(start,end));
startTime.insert(start);
}

vector<int> result = findOverLappingJobs(jobs,startTime);

for(auto itr = result.begin(); itr != result.end(); ++itr)
{
if(*itr == -1)
{
cout << endl;
continue;
}
cout << "[" << *itr;
cout << "," << *(++itr) << "]";
}
delete &result;
return 0;``````

}

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

Complexity will be O(n)

Comment hidden because of low score. Click to expand.
3

I got your solution, I think its not O(N) since you iterate from *iter to max which mean its O(NM) where M is the maximum range distance, since its a time we are limited by 24 hour a day, which make since then. its like counting sort!

by the way its a nice trick :)

here is a simpler way to write the code

``````vector<int> findOverLappingJobs2(vector< pair<int, int> >& jobs) {

vector<int> dayTime(24, 0);
vector<int> res;

for (int i = 0; i < jobs.size(); i++) {
for (int s = jobs[i].first; s <= jobs[i].second; s++) {
dayTime[s]++; // those who overlapp will have count more than 1
}
}

for (int i = 0; i < jobs.size(); i++) {
for (int s = jobs[i].first; s <= jobs[i].second; s++) {
if (dayTime[s] > 1) {
res.push_back(i);
break;
}
}
}

return res;
}``````

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

I think running time will be O(n). Since i am deleting the traversed nodes from the set of starting time.

startTime.erase(i);

So we are visiting each process exactly once.

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

to get my idea, just try your code or my latest code with this input
[1,10],[1,100000000],[0,6], if its only N it should run as fast is for [1,10] [0,6] [1,3] but you will notice that it will get many seconds before it return the result to you !

that because you iterate all the distance between *iter to the max in your code.

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

Order the indices based on start and end time such that the start times are ordered in buckets and within those buckets, the end times are ordered.

In your example, we order from

[1,2][5,6][1,5][7,8][1,6]

to

[1,2][1,5][1,6][5,6][7,8]

Now iterate through these indices. As long as:

end time of the previous index > start time of current index

this index will be in a set.

Comment hidden because of low score. Click to expand.
2

Does your solution keep track of the indices after the sort ? we need to keep tack of them !

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

A day has hours between 0 and 23.

Keep a integer array (say hours) of 24 elements.For each job schedule increment the hour which is the part of schedule.
For example For job [1,2] increment hours by one and hour by one
Do this for all job schedules
Finally iterate through all hours of day.Hours which has count > 1 has conflicts.

Time complexity : O(noOfJobs);
SpaceComplexity : O(24) = O(1); // only array of 24 is required

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

How does your solution will give total number of overlapping jobs or indices of jobs which are overlapping?

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

I think he wrote a correct answer, but without a code to describe it, this is how this written ! its the idea of counter sort

``````vector<int> findOverLappingJobs2(vector< pair<int, int> >& jobs) {

vector<int> dayTime(24, 0);
vector<int> res;

for (int i = 0; i < jobs.size(); i++) {
for (int s = jobs[i].first; s <= jobs[i].second; s++) {
dayTime[s]++; // those who overlapp will have count more than 1
}
}

for (int i = 0; i < jobs.size(); i++) {
for (int s = jobs[i].first; s <= jobs[i].second; s++) {
if (dayTime[s] > 1) {
res.push_back(i);
break;
}
}
}

return res;
}``````

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

Wouldn't this time complexity be O(n^2), where n is the number of jobs, since you have to iterate over all of the jobs twice?

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

We need to create RangeSets for all job schedule times. With two scans of schedule sets, we can create all RangeSets.

input: [1,2] [5,10] [7,8] [11,12] [1,6] [10,11] [20,21] [30,31] [11,20]
1st scan (RangeSets) : [1, 6] [5, 20] [11,12] [20,21] [30,31]
2nd scan (RangeSets) : [1,21] [30,31]

Final step: Now, using RangeSets, we can create the set of overlapping indices
return: [0,1,2,3,4,5,6,8]

Time Complexity: 1st scan = O(n)
2nd scan = O(n)
3rd scan = O(n)

Total = O(n) +O(n) +O(n) = O(n)

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

What is RangeSet ? and how it works ?

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

I doubt RangeSet merge and split operation works in constant time.

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

I doubt that RangeSet merge and split works in constant time.

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

Idea is to find all closures of the set. Maintain a queue of remaining jobs (haven't been added to any closure yet). Start by choosing any job from remaining jobs queue and add it to the current closure. Then recurse on every job added to the current closure and do the same thing. Do this until every job is added to some closure (even if it means a closure with just itself).

Best case runtime: O(n) when every job is part of the same closure
Worst case: O(n^2) when every job is in a different closure by itself

``````public Set<Set<Job>> getClosures(Set<Job> jobs) {

Set<Set<Job>> closures = new Set<Set<Job>>();
Set<Job> currentClosure = null;

while (!jobs.isEmpty()) {

// Reset current closure
currentClosure = new Set<Job>();

// Grab some job that hasn't been added to any closure yet
Job currJob = getNextJob(jobs);

// Remove job from remaining jobs and add to current closure
jobs.remove(currJob);

// Compute closure of current job
for (Job j : jobs) {
// If a job not added to any closure yet intersects with this job,
// add it to this closure and remove it from the set of jobs not
if (intersects(j, job)) {
jobs.remove(j);
}
}
}

// Add closure of current job into result set
}

return closures;
}``````

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

Sort list of jobs by start and end times (in that order). Iterate through resulting list checking for overlaps. This requires only one iteration since sorting this way guarantees that if job i does not overlap with job i-1, then all jobs i and later do not overlap with any jobs i-1 and earlier.

``````First, each job needs to implement Comparable, ex:
public int compareTo(Job j) {
if (this.start < j.start) return -1;
if (this.start > j.start) return 1;
if (this.end < j.end) return -1;
if (this.end > j.end) return 1;
return 0;
}

public Set<Set<Job>> getOverlappingSets(Job [] jobs) {

Set<Set<Job>> overlappingSets = new Set<Set<Job>>();
if (jobs == null || jobs.length == 0) {
return overlappingSets;
}

// Sort jobs ascending based on start times, then end times
Arrays.sort(jobs);

// Compute overlapping sets
Set<Job> currentOverlappingSet = new Set<Job>();
int prevEnd = jobs.end;
for (int i = 1; i < jobs.length; i++) {
// If this job overlaps with the previous job's end
// add it to the current set and update prevEnd
if (jobs[i].start < prevEnd) {
prevEnd = jobs[i].end;
} else {
// This job does not overlap
// Add previous set to results if it has overlaps
if (currentOverlappingSet.length > 1) {
}
// Start new set and add this job to it
currentOverlappingSet = new Set<Job>();
}
}

return overlappingSets;
}``````

Runtime: O(nlgn) mainly due to sort operation

It's important to understand why we need to sort by start times then end times. This primarily allows us to iterate over the jobs in a single pass.

We couldn't accomplish this if we sorted first by end times.
Ex. [1,5], [7,10], [3,15] does not guarantee that if job i does not overlap with job i-1 that job i+1 will also not overlap. In this case, you'd have to back-track to figure out that [7,10] actually should be included.

This wouldn't work if we just sorted by start times either.
Ex. [1,5], [1,3], [4,5]. The problem is identical to the one above. [4,5] should be included, but we wouldn't know this without back-tracking and looking at [1,5].

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

1) Put jobs into a map where the key is the hour and the value is the vector of job indices.

2) Loop over the map and place overlaps (where there is more than one index in an hour) into a set.

3) Convert the set to a vector

``````std::vector<int> getIndexes(std::vector<std::pair<int, int>>& sets)
{
std::map<int, std::vector<int>> schedule;
std::set<int> dups;

int index = 0;

// construct the schedule
for (const auto& p : sets)
{
for (int i = p.first; i <= p.second; ++i)
{
schedule[i].push_back(index);
}
++index;
}

for (const auto& p : schedule)
{
if (p.second.size() > 1)
{
for (const auto& d : p.second)
{
dups.insert(d);
}
}
}

return std::vector<int>(dups.begin(), dups.end());
}``````

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

Actually it is interesting that people though that the time were hours in a single day which seems to allow linear time algorithms.

I myself though of times out of something so time could be more than a 24 hour boundary.

``````public static IEnumerable<int> FindIntersections(Tuple<int, int>[] TS)
{
// int => first, Tuple<int, int> => largest range, int => position
var sorted = new SortedDictionary<int, Tuple<Tuple<int, int>, int>>();

HashSet<int> result = new HashSet<int>();

for(int i = 0; i < TS.Length; i++)
{
var ts = TS[i];

// Probably the best approach is to is a HashTable first to remove
// intersections so lookups are O(1) rather than O(logn)
if(sorted.ContainsKey(ts.Item1))
{
var val = sorted[ts.Item1];
if(val.Item1.Item2 < ts.Item2)
{
sorted[ts.Item1] = new Tuple<Tuple<int, int>, int>(ts, i);
}
}
else
{
sorted.Add(ts.Item1, new Tuple<Tuple<int, int>, int>(ts, i));
}
}

var prev = new Tuple<Tuple<int, int>, int>(new Tuple<int, int>(-1, -1), -1);
foreach(var kvp in sorted)
{
if(prev.Item1.Item2 > kvp.Key)
{
}

prev = kvp.Value;
}

result.Remove(-1);

// It is not sorted
return result;
}``````

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

``````public static Group{
int min;
int max;

Group merge(Group g){
if(g.min < min){
min = g.min;
}
if(g.max > max){
max = g.max;
}
}

boolean overlaps(Group g){
return !( max < g.min || min > g.max);
}

int[] getSets(){
int[] results = new int[setIndices.size()];
Iterator<Integer> iterator = setIndices.iterator();
for(int i = 0; i < results.length; i++){
results[i] = iterator.next();
}
return results;
}
}

public static int[][] getOverlaps(int[][] schedules){
//if feeling froggy, sort the schedules somehow here
for(int i = 0; i < schedules.length; i++){
int[] sched : schedules[i];
Group g = new Group;
g.min = sched;
g.max = sched;
}
boolean merged = true;
while(groups.size() > 0){
Group check = groups.removeFirst();
boolean notMerged = true;
for(int i = 0; i < groups.size(); i++){
Group temp = groups.removeFirst();
if(check.overlaps(temp)){
check.merge(temp);
notMerged = false;
else{
}
}
if(notMerged){
if(check.setIndices.size() > 1){
}
}
else{
}
}
int[][] results = new int[complete.()][];
for(int i = 0; i < complete.size(); i++){
results[i] = complete.removeFirst().getSets();
}
return results;
}``````

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

public class FindOverlapJobs {

public static List<Integer> findOverLappingJobs(Job[] jobs) {
int[] hours = new int;
List<Integer> overlaps = new ArrayList<Integer>();
for (int i = 0; i < jobs.length; i++) {
for (int j = jobs[i].getStartTime(); j <= jobs[i].getEndTime(); j++) {
hours[j] = hours[j] + 1;
}
}

for (int i = 0; i < jobs.length; i++) {
if ((hours[jobs[i].getStartTime()] > 1) || (hours[jobs[i].getEndTime()] > 1)) {
}
}
return overlaps;

}

public static void main(String[] args) {
Job[] jobs = new Job;
jobs = new Job(1, 2);
jobs = new Job(5, 6);
jobs = new Job(1, 5);
jobs = new Job(7, 8);
jobs = new Job(1, 6);
System.out.println(findOverLappingJobs(jobs));
}
}

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

public class FindOverlapJobs {

public static List<Integer> findOverLappingJobs(Job[] jobs) {
int[] hours = new int;
List<Integer> overlaps = new ArrayList<Integer>();
for (int i = 0; i < jobs.length; i++) {
for (int j = jobs[i].getStartTime(); j <= jobs[i].getEndTime(); j++) {
hours[j] = hours[j] + 1;
}
}

for (int i = 0; i < jobs.length; i++) {
if ((hours[jobs[i].getStartTime()] > 1) || (hours[jobs[i].getEndTime()] > 1)) {
}
}
return overlaps;

}

public static void main(String[] args) {
Job[] jobs = new Job;
jobs = new Job(1, 2);
jobs = new Job(5, 6);
jobs = new Job(1, 5);
jobs = new Job(7, 8);
jobs = new Job(1, 6);
System.out.println(findOverLappingJobs(jobs));
}
}

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

public class FindOverlapJobs {

public static List<Integer> findOverLappingJobs(Job[] jobs) {
int[] hours = new int;
List<Integer> overlaps = new ArrayList<Integer>();
for (int i = 0; i < jobs.length; i++) {
for (int j = jobs[i].getStartTime(); j <= jobs[i].getEndTime(); j++) {
hours[j] = hours[j] + 1;
}
}

for (int i = 0; i < jobs.length; i++) {
if ((hours[jobs[i].getStartTime()] > 1) || (hours[jobs[i].getEndTime()] > 1)) {
}
}
return overlaps;

}

public static void main(String[] args) {
Job[] jobs = new Job;
jobs = new Job(1, 2);
jobs = new Job(5, 6);
jobs = new Job(1, 5);
jobs = new Job(7, 8);
jobs = new Job(1, 6);
System.out.println(findOverLappingJobs(jobs));
}
}

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

O(nlogn)

``````#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct Interval {
int index = 0;
int left;
int right;

Interval(int left, int right) : left(left), right(right) {}
};

vector<int> getOverllaped(vector<Interval> intervals) {
vector<int> res;
if (intervals.empty()) return res;

// store original indices before sorting
for (int i = 0; i != intervals.size(); ++i)
intervals[i].index = i;

// sort by left value
sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b){ return a.left < b.left; });

Interval interval = intervals;
for (int i = 1; i != intervals.size(); ++i) {
if (interval.right < intervals[i].left) {
interval = intervals[i];
} else {
if (i == 1) res.push_back(intervals.index);
res.push_back(intervals[i].index);
interval = Interval(min(interval.left, intervals[i].left), max(interval.right, intervals[i].right));
}
}
return res;
}

int main()
{
vector<Interval> intervals;
intervals.push_back(Interval(1, 2));
intervals.push_back(Interval(5, 6));
intervals.push_back(Interval(1, 5));
intervals.push_back(Interval(7, 8));
intervals.push_back(Interval(1, 6));

cout <<  "Overllapped: ";
vector<int> res = getOverllaped(intervals);
for (int i = 0; i != res.size(); ++i)
cout << res[i] << " ";

}``````

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

R

``````input <- "[1,2][5,6][1,5][7,8][1,6]"
j <- input
j <- gsub(pattern='\\[','',j)
j <- strsplit(j, ']')[]
j <- sapply(j,FUN=strsplit,split=',')
pairs <- matrix(as.numeric(unlist(j)),byrow=T, ncol=2)

myRange <- function(data){
return(seq(from=data, data, by=1))
}

ls <- apply(pairs, 1,FUN= myRange)

getOverlappingSets <- function(ls){
inside <- c()
for(i in 1:(length(ls))){
count <- 0
for(j in 1:length(ls)){
if( i != j ){
if(any(ls[[i]] %in% ls[[j]])){
count <- count + 1
}
}
}
if(count > 0){
inside <- c(inside, i)
}
}
return(inside)
}

getOverlappingSets(ls)

# test case
x = floor(runif(8,0,9)*10)
y = x + floor(runif(8, 1, 10))*3
pairs <- data.frame(x,y)
ls <- apply(pairs, 1,FUN= myRange)
getOverlappingSets(ls)``````

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

``````package com.home.project.test;

import java.util.HashMap;

/*Given set of job schedules with start and end time, write a function that returns indexes of overlapping sets.

for ex :-
input -> [1,2][5,6][1,5][7,8][1,6]
return -> [0,1,2,4]*/

public class OverlapSet {

HashMap<Integer, String> inputMap;
int inputmapSize = 0;
int[][] inputAList;

public OverlapSet() {
inputMap = new HashMap();
inputAList = new int;

}

private void populate(int startNum, int endNum) {

if (startNum < endNum) {
inputAList[inputmapSize] = startNum;
inputAList[inputmapSize] = endNum;
} else {
inputAList[inputmapSize] = startNum;
inputAList[inputmapSize] = endNum;
}
inputmapSize++;
}

private void printOverLapSet() {
for (int i = 0; i < inputmapSize; i++) {
for (int j = 0; j < inputmapSize; j++) {
if (i == j)
continue;
if (inputAList[j] <= inputAList[i]
|| inputAList[j] <= inputAList[i]
|| inputAList[j] <= inputAList[i]
|| inputAList[j] <= inputAList[i]) {
inputMap.put(j, "Overlap");
}
}
}
for (Integer key : inputMap.keySet()) {

System.out
.println("------------------------------------------------");
System.out.println("key: " + key + " value: " + inputMap.get(key));
}
}

public static void main(String[] args) {
OverlapSet olSet = new OverlapSet();
olSet.populate(1, 2);
olSet.populate(5, 6);
olSet.populate(1, 5);
olSet.populate(7, 8);
olSet.populate(1, 6);
olSet.printOverLapSet();
}

}``````

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

solution :
Create a matrix A (maximum value in of the array/constant array of 24).
initialise all elements to 0
insert "1" for the values that correspond tovalues provided in the input.
Eg : have one in [1,2] , [1,5] , [1,6] ...

once done , loop through the input and check if the row or the column has 1's , if then mark the index as overlapping.

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

I got a O(nlogn) and O(n) solution in computation and space respectively.
Here is how the example works out.

``````Let's take a look at the example: [1, 2], [5, 6], [1, 5], [7, 8], [1, 6]
The sorted lower and upper bounds are,
- Lower bounds: {1, 1, 1, 5, 7}
- Upper bounds: {2, 5, 6, 6, 8}
Here is the algorithm runs
- Take 1 as the lower bound of the first interval
- Ui = 2, Li+1 = 1, where  i = 1. it is a OVERLAP case and continue
- Ui = 5, Li+1 = 1, where i = 2, it is a OVERLAP case and continue
- Ui = 6, Li+1 = 5, where i = 3, it is a OVERLAP case and continue
- Ui = 6, Li+1 = 7, where i = 4, it is NOT a OVERLAP case
* The first interval stops her as [1, 6]
* The second interval starts here with lower bound as 7
- Reach the end, construct the second interval with the upper bound of Un, [7, 8]
Two overlapped intervals generated as [1, 6] and [7, 8]
Insert key 1 with empty vector and key 7 with empty vector into hash map,
Order the overlapped interval's lower bounds as {1, 7}
- Task [1, 2]: the 1st value <= 1 is 1. then append 0 into the value of Key 1 of hash map
- Task [5, 6]: the 1st value <= 5 is 1. then append 1 into the value of Key 1 of hash map
- Task [1, 5]: the 1st value <= 1 is 1. then append 2 into the value of Key 1 of hash map
- Task [7, 8]: the 1st value <= 7 is 7. then append 3 into the value of Key 7 of hash map
- Task [1, 6]: the 1st value <= 1 is 1. then append 4 into the value of Key 1 of hash map
Go through the hash map,
[0, 1, 2, 4] in one group
 in one group``````

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.

### 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.