## Google Interview Question for Software Engineer / Developers

• 6

Country: United States
Interview Type: Phone Interview

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

Here's a very simple way to do it. Make an array of booleans (or bits) of size N^2, where arr[i-1] indicates whether i+1 is adjacent to i. Then, iterate over the matrix, checking for each cell the four neighbors and populating the relevant entry in the boolean array. Then just look for the longest run of "true" values in the boolean array, which can be done with one pass.

This approach is linear in time and space with the size of the input. The space needed is only 1 bit per element, so the constant factor is really low for space. The constant factor for time should be reasonably good as well because we only do a few array accesses and comparisons for each element in the input.

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

I don' t think this takes into encounter whether it forms an increasing sequence It just ensures hat the values taken are consequent. Ex:
5 6 7 4
1 7 6 2
will probably give 6 7 6 7 as ans, if I am interpreting your algorithm correctly. Kindly correct me if I am wrong.

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

First, the question tells us to assume that we have all numbers from 1 to n*n EXACTLY once, so your situation cannot happen.

Also, if you're not guaranteed distinct integers, the algorithm does not make any sense. What do you store in arr[5] if one of the 6s is adjacent to 7 but the other one isn't?

I hope that clears up some confusion.

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

Yes, the algorithm is only valid if all the integers are distinct. We can still solve in linear time and space with respect to the size of the input if they're not distinct, but you would need a different algorithm. You could do it using dynamic programming. Let F(x,y) be the longest sequence starting from coordinates (x, y). Then F(x, y) = 1 if there are no neighbors with value arr[x][y]+1, or 1 + max over all such neighbors if any exist.

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

The problem statement says " NxN matrix which contains all distinct 1 to n^2 numbers" and this is an elegant solution. It's probably the answer the interviewer expecting too. +1.

@Eugene says it's linear time, but it's actually O(N^2) time and space, because input size is N^2.

Comment hidden because of low score. Click to expand.
2

Note that I said the algorithm is "linear in time and space with the size of the input", not linear in terms of N. The input size is N^2, so the time and space complexities are O(N^2). I chose to talk about the performance relative to the size of the input because that makes it clear that this algorithm is asymptotically optimal, since any algorithm must look at all or most of the input.

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

can you explain how will you modify the entry in the boolean array when you traverse the matrix? I might be missing something. The solution is a bit unclear to me.

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

got it. never mind.

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

time O(n^2) space O(n^2) solution.
we will need a 2D array visited[n][n] and two global vars->start and max=0.
Now we will traverse the matrix row by row.
for each 'not visited' element k start a recursive dfs such that next element is k+1.
Mark all traversed elements as visited so that you do not start a traversal from them again
the dfs() will return you the depth value till which it could go.
e.g. for 6 it will return 4 (6-7-8-9). for 7 it will return 3 (7-8-9).
if this value is greater than max, then update max and start value.

At last print max no. of consecutive characters from start value.

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

``````#include <stdio.h>
#define X 4
#define Y 4

int m[X][Y] = {
1, 2, 4, 0,
5, 12, 11, 100,
6, 7, 10, 111,
1111, 8, 9, 122
};
int dfs(int i, int j, int visit[][Y])
{
if (i-1 > 0 && j > 0 && ((m[i-1][j]) == (m[i][j]+1)) && !visit[i-1][j]) {
visit[i-1][j] = 1;
return 1 + dfs(i-1, j, visit);
}
if (i+1 < X && j < Y && ((m[i+1][j]) == (m[i][j]+1)) && !visit[i+1][j]) {
visit[i+1][j] = 1;
return 1 + dfs(i+1, j, visit);
}
if (i < X && j-1 > 0 && ((m[i][j-1]) == (m[i][j]+1)) && !visit[i][j-1]) {
visit[i][j-1] = 1;
return 1 + dfs(i, j-1, visit);
}
if (i > 0 && j+1 < Y && ((m[i][j+1]) == (m[i][j]+1)) && !visit[i][j+1]) {
visit[i][j+1] = 1;
return 1 + dfs(i, j+1, visit);
}
return 0;
}

int main()
{
int visited[X][Y] = {0};
int old_max = 0;
int max = 0, i, j, k, l;

for (i=0;i<X;i++)
for (j=0;j<Y;j++) {
max = dfs(i, j, visited);
if (max >= old_max)
old_max = max;
}
printf("%d\n", old_max);
return 0;
}``````

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

Your sample data ignores the constraints of the question: that the array is rectangular (that is, X == Y, so why not use only one constant?) and that the array is populated with the numbers 1...N^2. With X == Y == 4, you shouldn't have any number larger than 16 or less than 1.

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

1. In an array, store the position of every integer from 1 to n^2 by simply reading every entry of the matrix.

2. Iterate through the array. At every step, check if the next position is adjacent to the current position. If so, your current sequence's size increases by 1. If not, your current sequence is over. Every time a sequence terminates, if its length is greater than the longest sequence seen so far, remember its length and where it ends.

3. Knowing the size of the longest sequence and on which number it ends, you can easily print the sequence by printing the numbers from "end - length + 1" to "end".

Running the algorithm on the given example looks like this:

``````input
1 5 9
2 3 8
4 6 7``````

1. Produce the following array:
[(0,0), (0,1), (1,1), (0,2), (1,0), (1,2), (2,2), (2,1), (2,0)]

