## Epic Systems Interview Question

• 1

Country: United States

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

I just had this in my exam yesterday. The simple solution is traverse each matrix, and check for i whether (i,j) ,(i+1,j) and (i+2,j) are same. If yes then points++, also check for i whether (i,j), (i,j+1) and (i,j+2) are same and for i whether (i,j), (i+1,j+1) and (i+2,j+2) are same. Do points++ if they are same.
Do this till (i<n-1) and (j<n-2).
Compare points of player 1 and player 2 and return the winner.
Time complexity O(n sq).

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

what is n here? size of the array length wise? or breadth? can u post ur code?

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

its already written in the question that matrix is of n*n.. could you please read the question properly before commenting anything on the forum..

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

but this is just checking for three consecutive positions and skipped the four consecutive positions with red color.

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

you should also check for (i,j), (i-1, j-1), (i-2, j-2) - the other diagonal from Right to Left

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

can someone explain the boundary condition (i<n-1) and (j<n-2) ?

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

@abhishek: did you write syntactically correct code or is pseudo code enough for the written test

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

We need to count triplets of each color (red or black), in the following directions
1) Horizontally
2) Vertically
3) Diagonally, top to bottom. (as we are counting triplets, we can have more diagonals, ex: 2 in case of 4x4 matrix)
4) Diagonally, bottom to top.(as we are counting triplets, we can have more diagonals, ex: 2 in case of 4x4 matrix)

``````public class Matrix_Color_Points {
public static void main(String[] args) {

char[][] matrix = { { 'r', 'r', 'r', 'b' }, { 'b', 'r', 'b', 'r' },
{ 'b', 'r', 'r', 'b' }, { 'b', 'r', 'b', 'b' } };
int red_count = findCount(matrix, 4, 4, 'r');
int blue_count = findCount(matrix, 4, 4, 'b');
System.out.println("Count of red triplets: " + red_count);
System.out.println("Count of blue triplets: " + blue_count);
}

private static int findCount(char[][] matrix, int row, int col, char c) {
/**
* As we need to count horizontal triplets, we must look at all rows but
* stop two columns before, otherwise we would get IndexOutOfBound since
* we need to count only triplets.
*/
int count = 0;
// For all horizontal triplets.
for (int i = 0; i < row; i++) {
for (int j = 0; j < col - 2; j++) {
if (matrix[i][j] == c && matrix[i][j + 1] == c
&& matrix[i][j + 2] == c)
count++;
}
}

/**
* As we need to count vertical triplets, we must look at all columns
* but stop two rows before, otherwise we would get IndexOutOfBound
* since we need to count only triplets.
*/
// for all vertical triplet
for (int i = 0; i < row - 2; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == c && matrix[i + 1][j] == c
&& matrix[i + 2][j] == c)
count++;
}
}

/**
* As we need to count diagonal triplets from top to bottom, we must but
* stop two rows and two columns before, otherwise we would get
* IndexOutOfBound since we need to count only triplets.
*/
// for all top down diagonal triplets
for (int i = 0; i < row - 2; i++) {
for (int k = 0; k < col - 2; k++) {
if (matrix[i][k] == c && matrix[i + 1][k + 1] == c
&& matrix[i + 2][k + 2] == c)
count++;
}
}

/**
* As we need to count diagonal triplets from bottom to top, we must but
* stop two rows and two columns before, otherwise we would get
* IndexOutOfBound since we need to count only triplets. And we start
* from bottom.
*/
// for all bottom to top diagonal triples
for (int i = row - 1; i > 1; i--) {
for (int k = 0; k < col - 2; k++) {
if (matrix[i][k] == c && matrix[i - 1][k + 1] == c
&& matrix[i - 2][k + 2] == c)
count++;
}
}
return count;
}

}``````

Count of red triplets: 5
Count of blue triplets: 1

Comment hidden because of low score. Click to expand.
-2

Question says if 4 same colors appears vertically then give 2 point to that color.
I think you missed that point.

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

@ajay:
(R,R,R,R) = (R1,R2,R3), (R2,R3,R4). Hence 2 pts. Nothing special about being vertical or 4 tiles long.

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

