Goldman Sachs Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
lolmax,
how about this matrix?
0 0 0 1 1
1 1 1 0 1
0 1 1 1 0
0 0 1 0 0
1 1 1 0 0
according to ur algo its 6, but its 8.
lolmax,
how about this matrix?
0 0 0 1 1
1 1 1 0 1
0 1 1 1 0
0 0 1 0 0
1 1 1 0 0
according to ur algo its 6, but its 8.
just try to find out all the possible routes and at last choose the one that returns the longest path
#include <stdio.h>
int array[5][5]={0,0,0,1,1,1,1,1,0,1,0,1,1,1,0,0,0,1,0,0,1,1,1,1,1};
void disp_function(int m,int n)
{
if((m+1)<5)
{
if(array[m+1][n]==1)
{
printf("%d",array[m+1][n]);
disp_function(m+1,n);
}
}
if((n+1)<5)
{
if(array[m][n+1]==1)
{
printf("%d",array[m][n+1]);
disp_function(m,n+1);
}
}
printf("\n");
}
int main()
{
int i,j;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
if(array[i][j]==1)
{
printf("%d",array[i][j]);
disp_function(i,j);
}
}
}
return 0;
}
we use dynamic programming here,
let's the given matrix of zeros and ones is M and is of size n*m, we create an another matrix N of size (n+1)*(m+1)
and we start from the point (n+1,m+1)(right most corner) and move to point (1,1)(left most corner),
so final algorithm is following :
for i=1 to n+1
N[i][m+1] = 0;
for j=1 to m+1
N[n+1][j] = 0;
for i=n to 1
for j=m to 1
if M[i][j] == 1
N[i][j] = 1 + max(N[i+1][j] , N[i][j+1]);
else
N[i][j] = 0
search max element in matrix, output it.
complexity : O(n*m)(time) + O(n*m)(space)
#include<stdio.h>
#include<conio.h>
void getNonZeroIndex(int *, int *);
int getMaxPath(int, int);
int arr[5][5] = {{0,0,0,1,1}, {1,1,1,0,1}, {0,1,1,1,0}, {0,0,1,0,0}, {1,1,1,1,1}};
void main()
{
int maxPathLength = -1;
int maxTemp, i, j;
//sqrt(144);
for(i=0; i<5; i++){
for(j=0; j<5; j++){
getNonZeroIndex(&i, &j);
maxTemp = getMaxPath(i,j);
if(maxTemp > maxPathLength)
maxPathLength = maxTemp;
}
}
printf("Maximum path lenght: %d", maxPathLength);
getch();
}
int getMaxPath(int x, int y){
if(x>=5 && y>=5)
return 0;
else{
if(x+1<5 && y+1 < 5 && arr[x][y+1] == 1 && arr[x+1][y] == 1){
int p,q;
p = getMaxPath(x,y+1); q = getMaxPath(x+1,y);
if(p>q)
return p+1;
else
return q+1;
}else if(y+1 < 5 && arr[x][y+1] == 1){
return getMaxPath(x,y+1)+1;
}else if(x+1<5 && arr[x+1][y] == 1){
return getMaxPath(x+1,y)+1;
}else
return 0;
}
}
void getNonZeroIndex(int *x, int *y){
for(int i = *x; i< 5; i++){
for(int j = *y; j<5; j++)
if(arr[i][j] == 1){
*x = i; *y = j;
return;
}
}
}
#include<iostream>
using namespace std;
int main()
{
int A[5][5] = {{0,0,0,1,1},{1,1,1,0,1},{0,1,1,1,0},{0,0,1,0,0},{1,1,1,1,1}};
int temp[5][5];
int end_r(0), end_c(0);
for(int i=0; i<5; i++){
for(int j=0; j<5; j++){
temp[i][j] = A[i][j];
int top(0), left(0), max(0);
if(i>0) top = temp[i-1][j];
if(j>0) left = temp[i][j-1];
if(top>left) max = top; else max=left;
if(temp[i][j] && max) {temp[i][j] = ++max, end_r=i; end_c=j;}
cout<<temp[i][j]<<" ";
}
cout<<endl;
}
int i = end_r, j = end_c, count=temp[i][j];
--count;
while(count){
if((temp[i-1][j]) == count) --i; else --j;
--count;
}
cout<<"Starting Point"<<" "<<i<<" "<<j<<endl;
cout<<"Ending Point"<<" "<<end_r<<" "<<end_c<<endl;
cout<<"Max Length"<<" "<<temp[end_r][end_c];
return 0;
}
public static void main(String[] args) {
int[][] arr = new int[][]{
{0,0,0,1,1},
{1,1,1,0,0},
{0,1,1,1,0},
{1,1,1,1,0},
{0,0,1,0,0},
{1,1,1,1,0}
};
int row = 0;
int maxOnesRow = 0;
int onesCount =0;
int tmpOnesCnt = 0;
for (int[] rows : arr) {
if(row ==0){
tmpOnesCnt =onesCount;
}
if(tmpOnesCnt<onesCount){
maxOnesRow = row;
tmpOnesCnt =onesCount;
}
onesCount =0;
for (int cols : rows) {
if (cols == 1) {
onesCount++;
}
}
row++;
}
System.out.println(maxOnesRow);
}
{
{
{
package in.co.matrix;
public class FindingMaxOnes {
public static void main(String[] args) {
int A[][] = {
{0,0,0,1,1},
{1,1,1,0,1},
{0,1,1,1,0},
{0,0,1,0,0},
{1,1,1,1,1}
};
doProcess(A);
}
public static void doProcess(int[][] old) {
int size = old.length;
int length = old[0].length;
int[][] newArray = new int[size][length];
int maxValue = 0;
int tmpMaxValue = 0;
for (int i = 0; i < size ; i++) {
for (int j = 0; j < length; j++) {
if(old[i][j]==0)
newArray[i][j] = 0;
else {
int behind = behind(i, j, newArray);
int forward = getForword(i,j,old,size,length);
if (forward ==0 && behind == 0)
newArray[i][j] = 0;
tmpMaxValue = 1+behind;
if(tmpMaxValue >maxValue)
maxValue = tmpMaxValue;
newArray[i][j] = tmpMaxValue;
}
}
}
System.out.println("Max Value :: "+maxValue);
}
private static int getForword(int i, int j, int[][] old, int size, int length) {
if(i+1 >= size && j+1>=length )
return 0;
if(i+1 >= size) {
return old[i][j+1];
}
if (j+1 >= length) {
return old[i+1][j];
}
return old[i+1][j]>old[i][j+1]?old[i+1][j]:old[i][j+1];
}
private static int behind(int i, int j, int[][] old) {
if(i-1 < 0 && j-1 < 0 )
return 0;
if(i-1 <0) {
return old[i][j-1];
}
if (j-1 < 0) {
return old[i-1][j];
}
int c = old[i-1][j]>old[i][j-1]?old[i-1][j]:old[i][j-1];
return c;
}
}
}
}
}
package interview;
public class ModifiedLCS {
/**
* @param args
*/
public static int MAX_WIDTH = 5;
public static int MAX_HEIGHT = 5;
public static int MAX_PATH_LEN = 0;
public static String MAX_PATH="";
public static int MAX_X =0;
public static int MAX_Y = 0;
public static int input[][] = {
{0, 0, 0, 1, 1},
{1, 1, 1, 0, 1},
{0, 1, 1, 1, 0},
{0, 0, 1, 0, 0},
{1, 1, 1, 0, 0}
};
public static int bestPath[] [] = {
{-1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1}
};
public static void main(String[] args) {
path(0,0);
System.out.println(MAX_PATH_LEN);
System.out.println(MAX_X +" " + MAX_Y);
}
public static int path(int i, int j){
if (i >= MAX_HEIGHT || j >= MAX_WIDTH) return 0;
if(bestPath[i][j] != -1) return bestPath[i][j];
int pathRight = path(i, j+1);
int pathDown = path(i+1, j);
int path = pathRight > pathDown ? pathRight : pathDown;
path += input[i][j];
bestPath[i][j] = path;
if(path > MAX_PATH_LEN)
{
MAX_PATH_LEN = path;
MAX_X = i;
MAX_Y = j;
}
return path;
}
}
This can be solved using dynamic programming.
void cal_one(int a[][])
{
for(int j=1;j<=n;j++)
b[1][j]=a[1][j];
for(int i=1;j<=n;j++)
b[i][1]=a[i][1];
for(int i=2;i<=n;i++)
{
for(int j=2;j<=n;j++)
{
if(a[i][j]==1)
b[i][j]=1+max(a[i-1][j],a[i][j-1]);
else
b[i][j]=0;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
return Max(a[i][j]);
}
}
//the answer to this problem is 8
Here's a naive recursive solution in Python. it can be easily memoized to reduce complexity (mark visited points in the grid with the length of the path computed at a previous iteration. only continue if the path is currently greater).
right now it's O(N^3) for an NxN matrix, via
summation(N^2 - k*N) from k = 0 to k = N
solution:
def longest(matrix, i, j, length = 0):
if matrix[i][j] == 0:
return length
length += 1
return max(longest(matrix, i + 1, j, length),
longest(matrix, i, j + 1, length))
def longest_path(matrix):
longest_path = 0
for i in range(len(matrix)):
for j in range(len(matrix[i])):
longest_path = max(longest_path, longest(mtarix, i, j))
return longest_path
public class LongestSequenceOfOne {
public static int arr[][] = {
{0, 0, 0, 1, 1},
{1, 1, 1, 0, 1},
{0, 1, 1, 1, 0},
{0, 0, 1, 0, 0},
{1, 1, 1, 1, 1}};
//can only move to the right OR down
public static int point(int row,int column,int countSoFar){
if (row>=arr.length || column>=arr[row].length) return countSoFar; //outside
if (arr[row][column]==0) return countSoFar; // cant move on 0
return Math.max(point(row, column + 1, countSoFar + 1), point(row + 1, column, countSoFar + 1));
}
public static void main(String[] args) {
int max = 0, row=-1, column=-1;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
int maxTemp = point(i, j, 0);
if (maxTemp>max){
max = maxTemp;
row = i;
column = j;
}
}
}
System.out.println(max+" at ("+row+","+column+")");
}
}
Output : 8 at (1,0)
package com.algorithms.test;
public class LongestPathInMatrixWith01 {
public static int FindLongestSequences(int[][] matrix, int row,int col){
int maxCnt = 0;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
int a = (i==0) ? 0: matrix[(i-1)][j];
int b = (j==0) ? 0: matrix[i][j-1];
System.out.println("i: "+i+" j:"+ j);
System.out.println("a: "+a+" b:"+b+" "+matrix[i][j]);
matrix[i][j] =( matrix[i][j]>0) ? max(a,b)+1 :0;
System.out.println(matrix[i][j]);
maxCnt = max(maxCnt,matrix[i][j]);
}
}
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
System.out.print(matrix[i][j]);
}
System.out.println();
}
return maxCnt;
}
public static int max(int a , int b){
return (a>b) ? a :b;
}
public static void DoTest(int[][] matrix, int rows, int col){
if(matrix == null ) return;
if(rows < 1) return;
if(col < 1) return;
for(int i=0;i<rows;i++){
for(int j=0;j<col;j++){
System.out.print(matrix[i][j]);
}
System.out.println();
}
int len = FindLongestSequences(matrix, rows, col);
System.out.println("Maximum Length "+len);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] matrix = {
{0, 0, 0, 1, 1},
{1, 1, 1, 0, 1},
{0, 1, 1, 1, 0},
{0, 0, 1, 0, 0},
{1, 1, 1, 1, 1}
};
DoTest(matrix,matrix.length,matrix[0].length);
}
}
import numpy as np
arr = np.array([
[0,0,0,1,1],
[1,1,1,0,1],
[0,1,1,1,0],
[0,0,1,0,0],
[1,1,1,1,1],
])
def longest_path(arr):
assert arr.shape[0] == arr.shape[1]
n = arr.shape[0]
dp = np.zeros(arr.shape)
_max = 0
for i in range(arr.shape[0]):
for j in range(arr.shape[1]):
if arr[i,j] == 0: # not ending here
continue
left = 0 if j==0 else dp[i, j-1]
up = 0 if i==0 else dp[i-1, j]
dp[i,j] = max(left, up) + 1 # ending here
_max = max(dp[i,j], _max)
return _max
print(longest_path(arr)) #8
This is a modified LCS problem
Looking for longest subsequence of 1's
Solve by dynamic programming
Then find the max value and backtrack from there to get the sequence
- sme January 20, 2013