2.
Set length counter to 1.
(0,0) is adjacent to (0,1): +1;
(0,1) is adjacent to (1,1): +1;
(1,1) is not adjacent to (0,2): sequence length is 3, our current best, so lets remember the length and that it ended on the 3rd entry. Reset length counter to 1.
(0,2) is not adjacent to (1, 0): sequence length is 1, not our best. Simply reset counter to 1.
(1,0) is not adjacent to (1, 2): sequence length is 1, not our best. Simply reset counter to 1.
(1,2) is adjacent to (2,2): +1;
(2,2) is adjacent to (2,1): +1;
(2,1) is adjacent to (2,0): +1;
(2,0) is the end of the array, so the sequence ends: sequence length is 4, our current best, so lets remember the length and that it ended on the 9th entry.

3.
Our longest sequence has length 4 and ends at 9. So it starts at 9 - 4 + 1 = 6. So we output 6 7 8 9.

This algorithm has O(n^2) time and space complexity. O(n^2) is optimal for time complexity because you have to at least look at all of the entries, but O(n^2) is not optimal for space complexity. I can't seem to reduce the space complexity without increasing the time complexity however...

In Java:

``````void printLongestSnake(int[][] matrix) {
int n = matrix.length;
int nSquared = n * n;
Coordinate[] positions = new Coordinate[nSquared];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
positions[matrix[i][j] - 1] = new Coordinate(i, j);
}
}
int maxLength = 1;
int maxEnd = 1;
int currentLength = 1;
for (int i = 1; i < nSquared; ++i) {
++currentLength;
} else {
if (currentLength > maxLength) {
maxLength = currentLength;
maxEnd = i;
}
currentLength = 1;
}
}
if (currentLength > maxLength) {
maxLength = currentLength;
maxEnd = nSquared;
}
for (int i = maxEnd - maxLength + 1; i < maxEnd; ++i) {
System.out.print(i + " ");
}
System.out.println(maxEnd);
}``````

