Amazon Interview Question
SDETsCountry: India
Interview Type: In-Person
right. Dynamic programming will solve this in O(n^2) where the matrix is nXn.
the formula will be:
v(x,y) = max of neighbors ( v(neighbor)+1 if neighbor is next character, otherwise 0).
OP, at lease get your question right.....
I don't get how we can use dyn. prog. here since we can go in 8 directions.
With, let's say, right, down, down-right only ok, because your "from" neighboor values are always defined.
Otherwise, from where are we starting?
This can be done very simply by creating a directed graph of all the letters and then doing a DFS search starting at every position to compute the longest consecutive String. O(n) complexity to create the graph with O(n) space and O(n) complexity to complete the DFS.
class Graph{
ArrayList<int[]>[][] connections;
Graph(int x, int y){
this.connections = new ArrayList<int[]>[x][y];
for(int i = 0; i < x; i++){
for(int j = 0; j < y; j++){
this.connections[i][j] = new ArrayList<int[]>();
}
}
}
void connect(int[] from, int[] to){
this.connections[from[0]][from[1]].add(to);
}
}
public static int longestConsecutive(char[][] arr){
if(arr == null){
throw new NullPointerException();
}
if(arr.length == 0 || arr[0].length == 0){
throw new IllegalArgumentException();
}
//build graph
Graph g = buildGraph(arr);
//DFS of graph
return depth(g);
}
private static Graph buildGraph(char[][] arr){
int xDim = arr.length;
int yDim = arr[0].length;
Graph g = new Graph(xDim, yDim);
for(int i = 0; i < xDim; i++){
for(int j = 0; j < yDim; j++){
makeConnections(g, arr, i, j);
}
}
}
private static void makeConnections(Graph g, int[][] arr, int x, int y){
int xMin = x > 0? x -1 : x;
int xMax = x < arr.length -1 ? x + 1 : x;
int yMin = y > 0? y -1 : y;
int yMax = y < arr[0].length -1 ? y + 1 : y;
int[] from = new int[]{x, y};
int[] to = new int[2];
int desiredCharInt = ((int)arr[x][i]) - ((int)'a') + 1;
for(int i = xMin; i <= xMax; i++){
for(int j = yMin; j <= yMax; j++){
if(i != x || j != y){
if( ((int)arr[i][j]) - ((int)'a') == desiredCharInt){
to[0] = i;
to[1] = j;
g.connect(from, to);
}
}
}
}
}
private static int depth(Graph g){
Worker worker = new Worker(g);
return worker.execute();
}
static class Worker{
Graph g;
int xDim;
int yDim;
int[][] depth;
Worker(Graph g){
this.g = g;
this.xDim = g.connections.length;
this.yDim = g.connections[0].length;
this.depth = new int[this.xDim][this.yDim];
}
int execute(){
int maxDepth = 0;
for(int i = 0; i < this.xDim; i++){
for(int j = 0; j < this.yDim; j++){
int depth = this.depthRecur(i, j);
if(depth > maxDepth){
maxDepth = depth;
}
}
}
return maxDepth;
}
int depthRecur(int x, int y){
//if the depth is already known, use that
if(this.depth[x][y] > 0){
return this.depth[x][y];
}
//otherwise, check it by traversing the graph
for(int[][] child : this.g.connections[x][y]){
int tempChildDepth = depthRecur(child[0], child[1]);
if(tempChildDepth > depth[x][y]){
this.depth[x][y]= tempChildDepth;
}
}
//add the local node
this.depth[x][y]++;
//set the cached value
return this.depth[x][y];
}
}
@jaks
Well, that depends on how you define n. If the matrix is sized n x n, then absolutely, it would be O (n^4). However, I just took the entire matrix to be of size n since the example was not square.
Hi, just wanted to confirm one thing...
You are converting each row of the matrix into a adjacency entry ?
So for e.g. the first row "a b e d", you use "a" as the starting vertex and then "b","e","d" are treated adjacent to "a" and so on ?
I think this on its own could be a nice theoretical CS question i.e. convert an Adj. Matrix into Adj. Lists
First, I search the matrix for the starting letter of the given alphabet. Then starting from that Position, I perform a Depth First Search and store the maxDepth.
I use a class Position to hold the coordinates of the current Position; a Position holds the coordinates i,j in the board and also knows his depth in the current Path.
The method:
List<Position> possibleMoves(int i, int j, char[][] board, int depth)
retrieves the list of possible moves from the current Position. From a Position you can move to another Position in the board if it is an existing adjacent Position in the board and the Char in that Position is the Char following the Char in the current Position in the Alphabet. In my solution I define the First Char in the Alphabet as the Next of the Last Char in the Alphabet, in this way we can get Paths longer than the size of the Alphabet.
The method:
boolean isNextInAlphabet(char c1, char c2)
check if the char c2 is next of the char c1 in the Alphabet.
You can use genBoard(int n, int m) and printBoard() to generate and print a new board. The Alphabet used in the example is just 'a','b','c' but you can add more characters if you want to test it, just take into account that the longer the alphabet the harder to get a Path in a random generated board from the method genBoard. Here is my code for this solution:
import java.util.*;
class Position {
int i;
int j;
int depth;
public Position(int i,int j, int depth) {
this.i=i;
this.j=j;
this.depth = depth;
}
public String toString() {
return "("+this.i+","+this.j+")";
}
}
public class MaxAlphabetPathInMatrix {
//final static char[] ALPHA = {'a','b','c','d','e','f','g','h','i','l','m','n','o','p','q','r','s','t','u','v','z'};
final static char[] ALPHA = {'a','b','c'};
public static int maxAlphabetPath(char[][] board) {
if(board==null || board.length==0) {
return 0;
}
int maxDepth = 0;
int currDepth = 0;
int[][] visited = new int[board.length][board[0].length];
Stack<Position> tovisit;
for(int i=0;i<board.length;i++) {
for(int j=0;j<board[i].length;j++) {
if(board[i][j]=='a' && visited[i][j]!=1) {
tovisit = new Stack<Position>();
Position start = new Position(i,j,1);
tovisit.push(start);
Position visiting;
currDepth = 0;
while(!tovisit.empty()) {
visiting=tovisit.pop();
System.out.println("Popping "+visiting);
currDepth = visiting.depth;
System.out.println("board["+visiting.i+"]["+visiting.j+"]="+board[visiting.i][visiting.j]+":"+visiting.depth);
if(currDepth>maxDepth) {
maxDepth = currDepth;
}
if(visited[visiting.i][visiting.j]!=1) {
visited[visiting.i][visiting.j] = 1;
for(Position p: possibleMoves(visiting.i,visiting.j,board,currDepth+1)) {
System.out.println("Pushing "+p);
tovisit.push(p);
}
}
}
}
}
}
return maxDepth;
}
public static List<Position> possibleMoves(int i, int j, char[][] board, int depth) {
List<Position> moves = new ArrayList<Position>();
int[] dx = {-1,0,1,-1,0,1,-1,0,1};
int[] dy = {-1,-1,-1,0,0,0,1,1,1};
for(int k=0;k<dx.length;k++) {
if(i+dy[k]>=0 && i+dy[k]<board.length && j+dx[k]>=0 && j+dx[k]<board[i+dy[k]].length) {
if(isNextInAlphabet(board[i][j],board[i+dy[k]][j+dx[k]])) {
Position nextPos = new Position(i+dy[k],j+dx[k],depth);
moves.add(nextPos);
}
}
}
return moves;
}
public static boolean isNextInAlphabet(char c1, char c2) {
boolean isNext = false;
if(ALPHA[ALPHA.length-1]==c1 && ALPHA[0]==c2) {
isNext = true;
}
for(int i=0;i<ALPHA.length-1;i++) {
if(ALPHA[i]==c1 && ALPHA[i+1]==c2) {
isNext=true;
break;
}
}
return isNext;
}
public static char[][] genBoard(int n, int m) {
if(n<=0 || m<=0) {
System.out.println("Error: wrong size for generating board");
return null;
}
char[][] board = new char[n][m];
Random r = new Random();
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
board[i][j] = ALPHA[r.nextInt(ALPHA.length)];
}
}
return board;
}
public static void printBoard(char[][] board) {
for(int i=0;i<board.length;i++) {
System.out.print("[");
for(int j=0;j<board[i].length-1;j++) {
System.out.print(board[i][j]+",");
}
System.out.print(board[i][board[i].length-1]);
System.out.println("]");
}
}
public static void main(String[] args) {
char[][] board = genBoard(3,4);
printBoard(board);
int maxPath = maxAlphabetPath(board);
System.out.println("Max Path: "+maxPath);
}
}
With the input you suggest my solution will retrieve a max path of length 1, since from the char 'a' you cannot reach the following char in the alphabet ('b')
Here is a piece of code which finds all the sequences for the given character. it should be easy to extend this to print the longest sequence.
#include <iostream>
using namespace std;
static const int width=4;
static const int height=4;
char getMax(char max, char ret)
{
return max>ret?max:ret;
}
char findlen(int i, int j, char c, char matrix[width][height])
{
//The following can be also be put in a for loop.
char max = c;
//top-left
if(i>0 && j>0 && matrix[i-1][j-1]==(c+1))
max = getMax(max, findlen(i-1, j-1, c+1, matrix));
//top
if(j>0 && matrix[i][j-1]==(c+1))
max = getMax(max, findlen(i, j-1, c+1, matrix));
//top-right
if(i<(width-1) && j>0 && matrix[i+1][j-1]==(c+1))
max = getMax(max, findlen(i+1, j-1, c+1, matrix));
//right
if(i<(width-1) && matrix[i+1][j]==(c+1))
max = getMax(max, findlen(i+1, j, c+1, matrix));
//bottom-right
if(i<(width-1) && j<(height-1) && matrix[i+1][j+1]==(c+1))
max = getMax(max, findlen(i+1, j+1, c+1, matrix));
//bottom
if(i<(height-1) && matrix[i][j+1]==(c+1))
max = getMax(max, findlen(i, j+1, c+1, matrix));
//bottom-left
if(i<(width-1) && j<(height-1) && matrix[i-1][j+1]==(c+1))
max = getMax(max, findlen(i-1, j+1, c+1, matrix));
//left
if(i>0 && matrix[i-1][j]==(c+1))
max = getMax(max, findlen(i-1, j, c+1, matrix));
return max;
}
enum {a='a',b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z};
int main()
{
char matrix[width][height]=
{
{a,b,c,d},
{l,m,n,e},
{k,p,o,f},
{j,i,h,g}
};
char tofind = a;//specify the required character here
for(int I=0;I<width;I++)
{
for(int J=0;J<height;J++)
{
if(matrix[I][J] == tofind)
cout<<(findlen(I, J, tofind, matrix) - tofind + 1)<<endl;
}
}
return 0;
}
Will print 16
def _get_longest_inefficient(root_str, m, row, col):
# base case
if row < 0 or col < 0 or row >= len(m) or col >= len(m[0]) or (row, col) in root_str: # can't look here
return 0
if root_str and ord(m[root_str[-1][0]][root_str[-1][1]]) + 1 != ord(m[row][col]): # not ascending
return 0
# recursive case
root_str.append((row, col))
max_length = 1
for i in range(row - 1, row + 2):
for j in range(col - 1, col + 2):
max_length = max(max_length, 1 + _get_longest_inefficient(root_str, m, i, j))
return max_length
def get_longest_consecutive_alpha_path_inefficient(m):
longest = 0
# for all beginning points, explore and try to find longest
for i in range(len(m)):
for j in range(len(m[0])):
cur_len = _get_longest_inefficient([], m, i, j)
longest = max(cur_len, longest)
return longest
m = [['a', 'z', 'i', 'h', 'f'],
['b', 'j', 'd', 'e', 'g'],
['a', 'c', 'f', 'e', 'f'],
['a', 'z', 'd', 'e', 'f'],
]
print get_longest_consecutive_alpha_path_inefficient(m)
# more efficient way
solution_matrix = []
def _get_longest_efficient(root_str, m, row, col):
# base case
if row < 0 or col < 0 or row >= len(m) or col >= len(m[0]) or (row, col) in root_str: # can't look here
return 0
if root_str and ord(m[root_str[-1][0]][root_str[-1][1]]) + 1 != ord(m[row][col]): # not ascending
return 0
if solution_matrix[row][col] != 1:
return solution_matrix[row][col]
# recursive case
root_str.append((row, col))
max_length = 1
for i in range(row - 1, row + 2):
for j in range(col - 1, col + 2):
max_length = max(max_length, 1 + _get_longest_efficient(root_str, m, i, j))
solution_matrix[row][col] = max_length
return max_length
def get_longest_consecutive_alpha_path_more_efficient(m):
longest = 0
# initialize solution matrix
for row in m:
solution_matrix.append([1] * len(row))
# for all beginning points, explore and try to find longest
for i in range(len(m)):
for j in range(len(m[0])):
cur_len = _get_longest_efficient([], m, i, j)
longest = max(cur_len, longest)
return longest
# even more efficient way
def get_longest_consecutive_alpha_path_using_graph(m):
directed_graph_of_letters_indices = {}
# first create a directed graph of letter indices
for i in range(len(m)):
for j in range(len(m[0])):
directed_graph_of_letters_indices[(i, j)] = []
# loop through all 9 cases
for row in range(i-1, i+2):
for col in range(j-1, j+2):
if row >= 0 and col >= 0 and row < len(m) and col < len(m[0]):
if ord(m[i][j]) - 1 == ord(m[row][col]): # only put next consecutive neighbor in
directed_graph_of_letters_indices[(i, j)].append((row, col))
max_depth = 0
solutions_dict = {}
for key in directed_graph_of_letters_indices:
# do depth first search and put any solutions in solutions dict
if key not in solutions_dict:
max_depth = max(max_depth, 1 + get_greatest_depth(directed_graph_of_letters_indices, key, solutions_dict))
return max_depth
def get_greatest_depth(g, source, solutions_dict):
if source[0] == 0:
print source
if source in solutions_dict:
return solutions_dict[source]
neighbors = g[source]
max_depth = 0
for neighbor in neighbors:
max_depth = max(max_depth, 1 + get_greatest_depth(g, neighbor, solutions_dict))
solutions_dict[source] = max_depth
return max_depth
m = [['a', 'z', 'i', 'h', 'f'],
['b', 'j', 'd', 'e', 'g'],
['a', 'c', 'f', 'e', 'f'],
['a', 'z', 'd', 'e', 'f'],
]
print get_longest_consecutive_alpha_path_using_graph(m)
DP Solution, in python. Runs in O(n^2) - ie linear in number of elements in the array.
#!/usr/bin/env python
class CharMatrix(object):
def __init__(self, matrix):
if not isinstance(matrix, list): raise Exception()
rowLength = None
for row in matrix:
if not isinstance(row, list): raise Exception()
if rowLength:
if len(row) != rowLength: raise Exception()
else:
rowLength = len(row)
self.matrix = matrix
def longestPath(self):
retDict = dict() # Holds, for key (i, j), length of longest path beginning at (i, j) and best following point (nI, nJ)
w, h = self._matrixSize()
for rowIndex in range(h):
for columnIndex in range(w):
self._longestPath((rowIndex, columnIndex), retDict)
# Find max length...
maxLength = 0
startPos = None
for key, value in retDict.iteritems():
maxLenghtCandidate, nextPos = value
if maxLenghtCandidate > maxLength:
maxLength = maxLenghtCandidate
startPos = key
# Backtrack...
string = ''
curPos = startPos
while curPos:
i, j = curPos
string += self.matrix[i][j]
nextMaxLength, nextPos = retDict[curPos]
curPos = nextPos
return maxLength, startPos, string
def _longestPath(self, pos, retDict):
if pos in retDict:
return retDict[pos]
i, j = pos
curChar = self.matrix[i][j]
nextChar = self._nextChar(curChar)
maxLength = 1
nextPos = None
for newPos in self._possibleMoves(pos):
nI, nJ = newPos
newChar = self.matrix[nI][nJ]
validChar = self._nextChar(curChar)
if newChar == validChar:
maxLengthCandidate, nextCandidate = self._longestPath(newPos, retDict)
maxLengthCandidate += 1
if maxLengthCandidate > maxLength:
maxLength = maxLengthCandidate
nextPos = newPos
ret = (maxLength, nextPos)
retDict[pos] = ret
return ret
def _matrixSize(self):
width = len(self.matrix[0])
height = len(self.matrix)
return (width, height)
def _possibleMoves(self, pos):
i, j = pos
w, h = self._matrixSize()
ret = list()
for dI in range(-1, 2):
for dJ in range(-1, 2):
if dI == 0 and dJ == 0: continue
nI = i + dI
nJ = j + dJ
if nI < 0 or nI >= h: continue
if nJ < 0 or nJ >= w: continue
ret.append((nI, nJ))
return ret
def _nextChar(self, char):
if char == 'z':
return None
else:
return chr(ord(char) + 1)
def main():
print 'Woohoo! :)'
m = [['a', 'b', 'e', 'd'],
['b', 'c', 'f', 'e'],
['a', 'b', 'd', 'd']]
cm = CharMatrix(m)
print cm.longestPath()
if __name__ == '__main__':
main()
DP Solution, in python. Runs in O(n^2) - ie linear in number of elements in the array.
#!/usr/bin/env python
class CharMatrix(object):
def __init__(self, matrix):
if not isinstance(matrix, list): raise Exception()
rowLength = None
for row in matrix:
if not isinstance(row, list): raise Exception()
if rowLength:
if len(row) != rowLength: raise Exception()
else:
rowLength = len(row)
self.matrix = matrix
def longestPath(self):
retDict = dict() # Holds, for key (i, j), length of longest path beginning at (i, j) and best following point (nI, nJ)
w, h = self._matrixSize()
for rowIndex in range(h):
for columnIndex in range(w):
self._longestPath((rowIndex, columnIndex), retDict)
# Find max length...
maxLength = 0
startPos = None
for key, value in retDict.iteritems():
maxLenghtCandidate, nextPos = value
if maxLenghtCandidate > maxLength:
maxLength = maxLenghtCandidate
startPos = key
# Backtrack...
string = ''
curPos = startPos
while curPos:
i, j = curPos
string += self.matrix[i][j]
nextMaxLength, nextPos = retDict[curPos]
curPos = nextPos
return maxLength, startPos, string
def _longestPath(self, pos, retDict):
if pos in retDict:
return retDict[pos]
i, j = pos
curChar = self.matrix[i][j]
nextChar = self._nextChar(curChar)
maxLength = 1
nextPos = None
for newPos in self._possibleMoves(pos):
nI, nJ = newPos
newChar = self.matrix[nI][nJ]
validChar = self._nextChar(curChar)
if newChar == validChar:
maxLengthCandidate, nextCandidate = self._longestPath(newPos, retDict)
maxLengthCandidate += 1
if maxLengthCandidate > maxLength:
maxLength = maxLengthCandidate
nextPos = newPos
ret = (maxLength, nextPos)
retDict[pos] = ret
return ret
def _matrixSize(self):
width = len(self.matrix[0])
height = len(self.matrix)
return (width, height)
def _possibleMoves(self, pos):
i, j = pos
w, h = self._matrixSize()
ret = list()
for dI in range(-1, 2):
for dJ in range(-1, 2):
if dI == 0 and dJ == 0: continue
nI = i + dI
nJ = j + dJ
if nI < 0 or nI >= h: continue
if nJ < 0 or nJ >= w: continue
ret.append((nI, nJ))
return ret
def _nextChar(self, char):
if char == 'z':
return None
else:
return chr(ord(char) + 1)
def main():
print 'Woohoo! :)'
m = [['a', 'b', 'e', 'd'],
['b', 'c', 'f', 'e'],
['a', 'b', 'd', 'd']]
cm = CharMatrix(m)
print cm.longestPath()
if __name__ == '__main__':
main()
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>
#include <cassert>
#define INF INT_MAX
#define NIL -1
#define PR(A) cout<<endl<<#A<<" = "<<A;
#define INF INT_MAX
using namespace std;
typedef vector<vector<int> > matrix;
typedef vector<int> arr;
typedef unsigned int ui;
vector<vector<int> > & make_matrix(int m,int n,int r=0){
vector<vector<int> >&q=*(new vector<vector<int> >);
q.resize(m);
for(vector<vector<int> >::iterator i=q.begin();i!=q.end();i++){
(*i).resize(n);
fill(i->begin(),i->end(),r);
}//edn fr
return q;
}//end vector
void printarr(arr &a,int low=0,int high=INT_MAX){
if(high==INT_MAX){
high=a.size()-1;
}//END IF
cout<<endl;
for(int i=low;i<=high;i++){
cout<<a[i]<<' ';
}//end for
}//end [rint
void printmatrix(matrix &a){
for(vector<vector<int> >::iterator i=a.begin();i!=a.end();i++){
cout<<endl;
for(vector<int> ::iterator j=i->begin();j!=i->end();j++){
cout<<*j<<" ";
}//end for
}//end for
}//end [rint
bool isvalid(vector<vector<char>>&q,int i,int j){
if(i>=0 && j>=0){
if(i<q.size() && j<q[0].size())
return true;
}
return false;
}//end isvalid
void dfs(vector<vector<char>>&q,vector<vector<int>>&dp,vector<vector<bool>>&visited,int i,int j,vector<pair<int,int>>&moves){
int count=0;
if(dp[i][j]!=-1 || visited[i][j])
return ;
visited[i][j]=true;
for(int k=0;k<moves.size();k++){
int x=i+moves[k].first;
int y=j+moves[k].second;
if(!isvalid(q,x,y))
continue;
if(q[x][y]==1+q[i][j]){
// if(dp[x][y]==-1){
if(!visited[x][y])
dfs(q,dp,visited,x,y,moves);
//}//end if
count=max(count,dp[x][y]);
}//en
}//end for
dp[i][j]=1+count;
}//end dfs
int main(){
vector<pair<int,int>>moves{{0,-1},{0,1},{-1,0},{1,0},{-1,-1},{1,1},{1,-1},{-1,1}};
vector<vector<char>>q{
{'a','b','e','d'},{'b','c','f','e'},{'a','b','d','d'}
};
vector<vector<bool>>visited(q.size());
for(auto &i:visited){
i.resize(q[0].size());
fill(i.begin(),i.end(),false);
}//end for
matrix dp=make_matrix(q.size(),q[0].size(),-1);
for(int i=0;i<q.size();i++){
for(int j=0;j<q[0].size();j++){
if(q[i][j]=='d'){
dfs(q,dp,visited,i,j,moves);
cout<<endl<<i<<" "<<j<<" = "<<dp[i][j];
}//end if
}//end for
}//end fpr
return 0;
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static void findLongestPath(char a[][],char start)
{
int value = (int)start;
boolean isStartIndexFound = false;
int path = 1;
int x,y;
//System.out.println(" v "+value);
for(int i=0;i<3;i++)
{
for(int j=0;j<4;j++)
{
if((int)a[i][j] == value && !isStartIndexFound)
{
isStartIndexFound = true;
}
if(isStartIndexFound)
{
//Step1
if((i+1)<3)
{
if((int)a[i+1][j] == value+1)
{
path++;
value = value+1;
i = i+1;
//System.out.println("(i+1) "+path + " v "+value+ " i " +i +" j "+j);
}
}
//Step2
if((i-1)>=0)
{
if((int)a[i-1][j] == value+1)
{
path++;
value = value+1;
i = i-1;
//System.out.println("(i-1) "+path + "v "+value+ " i " +i +" j "+j);
}
}
//Step3
if((i+1)<3 && (j+1)<4)
{
if((int)a[i+1][j+1] == value+1)
{
path++;
value = value+1;
i = i+1;
j= j+1;
//System.out.println("i+1 & j+1 "+path + "v "+value+ " i " +i +" j "+j);
}
}
//Step4
if((i-1)>=0 && (j-1)>=0)
{
if((int)a[i-1][j-1] == value+1)
{
path++;
value = value +1;
i = i-1;
j=j-1;
//System.out.println("(i-1),j-1 "+path + "v "+value+ " i " +i +" j "+j);
}
}
//Step5
if((j+1)<4)
{
if((int)a[i][j+1] == value+1)
{
path++;
value = value+1;
j = j+1;
//System.out.println("i,j+1 "+path + "v "+value+ " i " +i +" j "+j);
}
}
//Step6
if((j-1)>=0)
{
if((int)a[i][j-1] == value+1)
{
path++;
value = value+1;
j = j-1;
// System.out.println("j-1 "+path + "v "+value+ " i " +i +" j "+j);
}
}
//Step7
if((i-1)>=0 && (j+1)<4)
{
if((int)a[i-1][j+1] == value+1)
{
path++;
value = value+1;
i = i-1;
j = j+1;
// System.out.println("i-1,j+1"+path + "v "+value+ " i " +i +" j "+j);
}
}
//Step8
if((i+1)<3 && (j-1)>=0)
{
if((int)a[i+1][j-1] == value+1)
{
path++;
value = value + 1;
i = i+1;
j = j-1;
//System.out.println("i+1,j-1 "+path + "v "+value+ " i " +i +" j "+j);
}
}
}
}
}
System.out.println("max len : "+path);
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
char a[][]= new char[][]{ {'a' ,'b' ,'e' ,'d'},
{'b' ,'c' ,'f', 'e'}, //f,e //g,h
{'a', 'b', 'd', 'd'}
};
findLongestPath(a,'c'); //'a'
}
}
Isn't this a bit related to the Island Problem? I think two things simplify this algorithm:
- Two path joining at a particular letter will have the same length
- Nodes cannot be 'reused'
This means, if I do an DSF starting in each 'a' and mark all visited letters, then i can easiliy find the longest path without visiting nodes twice.
Complexity: O(n)
One obvious solution is using dynamic programming..
- naren December 18, 2014Question: Why stop at d when you can move in 8 directions? a->b->c->d->e->f Is this not the path for the question.