Google Interview Question for Software Engineers


Country: India
Interview Type: In-Person




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

A simple AI could check whether the number of valid positions before and after a move and prefer moves which create an odd or even number of moves depending on which one would allow the AI to have the final turn. This would require first writing a method to check the valid moves on the board with a given state. I'd talk about how you could train an AI but obviously that wouldn't be implemented in an interview.

- Anonymous April 16, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
enum Layout {H,V};
struct Move { int cell; Layout layout;};
Move LoseMove { -1, H };

class Board
{

public:	
    Board(int h, int v, bool _myTurn) : numCells(h * v), hSize(h), myTurn(_myTurn)
    {
        state = new bool[numCells];
        for (int i = 0; i < numCells; ++i) state[i] = false;
    }
    
    virtual ~Board()
    {
        delete[] state;
    }
    
	Board(const Board& other, const Move& m) : numCells(other.numCells), hSize(other.hSize), myTurn(!other.myTurn)
	{
		state = new bool[numCells];
		for (int i = 0; i < numCells; ++i)
		{
		    state[i] = other.state[i];
		}
		set(m.cell);
		switch (m.layout)
		{
		    case H: set(m.cell + 1);break;
		    case V: set(m.cell + hSize); break;
		}
	}

	vector<Move> generatePossibleMoves() const
	{
		vector<Move> ret;
		for (int i = 0; i < numCells; ++i)
		{
			if (state[i]) continue;
			bool rightmost =  i % hSize == hSize - 1;
			bool bottom = i / hSize == (numCells / hSize) - 1;
			if ((!rightmost) && !(state[i+1])) ret.push_back({i, H});
			if ((!bottom) && !(state[i+hSize])) ret.push_back({i, V});
		}
		return ret;
	}
	void set(int cell)
    {
        assert(!state[cell]);
		state[cell] = true;
    }
    
private:
	int numCells;
	int hSize;
	bool myTurn;
	bool* state;
};

Move solve(const Board& current)
{
	vector<Move> nextMoves = current.generatePossibleMoves();
	for (Move move : nextMoves)
	{
		Board newBoard(current, move);
		Move bestEnemyPlan = solve(newBoard);
		if (bestEnemyPlan.cell == -1 /* losing move */)
		{
			return move ;
		}
	}
	return LoseMove;
}

int main()
{
    Board b(3,2, true);
    b.set(2); b.set(3);
    Move m = solve(b);
    cout << m.cell << "," << m.layout << endl;
}

- ymorag June 04, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the board has a cell symmetry in it then the player who can first exploit it will win. Example on a even*even board the second player can always win, by simply imitating all moves made by the first player ensuring that his moves are symmetrical against the same diagonal. This way the number of domino positions is even, and they are consumed at identical rates across the two diagonally opposed triangles.

On the other hand if the board is even * odd, then the first player has winning strategy by occupying the center cells. Once done all remaining cells are symmetric by a diagonal, and the first player merely has to repeat the same move, thus again ensuring that the free positions are consumed at an identical rates across the two diagonally opposed triangles.

If the board is even * even, then in some cases one player still has winning strategy if it manages to 'win' or 'loose' the extra column or row in a way that all the larger board rectangle can be won per previous two strategies.

If all else fails standard game tree search minmax / alphabeta / transposition tables / iterative deepening / mtd(f) or newer monte carlo search could be used. Albeit in these algos might not fit into the interview time window. This would suggest that perhaps there is a simplification that would allow optimal strategy for at least one player without having to do tree search.

- Zsombor July 01, 2020 | 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