Interview Question for Software Engineer Interns


Interview Type: In-Person




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

A maze is, when simplified, little more than a set of permutations of choices, of which only one (unless it has multiple paths to end) is the correct. For a position p in the maze, there are at most c choices (usually 3, left, right, forward) so to traverse the maze accurately you need O(c^n) time, where n is the maximum number of turns possible in the maze before hitting a dead end or the end of the maze. This is essentially a tree.

Supposing the robot is able to backtrack and has no awareness of what lay around any of the presented options (left, right, forward) you can utilize a recursive algorithm

in python with some assumed functions:

class Position:
	#contains a list of pointers, choices, and position value.
	# also contains a function move_to which creates a position for that direction
	#and a function is_end which specifies if the position is the end of the maze

	#contains a static set called visited which indicates when a specific position has
	#been previously visited by the algorithm.


def solve_maze(position):
	if position in position.visited:
		return []
	position.visited.add(position)
	if position.is_end():
		return [position]
	for x in position.choices:
		y = solve_maze(position.move_to(x))
		if not y:
			continue
		else:
			return position + y
	return []

The solve_maze function returns a ordered list of positions. If the returned list is empty, it is ignored as it means that that sub-tree of movements resulted in a dead end. Otherwise, the current position of that recursion layer is added to it, and returned.

What this means is the recursion will always hit the bottom of the tree of possible paths first, then begin working in depth-first order. The only paths which will propagate back up to the root are those which result in reaching the end of the maze.

Additionally, the visited list will prevent parts of the maze which loop creating an infinite recursion. In no maze is there ever a reason to go to the same point twice.

The Position class will, when given the move_to command, continue until the next point in the maze where you encounter a choice.

This will run in the runtime stated above, not terribly efficient. Memoization is provided in the form of the visited list, as any one point will have a fixed set of valid paths, regardless of which direction it is approached from.

- Javeed April 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Dijjkstra's algorithm or an A* variant.

- Alex April 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is same as depth first traversal of graph

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

This is same as Depth first traversal of a graph.
1. Choose a random node
2. Push node to stack
3. Visit the first adjacent unvisited node next to this node.
4. Mark the node in step# 3 as visited
5. Push the node in step #3 to stack
If step #3 is not possible, pop node from stack

- vittal.setty May 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just use right hand rule for a robot, always go forward, if it is not possible turn right and go forward, until robot finds the exit.

- madi.sagimbekov April 26, 2016 | 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