Amazon Interview Question for SDETs


Country: India
Interview Type: In-Person




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

One obvious solution is using dynamic programming..

Question: 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.

- naren December 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@naren .. sorry for that . Yes you are right .

- Rahul Sharma December 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.....

- gen-y-s December 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- mdu December 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not sure about DP either since we can go any directions. What about DFS

- aa January 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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];
	}
}

- zortlord December 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution, but it runs in O(n^4), not in O(n^2).

- jaks December 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- zortlord December 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- abettikk December 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}
}

- gigi84 December 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What happens with the following input?

a, c, b
c, c, d

- zortlord December 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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')

- gigi84 December 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It depends on the the node you give. If the start node is given as 'c', then the length is 2.. c->d

- sumanthmadivala January 13, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ramprasad85 December 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- brad December 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# 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

- brad December 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# 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)

- brad December 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()

- Manuel February 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()

- Manuel February 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String args[])

- test June 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reused

- Anonymous June 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

huhuhuhuhuhu

- Anonymous June 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

popopopopopopopoopopopopp

- Anonymous June 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Klaus July 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/* 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'
}
}

- Himanshu Jain December 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- Flo December 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

opppoooooooooooppppppppppppoppppppppppoooooooooppppppppppppppppiiiiiiiiiipppppppppyyyyyyyyyyyypppppppppppiiiiiiiiiiiooooooooooooyyyyyyyyyyyyyytttttttttt

- Anonymous June 24, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More