## Amazon Interview Question for SDE-2s

• 2

Country: India
Interview Type: In-Person

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

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

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

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.

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

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)

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

The ideal data structure would be a LinkedHashMap.
You will have the entries ordered in the way they come.
And retrieval is easy, as you can iterate over the entry set for the required to and from time.

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

Just to clarify, would it help to have a BST with key-value nodes to lookup the time while also the number of orders?

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

Use Interval Tree.

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

TreeMap can be used to solve this problem. Time as key and number of order as value in map and iterate map for given time interval.

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

A hashmap can be used to store the time and the data, and we can interate over the for loop to get the required sum.

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

``````{
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);
}``````

}

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

Data should store in the array and using binary to search for the start time and end time.
Than calculating total order between start time and end time will be (total order up to end time) - (total order up to start time)

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

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.

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

We can solve this problem by implementing priority queue (min/max), key is the time, value is the received orders count.

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

Use segment tree to query over a range
and to use time convert it to single int using equation = hour*60 + min

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

Hash Table can also be used. define hash table for each interval like index 0 for interval 12 - 1, index 1 for 1 - 2 and so on. so now we can traverse input and store total number of order in particular interval.

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

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

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

Segment tree should be used to handle this problem

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

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;
}

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

``````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;
}``````

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

``````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;``````

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

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

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

Use Array of size 24 all initialized to 0. All coming orders if are from 00:00:00 to 00:59:59 should get added to value at 0 and then stored at 0....THEN, All coming orders if are from 01:00:00 to 01:59:59 should get added to value at 1 and then stored at 1.....and so on.....

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

Just use an Array. Create an Array of size 24 with all values as 0. All coming orders that lie in the interval 00:00:00 to 00:59:59 should get added and stored at 0.......All coming orders that lie in the interval 01:00:00 to 01:59:59 should get added and stored at 1.....and so on

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

``Just use an Array. Create an Array of size 24 with all values as 0. All coming orders that lie in the interval 00:00:00 to 00:59:59 should get added and stored at 0.......All coming orders that lie in the interval 01:00:00 to 01:59:59 should get added and stored at 1.....and so on``

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

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??

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

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??

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

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))

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

TreeMap can be used for storing data. Iterate the tree map for particular interval.

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

TreeMap can be used to solve this problem. Time as key & number of order as value. Iterate the map for given time interval.

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.