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

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]

- Loghman Barari October 24, 2019 | Flag Reply
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 = {}

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

- Loghman Barari October 24, 2019 | Flag Reply
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')

- adr October 25, 2019 | Flag Reply
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

- novastorm123 October 25, 2019 | Flag Reply
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][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

- Anonymous October 31, 2019 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More