where Coordinate is the following simple class (you could just use an array of size 2 instead of making a class if you want to be more efficient, but then, you shouldn't be using Java lol)

``````class Coordinate {
private int x;
private int y;

public Coodinate(int x, int y) {
this.x = x;
this.y = y;
}

if (x == c.x && (y == c.y - 1 || y == c.y + 1) {
return true;
}
if (y == c.y && (x == c.x - 1 || x == c.x + 1) {
return true;
}
return false;
}
}``````

I assumed that you want to print the *longest* sequence of of consecutive numbers that are adjacent in the array. If not could you please clarify your question please, thanks.

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

``````public static class LongestSequence
{
public static void PrintLongestSeq(int[][] M)
{
if (M == null || M.Length == 0 || M[0].Length == 0)
return;
var maxSeq = new List<int>();
for (var i = 0; i < M.Length; i++)
for (var j = 0; j < M[0].Length; j++)
{
var currSeq = GetLongestSeq(M, i, j);
if (maxSeq.Count < currSeq.Count)
maxSeq = currSeq;
}
maxSeq.Print();
}

private static void Print(this List<int> l)
{
foreach (var e in l)
Console.Write(e);
}

private static List<int> GetLongestSeq(int[][] M, int i, int j)
{
var res = new List<int>();
if (i >= M.Length || j >= M.Length) return res;
bool done = false;
while (!done)
{
done = true;
if (i < M.Length - 1 && M[i][j] == M[i + 1][j] - 1)
{
i += 1;
done = false;
}
if (i > 0 && M[i][j] == M[i - 1][j] - 1)
{
i -= 1;
done = false;
}
if (j < M.Length - 1 && M[i][j] == M[i][j + 1] - 1)
{
j += 1;
done = false;
}
if (j > 0 && M[i][j] == M[i][j - 1] - 1)
{
j -= 1;
done = false;
}
}
return res;
}

public static void Test()
{
var m = new int[3][];
m[0] = new[] { 1, 5, 9 };
m[1] = new[] { 2, 3, 8 };
m[2] = new[] { 4, 6, 7 };
PrintLongestSeq(m);
}
}``````

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

Could you please explain how is it an increasing sequence from the matrix? not when i read thru row or cols, so how should i read the matrix? if through the edge of the matrix, then 1246789 seems to be also the sequence

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

Please explain the increasing sequence here as there are others that might be possible of the same sequence.

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

I updated the question guys. its the adjacent sequential numbers like 6 7 8 but not 1 2 4

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

We can implement using below graph by getting the adjacent value then check for increasing order needs extra effort.

1 2 3 4 5 6 7 8 9

1 0 1 0 0 1 0 0 0 0

2 1 0 1 1 1 0 0 0 0

3 0 1 0 0 1 1 0 1 0

4 0 1 0 0 0 1 0 0 0

5 1 0 1 0 0 0 0 0 1

6 0 0 1 1 0 0 1 0 0

7 0 0 0 0 0 1 0 1 0

8 0 0 1 0 0 0 1 0 1

9 0 0 0 0 1 0 0 1 0

the sequence can be pushed into the stack for the result.

Suggest if the above solution is wrong.

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

might not be super efficient; but would work

``````package Google;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class mSort {

public static ArrayList<Integer> mergeSort(ArrayList<Integer> a) {
if (a.size() <= 1) {
return a;
}
ArrayList<Integer> firstHalf = new ArrayList<Integer>();
ArrayList<Integer> secondHalf = new ArrayList<Integer>();
for (int i = 0; i < a.size() / 2; i++) {
}
for (int i = a.size() / 2; i < a.size(); i++) {
}
return merge(mergeSort(firstHalf), mergeSort(secondHalf));
}

public static ArrayList<Integer> merge(ArrayList<Integer> l1, ArrayList<Integer> l2) {
if (l1.size() == 0) {
return l2;
}
if (l2.size() == 0) {
return l1;
}
ArrayList<Integer> result = new ArrayList<Integer>();
int nextElement;
if (l1.get(0) > l2.get(0)) {
nextElement = l2.get(0);
l2.remove(0);
} else {
nextElement = l1.get(0);
l1.remove(0);
}
return result;
}

public static HashSet<Integer> getLargestSequence(Integer [] A) {
HashSet<Integer> result = new HashSet<Integer>();
if (A == null) {
return result;
}
int len = A.length;
Map<Integer, HashSet<Integer>> dataMap = new HashMap<Integer, HashSet<Integer>>();

for (int i=0; i<len; i++) {
int less = A[i] - 1;
int more = A[i] + 1;
HashSet<Integer> list = new HashSet<Integer>();
boolean leftUpdated = false;
boolean rightUpdated = false;
if (dataMap.containsKey(less)) {
list = dataMap.get(less);
dataMap.put(less, list);

HashSet<Integer > keylist = dataMap.get(A[i]);
if (keylist != null) {
} else {
keylist = new HashSet<Integer>();
}
dataMap.put(A[i], keylist);

leftUpdated = true;
}
if (dataMap.containsKey(more)) {
list = dataMap.get(more);
dataMap.put(more, list);

HashSet<Integer > keylist = dataMap.get(A[i]);
if (keylist != null) {
} else {
keylist = new HashSet<Integer>();
}
dataMap.put(A[i], keylist);

rightUpdated = true;
}
if (!leftUpdated && !rightUpdated) {
dataMap.put(A[i], list);
}
}
Iterator<Entry<Integer, HashSet<Integer>>> it = dataMap.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, HashSet<Integer>> pair = (Map.Entry<Integer, HashSet<Integer>>)it.next();
if (pair.getValue().size() > result.size()) {
result = pair.getValue();
}
}

return result;

}

public static void main(String[] args) {

int [][] M ={ {1,2,3,4},{12,6,10,22},
{11,9,7,8},{20,29,28,15}};
ArrayList<Integer> list = new ArrayList<Integer>();
//First sort the MxM matrix; complexity O(nlogn)
for(int r=0;r<4;r++){
for(int c=0;c<4;c++){
}
}
list = mergeSort(list);
Integer[] list1 = list.toArray(new Integer[0]);
// from the sorted list find the largest sequence
HashSet<Integer> sequenceList = getLargestSequence(list1);
Iterator<Integer> iter = sequenceList.iterator();
System.out.println("Subset which forms the longest consecutive sequence: ");
while (iter.hasNext()) {
System.out.print(iter.next() + " ");
}
System.out.println();

}

}``````

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

The question says the array is square and NxN in size; and that it is populated with numbers 1...n^2. Why does your 4x4 array have numbers like 29 and 28 in it?

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

Right or wrong, remember that this is an interview question. Code clarity, time to write, avoiding unnecessary structures and dependencies are measured as well. I believe the expectation for such question is that one can write the full code within 20-25 minutes...

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

``````#include<iostream>
#include<vector>
using namespace std;

int X[4] = {0, -1, 0, 1};
int Y[4] = {-1, 0, 1, 0};
int n;
vector<int> curr_seq, max_seq;
void explore(int a[][3], int i, int j, int x){
if(i<0 || i>n-1 || j<0 || j>n-1)
return;
if(a[i][j] - x != 1 && a[i][j]-x!=a[i][j])
return;
curr_seq.push_back(a[i][j]);
for(int t=0;t<4;t++){
explore(a, i+X[t], j+Y[t], a[i][j]);
}
}

int MaxSequence(int a[][3]){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
explore(a, i, j, 0);
if(curr_seq.size() > max_seq.size()){
max_seq.clear();
for(int i=0;i<curr_seq.size();i++)
max_seq.push_back(curr_seq[i]);
}
curr_seq.clear();
}
}
for(int i=0;i<max_seq.size();i++)
cout<<max_seq[i]<<" ";
}

int main(){
int a[3][3]= {{2, 3, 9},
{1, 4, 8},
{6, 5, 7}};
n=3;
MaxSequence(a);
}``````

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

public static void search(int cur, ArrayList<Node> mat,String result, ArrayList<String> results){
int left = cur%3 -1;
int right = cur%3 +1;
int up = cur/3 -1;
int down = cur/3 +1;
mat.get(cur).visit = true;
result += mat.get(cur).num+"";
boolean haha = false;
if(left >=0 && left < 3){
if(mat.get(cur-1).num-mat.get(cur).num == 1 && !mat.get(cur-1).visit){
search(cur-1, mat,result, results);
haha = true;
}
}
if(right >=0 && right < 3){
if(mat.get(cur+1).num-mat.get(cur).num == 1 && !mat.get(cur+1).visit){
search(cur+1, mat,result, results);
haha = true;
}
}
if(up >=0 && up < 3){
if(mat.get(cur-3).num-mat.get(cur).num == 1 && !mat.get(cur-3).visit){
search(cur-3, mat,result, results);
haha = true;
}
}
if(down >=0 && down < 3){
if(mat.get(cur+3).num-mat.get(cur).num == 1 && !mat.get(cur+3).visit){
search(cur+3, mat,result, results);
haha=true;
}
}

if(!haha){
}

}

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

