Amazon Interview Question for Software Engineer / Developers


Country: United States




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

I could use a modified dijkstra's algorithm. Initially we assign each entry to be 0 and 1 where there is a path from S to pi. And then we get the group of largest distance we have, and visit each of the points and try to modify the largest distance in our array so we have a new distance array from S to each node in our graph. This step is crucial, consider all situations we might encounter and you will find it is correct. Finally, when we will find our destination point would be the largest distance in the array if the point is a sink.

- shengzhc March 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I used the modified BFS. A visited node would be recycled if its original path len is shorter. Each to be visited node contains a path and a set for those node in the path, the outgoing edge would not be considered if it is in the set of the path to avoid cycles.

def find_longest_path(graph, S, C): 
    #Queue has the tuple[nodeid, max_path_set, max_path)
    actionlist= []
    actionlist.append((S, set([S]), [S]))
    visited = {}
    visited[S] = 1   
    maxpath = []
    while len(actionlist) > 0:
        cur = actionlist.pop()    
        u = cur[0]
        pathset = cur[1]
        path = cur[2]
        pathlen = len(path)
        if u == C and pathlen > len(maxpath):
            maxpath = path
        for node in graph[u].outgoing:
            v = node.id
            if v in pathset:
                continue
            npathset = set(path)
            npath = list(path)
            npathset.add(v)
            npath.append(v)
            if v is not visited:
                actionlist.append((v, npathset, npath))
                visited[v] = len(npath)
            else:
                if visited[v] < len(npath):
                    visited[v] = len(npath)
                    #recycle node v
                    actionlist.append((v, npathset, npath))
    return maxpath

- lll March 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use DFS. For each node we can keep a "path id", parent, and depth from the source node. If we encounter a node which is "visited" and "whose length could become better" and *"it's not on the same path-id as current node"* then we can update that node and paths propogating from that node.

- Amol March 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

is not the visited array we maintain to avoid cycles?
Regarding the longest path below should do?

dfs(source ,destination, graph)
{
	if(source == destination)
                   we have a path here.What is the size?
		   if(size > present_size)
			update present_size;
	visited[source] = 1;
	for(all the connected nodes to source)
			if(visited[connected_node] == 0)
				dfs(connected_node, destination)
					visited[connected_node] = 0;
}

- aka March 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Isnt there a better algo than DFS?

- jimmy514in March 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Logic:do dfs and with backtracking find out all the paths and store it.
Do a search for the maximum number of nodes in the paths stored during backtracking
and print it.
It is not that efficient but this is what I came up with.

#include <stdio.h>
#include <limits.h>
#define SIZE 7
//#define ALL_PATH

int visited[SIZE]={0};
int count=0;
int path[SIZE]={0};
struct list{
	int count;
	int *mem;
};
struct list *p_backup;
int i_x = 0;

/*adjacency matrix */
int a[SIZE][SIZE] = {// A, B, C, D, E, F, G
			0, 1, 1, 1, 1, 1, 1,
			1, 0, 0, 1, 1, 1, 1,
			1, 1, 0, 1, 1, 1, 1,
			1, 1, 1, 0, 1, 1, 1,
			1, 1, 1, 1, 0, 1, 1,
			1, 1, 1, 1, 1, 0, 1,
			1, 1, 1, 1, 1, 1, 0,
			};

void dfs(int node, int destination)
{
	int i;

	path[count] = node;
	count++;
	visited[node] = 1;
	/*found the path */
	if(node == destination) {
		p_backup[i_x].count = count;
		p_backup[i_x].mem = malloc(sizeof(int)*(count));
		memcpy(p_backup[i_x].mem, path, (count)*sizeof(int));
		i_x++;
		return;
	}
	for(i=0;i<SIZE;i++) {
		if(a[node][i] == 1 && (visited[i] != 1)) {
			dfs(i, destination);
			visited[i] = 0;
			count--;
		}
	}
}

int main()
{
	int i, min = -1, m_index=0, j;
	p_backup = malloc(sizeof(struct list)*500); /*this can go really big for all paths*/
	dfs(4, 6);
	/* search in the list with maximum nodes */
	for(i=0;i<i_x;i++) {
		if(p_backup[i].count > min){
			min = p_backup[i].count;
			m_index = i;
		}
	}
#ifdef ALL_PATH
	for(i=0;i<i_x;i++) {
		for(j=0;j<p_backup[i].count;j++)
			printf("%d->", p_backup[i].mem[j]);
		printf("\n");
	}
#else
	for(i=0;i<p_backup[m_index].count;i++)
		printf("%d->", p_backup[m_index].mem[i]);
	printf("\n");
#endif
	return 0;
}

- aka March 30, 2013 | 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