# [Challenge] Largest Score off of a Deque Game

Page 1 of 1

## 12 Replies - 4659 Views - Last Post: 27 February 2014 - 05:24 PM

### #1 Dogstopper

Reputation: 2972
• Posts: 11,223
• Joined: 15-July 08

# [Challenge] Largest Score off of a Deque Game

Posted 23 February 2014 - 01:18 PM

Hey all!

This week's algorithm challenge is one that is almost always on job interviews, and as such, it is an extremely useful algorithm to learn. The algorithm should solve the following game:

Given a Deque (Double Ended Queue) full of numbers that both players can fully observe. Each player then takes a turn to take their favorite number off the end of the deque until there are no numbers left. You may assume that there are an even number of numbers on the deque. The goal is to maximize the number of points you earn and minimize your opponents.

This algorithm should return the maximum score that you can achieve and the steps necessary to reach that maximum. (Return an array of "F" or "B" meaning front or back).

Good Luck! Have fun!

Is This A Good Question/Topic? 2

## Replies To: [Challenge] Largest Score off of a Deque Game

### #2 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

## Re: [Challenge] Largest Score off of a Deque Game

Posted 23 February 2014 - 05:33 PM

Alrighty then, this was fun.

Spoiler

Editing on DIC can be a pain, we need some Latex support here

This post has been edited by mostyfriedman: 23 February 2014 - 06:24 PM

### #3 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

## Re: [Challenge] Largest Score off of a Deque Game

Posted 23 February 2014 - 05:39 PM

Btw I don't know if by "Algorithm to learn" you mean that there's a standard algorithm for this specific problem, or that there's a general strategy that is generally useful for these kinds of problems.

### #4 Dogstopper

Reputation: 2972
• Posts: 11,223
• Joined: 15-July 08

## Re: [Challenge] Largest Score off of a Deque Game

Posted 23 February 2014 - 10:53 PM

Yeah, I mean there are different ways to do it, but the algorithm that you gave is generally accepted as the correct answer! So kudos to you!

### #5 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

## Re: [Challenge] Largest Score off of a Deque Game

Posted 24 February 2014 - 03:43 AM

Kewl, this is the first time i see this problem and it was fun. I suppose one can also use search, but I that'll be much slower.

### #6 baavgai

• Dreaming Coder

Reputation: 7483
• Posts: 15,510
• Joined: 16-October 07

## Re: [Challenge] Largest Score off of a Deque Game

Posted 24 February 2014 - 04:34 AM

This looks interesting; I've also never seen it before.

I'm going to assume I'm the first player. Should I return the max I can get, period. Or, the max I can get if the opponent is also playing optimally?

### #7 Dogstopper

Reputation: 2972
• Posts: 11,223
• Joined: 15-July 08

## Re: [Challenge] Largest Score off of a Deque Game

Posted 24 February 2014 - 07:22 AM

Baavgai, go with if the player is a rational agent and is playing optimally

### #8 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

## Re: [Challenge] Largest Score off of a Deque Game

Posted 24 February 2014 - 07:29 AM

I assumed if both are playing optimally and I start first. If the other isn't playing optimally, the problem will be trivial to solve.

### #9 Skydiver

• Code herder

Reputation: 7056
• Posts: 23,986
• Joined: 05-May 12

## Re: [Challenge] Largest Score off of a Deque Game

Posted 24 February 2014 - 09:57 PM

I remember encountering this question at an interview at Amazon.

### #10 domfx

• New D.I.C Head

Reputation: 1
• Posts: 1
• Joined: 25-February 14

## Re: [Challenge] Largest Score off of a Deque Game

Posted 25 February 2014 - 10:26 PM

Hi there,

I'm new here and I came across this post and decided to have a go.

Spoiler

### #11 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

## Re: [Challenge] Largest Score off of a Deque Game

Posted 26 February 2014 - 04:53 PM

domfx, on 26 February 2014 - 08:26 AM, said:

Hi there,

I'm new here and I came across this post and decided to have a go.

Spoiler

Good try, but unfortunately the greedy strategy will not give optimal results. Try this test case:
{5, 100, 1, 2}

In this case player 1 will greedily choose 5, player 2 chooses 100, player 1 chooses 2, player 2 chooses 1
That will give a total score of 7 for player 1, and 101 for player 2.

However, if they both play optimally, then the game can proceed as follows:

player 1 chooses 2, player 2 chooses 5, player 1 chooses 100, player 2 chooses 1.

That will result in a total score of 102 for player 1, and 6 for player 2.

Think about that, and see how you can fix it .

### #12 cfoley

• Cabbage

Reputation: 2392
• Posts: 5,024
• Joined: 11-December 07

## Re: [Challenge] Largest Score off of a Deque Game

Posted 27 February 2014 - 10:09 AM

Spoiler

This post has been edited by cfoley: 27 February 2014 - 10:11 AM

### #13 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

## Re: [Challenge] Largest Score off of a Deque Game

Posted 27 February 2014 - 05:24 PM

cfoley, on 27 February 2014 - 08:09 PM, said:

Spoiler

It's a bit tricky, but really not hard. You're on the right track though.