Epic Systems Interview Question
Country: United States
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..
but this is just checking for three consecutive positions and skipped the four consecutive positions with red color.
you should also check for (i,j), (i-1, j-1), (i-2, j-2) - the other diagonal from Right to Left
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
Question says if 4 same colors appears vertically then give 2 point to that color.
I think you missed that point.
@ajay:
(R,R,R,R) = (R1,R2,R3), (R2,R3,R4). Hence 2 pts. Nothing special about being vertical or 4 tiles long.
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?
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"
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.
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;
}
}
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;
}
no need to write the last loop seperately . You can check this right to left condition in the same loop.
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));
}
}
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']
]));
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;
}
#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;
}
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;
}
}
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.
- abhishek7446 March 02, 2014Do 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).