This write-up despite the title is actually not about the interview process in Facebook, but it is or it could become the first to the series of front-end centered write ups if I stick to the plan. I'm going to design a simple game, something what already had been done many times over and I'm going to enjoy the process along. The plan is that once I'm done, I will re-write the front end part in few different ways to learn and to illustrate what are the differences and the pros and the cons of each way.
The chosen project is the old school mine sweeper game. There is a great chance that everybody reading this is also familiar with minesweeper game so there is no need to explain any further that part. Let's go to the business then.
Few years I got an email from Facebook recruiter about an open position for support engineer at a data-center and the required set of skills included FE technologies, networking, Linux literacy and the general computer sciency stuff. I immediately thought that it fits the bill perfectly and I have to give it a try.
After about 3 or 4 telephone calls I was finally invited for a day long on site interview with the panel of engineers and one manager.
It is by far the most rigorous and expensive interview process I've ever been through. I was given about a month to prepare and couple of links leading to something which looked like a course on how to pass job interview to Facebook. I did what almost every software engineer would do. I ignored it.
On the day of the interview I arrived to what could be described as frivolously designed modern office environment. I was assigned a guide who made me a company around the building, between meetings (interviews) and for the lunch break. The people were nice, the building was nice and the food was excellent. I'm not going to bore the reader with the details.
Basically if I would be given positive feedback from all five interviewers I would most likely be offered a position. I got four time a positive feedback, essentially four yeses and one X buzzer. I was a bit peeved and disappointed. I thought that the interviews went excellent with only one hiccup... Yes, that one. I failed on probably most stupid part. So let's connect the minesweeper to Facebook interview.
I was given a task - to make a minesweeper game engine, specifically the part which seeds the mines and creates the map of numbers indicating how many mines are around each empty square. I had only about 20-30min so I knew I will not need to go into details.
Basically just pseudo code on a white board. Computer was also there, but I chose not to use it. Easy peasy, so I thought.
I started first by randomly seeding mines and checking whether the mine is already in the position or not. Not the best approach (details later). Than I rushed into the part two - algorithm which iterates over the fields and counts the mines. I kind of did it, the code was rough, but would probably work when cleaned up but I could feel that I didn't do my best. The interviewer giving me rather cold shoulder when I met him during the lunch break wasn't good sign either. Perhaps I should have taken one of the linked courses I got from the recruiter. Who knows. I know now I rushed too quickly into most trivial solution. Not that it was particularly bad, but I gave poor reasoning for my choices. And also there where better choices available.
I was first angry and disappointed with myself and the world, than forgot about it. Later on I got the idea to do some FE related write-ups on different FE frameworks and minesweeper game got my attentions as nice and simple but not usually boring "back end", like to-dos or two player tic-tac-toe.
Here is how the solution should look like and I am pretty convinced that have I done something along these lines I wouldn't be writing this blog at this moment, but probably it would some UI framework for Facebook data-center.
minesweeper board
The board is X times Y or width x height The input values are the size of a field X x Y and the number of mines spread randomly in the field The number would be limited by the size of a field and in order for the game to be playable it should have constrains some constrains.
- max number should be 50% of all fields
- min number should be 5% of all fields
n - number of mines N - number of fields (width * height)
The goal is to randomly assign the mine fields and calculate the number of mines around each field. That's when user clicks on a hidden field and there is no mine under.
Let's consider more realistic minesweeper game anyone could play on a laptop, desktop, tablet or a phone not hypothetical 1 million+ square field. I don't believe anything above 100x100 is really playable. If it takes 1s to uncover one field, which is pretty fast pace, 100x100 field would require 10,000 seconds which is short 15min 3 hours.
counting mines
One option would be to take the number of mines and for each mine to generate the random position in the field. In this case we need to keep track of the positions and verify that we do not place more than one mine into the same field. The algorithm could work in this lines:
function seedMines(n, field) {
const mines = [];
let minesAvailable = n;
while (minesAvailable > 0) {
cont pos = getRandomPosition(N);
if (pos not in mines) {
mines.push(pos)
minesAvailable -=1
countMines(field, mines, pos)
}
}
This loops until all mines n is seeded in the field. We generate random position for each mine, verify if the position is already taken and if not we place the mine. countMines recounts all 8 affected squares around the mine.
To look at the computational complexity of this solution we need to break this into 2 parts:
- generate the set of unique random numbers
- update the mine count.
The computational complexity of the first one can by described as
Here we need to note that the maximum ratio of evaluated mines to squares is 50%. Anything above rather than mines we could rather be seeding empty squares. Thus if we run couple of calculations we see that it is about 1.25*n if 50% squares are containing a mine.
The second part is simpler and it is just n as we need to recount the 8 fields around whenever and wherever we place a mine. This makes it together:
or
counting fields
In this option we look at the probability for each square to contain a mine. The probability is
r/S
where r is the count of remaining mines and S is the count of the remaining squares.
This will adjust the probability after evaluating each square and ensures that all mines are distributed. Since we are going through the field one by one we could also count the dropped mines around each square along. We only need to do it with the offset of
(width * -1) -1.
The computational complexity of the seeding part and the counting part together is thus the number of squares:
N
Here is the simple implementation of the field method:
function createMineField(width, height, mines) {
remianingFields = width * height
const field = Array(remainingFields)
let remainingMines = mines
fields.forEach((_field, index) => {
if fields[index] = dropMine(remainingMines / remainingFields)
remianingMines -= 1
fields.countMines(index - width)
remianingFields -= 1
})
countLastRowAndColumn(width, height, field)
return field
}
It turned out that both methods of seeding mines are very similar in terms of efficiency. Where mine method is more efficient with scarcely populated fields and field method more efficient with heavily populated fields where
is the tip off point.
wrap up
I believe if I presented this solution without even giving any further detail on how those solution would work I would have gotten the last "yes" and possibly would be today working for Facebook.
Here is my brief recommendation for every job interview - always stick to the bigger picture as there is usually not enough time to go into specifics. Never let interviewer lead your answers. Show your thinking skills, not your coding skills.
