## Google Interview Question

Backend Developers**Country:**United States

**Interview Type:**In-Person

I use queue for BFS, you can improve the code by ignore traversing the graph with much less similarity of the last path which has been found

```
from collections import deque
from bisect import insort
class RuleMap:
def __init__(self, n):
self._n = n
self._rules = {}
def add_rule(self, rule, value):
rules = self._rules
for i,x in enumerate(rule):
if x not in rules:
rules[x] = {}
if i==self._n-1:
rules[x] = value
else:
rules = rules[x]
def get_value(self, rule):
ans = []
q = deque()
#rule/similarity/index
q.append([self._rules, 0, 0])
while q:
curr_rule, similarity, idx = q.popleft()
if rule[idx] in curr_rule:
if idx==self._n-1:
insort(ans, (similarity+1, curr_rule[rule[idx]]))
else:
q.append([curr_rule[rule[idx]], similarity+1, idx+1])
if '*' in curr_rule:
if idx==self._n-1:
insort(ans, (similarity, curr_rule['*']))
else:
q.append([curr_rule['*'], similarity, idx+1])
return ans and ans[-1][1]
if __name__=='__main__':
data = [
[3,
[
[['A1', 'B1', 'C1'], 30],
[['*', 'B1', 'C2'], 20],
[['A2', 'B1', '*'], 25]
],
[
[['A1', 'B1', 'C1'], 30],
[['A1', 'B1', 'C2'], 20],
[['A2', 'B1', 'C3'], 25],
]
]
]
print('Check rules with maximum match:')
for d in data:
rm = RuleMap(d[0])
for r in d[1]:
rm.add_rule(*r)
for r in d[2]:
print('for rule: ', r[0], 'output is', rm.get_value(r[0]), 'expected', r[1])
```

Construct a trie based on rules. If while processing the end of the rule we discover that a different value was already inserted for the node we abandon rule processing and print 'ambiguous'.

```
I='''
A1 B2 C3 40
A1 B1 C1 20
A2 B2 C2 10
A1 B1 C1 40
* B1 * 20
A5 B2 * 10
'''
rules = [x.split()
for x in I.split('\n') if x.strip()]
root = {}
for r in rules:
trs = [root]
for x in r[:-1]:
trs = [z for tr in trs for z in (tr.values() if x == '*' or '*' in tr else [tr.setdefault(x,{})])]
v = r[-1]
if any(tr.setdefault(None,v) != v for tr in trs):
print('ambiguous')
break
else:
print('unambiguous')
```

```
from typing import List, Dict, Tuple, Set
def input_string_to_2d_array(input: str) -> List[List[str]]:
list_of_rows = input.strip().split('\n')
list_of_list_of_terms = map(lambda x: x.strip().split(' '), list_of_rows)
return list(list_of_list_of_terms)
```

First, we convert the input to a directed graph.

The graph has a single source "Source" that is has outgoing edges to all the vertices corresponding to the first column

of the rule table. Every other vertex has an outgoing edge to the rule in the next column of the rule table on the same

row.

Next, we start minimizing the graph as follows.

For each vertex (starting with 'Source'),

1. merge all children that have the same name into a single vertex

2. merge the same name nodes' children into a single set

3. update the number of rules that reach the vertex as the sum of number of rules that reach each of the vertices with the same name.

4. For children that are a '\*' vertex, make a copy of suffix of '\*' vertex and merge it with each of the non-'\*'

node's children.

Recursively perform this minimization on each of the vertex's children.

After minimizing the entire graph, if some sink node that mode than one value, then the ruleset is ambiguous.

