Loghman Barari
BAN USERloghmanb@gmail.com
I solve this problem by recursive function.
f(n) = min(1+f(n-root^2), n//(root-1)^2+f(n%(root-1)^2)
f(0...4) = 0...4
import math
import sys
def find_no_of_perfect_square(n):
if n<0:
return sys.maxsize
if n<4:
return n
elif n==4:
return 1
root = int(math.sqrt(n))
if root>=2:
return min(
1+find_no_of_perfect_square(n-pow(root, 2)),
n//pow(root-1,2) + find_no_of_perfect_square(n%pow(root-1,2))
)
else:
return n
if __name__=='__main__':
data = [
[5, 2],
[7, 4],
[12, 3],
[20, 2],
]
for d in data:
print('the least no of perfect square for', d[0], 'is', find_no_of_perfect_square(d[0]), 'expected', d[1])
from collections import defaultdict
def find_common_hotels(users):
no = len(users.keys())
d = defaultdict(set)
for user in users:
for hotel_id in users[user]:
d[hotel_id].add(user)
ans = list(filter(lambda hid:len(d[hid])==no, d.keys()))
return ans
if __name__ == "__main__":
data = [
[
{'userA': [2, 3, 1], 'userB': [2, 5, 3], 'userC': [7, 3, 1]},
[3]
]
]
print('find common hotel ids:')
for d in data:
print('users log', d[0], 'result', find_common_hotels(d[0]), 'expected', d[1])
def find_min_diff(arr):
arr = sorted(arr)
min_diff = None
for i in range(1, len(arr)):
diff = arr[i]-arr[i-1]
if min_diff is None or min_diff>diff:
min_diff = diff
return min_diff
if __name__=='__main__':
data = [
[[100, 20, 52, 18, -4], 2]
]
print('Find minimum difference between items in array')
for d in data:
print('array is', d[0], 'result', find_min_diff(d[0]), 'expected', d[1])
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])
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 27, 2019