Epic Systems Interview Question Software Developers
Country: United States
Interview Type: Written Test
public class Mingo {
public void findMingo(int arr[][], int[] called) {
ArrayList<ArrayList<Integer>> sequencedLists = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> row = getRow(arr, i);
ArrayList<Integer> column = getColumn(arr, i);
sequencedLists.add(row);
sequencedLists.add(column);
}
sequencedLists.add(getFirstDiagonal(arr));
sequencedLists.add(getSecondDiagonal(arr));
for (int i = 0; i < called.length; i++) {
//Now loop throgh each sequence and remove the called number.
//Exit if Bingo!
for (ArrayList<Integer> sequence : sequencedLists) {
if (sequence.contains(called[i])) {
sequence.remove(new Integer(called[i]));
if (sequence.isEmpty()) {
System.out.println("Mingo after " + (i + 1) + " calls!");
return;
}
}
}
}
System.out.println("No Mingo for you :'(");
}
private ArrayList<Integer> getFirstDiagonal(int arr[][]) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < 10; i++) {
list.add(arr[i][i]);
}
return list;
}
private ArrayList<Integer> getSecondDiagonal(int arr[][]) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < 10; i++) {
list.add(arr[i][9 - i]);
}
return list;
}
private ArrayList<Integer> getRow(int arr[][], int index) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < 10; i++) {
list.add(arr[index][i]);
}
return list;
}
private ArrayList<Integer> getColumn(int arr[][], int index) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < 10; i++) {
list.add(arr[i][index]);
}
return list;
}
public static void main(String[] args) {
int matrix[][] = {
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
{11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
{21, 22, 23, 24, 25, 26, 27, 28, 29, 30},
{31, 32, 33, 34, 35, 36, 37, 38, 39, 40},
{41, 42, 43, 44, 45, 46, 47, 48, 49, 50},
{51, 52, 53, 54, 55, 56, 57, 58, 59, 60},
{61, 62, 63, 64, 65, 66, 67, 68, 69, 70},
{71, 72, 73, 74, 75, 76, 77, 78, 79, 80},
{81, 82, 83, 84, 85, 86, 87, 88, 89, 90},
{91, 92, 93, 94, 95, 96, 97, 98, 99, 100}
};
int called[] = {1, 2, 3, 4, 73, 82, 91, 5, 6, 7, 8, 9, 10};
Mingo mingo = new Mingo();
mingo.findMingo(matrix, called);
}
}
1: Create a HashMap between the numbers in the matrix and their corresponding (row,column) id, that is if the number '5' is as position (2,3) then '5' is the key and (2,3) is the value in the hash table.
This HashMap will ensure that you will have O(1) complexity when retrieving the position of a number in the "called" array.
2: Create two new HashMap, one where the keys are all the row indices from 1-100 and all the values are initialized to zero and the other HashMap represents the same for the columns.
3. Iterate over the "called" array for each element get its position (row,column) using the first HashMap, increment the value of corresponding row key and column key in the other two hashmap's, after every increment check the value of that key to see if its equal to 100, if it is then stop and return corresponding row or column id.
4: Maintain a separate counter that is incremented whenever the position returned from the first hashmap is on the diagonal (row_id=column_id).
Note: If there are duplicate numbers on the matrix then assume that in call both these positions are called and increment their row and column hashmap accordingly.
Weird game seems like a Bingo in steroids with a 100X100 board.
I've been explicit with the booleans and combined multiple loop into one but I don't know it the performance would be better than separate as there are additional comparisons and jumping all around memory.
In reality in an interview problably the best way is to create a generalized method which you tell how to advance to the next cell but because I wanted to have the best performance I've avoid it.
public static int MinMingo(int[][] board, int[] called)
{
if(called.Length < 100)
{
return -1;
}
// This is used to track the last position on the array.
Dictionary<int, int> set = new Dictionary<int, int>();
for(int i = 0; i < called.Length; i++)
{
set.Add(called[i], i);
}
int minMingo = -1;
int maxIndexDiagonal1 = 0;
int maxIndexDiagonal2 = 0;
// Using single loop for all of the lookups.
for(int i = 0; i < 100; i++)
{
int maxIndexRow = 0;
int maxIndexColumn = 0;
for(int j = 0; j < 100;++)
{
if(!set.ContainsKey(board[i][j]))
{
maxIndexRow = -1;
if(maxIndexColumn == -1)
break;
}
else if(maxIndexColumn != -1 && maxIndexColumn < set[board[i][j]]
{
maxIndexColumn = set[board[i][j]];
}
if(!set.ContainsKey(board[j][i]))
{
rowColumn = int.MaxValue;
if(foundRow == -1)
break;
}
else if(maxIndexRow != -1 && maxIndexRow < set[board[j][i]])
{
maxIndexRow = set[board[j][i]];
}
}
// finds if is the smallest index
if(maxIndexRow > 0 && minMingo > maxIndexRow)
minMingo = maxIndexRow;
if(maxIndexColumn > 0 && minMingo > maxIndexColumn)
minMingo = maxIndexColumn
// Track the maximum index diagonal from the begining of x
if(!set.Contains(board[i][i]))
{
maxIndexDiagonal1 = -1;
}
else if(foundDiagonal1 != -1 && maxIndexDiagonal1 < set[board[i][i]])
{
maxIndexDiagonal1 = set[board[i][i]];
}
// Tracks the maximum index diagonal starting from the end of x
if(!set.Contains(board[100-i-1][i]))
{
maxIndexDiagonal2 = -1;
}
else if(maxIndexDiagonal2 != -1 && maxIndexDiagonal2 < set[board[100-i-1][i]])
{
maxIndexDiagonal2 = set[board[100-i-1][i]];
}
}
if(maxIndexDiagonal1 > 0 && minMingo > maxIndexDiagonal1))
minMingo = maxIndexDiagonal1;
if(maxIndexDiagonal2 > 0 && minMingo > maxIndexDiagonal2))
minMingo = maxIndexDiagonal2;
return (minMingo != int.MaxValue)?minMingo:-1;
}
int bingo(vector<vector<int>> matrix, vector<int> numbers)
{
int min=INT_MAX;
int current_max_diag1=0;
int current_max_diag2=0;
for(int i=0;i<100;i++)
{
int current_max_row=0;
int current_max_col=0;
for(int j=0;j<100;j++)
{
if(current_max_row>=0)
{
auto it=find(numbers.begin(),numbers.end(),matrix[i][j]);
if(it!=numbers.end())
{
if(it-numbers.begin()>current_max_row)
current_max_row=it-numbers.begin();
}
else
{
current_max_row=-1;
}
}
if(current_max_col>=0)
{
auto it=find(numbers.begin(),numbers.end(),matrix[j][i]);
if(it!=numbers.end())
{
if(it-numbers.begin()>current_max_col)
current_max_col=it-numbers.begin();
}
else
{
current_max_col=-1;
}
}
}
if(current_max_diag1>=0)
{
auto it=find(numbers.begin(),numbers.end(),matrix[i][i]);
if(it!=numbers.end())
{
if(it-numbers.begin()>current_max_diag1)
current_max_diag1=it-numbers.begin();
}
else
{
current_max_diag1=-1;
}
}
if(current_max_diag2>=0)
{
auto it=find(numbers.begin(),numbers.end(),matrix[i][n-1-i]);
if(it!=numbers.end())
{
if(it-numbers.begin()>current_max_diag2)
current_max_diag2=it-numbers.begin();
}
else
{
current_max_diag2=-1;
}
}
if(current_max_diag1<min)
min=current_max_diag1;
if(current_max_diag2<min)
min=current_max_diag2;
if(current_max_row<min)
min=current_max_row;
if(current_max_col<min)
min=current_max_col;
}
return min;
}
Map from a number to the indices where it appears on the board. Remove a number from the map after it has been processed. Count the hits on each row, column, and diagonal, when one of them reaches 100 we are done.
O(n)
const int DIM = 100;
int mingo(int* pBoard, int* pCalled, int numCalled)
{
std::unordered_multimap<int, int> numToIdx;
for (int i = 0; i < DIM * DIM; i++)
numToIdx.insert({ pBoard[i], i });
int rows[DIM] = { 0 }, cols[DIM] = { 0 };
int diag1 = 0, diag2 = 0;
for (int i = 0; i < numCalled; i++)
{
auto range = numToIdx.equal_range(pCalled[i]);
for (; range.first != range.second; range.first++)
{
int row = range.first->second / DIM, col = range.first->second % DIM;
if ((++rows[row] == DIM) || (++cols[col] == DIM) ||
((row == col) && (++diag1 == DIM)) ||
((DIM - row - 1 == col) && (++diag2 == DIM)))
return i;
}
numToIdx.erase(pCalled[i]);
}
return -1;
}
public class Mingo {
// returns the number of calls to get a Mingo if there is otherwise returns 0
public static int findMingo(List<Integer> numbs) {
final int MINGO_SIZE = 10;
int[] rows = new int[MINGO_SIZE];
int[] columns = new int[MINGO_SIZE];
int diagnol = 0;
int i = 1;
for (int numb : numbs) {
int row = numb / MINGO_SIZE;
int column = numb % MINGO_SIZE;
if ((++rows[row] == MINGO_SIZE)
|| (++columns[column] == MINGO_SIZE)) {
return i;
}
if (row == column && ++diagnol == MINGO_SIZE) {
return i;
}
i++;
}
return 0;
}
}
- Puneet March 12, 2015public class Mingo { public void findMingo(int arr[][], int[] called) { ArrayList<ArrayList<Integer>> sequencedLists = new ArrayList<ArrayList<Integer>>(); for (int i = 0; i < 10; i++) { ArrayList<Integer> row = getRow(arr, i); ArrayList<Integer> column = getColumn(arr, i); sequencedLists.add(row); sequencedLists.add(column); } sequencedLists.add(getFirstDiagonal(arr)); sequencedLists.add(getSecondDiagonal(arr)); for (int i = 0; i < called.length; i++) { //Now loop throgh each sequence and remove the called number. //Exit if Bingo! for (ArrayList<Integer> sequence : sequencedLists) { if (sequence.contains(called[i])) { sequence.remove(new Integer(called[i])); if (sequence.isEmpty()) { System.out.println("Mingo after " + (i + 1) + " calls!"); return; } } } } System.out.println("No Mingo for you :'("); } private ArrayList<Integer> getFirstDiagonal(int arr[][]) { ArrayList<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < 10; i++) { list.add(arr[i][i]); } return list; } private ArrayList<Integer> getSecondDiagonal(int arr[][]) { ArrayList<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < 10; i++) { list.add(arr[i][9 - i]); } return list; } private ArrayList<Integer> getRow(int arr[][], int index) { ArrayList<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < 10; i++) { list.add(arr[index][i]); } return list; } private ArrayList<Integer> getColumn(int arr[][], int index) { ArrayList<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < 10; i++) { list.add(arr[i][index]); } return list; } public static void main(String[] args) { int matrix[][] = { {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16, 17, 18, 19, 20}, {21, 22, 23, 24, 25, 26, 27, 28, 29, 30}, {31, 32, 33, 34, 35, 36, 37, 38, 39, 40}, {41, 42, 43, 44, 45, 46, 47, 48, 49, 50}, {51, 52, 53, 54, 55, 56, 57, 58, 59, 60}, {61, 62, 63, 64, 65, 66, 67, 68, 69, 70}, {71, 72, 73, 74, 75, 76, 77, 78, 79, 80}, {81, 82, 83, 84, 85, 86, 87, 88, 89, 90}, {91, 92, 93, 94, 95, 96, 97, 98, 99, 100} }; int called[] = {1, 2, 3, 4, 73, 82, 91, 5, 6, 7, 8, 9, 10}; Mingo mingo = new Mingo(); mingo.findMingo(matrix, called); } }