CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for SDE-2s


Team: AWS
Country: United States
Interview Type: In-Person



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

Seems like storing in hashmap with user is as key and the rest metadata as value then finding key which has max resource consumption would solve it.

- Itsme September 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

-hash with uid as key rest as value
-simple liner loop to find max consumption

- tnutty2k8 September 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

The idea is to sort the table by UID (In the example the table is sorted by StartTime so we will take this as assumption if not we need to sort it)

After the table is sorted we can loop the table and calculate Max Total for each record.

package com.cracking.amazon;

import java.util.Arrays;
import java.util.Comparator;

public class ResourceConsumption {
	
	public static class LogRecord {
		public int UID,PID,StartTime,EndTime,Consumption,Total;
		
		public LogRecord(int UID,int PID,int StartTime,int EndTime,int Consumption) {
			this.UID = UID;
			this.PID = PID;
			this.StartTime = StartTime;
			this.EndTime = EndTime;
			this.Consumption = Consumption;
			this.Total = 0;
		}
		
		@Override
		public String toString() {
			String msg = String.format("\nUID = %d\tPID = %d\tStart = %d\tEnd = %d\tConsumption = %d\t Total = %d\n", 
					this.UID,
					this.PID,
					this.StartTime,
					this.EndTime,
					this.Consumption,
					this.Total);
			return msg;
		}
	}
	
	public static LogRecord[] logRecords = {
		new LogRecord(1, 1, 200, 300, 100),
		new LogRecord(2, 2, 230, 340, 80),
		new LogRecord(1, 3, 245, 315, 50),
		new LogRecord(1, 4, 305, 330, 20)
	};
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("Data");
		System.out.println(Arrays.toString(logRecords));
		
		Arrays.sort(logRecords, new Comparator<LogRecord>() {

			@Override
			public int compare(LogRecord o1, LogRecord o2) {
				// TODO Auto-generated method stub
				if(o1.UID < o2.UID) {
					return -1;  //small
				}
				
				if(o1.UID == o2.UID) {
					return 0;	//equal
				}
				
				
				return 1;	//big
			}
			
		});
		
		System.out.println("Sorted");
		System.out.println(Arrays.toString(logRecords));
		
		System.out.println("Calculate Totals");
		calculateTotal(logRecords);
		System.out.println(Arrays.toString(logRecords));

		int maxInd = getMaxTotal(logRecords);
		LogRecord maxRecord = logRecords[maxInd];
		System.out.println("Max Totals");
		String totalMsg = String.format("UID#%d\nBetween: %d - %d\nMax-Consumption: %d\n", 
				maxRecord.UID,
				maxRecord.StartTime,
				maxRecord.EndTime,
				maxRecord.Total);
		System.out.println(totalMsg);
		
	}
	
	public static void calculateTotal(LogRecord[] logRecords) {
		int len = logRecords.length;
		for(int i=0; i<len; i++) {
			LogRecord rec = logRecords[i];
			rec.Total = rec.Consumption;
			for(int j=i+1;j<len;j++) {
				LogRecord subRec = logRecords[j];
				if(subRec.StartTime >= rec.EndTime) {
					break;
				}
				
				if( (rec.StartTime <= subRec.StartTime) && (rec.EndTime > subRec.StartTime) ) {
					rec.Total += subRec.Consumption;
					continue;
				}
				
				break;
			}
		}
		
	}
	
	public static int getMaxTotal(LogRecord[] logRecords) {
		int maxInd = 0;
		int maxVal = logRecords[maxInd].Total;
		int len = logRecords.length;
		
		for(int i=1;i<len;i++) {
			if(maxVal < logRecords[i].Total) {
				maxInd = i;
				maxVal = logRecords[i].Total;
			}
		}
		
		return maxInd;
	}

}

Output:
=====


Data
[
UID = 1 PID = 1 Start = 200 End = 300 Consumption = 100 Total = 0
,
UID = 2 PID = 2 Start = 230 End = 340 Consumption = 80 Total = 0
,
UID = 1 PID = 3 Start = 245 End = 315 Consumption = 50 Total = 0
,
UID = 1 PID = 4 Start = 305 End = 330 Consumption = 20 Total = 0
]
Sorted
[
UID = 1 PID = 1 Start = 200 End = 300 Consumption = 100 Total = 0
,
UID = 1 PID = 3 Start = 245 End = 315 Consumption = 50 Total = 0
,
UID = 1 PID = 4 Start = 305 End = 330 Consumption = 20 Total = 0
,
UID = 2 PID = 2 Start = 230 End = 340 Consumption = 80 Total = 0
]
Calculate Totals
[
UID = 1 PID = 1 Start = 200 End = 300 Consumption = 100 Total = 150
,
UID = 1 PID = 3 Start = 245 End = 315 Consumption = 50 Total = 70
,
UID = 1 PID = 4 Start = 305 End = 330 Consumption = 20 Total = 20
,
UID = 2 PID = 2 Start = 230 End = 340 Consumption = 80 Total = 80
]
Max Totals
UID#1
Between: 200 - 300
Max-Consumption: 150