``````public static void search(int cur, ArrayList<Node> mat,String result, ArrayList<String> results){
int left = cur%3 -1;
int right = cur%3 +1;
int up = cur/3 -1;
int down = cur/3 +1;
mat.get(cur).visit = true;
result += mat.get(cur).num+"";
boolean haha = false;
if(left >=0 && left < 3){
if(mat.get(cur-1).num-mat.get(cur).num == 1 && !mat.get(cur-1).visit){
search(cur-1, mat,result, results);
haha = true;
}
}
if(right >=0 && right < 3){
if(mat.get(cur+1).num-mat.get(cur).num == 1 && !mat.get(cur+1).visit){
search(cur+1, mat,result, results);
haha = true;
}
}
if(up >=0 && up < 3){
if(mat.get(cur-3).num-mat.get(cur).num == 1 && !mat.get(cur-3).visit){
search(cur-3, mat,result, results);
haha = true;
}
}
if(down >=0 && down < 3){
if(mat.get(cur+3).num-mat.get(cur).num == 1 && !mat.get(cur+3).visit){
search(cur+3, mat,result, results);
haha=true;
}
}

if(!haha){
}

}``````

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

This is O(n)

``````public class LaregSeq{
int arr[][] = {{1,5,9},{2,3,8},{4,6,7}};
int st, len;
boolean visited[][];
public static void main(String args[]){
st = 0;
len = 0;
visited = new boolean[arr.length][arr.length];
for(r =0;r<n;r++)
for(c=0;c<n;c++)
if(!visited[r][c])
printLarge(0,0,arr[r][c]-1,arr[r][c]);
for(int i =st;i<st+len;i++)
System.out.println(i);
}

public void printLarge(int r, int c,int prev,int st){
if(r < 0 || r > =arr.length || c < 0 || c >= arr.length)
return;
if(arr[r][c] !=prev+1){
if( prev-st+1 > len){
len = prev -st+1;
st = st;
}
return;
}
visited[r][c] = true;
printLarge(r+1,c,arr[r][c],st);
printLarge(r,c+1,arr[r][c],st);
printLarge(r-1,c,arr[r][c],st);
printLarge(r,c-1,arr[r][c],st);
}
}``````

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

``````#include "stdio.h"

void longest_seq(int n, int data[][3])
{
int **flag;
flag = new int*[n];
for (int i=0; i<n; i++) {
flag[i] = new int[n];
}

int offset[][2] = {{0,0}, {0,1}, {1,0}, {0,-1}, {-1,0}};

// init
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (j+1<n && data[i][j]==data[i][j+1]-1) {
flag[i][j] = 1;
}
else if (i+1<n && data[i][j]==data[i+1][j]-1) {
flag[i][j] = 2;
}
else if (j-1>=0 && data[i][j]==data[i][j-1]-1) {
flag[i][j] = 3;
}
else if (i-1>=0 && data[i][j]==data[i-1][j]-1) {
flag[i][j] = 4;
}
else
flag[i][j] = 0;
}
}

// do the computation
int best_i=0, best_j=0, max_len=1;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (flag[i][j]==0) {
continue;
}

int cur_len=1;
int f = flag[i][j];
int n_i = i;
int n_j = j;
while(f>0) {
n_i += offset[f][0];
n_j += offset[f][1];

f = flag[n_i][n_j];
cur_len++;
}

if (cur_len > max_len) {
best_i = i;
best_j = j;
max_len = cur_len;
}
}
}

// print the seq..
int f = flag[best_i][best_j];
printf("%d", data[best_i][best_j]);
int n_i = best_i;
int n_j = best_j;

while (f>0) {
n_i += offset[f][0];
n_j += offset[f][1];

f = flag[n_i][n_j];
printf(" %d", data[n_i][n_j]);
}
printf("\n");

// release the space
for (int i=0; i<n; i++) {
delete[] flag[i];
}
delete[] flag;
}

// ./ex1
int main()
{
const int n = 3;
int data[][n] = {{1,5,9}, {2,3,8}, {4,6,7}};
longest_seq(n, data);
return 0;
}``````

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

Anyone else thinks that the Union-Find data structure would be perfect for this problem? O(2n) space requirements, O(log n) time to "connect" the numbers, constant time to check if 2 numbers are connected. O(n) time to find the largest set.

Th only problem with this and the above solutions is that their next question will probably be something along the lines of: "Well, what if the matrix is so big that it doesn't fit into memory?" :)

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

Union-find and tree traverse have similar space and time requirements.

Tree traverse by DFS may need recursive call.

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

Fairly brute force, O(n) scan with recursion on adjacent cells that are one value higher. Then sort of all possible answers to find longest (with largest sum, if more than one of same length):

python n_by_n_sequence.py matrix.in
[6, 7, 8, 9]

``````import sys

def max_sequence(vals, ndx, size):
# find the maximum sequential sequence starting from ndx
# vals is size * size list of unique numbers
# first check next right or left ndx +/- 1
# then up or down ndx +/- size
# and recurse, accounting for borders
is_left = ndx % size == 0
is_right = ndx % size == size-1
is_top = ndx / size == 0
is_bottom = ndx / size == size-1
seq = [vals[ndx]]
if not is_right:
if vals[ndx+1] == 1 + vals[ndx]:
return seq + max_sequence(vals, ndx+1, size)
if not is_bottom:
if vals[ndx+size] == 1 + vals[ndx]:
return seq + max_sequence(vals, ndx+size, size)
if not is_top:
if vals[ndx-size] == 1 + vals[ndx]:
return seq + max_sequence(vals, ndx-size, size)
if not is_left:
if vals[ndx-1] == 1 + vals[ndx]:
return seq + max_sequence(vals, ndx-1, size)
return seq

