Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
what is the condition for winning? Also can they remove just the last pointer on the list's either sides?
After each user plays the game- removal of a number from the list, the sum is collected for each user, as he proceeds in the game. After all the turns, the sum for each user is noted, and whichever is higher wins the game!
my question is can they pick any number or they have to pick sequentially and is the array sorted in any way?
The array is not sorted, they can remove the number from either ends of the dequeue. But this is done in an alternative fashion , starting with the first user.
If there are two users A, B . First A picks any number either from front;/ rear . And then B picks. And then A.. till the queue becomes empty!
What does the "...maximize the chance of each player winning..." mean? I am avoiding thinking along the min/max algo. direction.
Is it that the end sums of both the players needs be or will eventually be closer to each other as much as possible? And then the one who happens to have a larger sum wins?
so if I have understood this right, after each player makes the decision, the sum of the digits/numbes left behind in the deque is added to their total ?
> since you can either pop an element from the head or tail, the decision can just be based on comparing head->peek() and tail->peek() (whichever is smaller).
If on the other hand, after each player decides the number formed out of the digits/numbers in the deque are added to their total, the decision is mainly based on what the next element to head is.
For example: if the deque is,
head-> 6 2 5 4 3 1 7 8 <-tail
if head->next->peek() < head->value() { pop (tail) }
else if head->next->peek() == head->value() {
if tail->prev->peek() > tail->value {
pop (tail)
} else { pop (head) }
else { pop(head) }
(am assuming that the deque has a suitable API to support the operations mentioned above. idea is to discuss what an ideal strategy should be)
this is a Dynamic programming question..similar to maximum sum from coins in a line question..
- Anonymous March 25, 2013