Amazon Interview Question
SDE1sCountry: United States
Interview Type: In-Person
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)
{
uint32_t seen_mask = 0, dup_mask = 0;
std::vector<int> result;
for (const auto &job : jobs) {
uint32_t mask = (1ul << job.second) - (1ul << job.first);
dup_mask |= seen_mask & mask;
seen_mask |= mask;
}
for (int i = 0; i != jobs.size(); i++) {
uint32_t mask = (1ul << jobs[i].second) - (1ul << jobs[i].first);
if ((mask & dup_mask) != 0)
result.push_back(i);
}
return result;
}
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.
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.
yes it will. i intend to store the starting time in a set and will use a multimap to store starting and ending time.
I don't understand how it should work, but what your code execution time is it N^2 or NLogN or N
#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;
}
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;
}
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.
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.
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.
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[1] by one and hour[2] 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
How does your solution will give total number of overlapping jobs or indices of jobs which are overlapping?
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;
}
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)
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);
currentClosure.add(currJob);
// Compute closure of current job
Queue<Job> jobsAddedToClosure = new Queue<Job>();
jobsAddedToClosure.enqueue(currJob);
while (!jobsAddedToClosure.isEmpty()) {
Job job = jobsAddedToClosure.dequeue();
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
// added to any closure
if (intersects(j, job)) {
currentClosure.add(j);
jobsAddedToClosure.enqueue(j);
jobs.remove(j);
}
}
}
// Add closure of current job into result set
closures.add(currentClosure);
}
return closures;
}
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
// Start with adding first job
Set<Job> currentOverlappingSet = new Set<Job>();
currentOverlappingSet.add(jobs[0]);
int prevEnd = jobs[0].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) {
currentOverlappingSet.add(jobs[i]);
prevEnd = jobs[i].end;
} else {
// This job does not overlap
// Add previous set to results if it has overlaps
if (currentOverlappingSet.length > 1) {
overlappingSets.add(currentOverlappingSet);
}
// Start new set and add this job to it
currentOverlappingSet = new Set<Job>();
currentOverlappingSet.add(jobs[i]);
}
}
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].
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());
}
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];
result.Add(i);
result.Add(val.Item2);
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)
{
result.Add(prev.Item2);
result.Add(kvp.Value.Item2);
}
prev = kvp.Value;
}
result.Remove(-1);
// It is not sorted
return result;
}
public static Group{
LinkedList<Integer> setIndices = new LinkedList<Integer>();
int min;
int max;
Group merge(Group g){
if(g.min < min){
min = g.min;
}
if(g.max > max){
max = g.max;
}
setIndices.addAll(g.setIndices);
}
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
LinkedList<Group> groups = new LinkedList<Group>();
for(int i = 0; i < schedules.length; i++){
int[] sched : schedules[i];
Group g = new Group;
g.setIndices.add(i);
g.min = sched[0];
g.max = sched[1];
}
LinkedList<Group> complete = new LinkedList<Group>();
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{
groups.add(temp);
}
}
if(notMerged){
if(check.setIndices.size() > 1){
complete.add(check);
}
}
else{
groups.add(check);
}
}
int[][] results = new int[complete.()][];
for(int i = 0; i < complete.size(); i++){
results[i] = complete.removeFirst().getSets();
}
return results;
}
public class FindOverlapJobs {
public static List<Integer> findOverLappingJobs(Job[] jobs) {
int[] hours = new int[24];
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)) {
overlaps.add(i);
}
}
return overlaps;
}
public static void main(String[] args) {
Job[] jobs = new Job[5];
jobs[0] = new Job(1, 2);
jobs[1] = new Job(5, 6);
jobs[2] = new Job(1, 5);
jobs[3] = new Job(7, 8);
jobs[4] = new Job(1, 6);
System.out.println(findOverLappingJobs(jobs));
}
}
public class FindOverlapJobs {
public static List<Integer> findOverLappingJobs(Job[] jobs) {
int[] hours = new int[24];
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)) {
overlaps.add(i);
}
}
return overlaps;
}
public static void main(String[] args) {
Job[] jobs = new Job[5];
jobs[0] = new Job(1, 2);
jobs[1] = new Job(5, 6);
jobs[2] = new Job(1, 5);
jobs[3] = new Job(7, 8);
jobs[4] = new Job(1, 6);
System.out.println(findOverLappingJobs(jobs));
}
}
public class FindOverlapJobs {
public static List<Integer> findOverLappingJobs(Job[] jobs) {
int[] hours = new int[24];
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)) {
overlaps.add(i);
}
}
return overlaps;
}
public static void main(String[] args) {
Job[] jobs = new Job[5];
jobs[0] = new Job(1, 2);
jobs[1] = new Job(5, 6);
jobs[2] = new Job(1, 5);
jobs[3] = new Job(7, 8);
jobs[4] = new Job(1, 6);
System.out.println(findOverLappingJobs(jobs));
}
}
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[0];
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[0].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] << " ";
}
R
input <- "[1,2][5,6][1,5][7,8][1,6]"
j <- input
j <- gsub(pattern='\\[','',j)
j <- strsplit(j, ']')[[1]]
j <- sapply(j,FUN=strsplit,split=',')
pairs <- matrix(as.numeric(unlist(j)),byrow=T, ncol=2)
myRange <- function(data){
return(seq(from=data[1], data[2], 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)
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[100][2];
}
private void populate(int startNum, int endNum) {
if (startNum < endNum) {
inputAList[inputmapSize][0] = startNum;
inputAList[inputmapSize][1] = endNum;
} else {
inputAList[inputmapSize][0] = startNum;
inputAList[inputmapSize][1] = 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][0] <= inputAList[i][0]
|| inputAList[j][0] <= inputAList[i][1]
|| inputAList[j][1] <= inputAList[i][0]
|| inputAList[j][1] <= inputAList[i][1]) {
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();
}
}
solution :
Create a matrix A[8][8] (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.
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
[3] in one group
More details about the algorithm and pseudo-code, please refer to: cpluspluslearning-petert.blogspot.co.uk/2015/06/data-structure-and-algorithm-find.html
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 0 result vector;
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.
- LaithBasilDotNet May 13, 2015