From aa66d9b83d5793bdbb7fe28368e0642f7c3dceac Mon Sep 17 00:00:00 2001 From: William Carroll Date: Thu, 12 Nov 2020 14:37:29 +0000 Subject: Add coding exercises for Facebook interviews Add attempts at solving coding problems to Briefcase. --- scratch/facebook/mesh-message.py | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100644 scratch/facebook/mesh-message.py (limited to 'scratch/facebook/mesh-message.py') diff --git a/scratch/facebook/mesh-message.py b/scratch/facebook/mesh-message.py new file mode 100644 index 000000000000..8438b059d843 --- /dev/null +++ b/scratch/facebook/mesh-message.py @@ -0,0 +1,40 @@ +from heapq import heappush, heappop +import random + +def shortest_path(a, b, graph): + seen = set() + h = [] + heappush(h, (0, a, [a])) + while h: + km, x, path = heappop(h) + if x == b: + return path + for c in graph[x]: + if c not in seen: + heappush(h, (km + 1, c, path + [c])) + raise Exception("We were unable to find a path from {} to {}".format(a, b)) + +graph = { + 'Min' : ['William', 'Jayden', 'Omar'], + 'William' : ['Min', 'Noam'], + 'Jayden' : ['Min', 'Amelia', 'Ren', 'Noam'], + 'Ren' : ['Jayden', 'Omar'], + 'Amelia' : ['Jayden', 'Adam', 'Miguel'], + 'Adam' : ['Amelia', 'Miguel', 'Sofia', 'Lucas'], + 'Miguel' : ['Amelia', 'Adam', 'Liam', 'Nathan'], + 'Noam' : ['Nathan', 'Jayden', 'William'], + 'Omar' : ['Ren', 'Min', 'Scott'], + 'Liam' : ['Ren'], + 'Nathan' : ['Noam'], + 'Scott' : [], +} + +result = shortest_path('Jayden', 'Adam', graph) +print(result) +assert result == ['Jayden', 'Amelia', 'Adam'] +print('Success!') + +beg = random.choice(list(graph.keys())) +end = random.choice(list(graph.keys())) +print("Attempting to find the shortest path between {} and {}".format(beg, end)) +print(shortest_path(beg, end, graph)) -- cgit 1.4.1