Interview Question
Software Engineer / DevelopersCountry: United States
# 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
# Answer is 5. [2,3,4,5,6].
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
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.
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.
The complexity is O(N^2), since in the worst case there is no way to move
- Vinh January 27, 2015