Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
8
of 8 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).

- JC315 July 21, 2016 | Flag Reply
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.

- Anonymous July 21, 2016 | Flag Reply
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)

- James Lee August 05, 2016 | Flag Reply
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.

- Friend July 21, 2016 | Flag Reply
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?

- ardzoht July 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Interval Tree.

- Ricky July 22, 2016 | Flag Reply
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.

- Anonymous July 23, 2016 | Flag Reply
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.

- Hitesh July 27, 2016 | Flag Reply
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);
	}

}

- Hitesh Pandey July 27, 2016 | Flag Reply
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)

- James August 05, 2016 | Flag Reply
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.

- Amit August 11, 2016 | Flag Reply
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.

- Senthil August 23, 2016 | Flag Reply
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

- Anonymous August 25, 2016 | Flag Reply
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.

- Anonymous September 08, 2016 | Flag Reply
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

- ot14 September 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Segment tree should be used to handle this problem

- Anonymous September 28, 2016 | Flag Reply
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;
}

- Sherwin November 08, 2016 | Flag Reply
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;
	}

- Sherwin November 08, 2016 | Flag Reply
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;

- Anonymous November 08, 2016 | Flag Reply
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).

- rmn November 27, 2016 | Flag Reply
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.....

- teji.catia@gmal.com December 23, 2016 | Flag Reply
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

- teji.catia December 23, 2016 | Flag Reply
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

- teji.catia December 23, 2016 | Flag Reply
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??

- undefined January 16, 2017 | Flag Reply
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??

- kvdeshmukh1989 January 16, 2017 | Flag Reply
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))

- Anonymous September 27, 2017 | Flag Reply
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.

- Anonymous July 23, 2016 | Flag Reply
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.

- dileepkr18 July 23, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More