## Google Interview Question for Backend Developers

Country: United States
Interview Type: In-Person

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

Check rules with maximum match:

in 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 = {}

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]

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

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 = {}

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]

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)
for r in d:
for r in d:
print('for rule: ', r, 'output is', rm.get_value(r), 'expected', r)``````

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

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')``````

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

is there a java solution for this question using trie or graph ?

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

i dont get the solution.. is there a leetcode link for this q

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

``````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])
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.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``````

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

``````package main.rules;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class RulesExecute {
public static void main(String[] args){

RulesExecute executor = new RulesExecute();

RulesTable table = new RulesTable();
RuleRecord r = new RuleRecord();
r.rule1="A1";r.rule2="B2";r.rule3="C3"; r.result=40;

r = new RuleRecord();
r.rule1="A1";r.rule2="B1";r.rule3="C1"; r.result=20;

r = new RuleRecord();
r.rule1="A2";r.rule2="B2";r.rule3="C2"; r.result=10;

r = new RuleRecord();
r.rule1="A1";r.rule2="B1";r.rule3="C1"; r.result=20;

r = new RuleRecord();
r.rule1="*";r.rule2="B1";r.rule3="*"; r.result=20;

r = new RuleRecord();
r.rule1="A5";r.rule2="B2";r.rule3="*"; r.result=10;

List<RuleRecord> tempList = new ArrayList<>( table.rules );
boolean ambiguous = table.rules.stream().anyMatch( record->{
tempList.remove( record );
return tempList.stream().filter( other->{
if(executor.ruleMatch( other.rule1, record.rule1 ) &&
executor.ruleMatch( other.rule2, record.rule2 ) &&
executor.ruleMatch( other.rule3, record.rule3 ) &&
other.result != record.result){
return true;
}else{
return false;
}
} ).collect(Collectors.toList()).size() > 0;

} );

System.out.print( ambiguous );
}

public boolean ruleMatch(String rule1, String rule2){
if(rule1.equals( "*" ) || rule2.equals( "*" )){
return true;
}else if(rule1.equals( rule2 )){
return true;
}

return false;
}

}``````

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

``````# With `r` = number of rules in `table` and `sr` = number of rules that contain at least one `*`:
# Time complexity = O(r) + O(r * sr)
def isAmbiguous(table):
seen = {}
starred_rules = {}
is_amb = False
for rule in table:     # O(r)
val = rule.pop()
curr_rule = tuple(rule)
if '*' in rule:
if curr_rule in starred_rules and starred_rules[curr_rule] != val:   # worst case: O(s) - assuming robust hash function with no collisions: O(1)
is_amb = True
break
starred_rules[curr_rule] = val
else:
if curr_rule in seen and seen[curr_rule] != val:       # worst case: O(se) - assuming robust hash function with no collisions: O(1)
is_amb = True
break
seen[curr_rule] = val
if not is_amb and bool(starred_rules):
for star_rule in starred_rules:   # O(sr)
for rule in seen:        # O(r)
if len(set(star_rule) - set(rule)) < 2:
return True
return is_amb``````

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

I am using trieNode that takes strings instead of char. The upper bound is m*(!n) where n is the length of rule.

``````class TrieNode{
public HashMap<String, TrieNode> childrenMap;
public String value;
public TrieNode(HashMap<String,TrieNode> map, String value){
this.childrenMap = map;
this.value = value;
}
}
boolean hasAmibiguouty(String [][] rules, TrieNode root){
HashSet<String> [] rulesSet = new HashSet[rules.length - 1];

for(int i = 0;i < rules.length - 1; i++){
rulesSet[i] = new HashSet<String>();
for(int j = 0; j < rules.length;j++){
if(rules[j][i] != "*" && !rulesSet[i].contains(rules[j][i]))
}
}
boolean duplicate = false;
for(int i = 0; i < rules.length; i++){
if(duplicate)return true;
}
return false;
}
boolean addRule(String [] rule, HashSet [] ruleSet, TrieNode root, int index){
if(index == rule.length - 1){
if(root.value != null)return true;
root.value = rule[index];
return false;
}
if(rule[index].equals("*")){
Iterator<String> it = ruleSet[index].iterator();
while(it.hasNext()){
String ruleName = it.next();
boolean duplicate = addRule(rule,ruleSet,root.childrenMap.get(ruleName),index + 1);
if(duplicate)return true;
}
}else{
}
return false;
}
if(root.childrenMap.containsKey(ruleName)){
return root;
}else{
TrieNode node = new TrieNode(new HashMap<String, TrieNode>(),null);
root.childrenMap.put(ruleName, node);
return root;
}
}``````

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.