if __name__ == '__main__':
# expects an input file that looks like:
# 159
# 238
# 437
# for example
with open(sys.argv[1]) as fd:
size = len(matrix[0].strip())
flattened = ''.join([line.strip() for line in matrix]).strip()
flattened = [int(val) for val in flattened]
vals = []
for i in range(len(flattened)):
vals.append(max_sequence(flattened, i, size))
# find the longest by sorting, use maximum sum if more than one of same length
sorted_answers = sorted(answers, lambda v1, v2: v1[2] - v2[2] if v1[1] == v2[1] else v1[1] - v2[1])

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

``````#include <list>
#include <iostream>

using namespace std;

const int N = 3;

void checkNeighbour(int arr[N][N], int i, int j, list<int> & snake)
{
if(arr[i + 1][j] - arr[i][j] == 1 && i + 1 < N)
{
snake.push_back(arr[i + 1][j]);
checkNeighbour(arr, i + 1, j, snake);
}
if(arr[i - 1][j] - arr[i][j] == 1 && i - 1 >= 0)
{
snake.push_back(arr[i - 1][j]);
checkNeighbour(arr, i - 1, j, snake);
}
if(arr[i][j - 1] - arr[i][j] == 1 && j - 1 >= 0)
{
snake.push_back(arr[i][j - 1]);
checkNeighbour(arr, i, j - 1, snake);
}
if(arr[i][j + 1] - arr[i][j] == 1 && j + 1 < N)
{
snake.push_back(arr[i][j + 1]);
checkNeighbour(arr, i, j + 1, snake);
}
return;
}

int main()
{
int arr[N][N] = {1, 5, 9, 2, 3, 8, 4, 6, 7}, max_length = 0;
list<list<int>> list_of_snakes;
list<int>	snake,	 //final snake
t_snake; //temporary snake
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
t_snake.push_back(arr[i][j]);
checkNeighbour(arr, i, j, t_snake);
if(t_snake.size() == 1)
{
t_snake.clear();
continue;
}
else list_of_snakes.push_back(t_snake);
t_snake.clear();
}
}
for(list<list<int>>::iterator i = list_of_snakes.begin(); i != list_of_snakes.end(); i++)
{
if(max_length < i->size())
{
max_length = i->size();
snake = *i;
}
}
for(list<int>::iterator i = snake.begin(); i != snake.end(); i++)
cout << *i << " ";
return 0;
}``````

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

Since all the content is exactly 1..N*N, create a map from these to the right cell (i,j).
Iterate, say with i, from 1 to N^2-1 - if the map.get(i) has distance of exactly 1 from map.get(i+1), augment this pair (say in List), when the above is false, if the List is not empty, print it out and empty.

(O(NXN)) memory and time

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSubInMatrix_Ski {
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSubInMatrix_Ski test = new longestContinousSubInMatrix_Ski();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

I can only find a way to calculate the length of the substring, can anyone help me to print out the string?

``````public class longestContinousSub{
int[][] longest= new int[3][3];
int[][] original= {{1,5,6},{2,8,7},{3,9,4}};
int max = 0;
if(longest[i][j]!=0) return longest[i][j];
//up
if(j>0 && original[i][j] == original[i][j-1]+1){
}
}
//down
if(j<2 && original[i][j] == original[i][j+1]+1){
}
}
//left
if(i>0 && original[i][j] == original[i-1][j]+1){
}
}
//right
if(i<2 && original[i][j] == original[i+1][j]+1){
}
}
longest[i][j] = max + 1;
return longest[i][j];
}

public static void main(String args[]){
longestContinousSub test = new longestContinousSub();
//int re = test.find();
int max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
max = Math.max(max, test.longest[i][j]);
}
}
System.out.print(max);
}
}``````

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

simple my version

``````public class LongContSeqMatrix {

/*
* Given a NxN matrix which contains all distinct 1 to n^2 numbers, write code to print
* sequence of increasing adjacent sequential numbers.
*
*/
static int [][] array = {{5,4,9},{6,3,2},{7,8,1}};
static String contSeq = "";
static int N = 3;

public static void main(String[] args) {
String finalLong = "";
for(int i=0;i<N*N;i++){
int row = i / N;
int col = i % N;
contSeq = "" + array[row][col];
getContSeq(i);

if(finalLong.length() < contSeq.length())
finalLong = contSeq;
}

System.out.println("finalLong-"+finalLong);

}

static void getContSeq(int currentIndx){
if(currentIndx >= 0 && currentIndx < N*N){
int row = currentIndx / N;
int col = currentIndx % N;
if(col < (N-1) && (array[row][col] + 1) == array[row][col+1] ){
contSeq = contSeq + array[row][col+1];
getContSeq(currentIndx+1);
}

if(row < (N-1) && (array[row][col] + 1) == array[row+1][col] ){
contSeq = contSeq + array[row+1][col];
getContSeq(currentIndx+N);
}

if(row > 0 && (array[row][col] + 1) == array[row-1][col] ){
contSeq = contSeq + array[row-1][col];
getContSeq(currentIndx-N);
}

if(col > 0 && (array[row][col] + 1) == array[row][col-1] ){
contSeq = contSeq + array[row][col-1];
getContSeq(currentIndx-1);
}
}
}

}``````

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

Could anyone please explain the question a bit in detail? My confusion stems from the concept that matrices are usually read 1 row at a time - top down. I am unable to see 6 7 8 9 as adjacent numbers, unless seen visually. matrix [row] [column] is the general declaration i have seen till now. A lot of folks are attempting the question means I am missing something here. Appreciate any help. Thanks!

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

