So just few minutes back I had my first onsite round with Google for L4 position(SWE-3), The interviewer was so cooperative and humble guy from Europe. Asked me to built a program to substitute a string with given variables:
#{'X':'%Z%', 'Y':'45', 'Z':'32'}
#string='%X%_%Y%'
#output: 32_45
earlier he didn't mentioned about variables can refer to other variables too, but later he followed up with that on which I tweaked my solution to a recursive approach.
Good experience over all.
My solution: almost 90-95% like this:
As there was very few minutes left when he asked followup I missed cycle detection in this, though it was very minor change for cycle detection.
class Solution:
def __init__(self, data):
self.data = data
def resolve_string(self, string_to_resolve, visited=None):
if visited is None:
visited = set()
if '%' not in string_to_resolve:
return string_to_resolve
var = ''
start = 0
n = len(string_to_resolve)
res_str = ''
var_part = False
while start < n:
if not var_part and string_to_resolve[start] == '%':
var_part = True
var = ''
elif var_part and string_to_resolve[start] != '%':
var += string_to_resolve[start]
elif var_part and string_to_resolve[start] == '%':
var_part = False
if var in visited:
raise ValueError(f"Cyclic reference detected: {' -> '.join(visited)} -> {var}")
visited.add(var)
resolved = self.resolve_string(self.data.get(var, f"%{var}%"), visited)
visited.remove(var)
res_str += resolved
elif not var_part:
res_str += string_to_resolve[start]
start += 1
return res_str
Comments (6)