- ProTechMulti September 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) : map.put( UID, cumulative ( end - start ) )

O(n) : max of values and finding max key

- Sunny September 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MaxConsumption {
public static void main(String[] args) {
int maxConsumption = 0;
int maxKey = 0;
HashMap<Integer, List<Integer>> hm = new HashMap<Integer, List<Integer>>();
List<Integer> consumptionval1 = new ArrayList<Integer>();
consumptionval1.add(100);
consumptionval1.add(50);
consumptionval1.add(20);

List<Integer> consumptionval2 = new ArrayList<Integer>();
consumptionval2.add(80);

hm.put(1, consumptionval1);
hm.put(2, consumptionval2);

for (Map.Entry<Integer, List<Integer>> m : hm.entrySet()) {
int key = m.getKey();
List<Integer> values = m.getValue();
System.out.println("key:" + key);
System.out.println("values:" + values);
int sum = 0;
for (int i = 0; i < values.size(); i++) {
sum = sum + values.get(i);
}
if (sum > maxConsumption) {
maxConsumption = sum;
maxKey = key;
}

}
System.out.println("UID is:"+maxKey+" "+"MaxConsumption is:"
+maxConsumption);

}
}

- Anonymous October 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MaxConsumption {
	public static void main(String[] args) {
		int maxConsumption = 0;
		int maxKey = 0;
		HashMap<Integer, List<Integer>> hm = new HashMap<Integer, List<Integer>>();
		List<Integer> consumptionval1 = new ArrayList<Integer>();
		consumptionval1.add(100);
		consumptionval1.add(50);
		consumptionval1.add(20);

		List<Integer> consumptionval2 = new ArrayList<Integer>();
		consumptionval2.add(80);

		hm.put(1, consumptionval1);
		hm.put(2, consumptionval2);

		for (Map.Entry<Integer, List<Integer>> m : hm.entrySet()) {
			int key = m.getKey();
			List<Integer> values = m.getValue();
			System.out.println("key:" + key);
			System.out.println("values:" + values);
			int sum = 0;
			for (int i = 0; i < values.size(); i++) {
				sum = sum + values.get(i);
			}
			if (sum > maxConsumption) {
				maxConsumption = sum;
				maxKey = key;
			}

		}
		System.out.println("UID is:"+maxKey+" "+"MaxConsumption is:"
				+maxConsumption);

	}
}

- magnish October 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MaxConsumption {
	public static void main(String[] args) {
		int maxConsumption = 0;
		int maxKey = 0;
		HashMap<Integer, List<Integer>> hm = new HashMap<Integer, List<Integer>>();
		List<Integer> consumptionval1 = new ArrayList<Integer>();
		consumptionval1.add(100);
		consumptionval1.add(50);
		consumptionval1.add(20);

		List<Integer> consumptionval2 = new ArrayList<Integer>();
		consumptionval2.add(80);

		hm.put(1, consumptionval1);
		hm.put(2, consumptionval2);

		for (Map.Entry<Integer, List<Integer>> m : hm.entrySet()) {
			int key = m.getKey();
			List<Integer> values = m.getValue();
			System.out.println("key:" + key);
			System.out.println("values:" + values);
			int sum = 0;
			for (int i = 0; i < values.size(); i++) {
				sum = sum + values.get(i);
			}
			if (sum > maxConsumption) {
				maxConsumption = sum;
				maxKey = key;
			}

		}
		System.out.println("UID is:"+maxKey+" "+"MaxConsumption is:"
				+maxConsumption);

	}
}

- magnish October 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MaxConsumption {
	public static void main(String[] args) {
		int maxConsumption = 0;
		int maxKey = 0;
		HashMap<Integer, List<Integer>> hm = new HashMap<Integer, List<Integer>>();
		List<Integer> consumptionval1 = new ArrayList<Integer>();
		consumptionval1.add(100);
		consumptionval1.add(50);
		consumptionval1.add(20);

		List<Integer> consumptionval2 = new ArrayList<Integer>();
		consumptionval2.add(80);

		hm.put(1, consumptionval1);
		hm.put(2, consumptionval2);

		for (Map.Entry<Integer, List<Integer>> m : hm.entrySet()) {
			int key = m.getKey();
			List<Integer> values = m.getValue();
			System.out.println("key:" + key);
			System.out.println("values:" + values);
			int sum = 0;
			for (int i = 0; i < values.size(); i++) {
				sum = sum + values.get(i);
			}
			if (sum > maxConsumption) {
				maxConsumption = sum;
				maxKey = key;
			}

		}
		System.out.println("UID is:"+maxKey+" "+"MaxConsumption is:"
				+maxConsumption);

	}
}

- magnish October 07, 2017 | 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