Here is another solution.

First we construct a graph, one node for each element in the matrix.
Then we add directed edges for every pair of adjacent nodes (a-->b) where b-1 == a.
Finally, we re-loop over all nodes checking the maximum length run by following the edges of each child node until no more exist.
When this final loop finishes we've noted the maximum length run and we return it.

We are looping over the input 3 times, but I belive the running time is O(n) where n is the size of the matrix.

``````def get_adjacent_increasing_run(matrix):

# Build Graph
graph = Graph()

for rIdx in xrange(0, len(matrix)):
for cIdx in xrange(0, len(matrix[rIdx])):
nodeIdx = matrixCoords2GraphIdx(matrix, rIdx, cIdx)

# Add directed edges for consecutive neighbors
for rIdx in xrange(0, len(matrix)):
for cIdx in xrange(0, len(matrix[rIdx])):
myNodeIdx = matrixCoords2GraphIdx(matrix, rIdx, cIdx)

# Locate neighbors values in matrix: [left, right, top, bottom]
for neighbor in [ (rIdx-1,cIdx), (rIdx+1,cIdx), (rIdx,cIdx-1), (rIdx,cIdx+1)]:
(neighborRIdx, neighborCIdx) = neighbor

if neighborRIdx < 0 or neighborRIdx >= len(matrix):
continue
if neighborCIdx < 0 or neighborCIdx >= len(matrix[neighborRIdx]):
continue

if matrix[neighborRIdx][neighborCIdx] - 1 == matrix[rIdx][cIdx]:
neighborNodeIdx = matrixCoords2GraphIdx(matrix, neighborRIdx, neighborCIdx)
break # Only one value can be chosen

# Find longest run
curLongestRun = []
for node in graph.nodes:
thisRun = getRun(graph, node)
if len(thisRun) > len(curLongestRun):
curLongestRun = thisRun
return curLongestRun

def getRun(graph, node):
run = []
while True:
run.append(node.data)

edges = graph.getEdges(node)
if not edges:
break
node = graph.nodes[edges[0].dstNodeIdx]
return run

def matrixCoords2GraphIdx(matrix, rIdx, cIdx):
return rIdx*len(matrix[rIdx]) + cIdx``````

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

``````/*
Given a NxN matrix which contains all distinct 1 to n^2 numbers, write code to print sequence of increasing adjacent sequential numbers.
ex:
1 5 9
2 3 8
4 6 7

should print
6 7 8 9

for visual c++ 2005
*/

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <iterator>
#include <math.h>
#include <numeric>
#include <sstream>
#include <stack>
#include <string>

using namespace std;

map<pair<int, int>, bool> mapIsNeighbor;

class Solution
{
public:
static void SetNeighbor( int i, int j)
{
if ( i < j )
mapIsNeighbor[ make_pair( i, j ) ] = true;
else
mapIsNeighbor[ make_pair( j, i ) ] = true;
}

static bool IsNeighbor( int i, int j)
{
if ( i < j )
return mapIsNeighbor.end() != mapIsNeighbor.find(make_pair( i, j ));
else
return mapIsNeighbor.end() != mapIsNeighbor.find(make_pair( j, i ));
}

static vector<int> FindIncNumbers(vector<vector<int>> vecInput)
{
vector<int> vecResult;
size_t N = vecInput.size();

for ( size_t i = 0; i < N; i ++)
for( size_t j = 0; j < N; j ++)
{
if ( j + 1 < N )
SetNeighbor( vecInput[i][j], vecInput[i][j + 1]);
if ( i + 1 < N )
SetNeighbor( vecInput[i][j], vecInput[i + 1][j]);
}

int nLength = 1;
vecResult.push_back(1);

int nFirstInt = 2;
while ( nFirstInt <= static_cast<int>( N * N ) )
{
int nInt = nFirstInt;
int nLenghTemp = 1;
while ( IsNeighbor( nInt - 1, nInt ) )
{
if ( nInt <= static_cast<int>( N * N ) )
nInt ++;
}

nLenghTemp = nInt - nFirstInt + 1;
if ( nLenghTemp > nLength )
{
nLength = nLenghTemp;
vecResult.clear();
for ( int i = nFirstInt - 1; i < nInt; i ++ )
vecResult.push_back( i );
}

if ( nFirstInt != nInt )
nFirstInt = nInt;
else
nFirstInt ++;
}

return vecResult;
}
};

int _tmain(int argc, _TCHAR* argv[])
{
// prepare input data
int arrLine1[] = {1,5,9};
int arrLine2[] = {2,3,8};
int arrLine3[] = {4,6,7};
vector< vector< int > > vecInput;
vecInput.push_back( vector<int>( arrLine1, arrLine1 + sizeof( arrLine1 ) / sizeof( int ) ));
vecInput.push_back( vector<int>( arrLine2, arrLine2 + sizeof( arrLine2 ) / sizeof( int ) ));
vecInput.push_back( vector<int>( arrLine3, arrLine3 + sizeof( arrLine3 ) / sizeof( int ) ));

vector<int> vecResult  = Solution::FindIncNumbers( vecInput );
// output result
copy( vecResult.begin(), vecResult.end(), ostream_iterator<int>( cout, " ") );

_getch();
return 0;
}``````

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

I am not sure I get the question - should the sample answer to the question not have printed out {1 2 3} and {6,7,8,9}, assuming that adjacency is just above, below, left and right?

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

#include <stdio.h>
#include <iostream>

using namespace std;

bool** check;
int searchLongestAdjaSeqInv(int**, int*, int, int, int);

