Amazon Interview Question SDE1s
Country: United States
Here is a recursive solution in java. To my knowledge, it looks like a little modification to the flood fill algorithm.
public class MatrixAlgorithms {
public static int findMaxSequence(int[][] array) {
int length = 0;
int n = array.length;
int m = array[0].length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int[][] visited = getVisitedArray(n, m);
length = Math.max(length, findMaxSequence(array, i, j, visited));
}
}
return length;
}
private static int findMaxSequence(int[][] array, int i, int j, int[][] visited) {
int n = array.length;
int m = array[0].length;
int length = 0;
if (visited[i][j] == 1) return 0;
visited[i][j] = 1;
if (isInRange(n, m, i + 1, j) && visited[i + 1][j] == 0 && Math.abs(array[i + 1][j] - array[i][j]) == 1)
length = Math.max(length, findMaxSequence(array, i + 1, j, visited));
if (isInRange(n, m, i - 1, j) && visited[i - 1][j] == 0 && Math.abs(array[i - 1][j] - array[i][j]) == 1)
length = Math.max(length, findMaxSequence(array, i - 1, j, visited));
if (isInRange(n, m, i, j + 1) && visited[i][j + 1] == 0 && Math.abs(array[i][j + 1] - array[i][j]) == 1)
length = Math.max(length, findMaxSequence(array, i, j + 1, visited));
if (isInRange(n, m, i, j - 1) && visited[i][j - 1] == 0 && Math.abs(array[i][j - 1] - array[i][j]) == 1)
length = Math.max(length, findMaxSequence(array, i, j - 1, visited));
return length + 1;
}
private static int[][] getVisitedArray(int n, int m) {
int[][] array = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
array[i][j] = 0;
}
}
return array;
}
private static boolean isInRange(int n, int m, int i, int j) {
if (i < 0 || i >= n) return false;
if (j < 0 || j >= m) return false;
return true;
}
}
@chris: sorry i gave the wrong input.Try this and it doesn't work.
3, 10,11, 4
4, 9, 10, 5
5, 8, 9, 6
6, 7, 8, 7
@aka: I don't see the problem here. The method returns 16 as expected. I believe, it is correct. It will be useful if you mention in which case it fails rather than just giving random values.
@Chris :
Nice. But, the above algo takes O(m^2*n^2) right ? We are basically searching for the longest sequence from all possible places ..
Can't we do any optimization here? I feel if we apply DP, we can do this in O(m*n) time. Any way we are using extra space.
@chris: here you go, i knew your code have bugs and here are below cases which fails.
{
{1, 2, 1, 1, 1, 1, 1, 1},
{2, 3, 4, 5, 1, 1, 1, 1},
{3, 2, 1, 6, 1, 1, 1, 1},
{4, 3, 4, 5, 1, 1, 1, 1},
{5, 4, 1, 1, 1, 1, 1, 1},
{6, 5, 6, 7, 8, 9, 10, 1},
{7, 1, 1, 1, 1, 1, 1, 1}
}));
18 instead of 22
{1, 2, 1, 1, 1, 1, 1, 1},
{0, 3, 4, 5, 1, 1, 1, 1},
{1, 2, 1, 6, 1, 1, 1, 1},
{1, 3, 4, 5, 1, 1, 1, 1},
{1, 4, 1, 1, 1, 1, 1, 1},
{1, 5, 6, 7, 8, 9, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1}
})
15 instead of 14.
@aka: That was a nice catch. I made few modifications to my old code and posted it again. Check whether it works.
By the way, output for the second case is 19 and not 14.
@aka For your 1st case, the maximum sequence length is 22, and the path is starting from array[0][2]:1 2 1 2 3 4 5 6 5 4 3 2 3 4 5 4 5 6 7 8 9 10. For the 2nd case, the max length is 19 and the path is from array[0][2]: 1 2 1 0 1 2 3 4 5 6 5 4 3 4 5 6 7 8 9.
How does this looks guys?
public static void checkMaxSeq(int[][] twoDArray){
Map<Integer, int[]> testMap = new HashMap<Integer, int[]>();
int lastIndexOfSeq = 0;
int startIndexOfSeq = 0;
boolean seriesStarted = false;
boolean seqFound = false;
first: for (int i = 0; i < twoDArray.length; i++) {
second: for (int j = 0; j < twoDArray[i].length; j++) {
if (j + 1 <= twoDArray[i].length - 1) {
third: while (twoDArray[i][j + 1] == (twoDArray[i][j] + 1)) {
// Take the start index of sequence
if (!seriesStarted)
startIndexOfSeq = j;
seriesStarted = true;
continue second;
}
}
lastIndexOfSeq = j;
if(seriesStarted){
if (testMap.get(i) == null
|| testMap.get(i).length < (lastIndexOfSeq - startIndexOfSeq))
testMap.put(i, Arrays.copyOfRange(twoDArray[i],
startIndexOfSeq, lastIndexOfSeq + 1));
}
if(testMap.get(i) == null && j == twoDArray[i].length-1)
testMap.put(i, Arrays.copyOfRange(twoDArray[i],
0, 1));
seriesStarted = false;
}
}
for(int[] nextArray : testMap.values()){
for(int i:nextArray)
System.out.println(i);
System.out.println();
}
}
There is a bug in my previous code. So posting it again with little modifications.
public class MatrixAlgorithms {
public static int findMaxSequence(int[][] array) {
int length = 0;
int n = array.length;
int m = array[0].length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int[][] visited = getVisitedArray(n, m);
length = Math.max(length, findMaxSequence(array, i, j, visited));
}
}
return length;
}
private static int findMaxSequence(int[][] array, int i, int j, int[][] visited) {
int n = array.length;
int m = array[0].length;
int length = 0;
if (visited[i][j] == 1) return 0;
visited[i][j] = 1;
if (isInRange(n, m, i + 1, j) && visited[i + 1][j] == 0 && Math.abs(array[i + 1][j] - array[i][j]) == 1)
length = Math.max(length, findMaxSequence(array, i + 1, j, getVisitedArrayCopy(visited)));
if (isInRange(n, m, i - 1, j) && visited[i - 1][j] == 0 && Math.abs(array[i - 1][j] - array[i][j]) == 1)
length = Math.max(length, findMaxSequence(array, i - 1, j, getVisitedArrayCopy(visited)));
if (isInRange(n, m, i, j + 1) && visited[i][j + 1] == 0 && Math.abs(array[i][j + 1] - array[i][j]) == 1)
length = Math.max(length, findMaxSequence(array, i, j + 1, getVisitedArrayCopy(visited)));
if (isInRange(n, m, i, j - 1) && visited[i][j - 1] == 0 && Math.abs(array[i][j - 1] - array[i][j]) == 1)
length = Math.max(length, findMaxSequence(array, i, j - 1, getVisitedArrayCopy(visited)));
return length + 1;
}
private static int[][] getVisitedArray(int n, int m) {
int[][] array = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
array[i][j] = 0;
}
}
return array;
}
private static int[][] getVisitedArrayCopy(int[][] array) {
int n = array.length;
int m = array[0].length;
int[][] newArray = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
newArray[i][j] = array[i][j];
}
}
return newArray;
}
private static boolean isInRange(int n, int m, int i, int j) {
if (i < 0 || i >= n) return false;
if (j < 0 || j >= m) return false;
return true;
}
}
@Chris: check this out :)
int[][] array = new int[][]{
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0}
};
You actually need to only check each item once. If the left or top item are one more (or less) than the current, that means that for the left or top item, the current item is one more or less. So all you need to do is check the right and bottom for each item, and keep going for as long as you can.
import java.util.ArrayList;
import utility.ListUtil;
public class FindLongestPath {
// 3 5 7 3
// 4 5 8 1
// 6 4 5 2
public static void main(String[] args) {
int [][] arr =
{
{3,5,7,3},
{4,5,8,1},
{6,4,5,2}
};
// for(int [] pos : findLongestPath(arr))
// {
// System.out.print(pos[0] +"," + pos[1] + "; ");
// }
for(int [] pos : findLongestPath(arr))
{
System.out.print(arr[pos[0]][pos[1]]+ ", ");
}
}
private static ArrayList <int[]> findLongestPath(int[][] arr2) {
int [][]arr = new int[arr2.length][arr2[0].length];
for(int i = 0; i < arr.length; i++)
{
for(int j = 0; j < arr[0].length; j++)
{
arr[i][j] = arr2[i][j];
}
}
ArrayList <int []> longestPath = new ArrayList<>();
for(int i = 0; i < arr.length; i++)
{
for(int j = 0; j < arr[0].length; j++)
{
if(arr[i][j] != -1)
{
ArrayList <int[]> p = findLongestPathHelper(arr, i, j);
if(p.size() > longestPath.size())
longestPath = p;
}
}
}
return longestPath;
}
private static ArrayList <int[]> findLongestPathHelper(int[][] arr, int i, int j) {
ArrayList<int []> longestPath = new ArrayList<>();
int cur = arr[i][j];
arr[i][j] = -1;
if(i+1 < arr.length && arr[i+1][j] != -1 && Math.abs(arr[i+1][j]-cur) == 1)
{
longestPath = findLongestPathHelper(arr, i+1, j);
}
if(j+1 < arr[0].length && arr[i][j+1] != -1 && Math.abs(arr[i][j+1]-cur) == 1)
{
ArrayList<int []> candidate = findLongestPathHelper(arr, i, j+1);
if(longestPath == null || candidate.size() > longestPath.size())
longestPath = candidate;
}
int [] at = new int[2];
at[0] = i;
at[1] = j;
longestPath.add(at);
return longestPath;
}
}
This actually worked
#include<iostream>
using namespace std;
int main(){
int i,j;
int tmp1;
int a[3][4]={{3,8,9,4},{4,7,8,5},{5,6,7,6}};
//int a[3][4]={{3,5,7,3},{4,5,8,1},{6,4,5,2}};
for(i=0;i<3;i++)
{
tmp1=0;
for(j=0;j<3;j++){
// cout<<a[i][j]<<" "<<a[i][j]<<endl;
if((a[i][j]-a[i][j+1]) == 1|| (a[i][j]-a[i][j+1]) == -1)
{
tmp1=1;
cout<<a[i][j]<<" "<<a[i][j+1]<<endl;
}
}
if(!tmp1)
cout<<a[i][0]<<endl;
}
cin.get();
}
For the test case of:
{1, 2, 1, 1, 1, 1, 1, 1},
{0, 3, 4, 5, 1, 1, 1, 1},
{1, 2, 1, 6, 1, 1, 1, 1},
{1, 3, 4, 5, 1, 1, 1, 1},
{1, 4, 1, 1, 1, 1, 1, 1},
{1, 5, 6, 7, 8, 9, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1}
My solution actually found 19 as a sequence. The sequence is as follows.
121XXXXX
0345XXXX
12X6XXXX
X345XXXX
X4XXXXXX
X56789XX
XXXXXXXX
package amazon;
public class LongestMatrixSequence {
public static void main(String[] args) {
new LongestMatrixSequence().run();
}
private int[][] _data;
private int _SIZE_X;
private int _SIZE_Y;
private int _max = 0;
public LongestMatrixSequence() {
_data = new int[][] { { 1, 0, 1, 0, 1, 0, 1, 0 }, { 0, 1, 0, 1, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1, 0, 1, 0 }, { 0, 1, 0, 1, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1, 0, 1, 0 }, { 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 1, 0 } };
_SIZE_Y = _data.length;
_SIZE_X = _data[0].length;
}
/**
* Main Loop
*
* @author MReyes
*/
public void run() {
boolean[][] flagRef = new boolean[_SIZE_Y][_SIZE_X];
START: for (int y = 0; y < _SIZE_Y; y++) {
for (int x = 0; x < _SIZE_X; x++) {
_reset(flagRef);
_process(flagRef, x, y, 0);
if (this._found())
break START;
}
}
System.out.println("MAX=" + _max);
}
/**
* Check if it is still worth proceeding.
* @return
* @author MReyes
*/
private boolean _found() {
return _SIZE_Y * _SIZE_X == _max;
}
/**
* Utility to reset the "AlreadyInspected" array.
* @param flagRef
* @author MReyes
*/
private void _reset(boolean[][] flagRef) {
for (int y = 0; y < _data.length; y++) {
for (int x = 0; x < _data[y].length; x++) {
flagRef[y][x] = false;
}
}
}
/**
* Check if the position is accessible.
* @param flagRef
* @param originValue
* @param posX
* @param posY
* @return
* @author MReyes
*/
private boolean _isAccessible(boolean[][] flagRef, int originValue, int posX, int posY) {
if (posX < _SIZE_X && posX > -1 && posY < _SIZE_Y && posY > -1)
return !flagRef[posY][posX] && (_data[posY][posX] - 1 == originValue || _data[posY][posX] + 1 == originValue);
return false;
}
/**
* Actual processing API which chooses to go in order: Right, Bottom, Left and then Top.
* @param flagRef
* @param posX
* @param posY
* @param counter
* @return
* @author MReyes
*/
private int _process(boolean[][] flagRef, int posX, int posY, int counter) {
flagRef[posY][posX] = true;
int value = _data[posY][posX];
counter++;
if (this._found())
return counter;
_processAccess(flagRef, value, posX + 1, posY, counter);
_processAccess(flagRef, value, posX, posY + 1, counter);
_processAccess(flagRef, value, posX - 1, posY, counter);
_processAccess(flagRef, value, posX, posY - 1, counter);
return counter;
}
/**
* Max inspection prior to going back.
* @param flagRef
* @param originValue
* @param posX
* @param posY
* @param counter
* @return
* @author MReyes
*/
private int _processAccess(boolean[][] flagRef, int originValue, int posX, int posY, int counter) {
if (_isAccessible(flagRef, originValue, posX, posY)) {
counter = _process(flagRef, posX, posY, counter);
if (counter > _max) {
_max = counter;
}
flagRef[posY][posX] = false;
}
return counter;
}
}
dfs apporach.
#include <stdio.h>
int a[3][4] = {
3, 8, 11, 10,
4, 7, 14, 9,
5, 6, 17, 81,
};
int dist[100][100];
int vist[100][100];
int n, m;
#define max(a,b) ((a)>(b)?(a):(b))
int DepthSearch(int x, int y)
{
int sum=0;
if(vist[x][y]) {
return dist[x][y];
}
if(dist[x][y])
return dist[x][y];
vist[x][y]=1;
if(y-1 >= 0 && (((a[x][y]+1) == a[x][y-1]) || ((a[x][y]-1) == a[x][y-1]))) {
sum = max(DepthSearch(x, y-1), sum);
}
if(y+1 < n && (((a[x][y]+1) == a[x][y+1]) || ((a[x][y]-1) == a[x][y+1]))) {
sum = max(DepthSearch(x, y+1), sum);
}
if(x+1 < m && (((a[x][y]+1) == a[x+1][y]) || ((a[x][y]-1) == a[x+1][y]))) {
sum = max(DepthSearch(x+1, y), sum);
}
if(x-1 >= 0 && (((a[x][y]+1) == a[x-1][y]) || ((a[x][y]-1) == a[x-1][y]))) {
sum = max(DepthSearch(x-1, y), sum);
}
dist[x][y] = sum+1;
return dist[x][y];
}
int solution()
{
int mx = 0,i, j;
for(i = 0; i < m; ++ i)
for(j = 0; j < n; ++ j) {
mx = max(mx, DepthSearch(i, j));
}
return mx;
}
int main()
{
int i, j;
m=3;
n=4;
for(i = 0; i < m; ++ i)
for(j = 0; j < n; ++ j) {
dist[i][j] = 0;
vist[i][j] = 0;
}
printf("%s: %d\n", "anish", solution());
return 0;
}
A little more clarification needed on the question. By "sequence" what do you mean? Horizontal or vertical or diagonal?
I'm not sure whether this makes much sense but I have a doubt.
Can the max sequence branch out? In other words, do we need to find the longest sequence or maximum block? Refer to the below example.
Given Matrix
2, 3, 4, 5
6, 4, 8, 9
9, 5, 10, 11
7, 6, 5, 6
In the below, which is the correct one?
2, 3, 4, 5
-, 4, -, -
-, 5, -, -
7, 6, 5, 6
(or)
-, 3, 4, 5
-, 4, -, -
-, 5, -, -
-, 6, 5, 6
Assuming a is the given array of n * m dimension.
for (int i=0;i<=n;i++)
{
int array=new int[m];
for(int j=0;j<m;j++)
{
if(((a[j]+1)==a[j+1])||(a[j]-1)==a[j+1])
{
array[j]=a[j];
}
if(((a[j-1]+1)==a[j])||((a[j-1]-1)==a[j])))
{
array[j]=a[j];
}
}
print this array.length
}
- sangeet.kumar June 06, 2013#include <stdio.h> int main(void) { int i, j; int a[3][4] = {{3, 5, 7, 3}, {4, 5, 8, 1}, {6, 4, 5, 2}}; for (i=0; i<3; i++) { int prev_index = 0; int prev_length = 1; int curr_index = 0; int curr_length = 1; for (j=1; j<4; j++) { int diff = a[i][j] - a[i][j-1]; if (diff == 1 || diff == -1) { curr_length++; if (curr_length > prev_length) { prev_index = curr_index; prev_length = curr_length; } } else { curr_index = j; curr_length = 1; } } for (j = prev_index; j < (prev_length + prev_index); j++) printf("%d ", a[i][j]); printf("\n"); } return 0; }