Google Interview Question
SDE1sCountry: United States
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
}
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
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
- Alex November 28, 2017