## Interview Question for Software Engineer / Developers

• 0

Country: United States

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

The complexity is O(N^2), since in the worst case there is no way to move

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

``````# Given a 2D array of size nXn with values from 1 to n^2 permuted in the 2D array i.e no duplicates.
# Find the longest snake in the array such that snake can go upward, downward, right, left and each and every adjacent value
# in the snake should differ by 1.
# Ex:
# 2 5 6
# 3 4 9
# 1 7 8

import random

N = 3

#generate array
arr = [i for i in range (N * N)]
visited = [False for i in range (N * N)]

random.shuffle (arr)

arr.append (-2)

def up (index):
if (index >= N):
return index - N
else:
return N*N

def down (index):
if (index <= N*N - N - 1):
return index + N
else:
return N*N

def left (index):
if (index % N > 0):
return index - 1
else:
return N*N

def right (index):
if (index % N <= N - 1):
return index + 1
else:
return N*N

longest = 0
logest_trace = list()
for i in range (N*N):
curr_len = 0
if (visited[i] == False):
visited[i] = True
curr_len += 1
curr_index = i
curr_list = list()
curr_list.append (arr[curr_index])
while (True):
if (arr[curr_index] == arr[up(curr_index)] + 1):
curr_len += 1
curr_index = up(curr_index)
curr_list.append (arr[curr_index])
visited [curr_index] = True
continue
elif (arr[curr_index] == arr[down(curr_index)] + 1):
curr_len += 1
curr_index = down(curr_index)
curr_list.append (arr[curr_index])
visited [curr_index] = True
continue
elif (arr[curr_index] == arr[right(curr_index)] + 1):
curr_len += 1
curr_index = right(curr_index)
curr_list.append (arr[curr_index])
visited [curr_index] = True
continue
elif (arr[curr_index] == arr[left(curr_index)] + 1):
curr_len += 1
curr_index = left(curr_index)
curr_list.append (arr[curr_index])
visited [curr_index] = True
continue
else:
break
if (curr_len > longest):
longest = curr_len
logest_trace = curr_list

print arr
print '----'
print logest_trace
print '----'
print longest``````

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

There are several issues and can be optimized, but the above code works.
The idea is: if you visited an element before, you do not need to visit it again.

The complexity is O(n), with n is total length of two dimension arrays (or O(n^2) if you only count 1 dimension)

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

Solution 1) Standard BFS or DFS will do the job. O(N^2) time, O(N^2) space. The solution is linear in terms of number of elements in the array

Solution 2) We can't do better than O(N^2) time but we can save space. If we scan the matrix top-down row-by-row we can track location of snake ends and their length at the current row. For this we need O(N) space. When we process each row we extend snake ends and in some cases merge them.

Solution 3) We can optimize solution 2 and reduce it to O(1) space if we allow to destroy original matrix. We just store the data there by updating rows in place.

Solution 4) We can do O(1) space, if we are allowed to temporarily mutate the original matrix but aren't allowed to destroy it (e.g. must leave intact at the end of algorithm) we can do it in O(1) space as well. We can store information in unused bits of integers in that matrix OR re-encode numbers by extending them to negative range in a way so they carry extra information but can be restored at exit.

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

This is really a graph problem, no? Each element in the matrix is connected to one (actually 0) or more adjacent elements. So you could convert the matrix to a graph and it becomes like a longest path problem, which is an NP-hard problem. Pretty lame interview question, unless I'm missing something. I would almost always assume any question I'm getting would have a P solution, so I'd be questioning my thinking the whole time.

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.