## Amazon Interview Question for SDE-3s

Country: United States
Interview Type: In-Person

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

``````from collections import defaultdict

def __init__(self, vertex, weight):
self.v = vertex
self.weight = weight

def get_v(self):
return self.v

def get_weight(self):
return self.weight

class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices

self.graph[u].append(node)

def topological_sort_util(self, v, visited, stack):
visited[v] = 1
for vert in self.graph[v]:
node = vert
if not visited[node.get_v()]:
self.topological_sort_util(node.get_v(), visited, stack)

stack.insert(0, v)

def topological_sort(self):
stack = []
visited = [0] * self.V
for i in range(self.V):
if not visited[i]:
self.topological_sort_util(i, visited, stack)
return stack

def longest_path(self, source):
dist = [-float('inf') if i is not source else 0 for i in range(self.V)]
top_sort = self.topological_sort()
while top_sort:
u = top_sort.pop(0)
if dist[u] != -(float('inf')):
for i in self.graph[u]:
if dist[i.get_v()] < (dist[u] + i.get_weight()):
dist[i.get_v()] = dist[u] + i.get_weight()
print max(dist)

g = Graph(6)
g.longest_path(3)``````

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

public static int maxDistance(final Node node, final int currentMax, int max) {
if ((node.getLeftNode() == null) && (node.getRightNode() == null)) {
if (currentMax > max) {
max = currentMax;
}
} else {
if (node.getLeftNode() != null) {
max = maxDistance(node.getLeftNode(), currentMax + 1, max);
} else if (node.getRightNode() != null) {
max = maxDistance(node.getRightNode(), currentMax + 1, max);
}
}
return max;
}

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

``````public static int maxDistance(final Node node, final int currentMax, int max) {
if ((node.getLeftNode() == null) && (node.getRightNode() == null)) {
if (currentMax > max) {
max = currentMax;
}
} else {
if (node.getLeftNode() != null) {
max = maxDistance(node.getLeftNode(), currentMax + 1, max);
} else if (node.getRightNode() != null) {
max = maxDistance(node.getRightNode(), currentMax + 1, max);
}
}
return max;
}``````

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

``````public static int maxDistance(final Node node, final int currentMax, int max) {
if ((node.getLeftNode() == null) && (node.getRightNode() == null)) {
if (currentMax > max) {
max = currentMax;
}
} else {
if (node.getLeftNode() != null) {
max = maxDistance(node.getLeftNode(), currentMax + 1, max);
} else if (node.getRightNode() != null) {
max = maxDistance(node.getRightNode(), currentMax + 1, max);
}
}
return max;
}``````

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

can we flip dijkstra's algorithm instead of calculating single source shortest path, we can find single source longest path using max heap instead of min heap?

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.

### 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.