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

#1 Dogstopper   User is offline

  • The Ninjaducky
  • member icon

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

[Challenge] Largest Score off of a Deque Game

Post icon  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   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • 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

Was This Post Helpful? 1
  • +
  • -

#3 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#4 Dogstopper   User is offline

  • The Ninjaducky
  • member icon

Reputation: 2972
  • View blog
  • 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!
Was This Post Helpful? 0
  • +
  • -

#5 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#6 baavgai   User is online

  • Dreaming Coder
  • member icon


Reputation: 7483
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#7 Dogstopper   User is offline

  • The Ninjaducky
  • member icon

Reputation: 2972
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#8 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#9 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7056
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#10 domfx   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • 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

Was This Post Helpful? 1
  • +
  • -

#11 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

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

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

Posted 26 February 2014 - 04:53 PM

View Postdomfx, 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 :).
Was This Post Helpful? 1
  • +
  • -

#12 cfoley   User is offline

  • Cabbage
  • member icon

Reputation: 2392
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#13 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

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

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

Posted 27 February 2014 - 05:24 PM

View Postcfoley, 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.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1