```
import copy
class Vertex:
def __init__(self, name: str):
self.name: str = name
self.prefix_count: int = 1 # Number of prefix paths leading to this vertex
self.children: List["Vertex"] = []
self.is_sink = True
def __repr__(self) -> str:
neighor_names = list(map(lambda x: x.name, self.children))
return f"<{self.name}, count: {self.prefix_count}) -> {neighor_names}>"
def __str__(self) -> str:
return self.__repr__()
def make_copy(self) -> "Vertex":
"""
Makes a deep copy of this vertex, and recursively makes a deep copy of all
its children.
"""
clone = copy.deepcopy(self)
clone.children = {child.make_copy() for child in self.children}
return clone
class RuleTable:
def __init__(self, rules: List[List[str]]):
self.rule_list = rules
self.source = Vertex("source")
self.is_ambiguous_rules = False
def make_graph(self) -> None:
"""
Creates the graph one row at a time.
"""
for row_number in range(len(self.rule_list)):
self._make_graph_for_row(row_number)
def _make_graph_for_row(self, row: int):
initial_vertex = Vertex(self.rule_list[row][0])
current_vertex = initial_vertex
col_count = len(self.rule_list[row])
for col in range(1, col_count):
next_vertex = Vertex(self.rule_list[row][col])
current_vertex.children.append(next_vertex)
current_vertex.is_sink = False
current_vertex = next_vertex
self.source.children.append(initial_vertex)
self.source.is_sink = False
def is_ambiguous(self) -> bool:
return self.minimize_graph(self.source)
def minimize_graph(self, parent_vertex: Vertex) -> bool:
"""
Minimizes the children of a given vertex by merging children with the same
name, and copying the wild children's suffixes to each of the (merged)
children. It also updates the number of rules that reach this vertex.
Then it recursively merges each of the children (updating the number of rules
that reach those vertices).
If we are merging the sink nodes, then the function determines if more than
one rule reaches the vertex before the sink vertex, and if it has more
than on child (so multiple sinks), then it states that the ruleset is
ambiguous, and returns that value.
"""
children = parent_vertex.children
minimized_children: Dict[str, Vertex] = {}
wild_children: List[Vertex] = []
for child in children:
if child.name == "*":
wild_children.append(child)
continue
if child.name not in minimized_children:
minimized_children[child.name] = child
continue
minimized_children[child.name].children.extend(child.children)
minimized_children[child.name].prefix_count+=child.prefix_count
parent_vertex.children = list(minimized_children.values())
# Now to deal with the wildcard children.
for wild_child in wild_children:
# for every non-wild child, extend its children by each of the wild
# child's suffix.
for child in parent_vertex.children:
wild_grandchildren = \
[grandchild.make_copy() for grandchild in wild_child.children]
child.children.extend(wild_grandchildren)
# The number of prefix rules that can reach this child must now be
# incremented by the number of prefix rules that can reach the wild
# child.
child.prefix_count+= wild_child.prefix_count
for child in parent_vertex.children:
self.minimize_graph(child)
if (parent_vertex.prefix_count > 1
and len(parent_vertex.children) > 1
and parent_vertex.children[0].is_sink):
self.is_ambiguous_rules = True
return self.is_ambiguous_rules
```

Tests:

```
all_wild_ambiguous_rule_string = """
a1 b2 c1 20
a2 b1 c2 40
a1 b1 c2 30
* * * 20
"""
all_wild_ambiguous_rule = RuleTable(
input_string_to_2d_array(all_wild_ambiguous_rule_string))
all_wild_ambiguous_rule.make_graph()
assert all_wild_ambiguous_rule.is_ambiguous()
one_rule_string = """
a1 b2 c1 20
"""
one_rule = RuleTable(input_string_to_2d_array(one_rule_string))
one_rule.make_graph()
assert one_rule.is_ambiguous() is False
one_rule_all_wild_string = """
* * * * 20
"""
one_rule_all_wild = RuleTable(
input_string_to_2d_array(one_rule_all_wild_string))
one_rule_all_wild.make_graph()
assert one_rule_all_wild.is_ambiguous() is False
all_wild_ambiguous_2_rule_string = """
* * * 40
* * * 20
"""
all_wild_ambiguous_2_rule = RuleTable(
input_string_to_2d_array(all_wild_ambiguous_2_rule_string))
all_wild_ambiguous_2_rule.make_graph()
assert all_wild_ambiguous_2_rule.is_ambiguous() is False
ambiguous_rule_string = """
a1 b2 c1 d345 20
a2 b1 c2 d34 40
a1 b2 c1 d345 30
"""
ambiguous_rule = RuleTable(input_string_to_2d_array(ambiguous_rule_string))
ambiguous_rule.make_graph()
assert ambiguous_rule.is_ambiguous()
non_ambiguous_rule_string = """
a1 b2 c1 d34 20
a2 b1 c2 d34 40
a1 b2 c1 d345 30
"""
non_ambiguous_rule = RuleTable(
input_string_to_2d_array(non_ambiguous_rule_string))
non_ambiguous_rule.make_graph()
assert non_ambiguous_rule.is_ambiguous() is False
```

Check rules with maximum match:

- Loghman Barari October 24, 2019in here, we use queue for BFS of graph, you can improve performance with check similarity and ignore graph with low similarity to continue.

from collections import deque

from bisect import insort

class RuleMap:

def __init__(self, n):

self._n = n

self._rules = {}

def add_rule(self, rule, value):

rules = self._rules

for i,x in enumerate(rule):

if x not in rules:

rules[x] = {}

if i==self._n-1:

rules[x] = value

else:

rules = rules[x]

def get_value(self, rule):

ans = []

q = deque()

#rule/similarity/index

q.append([self._rules, 0, 0])

while q:

curr_rule, similarity, idx = q.popleft()

if rule[idx] in curr_rule:

if idx==self._n-1:

insort(ans, (similarity+1, curr_rule[rule[idx]]))

else:

q.append([curr_rule[rule[idx]], similarity+1, idx+1])

if '*' in curr_rule:

if idx==self._n-1:

insort(ans, (similarity, curr_rule['*']))

else:

q.append([curr_rule['*'], similarity, idx+1])

return ans and ans[-1][1]