Amazon Interview Question
SDE-2sCountry: United States
public class Doors {
public class visitor {
int time;
String dir;
public visitor(int time, String dir) {
this.time = time;
this.dir = dir;
}
}
public String defaultDir = "In";
public String lastDir = defaultDir;
public static void main(String[] args) {
int[] time = new int[] { 2, 3, 5, 1, 7, 4, 2 };
String dir[] = new String[] { "In", "Out", "In", "Out", "Out", "In", "Out" };
Doors obj = new Doors();
obj.findTime(time, dir);
}
private void findTime(int[] time, String[] dir) {
Map<Integer, Map<String, List<visitor>>> myMap = new TreeMap<>();
for (int i = 0; i < time.length; i++) {
List<visitor> myList = new ArrayList<Doors.visitor>();
if (!myMap.containsKey(time[i])) {
Map<String, List<visitor>> visitorMap = new HashMap<String, List<visitor>>();
myList.add(new visitor(time[i], dir[i]));
visitorMap.put(dir[i], myList);
myMap.put(time[i], visitorMap);
} else {
Map<String, List<visitor>> visitorMap = myMap.get(time[i]);
if (!visitorMap.containsKey(dir[i])) {
myList.add(new visitor(time[i], dir[i]));
visitorMap.put(dir[i], myList);
} else {
myList = visitorMap.get(dir[i]);
myList.add(new visitor(time[i], dir[i]));
visitorMap.put(dir[i], myList);
}
}
}
for (Entry<Integer, Map<String, List<visitor>>> entry : myMap.entrySet()) {
if (entry.getValue().size() > 1) { // now we know multiple people are trying to enter at the same time
List<visitor> visitors = entry.getValue().get(lastDir);
for (visitor v : visitors) {
System.out.println(v.time + " : " + v.dir);
}
lastDir = lastDir.contentEquals("In") ? "Out" : "In";
visitors = entry.getValue().get(lastDir);
for (visitor v : visitors) {
System.out.println(v.time + " : " + v.dir);
}
} else {
if (entry.getValue().containsKey("In")) {
List<visitor> visitors = entry.getValue().get("In");
for (visitor v : visitors) {
System.out.println(v.time + " : " + v.dir);
}
lastDir = "In";
} else {
List<visitor> visitors = entry.getValue().get("Out");
for (visitor v : visitors) {
System.out.println(v.time + " : " + v.dir);
}
lastDir = "Out";
}
}
entry.setValue(new HashMap<String, List<visitor>>());
}
}
}
Assumptions: time is in minutes, 0 means "in position" and 1 means "out position". Therefore direction Array has either 0 or 1 indicating that person is either going in or out.
Note: the code is not tested.
int [] getSequence(int [] timeList, int [] directionList){
if(timeList.length == 0 || directionList.length != timeList.length)return null;
HashMap<int,List<Integer>> map = new HashMap<>();
int [] result = new int [timeList.length];
int door = 0;
int minTime = getMinTime(timeList);
int maxTime = getMaxTime(timeList);
for(int i = 0; i < timeList.length; i++){
map.putIfAbsent(timeList[i],new ArrayList<Integer>());
map.get(timeList[i]).add(directionList[i]);
}
int j = 0;
for(int i = minTime; i <= maxTime; i++){
if(map.containsKey(i)){
List<Integer> list = map.get(i);
if(list.size() == 1){
result[++j] = list.get(0);
door = reslut[j];
}else if(list.size() >= 2){
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
if(iterator.next() == door){
iterator.remove();
result[++j] = door;
}
}
for(int value : list){
door = value;
result[++j] = value;
}
}
}
}
return result;
}
private int getMaxTime(int [] timeList){
int maxTime = -1;
for(int time : timeList)
maxTime = time > maxTime? time : maxTime;
return maxTime;
}
private int getMinTime(int [] timeList){
int minTime = Integer.MaxVal;
for(int time : timeList)
minTime = time < minTime? time : minTime;
return minTime;
}
}
- ash April 22, 2020