Why are again counting from bottom to top wen u did for top to bottom??

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

Why not spend an extra 2 min. typing the question more clearly, with more details , and possibly an example? This might save hordes of people many minutes, don't you think?

Comment hidden because of low score. Click to expand.
2

u r right

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

true.. nothing is clear from question except we need to use DP. Please be more specific so that we can provide proper solution.

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

The easiest way -brute force, will be for each cell, try all possible moving directions in 3 steps, and store the resulting triple-cell into a hashmap. count them at the end and compare.

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

``````def points(board):
if len(board)>=3:
points= {"red":0,"black":0}
point_h=False
point_v=False
point_d=False

for n,line in enumerate(board):
for m,x in enumerate(line):
if len(board[n])-(m)>=3:
if board[n][m]==board[n][m+1] and board[n][m]==board[n][m+2] and not point_h:
points[board[n][m]]+=1
point_h=True
print board[n][m], "horizontal"
if len(board[n])-(m)>=4:
if board[n][m]==board[n][m+3]:
points[board[n][m]]+=1
print board[n][m], "horizontal"
else:
point_h=False

if len(board)-(n)>=3:
if board[n][m]==board[n+1][m] and board[n][m]==board[n+2][m] and not point_v:
points[board[n][m]]+=1
point_v=True
print board[n][m], "vertical"
if len(board)-(n)>=4:
if board[n][m]==board[n+3][m]:
points[board[n][m]]+=1
print board[n][m], "vertical"
else:
point_v=False

if len(board)-(n)>=3 and len(board[n])-(m)>=3:
if board[n][m]==board[n+1][m+1] and board[n][m]==board[n+2][m+2] and not point_d:
points[board[n][m]]+=1
point_d=True
print board[n][m], "diagonal"
if len(board)-(n)>=4:
if board[n][m]==board[n+3][m]:
points[board[n][m]]+=1
print board[n][m], "diagonal"
else:
point_d=False
print points
if points["red"]>points["black"]:
return "Red"
elif points["black"]>points["red"]:
return "Black"
else:
return "Tie"
else:
return "Small board"``````

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

traverse from 4 directions. horizontally (N), vertically (N), from left top to right bottom (2N-5), from left top to right bottom (2N-5). Keep track of points during traversing.
Time complexity O(N)

Not sure if this is a right solution.

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

Hi

Regards

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

Are u sure time is O(N)?
In my understanding, in each horizontally traversal, you need to traversal each elements in colomn, and the time is O(N^2)

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

package DP;

public class Mattrix_color_points {

public static void main(String[] args) {

char[][] matrix = {{'r','r','r','b'},{'b','r','b','r'},{'b','r','r','b'},{'b','r','b','b'}};
int row = 4, column=4;
int red_count = findCount(matrix,4,4,'r');
int blue_count = findCount(matrix,4,4,'b');
System.out.println("Count of red triplets: "+red_count);
System.out.println("Count of blue triplets: "+blue_count);
}

private static int findCount(char[][] matrix, int m, int n, char c) {

int count = 0;

for(int i=0;i<m;i++)
{
for(int j=0;j<n-2;j++) //for all horizontal triplet
{
if(matrix[i][j]==c && matrix[i][j+1]==c && matrix[i][j+2]==c)
count++;
}
for(int k=0;k<n-2-i;k++) //top down diagonal
{
if(matrix[i][k]==c && matrix[i+1][k+1]==c && matrix[i+2][k+2]==c)
count++;
}
}
//for all vertical triplet
for(int i=0;i<m-2;i++)
{
for(int j=0;j<n;j++)
{
if(matrix[i][j]==c && matrix[i+1][j]==c && matrix[i+2][j]==c)
count++;
}
}
//for all bottom to top diagonal triples
for(int i=m-2;i<m;i++)
{
for(int k=0;k<n-2;k++)
{
if(matrix[i][k]==c && matrix[i-1][k+1]==c && matrix[i-2][k+2]==c)
count++;
}
}

return count;
}

}

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

