Amazon Interview Question for SDE-3s

• 1
of 1 vote

Country: United States
Interview Type: In-Person

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

edited, added corner cases and updated recursion
@tryingtolearn: yes it's dp, but watch out your recursion, it has some flaws, did you verify with examples?

``````'''
Assumption: if all are negative, we select empty set,
sum 0 > anything negative
Solution:
---------
Recursion:
/ max(0, value(0)), for i = 0
dp(i) = |  max(dp(0), value(1)), for i = 1
\ max(dp(i - 2) + value(i), dp(i - 1)), for i > 1
Optimization:
-------------
since the recursion only accesses dp(i-2) and dp(i-1) we can get around the dp-array
'''
def maxboxes(values):
if(len(values) == 0): return 0
dp = [0 for i in range(len(values))]
dp = max(0, values)
if(len(values) == 1): return dp
dp = max(dp, values)
for i in range(2, len(values)):
dp[i] = max(dp[i-2] + values[i], dp[i-1])
return dp[len(values)-1]

# optimized to remove dp-array
def maxboxesOpt(values):
if(len(values) == 0): return 0
dp0 = max(0, values)
if(len(values) == 1): return dp0
dp1 = max(dp0, values)
for i in range(2, len(values)):
tmp = dp1
dp1 = max(dp0 + values[i], dp1)
dp0 = tmp
return dp1

print(maxboxesOpt([0,1,-2,3])) # should be 4
print(maxboxesOpt([8,1,-1,2,2,10])) # should be 20
print(maxboxesOpt([10,0,0,0,20])) # should be 30
print(maxboxesOpt([-1, -2, -3])) # should be 0
print(maxboxesOpt([])) # should be 0
print(maxboxesOpt([-2])) # should be 0
print(maxboxesOpt()) # should be 99``````

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

@Chrisk, thank you for pointing out, my recursion is wrong. I apologize I wrote it without thinking though. I have a question in your solution
print(maxboxes([8,1,-1,2,2,10])) # should be 18, should not this be
20, { 8,2, 10} =20?

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

@ChrisK, your solution is not working for input containing all negatives, e.g. [-1,-2,-3]. Also, there is no need in dp list.

Here is my solution with O(n) time / O(1) memory. I hope it covers all corner cases :)

``````class Main {
public static void main(String[] args) {
System.out.println(solve(new int[] {0,1,-2,3}));      // -> 1+3 = 4
System.out.println(solve(new int[] {8,1,-1,2,2,10})); // -> 8+2+10 = 20
System.out.println(solve(new int[] {10,0,0,0,20}));   // -> 10+20 = 30
System.out.println(solve(new int[] {-1,-2,-3}));      // -> all negatives -> 0
}

private static int solve(int[] boxes) {
if (boxes.length == 0) return 0;
if (boxes.length == 1) return max(0, boxes);

int box2 = boxes;
int box1 = boxes;
for (int i = 2; i < boxes.length; i++) {
int curr = box2 + boxes[i];
box2 = max(box2, box1);
box1 = max(box1, curr);
}
return max(box1, max(box2, 0));
}
}``````

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

@petrov4feedly, thanks for providing optimized version without memorization,a minor bug that I see,
for e,g -3, -2 , -1 int curr = box2 + boxes[i]; this needs to be changed to int curr = max(box2 + boxes[i], boxes[I]))? or else your solution gives out -2

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

@petro4feedly , i had a question. What if we have boxes something like {8,9,1,1} then what is supposed to be the answer. Ans which variable gives us the answer

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

Am i reading the question wrong? It tells the boxes need to be sequential and also saying we cannot use a box next to what is selected.

so i need to first sort the list and then smart select boxes so that the sum is the maximum possible.

but if I follow these rules many of answers above looks wrong. what am i missing here?

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

Looks like I miss something here... I see answers and they looks good. but did not get how the conditions are met in the logic.

what we need to do : Select the numbers in order to have the maximum sum from collection.

Limitations.
1) sequentially placed boxes
2) Cannot select adjacent box to it, but can select any other.

So once I select a box i cannot select next one. so essentially I can skip one box but if a select a box i cannot select next box to it.

How these conditions are met.

10, 0, 0, 0, 20 -> 0, 0, 0, 10, 20 = 30? but it fails the rule since if i select 10 i cannot take 20.
8, 1, -1, 2, 20, 10 - > -1, 1, 2, 8, 10, 20 = 28. Yes i get the answer. but how it is coming in?
-1, -2, -3 = is this should be -1 and not zero since the maximum value must be the sum of one or more values from array?

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

``````public int maxProfit(int[] nums) {
int n = nums.length;
int even = 0;
int odd = 0;

for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
even = Math.max(odd, even + nums[i]);
} else {
odd = Math.max(even, odd + nums[i]);
}
}

return Math.max(even, odd);
}``````

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

``````int maxSum(const vector<int>& v)
{
const auto size = v.size();

if(size == 1)
{
return v;
}

if(size == 2)
{
return max(v, v);
}

// Assuming no integer overflow happens, i.e. sum variable will not overflow
int sum = (1 << (8 * sizeof(int) - 1));

for(auto iter = v.begin(); iter != prev(v.end(), 2); ++iter)
{
vector<int> v1(v.end() - iter - 2);

copy(next(iter, 2), v.end(), v1.begin());

sum = max(sum, *iter + maxSum(v1));
}

return sum;
}``````

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

this dynamic programming problem
f(m) is max value at index m
f(m) = max{ f(m-1) +value(m), f(m-1)}

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.