Amazon SDE I OA questions
Summary
I completed the Amazon SDE I Online Assessment, which consisted of two challenging algorithmic problems. The first involved processing a series of transactions to update a list and calculate sums, which I solved using a frequency hashmap. The second problem, to find the longest arithmetic progression with a single element change, I found very difficult and could not solve optimally.
Full Experience
Role: SDE I
Location: Nord Europe
Question 1:
Input: A list of integers entries and a 2D integer list transactions ( so a list of lists of integers).
Every transaction inside transactions is a pair of two numbers [old_v, new_v]. For each pair:
- Find all the indexes in entries where entries[idx] == old_v
- Replace the value at those indexes with new_v
- Calculate the sum of all the numbers in entries after the update
Output: Return a list of sums after each transaction.
Notes: The text explicitly said that brute force solutions would be considered wrong, even if they passed the tests.
Honestly, the hardest part here was understanding what the problem wanted, as the text was very long and unclear with a sort of story. There were also some edge cases like sums going into overflow for larger inputs, requiring the use of Longs
Solved optimally with a frequency hashmap.
Question 2:
Input: A list of integers deviation.
Task: Find the length of the longest contiguous subarray that forms an arithmetic progression (AP), where the difference between consecutive elements is constant. We are allowed at most one element change in the array to maximize this length.
Example: Given the array [8, 5, 2, 1, 100], if you change the 1 to -1, you get the progression [8, 5, 2, -1] with a constant difference of -3, giving a maximum length of 4.
I attempted this with a sliding window approach but only passed 3 out of 15 test cases. I also tried a brute force approach but that resulted in an LTE so I ended up submitting the sliding window. I guess it could be solved with a sort of Prefix Sum?
Honestly I found this problem very hard (but I'm sure for many of you it's a piece of cake).
Interview Questions (2)
Input: A list of integers entries and a 2D integer list transactions ( so a list of lists of integers).
Every transaction inside transactions is a pair of two numbers [old_v, new_v]. For each pair:
- Find all the indexes in entries where entries[idx] == old_v
- Replace the value at those indexes with new_v
- Calculate the sum of all the numbers in entries after the update
Output: Return a list of sums after each transaction.
Notes: The text explicitly said that brute force solutions would be considered wrong, even if they passed the tests.
Honestly, the hardest part here was understanding what the problem wanted, as the text was very long and unclear with a sort of story. There were also some edge cases like sums going into overflow for larger inputs, requiring the use of Longs
Input: A list of integers deviation.
Task: Find the length of the longest contiguous subarray that forms an arithmetic progression (AP), where the difference between consecutive elements is constant. We are allowed at most one element change in the array to maximize this length.
Example: Given the array [8, 5, 2, 1, 100], if you change the 1 to -1, you get the progression [8, 5, 2, -1] with a constant difference of -3, giving a maximum length of 4.
I attempted this with a sliding window approach but only passed 3 out of 15 test cases. I also tried a brute force approach but that resulted in an LTE so I ended up submitting the sliding window. I guess it could be solved with a sort of Prefix Sum?
Honestly I found this problem very hard (but I'm sure for many of you it's a piece of cake).