You should change the last loop for the top down approach.
It should be for(int i=m-1;i>=2;i--)

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

public static int findCount(char[][] matrix, int x, int y, char c){

int count = 0;

for(int i = 0; i < x; i++){

for(int j = 0; j < y; j++){
//Horizontal
if(j < y-2 && matrix[i][j]==c && matrix[i][j+1]==c && matrix[i][j+2]==c){
count++;
}
//Vertical
if(i < x-2 && matrix[i][j]==c && matrix[i+1][j]==c && matrix[i+2][j]==c){
count++;
}
//Diagonal left to right
if(i < x-2 && j < y-2 && matrix[i][j]==c && matrix[i+1][j+1]==c && matrix[i+2][j+2]==c){
count++;
}

}

for(int j = y-1; j > 0; j--){

//Diagonal right to left
if(i < x-2 && j > 1 && matrix[i][j]==c && matrix[i+1][j-1]==c && matrix[i+2][j-2]==c){
count++;
}
}

}

return count;
}

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

no need to write the last loop seperately . You can check this right to left condition in the same loop.

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

Question says if 4 same colors appears vertically then give 2 point to that color.
I think you missed that point.

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

public class Epic_REDBLK {
public String findWinner(int[][] grid){//1 is RED, 0 is BLK

int countRED = 0;
int countBLK = 0;
for(int row = 0;row<grid.length;row++){
for(int col = 0;col<grid[0].length;col++){
if(grid[row][col] == 1) countRED += findWinner(grid,1,row,col);
else countBLK += findWinner(grid,0,row,col);
}
}
return countRED>countBLK? "RED":(countRED==countBLK? "TIE":"BLACK");
}

/** just for test the result
*
* @param grid
* @param color
* @return the points of the target color
*/
public int findWinner(int[][] grid, int color){//1 is RED, 0 is BLK
int countRED = 0;
int countBLK = 0;
for(int row = 0;row<grid.length;row++){
for(int col = 0;col<grid[0].length;col++){
if(grid[row][col] == 1) countRED += findWinner(grid,1,row,col);
else countBLK += findWinner(grid,0,row,col);
}
}
return color==1? countRED:countBLK;
}

public int findWinner(int[][] grid, int target, int row, int col){
int countRED = 0;
int rows = grid.length;
int cols = grid[0].length;
int countCur = 1;
//right
for(int i=1;i+col<cols;i++){
if(grid[row][col+i]==target){
++countCur;
if(countCur==3){
++countRED;
break;
}
}else{
break;
}
}
countCur = 1;
//rightdown
for(int i=1;i+row<rows&&i+col<cols;i++){
if(grid[row+i][col+i]==target){
++countCur;
if(countCur==3){
++countRED;
break;
}
}else{
break;
}
}
countCur = 1;
//down
for(int i=1;i+row<rows;i++){
if(grid[row+i][col]==target){
++countCur;
if(countCur==3){
++countRED;
break;
}
}else{
break;
}
}
countCur = 1;
//leftdown
for(int i=1;i+row<rows&&col-i>=0;i++){
if(grid[row+i][col-i]==target){
++countCur;
if(countCur==3){
++countRED;
break;
}
}else{
break;
}
}

return countRED;
}

/**main func/test case
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Epic_REDBLK test = new Epic_REDBLK();

int[][] grid = new int[][]{
{0,1,0,1,1},
{0,1,1,1,1},
{0,1,0,1,1},
{1,0,1,0,1},
};
System.out.println(test.findWinner(grid));
}

}

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

Few bugs, but you get the idea.

``````var matrixTrval = (function() {

var findWinner = function(matrix, currentResult) {
if (matrix.length === 0) {
console.log(currentResult.score);
return currentResult.score;
}
var thisNodeScore = {};

currentResult = currentResult || {
color: matrix[0][0],
count: 0,
score: 0,
isVertical: true,
vcount: 0
}

if (matrix[0][0] === currentResult.color) {
thisNodeScore = {
count: currentResult.count + 1,
color: currentResult.color
};
if (currentResult.isVertical) {
if (currentResult.vcount >= 3) {
thisNodeScore.score = currentResult.score + 2;
}
thisNodeScore.vcount = currentResult.vcount + 1;
} else if (currentResult.count >= 2) {
thisNodeScore.score = currentResult.score + 1;
}
thisNodeScore.count = currentResult.count + 1;
}
thisNodeScore = {
count: thisNodeScore.count || 1,
color: currentResult.color,
isVertical: currentResult.isVertical,
vcount: thisNodeScore.vcount || 1,
score: thisNodeScore.score || 0
}

var moveDownMatrix = [];
var moveRightMatrix = [];
var moveDiagonalMatrix = [];
var i = 0;
var m = 0;
var length = matrix.length;
var vLength = matrix[0].length;

for (i = 0; i < length; i++) {
moveRightMatrix[i] = [];
moveDownMatrix[i] = [];
moveDiagonalMatrix[i] = [];
for (m = 0; m < vLength; m++) {
moveRightMatrix[i][m] = matrix[i][m];
moveDownMatrix[i][m] = matrix[i][m];
moveDiagonalMatrix[i][m] = matrix[i][m];
}
}

if (moveDownMatrix.length >= 1) {
moveDownMatrix = moveDownMatrix.slice(1);
thisNodeScore.isVertical = true;
}
for (i = 0; i < length && moveRightMatrix[i].length > 0; i++) {
moveRightMatrix[i] = moveRightMatrix[i].slice(1);
}

for (i = 0; i < length && moveDiagonalMatrix[i].length > 0; i++) {
moveDiagonalMatrix[i] = moveDiagonalMatrix[i].slice(1);
}
if (moveDiagonalMatrix.length > 1 && moveDiagonalMatrix[0].length >= 1) {
moveDiagonalMatrix = moveDiagonalMatrix.slice(1);
}
if (moveRightMatrix[0].length === 0) {
moveRightMatrix = [];
}
if (moveDiagonalMatrix[0].length === 0) {
moveDiagonalMatrix = [];
}

var moveDownScore = thisNodeScore.score;
if (moveDownMatrix.length > 0) {
moveDownScore = findWinner(moveDownMatrix, thisNodeScore);
}
thisNodeScore.isVertical = false;

var moveRightScore = thisNodeScore.score;

if (moveRightMatrix.length > 0) {
moveRightScore = findWinner(moveRightMatrix, thisNodeScore);
}

var moveDiagonalScore = thisNodeScore.score;
if (moveDiagonalMatrix.length > 0) {
moveDiagonalScore = findWinner(moveDiagonalMatrix, thisNodeScore);
}

var bestWinner = moveRightScore > moveDownScore ? moveRightScore : moveDownScore;
bestWinner = moveDiagonalScore > bestWinner ? moveDiagonalScore : bestWinner;

return bestWinner;
};

return function(matrix) {
return findWinner(matrix);
};
})();

console.log(matrixTrval([
['red', 'black', 'black', 'black', 'red'],
['red', 'black', 'black', 'black', 'red'],
['red', 'black', 'black', 'black', 'red'],
['red', 'black', 'black', 'black', 'red'],
['red', 'black', 'black', 'black', 'red'],
['red', 'black', 'black', 'black', 'red'],
['red', 'black', 'black', 'black', 'red'],
['red', 'black', 'black', 'black', 'red']
]));``````

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

Can you explain the logic?

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

hmmm. interesting, first time see anyone solve algorithm problems using javascript.

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

This question needs to be clarified a little bit.

Have you ever considered the case when the user goes right, then down, then upright?

For this question, tt seems that only one direction is considered at a time, which greatly reduce the complexity of this problem. But the random walk case seems more fun to do (seems like a 3 dimensional DP problem I guess).

Anyway, with a bit memoization steps, this question is easy to solve. O(n^2), O(n).

Playable code at

``ideone.com/qFgocO``

``````int countHelper(vector<vector<char>>& matrix, char targetColor, pair<int, int> dir, int onepoint=3) {
if (!matrix.size() || !matrix[0].size()) return 0;
int rowcount(matrix.size()), colcount(matrix[0].size());

int ret = 0;
vector<vector<int>> count(rowcount, vector<int>(colcount, 0));
for (int col = colcount - 1; col >= 0; --col) {		// col goes next
for (int row = rowcount - 1; row >= 0; --row) {	// row goes first
if (matrix[row][col] != targetColor) continue;
// check the next one along the line.
count[row][col] = 1;
int nextrow(row + dir.first), nextcol(col + dir.second);
if (!(nextrow < 0 || nextrow == rowcount || nextcol < 0 || nextcol == colcount))
count[row][col] += count[nextrow][nextcol];
ret += (count[row][col] >= onepoint);
}
}

return ret;
}

bool winner(vector<vector<char>>& matrix) {
int red = countHelper(matrix, 'r', pair<int, int>{-1, 1}) + \
countHelper(matrix, 'r', pair<int, int>{0, 1}) + \
countHelper(matrix, 'r', pair<int, int>{1, 1}) + \
countHelper(matrix, 'r', pair<int, int>{1, 0});

int black = countHelper(matrix, 'b', pair<int, int>{-1, 1}) + \
countHelper(matrix, 'b', pair<int, int>{0, 1}) + \
countHelper(matrix, 'b', pair<int, int>{1, 1}) + \
countHelper(matrix, 'b', pair<int, int>{1, 0});

return red > black;
}``````

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

#include <iostream>
#include <sstream>
#include <cmath>
#include <string.h>
using namespace std;

int main()
{
int n, counter=1,rpoint=0,bpoint=0;
cout<<"\n Enter n";
cin>>n;
int arr[n][n];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>arr[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<" "<<arr[i][j];
}
cout<<endl;
}
for(int i=0;i<n;i++)
{ counter=1;
for(int j=0;j<n-1;j++)
{
if(arr[i][j]==arr[i][j+1]) counter++;
else
{
if(counter>=3)
{
if(arr[i][j]==0)
{
bpoint+=(counter%3)+(counter/3);
counter=1;
}
else
{
rpoint+=(counter%3)+(counter/3);
counter=1;
}
}
else counter=1;
}
if(j==n-2)
{
if(counter>=3)
{
if(arr[i][j]==0)
{
bpoint+=(counter%3)+(counter/3);
counter=1;
}
else
{
rpoint+=(counter%3)+(counter/3);
counter=1;
}
}
else counter=1;
}

}
}
if(rpoint>bpoint) cout<<"r is winner";
else cout<<"b is winner";
return 0;
}

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

``````public class MatrixBlackWhite {
public static void main(String args[]){

int[][] BAndW ={{0,1,0,1,0},{1,0,1,0,1},{0,0,0,1,1},{1,1,1,1,1},{1,1,0,0,1}};
System.out.println(checkPoints(BAndW,0));
System.out.print(checkPoints(BAndW,1));
}
public static int checkPoints(int[][] a,int f){
int count=0;//You cannot set visibility scopes (private,...) to local variables.
//row
for(int i=0;i<a.length;i++){
for(int c1=0;c1<a[i].length-2;c1++){
if(a[i][c1]==a[i][c1+1]&&a[i][c1+1]==a[i][c1+2]&&a[i][c1]==f)
count++;
}
}
//column
for(int j=0;j<a[0].length;j++){
for(int c2=0;c2<a.length-2;c2++){
if(a[c2][j]==f&&a[c2][j]==a[c2+1][j]&&a[c2+1][j]==a[c2+2][j])
count++;
}
}
//diagonal
//lefttop-rightdown
for(int row=2;row>=0;row--){
for(int colm=0;colm<3-row;colm++){
if(a[row][colm]==f&&a[row+1][colm+1]==a[row][colm]&&a[row+2][colm+2]==a[row][colm])
count++;
}
}
//leftdown-righttop
for(int row=2;row>=0;row++){
for(int colm=0;colm<3-row;colm++){
if(a[row][colm]==f&&a[row-1][colm+1]==a[row][colm]&&a[row-2][colm+2]==a[row][colm])
count++;
}
}
return count;
}

}``````

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.