Amazon Interview

Q1 Connections on level

previous_connection_level = 0
total_connections = 0
for level in connections:
	current_level_connections = 0
	for node in level:
		if node == 1:
			current_level_connections += 1
	total_connections += previous_connection_level * current_level_connections
	if current_level_connections > 0:
		current_level_connections = previous_connection_level
"""
Time Complexity = O(NM), where N is the size of the row, and M is the size of the Column
Space Complexity = O(1), no additional space was used
"""

Q2 Investment query range

TreeMap<Integer> map = new TreeMap<>();
 
for (int query : queries) {
	map.put(query[0], map.getOrDefault(query[0], 0) + query[2])
	map.put(query[1] + 1, map.getOrDefault(query[1] + 1, 0) - query[2]);
}
 
int max = 0;
int curr = 0;
for (int key : map.keySet()) {
	curr += map.get(key);
	max = Math.max(max, curr);
}
return max;
/*
# Time Complexity = O(olog(n)), where o is the number of contributions and n is the maximum amount of elements (rounds) we can insert into our sorted map
Space Complexity = O(o) where o is the unique indexes in our contributions as it is the maximum unique numbers we can have in our sorted map
 
Alternative solution:
Create array of size n, and at each interval place decrements and increments, then traverse array and apply increments and decrements.
 
Time Complexity = O(o + n)
Space Complexity = O(n)
*/

Total time spent→ interview was for 70 minutes, 49 minutes left, so 21 minutes total OA1 did it on September 18th Saturday → Compiled maybe ~5 times for both OA2 Did it on September 19th Sunday