Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
You should do cumulative sum array and take the diff. You can do it by recording the sum at every given moment or just by attaching the new cumulative sum and the time. In the latter case you also need a binary search so it becomes logn, in the first case you get constant time complexity.
Store in a array, each array entry represent a minute time slot. In each entry we'll have number of order and up to current minute total order. Any minutes dose not have order coming in, simply maintain current total order and set number of order to 0.
All we have to do is using binary search on Array to locate starting time and end time. The order between these two time will be (total current order in the end time) - (total current order in the start time).
Total time is O(log n)
{
import java.util.*;
public class timeDataCareerCup {
public void timeDatae(timeData d, int value){
Map<timeData, Integer> map = new HashMap<timeData,Integer>();
map.put(d, value);
System.out.println(map);
int sum = 0;
for(timeData data : map.keySet()){
if(data.hr >= 1 && data.mint >= 30 && data.hr <= 2 && data.mint <= 30){
sum+= map.get(data);
}
}
System.out.println(sum);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int value = 10;
timeData u = new timeData();
u.setHr(1);
u.setMint(30);
u.setEst("pm");
timeDataCareerCup tdc = new timeDataCareerCup();
tdc.timeDatae(u, 1000);
u.setHr(2);
u.setMint(30);
u.setEst("pm");
tdc.timeDatae(u, 2000);
}
}
Use a hashmap<hashcode, count>
where hashcode is obtained by converting time using some hash function.
for eg. hashcode produced for 13:00:01:000 to 13:00:01:999 would be the same.
count is the number of orders we get during that minute.
When we want to find number of orders between 2 timestamps.. fetch all the relevant counts from the hashmap and add them up.
We need a Stack that, as events come in, remembers two things:
-the current time
-the sum of all elements up to now
Then, for each query we do two binary searches to find the start and end of the interval, and we return the sum of elements in the interval.
Complexity: O(logN)
Implementation: MUCH easier than a binary tree
public static Integer allOrder (Integer time1, Integer time2) {
HashMap<Integer, Integer> orderMap = new HashMap<Integer, Integer> ();
orderMap.put(1, 7);
orderMap.put(2, 5);
orderMap.put(3, 6);
orderMap.put(4, 5);
int sum = 0;
Set<Integer> keySet = orderMap.keySet();
for(Integer key : keySet) {
if(key >= time1 && key <= time2)
sum += orderMap.get(key);
}
return sum;
}
public static Integer allOrder (Integer time1, Integer time2) {
HashMap<Integer, Integer> orderMap = new HashMap<Integer, Integer> ();
orderMap.put(1, 7);
orderMap.put(2, 5);
orderMap.put(3, 6);
orderMap.put(4, 5);
int sum = 0;
Set<Integer> keySet = orderMap.keySet();
for(Integer key : keySet) {
if(key >= time1 && key <= time2)
sum += orderMap.get(key);
}
return sum;
}
public static Integer allOrder (Integer time1, Integer time2) {
HashMap<Integer, Integer> orderMap = new HashMap<Integer, Integer> ();
orderMap.put(1, 7);
orderMap.put(2, 5);
orderMap.put(3, 6);
orderMap.put(4, 5);
int sum = 0;
Set<Integer> keySet = orderMap.keySet();
for(Integer key : keySet) {
if(key >= time1 && key <= time2)
sum += orderMap.get(key);
}
return sum;
Most people suggested to use a TreeMap. If you use a TreeMap, both insertion and query will cost O(logN)
It's possible to do insertion in constant time by using a List of the below struct:
struct Order
{
DateTime time;
long orderCount;
long cumulativeOrderCount;
}
This list will be naturally sorted by time.
Whenever a query is performed, do a binary search on the list to find start time and end time (or the closest values) and return the difference in cumulativeOrderCount values.
This way, insertion is constant time, and only query is O(logN).
I think we can convert time to 2400 format and round it to floor hundred value.e.g. 01:15-> 1315->1300.
and then store them in following HashMap
HashMap<Integer, ArrayList<TimeOrderNode>> timeOrderMap;
public class TimeOrderNode {
public int time;
public int orderCount;
}
TimeOrderNode root = new TimeOrderNode();
root.time = 1205;
root.orderCount = 5;
ArrayList<TimeOrderNode> list = new ArrayLIst<>();
list.put(root);
timeOrderMap.put(1200, list);
The ArrayList will not grow beyond 60 mins, so traversing will be constant time.
Do you think its a good approach??
I think we can convert time to 2400 format and round it to floor hundred value.e.g. 01:15-> 1315->1300.
and then store them in following HashMap
HashMap<Integer, ArrayList<TimeOrderNode>> timeOrderMap;
public class TimeOrderNode {
public int time;
public int orderCount;
}
TimeOrderNode root = new TimeOrderNode();
root.time = 1205;
root.orderCount = 5;
ArrayList<TimeOrderNode> list = new ArrayLIst<>();
list.put(root);
timeOrderMap.put(1200, list);
The ArrayList will not grow beyond 60 mins, so traversing will be constant time.
Do you think its a good approach??
We can use RangeSum segment tree. Here we can take an array of size 24*60-1440 size.
This should be enough for a day's booking. The array element stores the number of orders and by default contains 0.
Implement segment tree where at each node you store, leftIndex, rightIndex and sum between the two indexes.
The time complexity of adding an order or finding is O(log(n))
You need a binary tree or equivalent representation that stores the total number of orders before the point in time. Then you simply do a binary search to find the node just before the time range and a binary search to find the node before the end of the time range and subtract the start from the beginning. Total time is O(log n).
- JC315 July 21, 2016