Interview Question for Software Engineer / Developers


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

- Vinh January 27, 2015 | Flag Reply
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 
# 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

- Vinh January 27, 2015 | Flag Reply
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)

- Vinh January 27, 2015 | Flag Reply
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.

- 0xF4 January 27, 2015 | Flag Reply
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.

- crig January 30, 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