Facebook Interview Question
SDE1sCountry: United States
There are many ways to do it, here is one.
/*
The regex is :
n2 = (\d)?x(\d)?y...(\d)?
under |string_n1| = |string_n2| + 1
*/
def get_number( sum_value ){
list ( [ 1: sum_value /2 + 1 ] ) -> {
n2 = $.o
n1 = sum_value - n2
// when the digits are not one up
s_n1 = str(n1)
s_n2 = str(n2)
continue ( size(s_n2) + 1 != size(s_n1) )
decorated_n2 = fold( s_n2.value , '(\d)?' ) -> { $.p + $.o + '(\d)?' }
continue( s_n1 !~ str(decorated_n2) )
[ n1, n2 ]
}
}
ns = get_number ( int(@ARGS[0]) )
println(ns)
My python solution.
# Brute force solution less than O(n^2))
# O(n*m)
# where m
# m =~ 10^(len(n)-1) - 10^(len(n)-2)
import math
def check(n1,n2):
n1 = list(str(n1))
n2 = list(str(n2))
if len(n1)-1 != len(n2):
return False
for char in n2:
if char not in n1:
return False
else:
n1.remove(char)
return True
n = 124
val = []
r = int(math.pow(10,len(str(n))-1))
a = int(math.pow(10,len(str(n))-2))
for n1 in xrange(n):
for n2 in xrange(a,r):
if n1+n2 == n:
if check(n1,n2):
val.append((n1,n2))
print val
To compute all possible pairs instead of using brute force which would mean all the possible pairs I have used as a lower bound 10 ** (digits of the sum - 1) - 10 ** (digits of the sum - 2) and sum - (10 ** (digits of the sum - 2) - 10 ** (digits of the sum - 3)). I am still sure there are better approximations
- Fernando May 22, 2017