int main() {
int i, j, N, len;
int **matrix, *seq;

cout << "size of matrix: ";
cin >> N;

matrix = new int *[N];
check = new bool *[N];
for(i=0; i<N; i++) {
matrix[i] = new int [N];
check[i] = new bool [N];
}

cout << "fill NXN matrix: ";
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
cin >> matrix[i][j];
check[i][j] = false;
}
}

seq = new int [N*N];

cout << "seq: ";
for(i=0; i<len; i++)
printf("%d ", seq[i]);

return 0;
}

int searchLongestAdjaSeq(int** matrix, int* seq, int N)
{
int i, j, k, ret, len;
int *tmpseq;

ret = 0;
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
if(check[i][j])
continue;

tmpseq = new int [N*N];
len = searchLongestAdjaSeqInv(matrix, tmpseq, N, i, j);

if(len > ret) {
for(k=0; k<len; k++)
seq[k] = tmpseq[k];

ret = len;
}

delete [] tmpseq;
}
}

return ret;
}

int searchLongestAdjaSeqInv(int** matrix, int* seq, int N, int i, int j)
{
int ret, k;
int *tmpseq;

ret = 0;
check[i][j] = true;
tmpseq = new int [N*N];
if (i!=0 && matrix[i][j]+1 == matrix[i-1][j])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i-1, j);
else if (i!=N-1 && matrix[i][j]+1 == matrix[i+1][j])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i+1, j);
else if (j!=0 && matrix[i][j]+1 == matrix[i][j-1])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i, j-1);
else if (j!=N-1 && matrix[i][j]+1 == matrix[i][j+1])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i, j+1);

ret++;
seq[0] = matrix[i][j];
for(k=1; k<ret; k++)
seq[k] = tmpseq[k-1];

return ret;
}

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

``````#include <stdio.h>
#include <iostream>

using namespace std;

bool** check;
int searchLongestAdjaSeqInv(int**, int*, int, int, int);

int main() {
int i, j, N, len;
int **matrix, *seq;

cout << "size of matrix: ";
cin >> N;

matrix	= new int *[N];
check = new bool *[N];
for(i=0; i<N; i++) {
matrix[i] = new int [N];
check[i] = new bool [N];
}

cout << "fill NXN matrix: ";
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
cin >> matrix[i][j];
check[i][j]	= false;
}
}

seq = new int [N*N];

cout << "seq: ";
for(i=0; i<len; i++)
printf("%d ", seq[i]);

return 0;
}

int searchLongestAdjaSeq(int** matrix, int* seq, int N)
{
int i, j, k, ret, len;
int *tmpseq;

ret = 0;
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
if(check[i][j])
continue;

tmpseq = new int [N*N];
len = searchLongestAdjaSeqInv(matrix, tmpseq, N, i, j);

if(len > ret) {
for(k=0; k<len; k++)
seq[k] = tmpseq[k];

ret	= len;
}

delete [] tmpseq;
}
}

return ret;
}

int searchLongestAdjaSeqInv(int** matrix, int* seq, int N, int i, int j)
{
int ret, k;
int *tmpseq;

ret = 0;
check[i][j] = true;
tmpseq = new int [N*N];
if (i!=0 && matrix[i][j]+1 == matrix[i-1][j])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i-1, j);
else if (i!=N-1 && matrix[i][j]+1 == matrix[i+1][j])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i+1, j);
else if (j!=0 && matrix[i][j]+1 == matrix[i][j-1])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i, j-1);
else if (j!=N-1 && matrix[i][j]+1 == matrix[i][j+1])
ret = searchLongestAdjaSeqInv(matrix, tmpseq, N, i, j+1);

ret++;
seq[0] = matrix[i][j];
for(k=1; k<ret; k++)
seq[k] = tmpseq[k-1];

return ret;
}``````

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

``````void increasing_adjacent_sequential_numbers_kernel(int* m, int i, int j, int nrow, int ncol, int &length) {
// reject condition1, outreach the bounds, condition2:
bool up    = false;
bool down  = false;
bool left  = false;
bool right = false;
if(i >= nrow || j >= ncol || i < 0 || j < 0) return;
if(j-1 >= 0) {
if(m[i*nrow+j-1]-m[i*nrow+j]   == 1)   left = true;
}
if(j+1 <= ncol) {
if(m[i*nrow+j+1]-m[i*nrow+j] == 1)     right = true;
}
if(i-1 >= 0) {
if(m[(i-1)*nrow+j]-m[i*nrow+j] == 1)   up = true;
}
if(i+1 <= nrow) {
if(m[(i+1)*nrow+j]-m[i*nrow+j] == 1)   down = true;
}
printf("visiting:%d\n",m[i*nrow+j]);
//accept
length++;
if(up) {
increasing_adjacent_sequential_numbers_kernel(m, i-1, j, nrow, ncol, length);
}
if(down) {
increasing_adjacent_sequential_numbers_kernel(m, i+1, j, nrow, ncol, length);
}
if(right) {
increasing_adjacent_sequential_numbers_kernel(m, i, j+1, nrow, ncol, length);
}
if(left) {
increasing_adjacent_sequential_numbers_kernel(m, i, j-1, nrow, ncol, length);
}
}

int m[9] = {1,5,9,
2,3,8,
4,6,7};
int max     = 0;
for(int i = 0; i < 3; i++) {
for(int j = 0; j <3; j++) {
int length  = 0;
increasing_adjacent_sequential_numbers_kernel(m, i, j, 3, 3, length);
printf("length:%d\n", length);
}
}
}``````

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

