Amazon Interview Question
Software Engineer / DevelopersCountry: United States
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
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.
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;
}
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;
}
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