## Google Interview Question for SDE1s

Country: United States

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

``````#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>

using namespace std;

int Random(int size, set<int> const &excluded)
{
int rnd = -1;
if (excluded.size() < size) {
size -= excluded.size();
rnd = rand() % size;
for (auto it = excluded.begin(); it != excluded.end() && *it <= rnd; ++it) {
++rnd;
}
}
return rnd;
}

void InitCell(vector<vector<int>> &m, int r, int c, int k)
{
set<int> excluded;
if (r - 2 >= 0 &&
m[r - 1][c] == m[r - 2][c] &&
m[r - 1][c] != -1)
{
excluded.insert(m[r - 1][c]);
}
if (r + 2 < m.size() &&
m[r + 1][c] == m[r + 2][c] &&
m[r + 1][c] != -1)
{
excluded.insert(m[r + 1][c]);
}
if (c - 2 >= 0 &&
m[r][c - 1] == m[r][c - 2] &&
m[r][c - 1] != -1)
{
excluded.insert(m[r][c - 1]);
}
if (c + 2 < m[r].size() &&
m[r][c + 1] == m[r][c + 2] &&
m[r][c + 1] != -1)
{
excluded.insert(m[r][c + 1]);
}
m[r][c] = Random(k, excluded);
}

vector<vector<int>> GenerateBoard(int m, int n, int k)
{
vector<vector<int>> board(m, vector<int>(n, -1));
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
InitCell(board, r, c, k);
}
}
return board;
}

int main()
{
srand(time(NULL));

int m = 8;
int n = 8;
int k = 5;

vector<vector<unordered_map<int, int>>> stats(m, vector<unordered_map<int, int>>(n));

for (int i = 0; i < 1000000; ++i) {
auto board = GenerateBoard(m, n, k);
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
++stats[r][c][board[r][c]];
}
}
}

for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
cout << "[" << r << "][" << c << "]\n";
for (auto el : stats[r][c]) {
cout << "\t" << el.first << "=>" << el.second << "\n";
}
}
}
}``````

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

I've interpreted the question as not using the same color more than twice in a row / column where the question was to not use the same color more than twice in adjacent fields on a row and on a column.

Anyways here's the backtracking algo for the Soduku like question:

``````vector<vector<uint>> generate_rnd_field(uint m, uint n, uint k)
{
vector<vector<vector<uint>>> options(m, vector<vector<uint>>(n));
vector<vector<uint>> result(m, vector<uint>(n, EMPTY));

vector<vector<uint>> rows(m, vector<uint>(k));
vector<vector<uint>> cols(n, vector<uint>(k));

stack<pair<size_t, size_t>> s;
s.push({0, 0});
while (!s.empty()) {
int r = s.top().first;
int c = s.top().second;
auto& field_options = options[r][c];
if (result[r][c] == EMPTY) {
// calculate options
for (uint i = 0; i < k; ++i) {
if (rows[r][i] + cols[c][i] < 2) {
field_options.push_back(i);
}
}
} else {
// an options was used but didn't succeed, put the value back into the
// rows and colums options
int value = result[r][c];
rows[r][value]--;
cols[c][value]--;
}
if (field_options.size() == 0) { // if it has no options
s.pop(); // backtrack
result[r][c] = EMPTY; // gets new options when coming back
} else {
size_t value_idx = rand() % field_options.size();
int value = field_options[value_idx];
rows[r][value]++;
cols[c][value]++;
result[r][c] = value;
field_options.erase(field_options.begin() + value_idx);
// next field
if (++c == n) {
c = 0;
if (++r == m) return result;
}
s.push({r, c});
}
}
return vector<vector<uint>>(); // empty to indicate no solution exists
}``````

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

``````import numpy as np
import random
m = 10
n = 10
k = range(5)

matrix = np.full(shape=(m, n), fill_value=-1)

for col in range(m):
for row in range(n):
for colour in k:
r = random.randint(0, colour)
if r == colour:
col_col_count = list(matrix[col][:]).count(colour)
row_col_count = list(matrix[:,row]).count(colour)
if col_col_count < 2 and row_col_count < 2:
matrix[col][row] = colour

print matrix``````

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

``````import numpy as np
import random
m = 10
n = 10
k = range(5)

matrix = np.full(shape=(m, n), fill_value=-1)

for col in range(m):
for row in range(n):
for colour in k:
r = random.randint(0, colour)
if r == colour:
col_col_count = list(matrix[col][:]).count(colour)
row_col_count = list(matrix[:,row]).count(colour)
if col_col_count < 2 and row_col_count < 2:
matrix[col][row] = colour

print matrix``````

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.

### 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.