To explain my code above, I'm using the backtracking techniques to recursively find the adjacent numbers. Precisely, I'm looking for the number which is 1 bigger than current stand in the up, down, left, right spots. If there exists such number than go that direction.

This algorithm will not work well since it only consider the increasing scenario. For example, the worst case should be:
{1,2,3,
6,5,4,
7,8,9} it will traverse all the previous numbers at each step. To improve the algorithm, we need additional space to trade off time which I have not gave a through thought yet.

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

``````static int[][] cache;
//find biggest value in cache
static int max = -1;
static int max_i = -1;
static int max_j = -1;

public static void main(String[] args)
{
int array[][] = {{1, 5, 9},
{2, 3, 8},
{4, 6, 7}};

solve(array);
System.out.println();
}

static void solve(int[][] mat)
{
cache = new int[mat.length][mat.length];

for (int i = 0; i < mat.length; i++)
{
for (int j = 0; j < mat.length; j++)
{
cache[i][j] = -1;
}
}

for (int i = 0; i < mat.length; i++)
{
for (int j = 0; j < mat.length; j++)
{
findSeqLength(mat, i, j);
}
}

int start = mat[max_i][max_j];

//walk the result.
for (int i = 0; i <= max + 1; i++)
{
System.out.print(start + i);
}
}

static void findSeqLength(int[][] mat, int i, int j)
{
//out of bound
if (i < 0 || i > mat.length - 1 || j < 0 || j > mat.length - 1)
{
return;
}

//checked
if (cache[i][j] != -1)
{
return;
}

//check
peek(mat, i, j, i, j + 1);
peek(mat, i, j, i + 1, j);
peek(mat, i, j, i - 1, j);
peek(mat, i, j, i, j - 1);
}

static void peek(int[][] mat, int i, int j, int target_i, int target_j)
{
if (target_i < 0 || target_i > mat.length - 1 || target_j < 0 || target_j > mat.length - 1)
{
return;
}

if (mat[target_i][target_j] - 1 == mat[i][j])
{
int temp = cache[target_i][target_j];
if (temp == -1)
{
findSeqLength(mat, target_i, target_j);
}

temp = cache[target_i][target_j];
if (cache[i][j] <= temp)
{
cache[i][j] = temp + 1;
if (cache[i][j] > max)
{
max = cache[i][j];
max_i = i;
max_j = j;
}
}
}
}``````

Fully testable code

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

Recursive JavaScript solution - returns an array of the longest sequence:

``````var matrixSequence = function(matrix) {

var n = matrix.length;
var result = [matrix[0][0]];

var findSequence = function(position, visited, sequence) {

visited = visited || {};
visited[position] = true;

sequence = sequence || [];
var value = matrix[position[0]][position[1]];
sequence.push(value);

var nextPosition = [];
// move up
nextPosition[0] = position[0] - 1;
nextPosition[1] = position[1];
if ( nextPosition[0] >= 0 && !visited[nextPosition] ) {
if ( value + 1 === matrix[nextPosition[0]][nextPosition[1]] ) {
visited[position] = true;
findSequence(nextPosition, visited, sequence, value);
}
}

// move down
nextPosition[0] = position[0] + 1;
nextPosition[1] = position[1];
if ( nextPosition[0] < n  && !visited[nextPosition] ) {
if ( value + 1 === matrix[nextPosition[0]][nextPosition[1]] ) {
visited[position] = true;
findSequence(nextPosition, visited, sequence, value);
}
}

// move left
nextPosition[0] = position[0];
nextPosition[1] = position[1] - 1;
if ( nextPosition[1] >= 0  && !visited[nextPosition] ) {
if ( value + 1 === matrix[nextPosition[0]][nextPosition[1]] ) {
visited[position] = true;
findSequence(nextPosition, visited, sequence, value);
}
}

// move right
nextPosition[0] = position[0];
nextPosition[1] = position[1] + 1;
if ( nextPosition[1] < n && !visited[nextPosition] ) {
if ( value + 1 === matrix[nextPosition[0]][nextPosition[1]] ) {
visited[position] = true;
findSequence(nextPosition, visited, sequence, value);
}
}

if ( sequence.length > result.length ) {
result = sequence;
}

};

for ( var i = 0; i < n; i++ ) {
for ( var j = 0; j < n; j++ ) {
findSequence([i,j]);
}
}

return result;
};``````

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

O(n)

``````void print_longest_adj(const vector<vector<int>>& matrix) {
const int DUMMY = -2;
const int N = matrix.size();
vector<bool> adjacent(N * N + 1);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int a = matrix[i][j];
int b = i+1 < N ? matrix[i+1][j] : DUMMY;
int c = j+1 < N ? matrix[i][j+1] : DUMMY;
if (a+1 == b || a+1 == c)
if (b+1 == a)
if (c+1 == a)
}
}

int max_length = 0, max_first = 0, length = 0, first = 0;
for (int i = 0; i < adjacent.size(); i++) {
length++;
if (length == 1)
first = i;
if (length > max_length) {
max_length = length;
max_first = first;
}
} else {
length = 0;
}
}

for (int i = 0; i <= max_length; i++)
printf("%d\n", max_first+i);
}``````

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

Basic idea:
use DFS. use another array, the initial values of it is 1. For an element array[i][j], if the value is larger than 1, then continue to check another element. Or recursively DFS to its adjacency, which the adjacency has its next number. The DFS will return the longest steps the adjacency can reach. So, the value of array[i][j] is DFS result plus 1.

time O(n^2), space O(n^2)

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.

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