Adobe Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




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

If N = 1, starting move is trivial.

For N > 1, the winning condition is to leave the opponent in a position that he will always has two boxes with same no. of sticks which are highest among all boxes. (e.g. 1, 2 , 3, 3)

Algorithm:
If the highest stick containing box has K sticks and second highest stick containing box has L sticks, pick up K - L sticks from the highest containing box. By doing this, you are reducing the problem size, and ensuring that you always have the control for winning condition. This way, the opponent can never put you in the same situation. In the end, the game will come down to X, X and ultimately reduce to 1, 1 with the opponent to play. This is where you will win the game.

Caveat:
If the game already starts with winning condition, and you have to play first, you don't have a chance to win (given the opponent is aware of the winning algorithm).

- Subrat October 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

:) Very nice game tree pruning.

- Urik's twin Cookie Monster (dead now) October 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What do you do in case of 1,2,3,3,3 ?

I haven't given much thought, just a quick one: If there are even no. of matchboxes with highest number of matchsticks, you pick all from one of them. If there are odd no. of such matchboxes, there is no winning move except if there is only one then you do same as (K-L).

But again whether it is a winning move would depend if you can get in similar situation again (i.e. more than 2 matchboxes with highest number of matchsticks). So, I guess we'll need to solve it to the last move to confirm if it is a winning move.

- chetan verma October 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, just reverse conditions for odd and even matchboxes.

- chetan verma October 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Find the last move for the win?

That would be:
All boxes empty except one, and last move being emptying last box.

Done. No coding needed?

- Urik's twin Cookie Monster (dead now) October 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

u added an example now, but you still have "final move"
change that to "first move"

- Urik's twin Cookie Monster (dead now) October 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <stdio.h>

typedef enum {false, true} bool;

int boxes[] = {1,1,2,1}; //boxes of sticks
#define N sizeof(boxes)/sizeof(*boxes)

/* mutually recursive functions our_move and opp_move return true
if 'we' are guaranteed a win with the right choices from that state;
can do this win 1 function (track "depth" recursion even vs. odd),
but mentally easier for me to think of 2 players*/
bool our_move();
bool opp_move()
{
bool opp_wins=false; //can opp. win from this state?
int rem_items, i, j;
for(i=0; i<N; i++) {
rem_items=boxes[i];
for(j=1; j<=rem_items; j++) {
boxes[i] -= j; //remove j sticks from box i as a move
if( !our_move() ) opp_wins=true; //opp. can win
boxes[i] += j;
if(opp_wins) return false; //we are not guaranteed win
}
}
return true; //boxes already empty, or we always win
}

bool our_move()
{
bool our_wins=false; //can we win from this state?
int rem_items, i, j;
for(i=0; i<N; i++) {
rem_items=boxes[i];
for(j=1; j<=rem_items; j++) {
boxes[i] -= j; //remove j sticks from box i as a move
if( opp_move() ) our_wins=true; //we "can" win
boxes[i] += j;
if(our_wins) return true; //we are guaranteed win
}
}
return false; //boxes already empty, or all choices lose
}

int main(void) {
int i, j;

/* we make our possible first moves and see if they guarantee win
(i.e, guarantee opp. loss ) */
for(i=0; i<N; i++)
for(j=1; j<=boxes[i]; j++)
{
boxes[i] -= j;
printf("First move <remove %d sticks from box %d>"
"can%s guarantee win\n",
j, i+1, (opp_move())?"":"not");
boxes[i] += j;
}
return 0;
}

- Urik's twin Cookie Monster (dead now) October 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

My interpretation of your question. QA it Mr. "Solve Me Some Quadratic Equations" (code 123).

ideone.com/cfGilp

#include <stdio.h>

typedef enum {false, true} bool;

int boxes[] = {1,1,2,1}; //boxes of sticks
#define N sizeof(boxes)/sizeof(*boxes)

/* mutually recursive functions our_move and opp_move return true 
   if 'we' are guaranteed a win with the right choices from that state;
   can do this win 1 function (track "depth" recursion even vs. odd), 
   but mentally easier for me to think of 2 players*/
bool our_move(); 
bool opp_move()
{
	bool opp_wins=false;  //can opp. win from this state?
	int rem_items, i, j;
	for(i=0; i<N; i++) {
		rem_items=boxes[i];
		for(j=1; j<=rem_items; j++) {
			boxes[i] -= j; //remove j sticks from box i as a move
			if( !our_move() ) opp_wins=true; //opp. can win
			boxes[i] += j;
			if(opp_wins) return false; //we are not guaranteed win
		}
	}
	return true;  //boxes already empty, or we always win
}

bool our_move()
{
	bool our_wins=false; //can we win from this state?
	int rem_items, i, j;
	for(i=0; i<N; i++) {
		rem_items=boxes[i];
		for(j=1; j<=rem_items; j++) {
			boxes[i] -= j; //remove j sticks from box i as a move
			if( opp_move() ) our_wins=true;  //we "can" win
			boxes[i] += j;
			if(our_wins) return true; //we are guaranteed win
		}
	}
	return false; //boxes already empty, or all choices lose
}

int main(void) {
	int i, j;
	
	/* we make our possible first moves and see if they guarantee win
	        (i.e, guarantee opp. loss )  */
	for(i=0; i<N; i++)
		for(j=1; j<=boxes[i]; j++)
		{
			boxes[i] -= j;
			printf("First move <remove %d sticks from box %d>" 
					"can%s guarantee win\n", 
					j, i+1, (opp_move())?"":"not");
			boxes[i] += j;
		}
	return 0;
}

- Urik's twin Cookie Monster (dead now) October 29, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More