Question 1:
My solution:
def find_lefmost_index_of_one(matrix):
if not matrix and not matrix[0]:
return -1
left, right = 0, len(matrix[0]) - 1
index = -1
while left < len(matrix) and right >= 0:
if matrix[left][right] == 1:
index = right
right -= 1
else:
left += 1
return indexQuestion 2:
-
We are given a list of pairs. A pair [a,b] means there is directed edge from a to b. We are also guaranteed there are no cycles in this graph. Given two nodes X and Y, return if they have common ancestor.
[[5,6],[2,3],[2,4],[1,2]]
1 | 2 5 / \ ^ 3 4 6X=3 Y=4 Yes
X=4 Y=6 No
X=5 Y=6 Yes
My solution:
def has_lca(pairs, X, Y):
if not pairs:
return 'No'
graph = [[] for _ in range(len(pairs))]
for u, v in pairs:
graph[u].append(v)
def bfs(u, v):
queue = collections.deque([u])
while queue:
node = queue.popleft()
if node == X or node == Y:
node_count += 1
for next_node in graph[node]:
queue.append(next_node)
node_count = 0
for u, v in pairs:
bfs(u, v, graph)
if node_count == 2:
return 'Yes'
node_count = 0
return 'No'Comments (9)