Amazon Interview Question Interns
Country: United States
Interview Type: Phone Interview
Correct me if I am wrong, I think the running time is not O(n*(log(n)), but it's O(m*(log(n)) where m is all your TimeSlots and n all the TimeSlots of your friends.
But it's just a detail.
Using Hashmap to Save all the timeslots. Complexity should O(nlogn).
Assumptions: TimeSlots are always of same size.
package careerCup;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
public class CommanTimeSlot {
static HashMap<String,List<TimeSlot>> timeslots = new HashMap<String,List<TimeSlot>>();
public static void main(String[] args) {
// TODO Auto-generated method stub
//HashMap<String,List<TimeSlot>> timeslots = new HashMap<String,List<TimeSlot>>();
// friend 1
List<TimeSlot> timeSlotList = new ArrayList<TimeSlot>();
timeSlotList.add(new TimeSlot(8, 9));
timeSlotList.add(new TimeSlot(10, 11));
timeSlotList.add(new TimeSlot(16, 17));
timeSlotList.add(new TimeSlot(19, 20));
timeSlotList.add(new TimeSlot(21, 22));
timeslots.put("friend1",timeSlotList);
// friend 2
ArrayList<TimeSlot> timeSlotList2 = new ArrayList<TimeSlot>();
timeSlotList2.add(new TimeSlot(7, 8));
timeSlotList2.add(new TimeSlot(13, 14));
timeSlotList2.add(new TimeSlot(19, 20));
timeSlotList2.add(new TimeSlot(21, 22));
timeslots.put("friend2",timeSlotList2);
// friend 3
ArrayList<TimeSlot> timeSlotList3 = new ArrayList<TimeSlot>();
timeSlotList3.add(new TimeSlot(5, 6));
timeSlotList3.add(new TimeSlot(13, 14));
timeSlotList3.add(new TimeSlot(19, 20));
timeSlotList3.add(new TimeSlot(21, 22));
timeslots.put("friend3",timeSlotList3);
// friend 4
ArrayList<TimeSlot> timeSlotList4 = new ArrayList<TimeSlot>();
timeSlotList4.add(new TimeSlot(6, 7));
timeSlotList4.add(new TimeSlot(13, 14));
timeSlotList4.add(new TimeSlot(19, 20));
timeSlotList4.add(new TimeSlot(21, 22));
timeslots.put("friend4",timeSlotList4);
List<String> friendList = new ArrayList<String>();
friendList.add("friend1");
friendList.add("friend2");
friendList.add("friend3");
System.out.println(new TimeSlot(19,20).equals(new TimeSlot(19,20)));
List<TimeSlot> output = printFirstNCommonTimeslots(friendList , 1);
System.out.println(output.toString());
}
private static List<TimeSlot> getTimeSlots(String friend){
return timeslots.get(friend);
}
private static List<TimeSlot> printFirstNCommonTimeslots(
List<String> friends, int i) {
HashMap<TimeSlot, Integer> timeSlotMap = new HashMap<TimeSlot, Integer>();
List<TimeSlot> commanTimeSlot = new ArrayList<TimeSlot>();
int length = friends.size();
for(String friend:friends){
List<TimeSlot> timeSlotsforFriend = getTimeSlots(friend);
System.out.println(timeSlotsforFriend.toString());
for(TimeSlot ts: timeSlotsforFriend){
System.out.println(timeSlotMap.containsKey(ts));
if(!timeSlotMap.containsKey(ts)){
System.out.println(ts.toString());
System.out.println("Not Equals");
timeSlotMap.put(ts,1);
System.out.println("HS"+timeSlotMap.toString());
}else{
timeSlotMap.put(ts,timeSlotMap.get(ts)+1);
System.out.println(timeSlotMap.toString());
System.out.println("Equals");
if(timeSlotMap.get(ts)==length){
System.out.println("HS"+timeSlotMap.toString());
commanTimeSlot.add(ts);
System.out.println(ts.toString());
}
}
}
}
if(commanTimeSlot.size() > i){
Collections.sort(commanTimeSlot);
return commanTimeSlot.subList(0,i);
}else
return null;
}
}
private class TimeSlot implements Comparable {
int init;
int end;
public TimeSlot(int init, int end) {
super();
this.init = init;
this.end = end;
}
@Override
public String toString() {
return init + " " + end;
}
@Override
public int hashCode(){
return this.init;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
TimeSlot other = (TimeSlot) obj;
if (this.end != other.end)
return false;
if (this.init != other.init)
return false;
return true;
}
@Override
public int compareTo(Object arg0) {
TimeSlot ts = (TimeSlot) arg0;
if(this.init > ts.init){
return 1;
}else if(this.init < ts.init){
return -1;
}
return 0;
}
}
Assume 1-2 slot is represented as 1, 5-6 time slot represented as 5 etc
Let
person1 free slot array {1, 5}
person2 free slot array {1,3.6}
preson 3 free slot array {1,5,6}
concatenate the 3 arrays to form new array and sort this array
now traverse the array from 0th index and stop at point where 3 consecutive elements are same.
sort takes 0(nlogn) and traverse takes o(n) so o(nlogn)
I'm not very familiar with Java. So.. I will write pseudo code. (may have some bugs.)
// Assume that TimeSlot is a pair of integer from [0,23];
List<TimeSlot> get3CommonTimeSlots(List<string> Friends){
int timeCounter[24];
List<TimeSlot> timeslots, commonSlot;
int nFriends = Friends.size();
for (int i=0; i<24; i++) timeCounter[i]=0;
for ( friend in Friends ){
timeslots = getTimeSlots(friend);
for( timeslot in timeslots ){
for(int i=timeslot.start; i<timeslot.end; i++){
timeCounter[i]++;
}
}
}
int index = 0;
for(int i=0; i<3; i++){
TimeSlot slot;
while(index<24 && timeCounter[index] < nFriends) index++;
if (index==24) break;
slot.start = index;
while(index<24 && timeCounter[index] == nFriends) index++;
slot.end = index;
commonSlot.append(slot);
}
return commonSlot;
}
The idea is to use combination of mergesort comparison and breaking down times based on usage.
- Take next smallest time interval from all persons and compare against the others.
- It could
1) exactly match, or
2) be subset/superset of, or
3) intersect
- With remaining friends, find the smallest interval which matches and add it to the answer.
- Now move to the next time slice and repeat above. This will depend on based on one of three options above. e.g. in case of subset/superset or intersection, we need to split the time slices further.
One approach is to merge all timeslots of person 1 with person 2.
Then merge the result of this with all timeslots of person 3.
Iteratively do this with all people. You will end up with a list of timeslots that satisfy all people (or nothing, if there is no timeslot that satisfies them all).
Alternatively, use a hash, or even just an array to count the number of people available at hour h. For example, if you have 10 people and a[5] = 10, it means everyone is available from 5am-6am. Simply find the first three disjoint contiguous blocks where a[i] = n where n is the total number of people.
Ex. n = 10, a = {3, 5, 2, 10, 10, 10, 8, 7, 10, 3}
Two blocks exist: 3am-6am, and 9am-10am.
//This list will contain the overlapped time slots for all the friends. Initially this list will be //empty.
List<TimeSlot> overlappedTimeSlots = new ArrayList<TimeSlot>()
for(String friend : friendList) {
List<TimeSlot> list = getTimeSlots(friend);
overlappedTimeSlots = getOverlappedTimeSlots(overlappedTimeSlots , list);
}
//return the sub list of overlappedTimeSlots that contain 3 elements.
//getOverlappedTimeSlots will return the list of overlapped time.
//e.g Friend A has (5-6) (9-12) and Friend B has (5,6) and (9,10)
//then getOverlappedTimeSlots will return (5,6) and (9,10)
The problem can be solved using the following approach:
1. pick a person as a pivot, let's say the first friend let's call him A. If there are common timeslots, then at least 1 timeslot of A is in common with all others.
2. Iterate over A's timeslots and compare them with all others, if A's current timeslot has no match with any of the next person's timeslots, flag it as not a candidate. interrupt iteration and pick next slot of A.
3. Timeslots will either match or be inside or intersect another person timeslot calculate the intersection of both timeslots.
4. If A's current timeslot matches (or intersects) all others include it as part of the final result. Keep this in a Hashset to avoid duplicates. Do this until there's no more timeslots for A or if already found K target timeslots.
*Obs: using time as int range from 0 - 23, so 1PM will be 13, while 1AM will be 1. This is to facilitate timeslot calculation.
Solution: Time: O(m*(log(n)) - where m is the number of slots of Person chosen as pivot, memory: O(1).
Implementation in Java:
- guilhebl March 16, 2015public class Solution { public static void main(String[] args) { List<List<TimeSlot>> timeslots = new ArrayList<List<TimeSlot>>(); // friend 1 List<TimeSlot> timeSlotList = new ArrayList<TimeSlot>(); timeSlotList.add(new TimeSlot(6, 9)); timeSlotList.add(new TimeSlot(10, 14)); timeSlotList.add(new TimeSlot(16, 17)); timeSlotList.add(new TimeSlot(19, 20)); timeSlotList.add(new TimeSlot(21, 22)); timeslots.add(timeSlotList); // friend 2 timeSlotList = new ArrayList<TimeSlot>(); timeSlotList.add(new TimeSlot(7, 8)); timeSlotList.add(new TimeSlot(13, 14)); timeSlotList.add(new TimeSlot(17, 18)); timeSlotList.add(new TimeSlot(20, 23)); timeslots.add(timeSlotList); // friend 3 timeSlotList = new ArrayList<TimeSlot>(); timeSlotList.add(new TimeSlot(5, 8)); timeSlotList.add(new TimeSlot(13, 15)); timeSlotList.add(new TimeSlot(19, 20)); timeSlotList.add(new TimeSlot(21, 23)); timeslots.add(timeSlotList); // friend 4 timeSlotList = new ArrayList<TimeSlot>(); timeSlotList.add(new TimeSlot(6, 8)); timeSlotList.add(new TimeSlot(13, 16)); timeSlotList.add(new TimeSlot(19, 20)); timeSlotList.add(new TimeSlot(21, 22)); timeslots.add(timeSlotList); printFirstNCommonTimeslots(timeslots, 3); } public static void printFirstNCommonTimeslots(List<List<TimeSlot>> timeslots, int n) { if (n <= 0 || timeslots == null || timeslots.isEmpty()) { return; } Set<TimeSlot> commonTimeSlots = new HashSet<>(); TimeSlot candidate = null; int i = 0; int candidatesFound = 0; int listsAnalyzed = 0; boolean stillCandidate = false; boolean candidateFound = false; // get timeslots from first person and check if it matches with all others List<TimeSlot> firstPersonTimeslots = timeslots.get(0); for (TimeSlot timeSlot : firstPersonTimeslots) { candidate = timeSlot; stillCandidate = true; i = 1; while(i < timeslots.size() && stillCandidate) { List<TimeSlot> listT = timeslots.get(i); for (int j = 0; j < listT.size() && !candidateFound; j++) { TimeSlot timeSlot2 = listT.get(j); int initTimeA = candidate.init; int endTimeA = candidate.end; int initTimeB = timeSlot2.init; int endTimeB = timeSlot2.end; if (initTimeA == initTimeB || endTimeB == endTimeA || (initTimeA < endTimeB && initTimeA > initTimeB) || (initTimeB < endTimeA && initTimeB > initTimeA)) { while (initTimeA != initTimeB) { if (initTimeA < initTimeB) { initTimeA++; } else if (initTimeA > initTimeB) { initTimeB++; } } while (endTimeA != endTimeB) { if (endTimeA < endTimeB) { endTimeB--; } else if (endTimeA > endTimeB) { endTimeA--; } } candidate = new TimeSlot(initTimeA, endTimeA); candidateFound = true; } } if (candidateFound) { listsAnalyzed++; candidateFound = false; } else { stillCandidate = false; listsAnalyzed = 0; } i++; } if (listsAnalyzed == timeslots.size() - 1) { commonTimeSlots.add(candidate); candidatesFound++; listsAnalyzed = 0; if (candidatesFound == n) { break; } } } if (candidatesFound > 0) { Iterator<TimeSlot> timeSlots = commonTimeSlots.iterator(); while(timeSlots.hasNext()) { System.out.println(timeSlots.next()); } } } } class TimeSlot { int init; int end; public TimeSlot(int init, int end) { super(); this.init = init; this.end = end; } @Override public String toString() { return init + " " + end; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; TimeSlot other = (TimeSlot) obj; if (end != other.end) return false; if (init != other.init) return false; return true; } }