Oracle Interview Question
Software DevelopersCountry: India
Interview Type: In-Person
Brute force.
#include <vector>
#include <iostream>
using namespace std;
inline bool Check(vector<vector<int>> const &m)
{
int size = m.size();
if (size > 0) {
int sum = numeric_limits<int>::min();
for (int i = 0; i < size; ++i) {
int s1 = 0;
int s2 = 0;
for (int j = 0; j < size; ++j) {
s1 += m[i][j];
s2 += m[j][i];
}
if (sum == numeric_limits<int>::min()) {
sum = s1;
}
if (s1 != sum ||
s2 != sum)
{
return false;
}
}
int s1 = 0;
int s2 = 0;
int r = 0;
int c = 0;
while (r < size &&
c < size)
{
s1 += m[r][c];
s2 += m[r++][size - 1 - c++];
}
if (s1 != sum ||
s2 != sum)
{
return false;
}
return true;
}
return false;
}
inline bool Next(vector<vector<int>> &m, int max_val)
{
int r = 0;
int c = 0;
while (++m[r][c] > max_val) {
m[r][c] = 0;
if (++c >= m.size()) {
c = 0;
if (++r >= m.size()) {
return false;
}
}
}
return true;
}
void Print(vector<vector<int>> const &m)
{
for (auto row : m) {
for (int v : row) {
cout << v << ", ";
}
cout << "\n";
}
cout << "-----\n";
}
void ProduceMagicMatrixes(int size, int max_val)
{
vector<vector<int>> m;
for (int i = 0; i < size; ++i) {
m.push_back(vector<int>());
m.back().resize(size, 0);
}
do {
if (Check(m)) {
Print(m);
}
} while (Next(m, max_val));
}
int main()
{
ProduceMagicMatrixes(3, 10);
return 0;
}
/*
For a matrix N X N where N is odd
take numbers 1.. N^2
Place 1 in the middle column of top row
Next number will go in one of the following positions
-- move up diagonally 1 place and place it here if this is empty
-- OR move 1 place down
Note: all position calculations are mod N
*/
public class MagicMatrix {
public static void main(String[] args) {
print(mm(9));
}
static int[][] mm(int N) {
if (N % 2 != 1)
throw new IllegalArgumentException("argument should be odd integer");
int result[][] = new int[N][N];
for (int p = 1, i = 0, j = N / 2; p < N * N + 1; p++) {
if (p == 1) {
//start in the middle column of top row
result[i][j] = p;
} else {
// move right and up diagonally
// and if that position is already full
// then move down
if (result[(N + i - 1) % N][(N + j + 1) % N] == 0)
result[i = (N + i - 1) % N][j = (N + j + 1) % N] = p;
else
result[i = (i + 1) % N][j] = p;
}
}
return result;
}
private static void print(int[][] mm) {
validate(mm);
for (int[] x : mm)
System.out.println(Arrays.toString(x));
}
private static void validate(int[][] mm) {
final int X = mm.length;
int[] rows = new int[X];
int[] cols = new int[X];
for (int i = 0; i < X; i++) {
rows[i] = 0;
for (int j = 0; j < X; j++) {
rows[i] += mm[i][j];
}
}
// System.out.println(Arrays.toString(rows));
for (int i = 0; i < X; i++) {
cols[i] = 0;
for (int j = 0; j < X; j++) {
cols[i] += mm[j][i];
}
}
//System.out.println(Arrays.toString(cols));
//TODO: add code for diagonals
final int tot = rows[0];
for (int i = 0; i < rows.length; i++) {
if (tot != rows[i]) throw new IllegalArgumentException("");
}
for (int i = 0; i < cols.length; i++) {
if (tot != cols[i]) throw new IllegalArgumentException("");
}
//etc
}
}
/*
Here is a matrix 9 x 9 with above code
[47, 58, 69, 80, 1, 12, 23, 34, 45]
[57, 68, 79, 9, 11, 22, 33, 44, 46]
[67, 78, 8, 10, 21, 32, 43, 54, 56]
[77, 7, 18, 20, 31, 42, 53, 55, 66]
[6, 17, 19, 30, 41, 52, 63, 65, 76]
[16, 27, 29, 40, 51, 62, 64, 75, 5]
[26, 28, 39, 50, 61, 72, 74, 4, 15]
[36, 38, 49, 60, 71, 73, 3, 14, 25]
[37, 48, 59, 70, 81, 2, 13, 24, 35]
all rows and cols etc add to 369
*/
this is a very difficult question, if you never have heard of magic squares. You can generate a square using random method and check if it is a magic square. There are ways to construct them: geeksforgeeks.org/magic-square/ or the linked wikipedia article.
- Chris September 27, 2017