horvthpeter
BAN USERPretty simple solution.
Just one thing needs clarification: what do you do when a node only has 1 child.
def correct(root):
if not root:
return 0
if not root.left and not root.right:
return root.val
root.val = int(correct(root.left) & correct(root.right))
return root.val

horvthpeter
May 22, 2017 @Dorianna you're solution is wrong.
Total votes  max votes doesnt give you the min votes, since it will also include the
votes between k smallest and k biggest.
@Adriano your solution is wrong take 1101 for example
 horvthpeter May 04, 2017@sonesh Your first solution makes no sense whatsoever.
@Abcd I'm not sure how you arrived at the conclusion that your solution is O(n+m) when you're clearly doing m insertions into a BST of n elements.
Your solution is O(logn*m) if the first BST is balanced, O(n*m) otherwise.
There are 2^(number of s's and a's in the string) outputs in total.
A simple solution would be to create a recursive function that has a result string, a position inside the original string, and whenever the letter at the current position is a or s, append all synonim elements and recurse.
Python:
def gen(s, res, pos):
if pos >= len(s):
print res
return
if s[pos] in 'as':
if s[pos] == 'a':
gen(s, res + 'a', pos + 1)
gen(s, res + '@', pos + 1)
elif s[pos] == 's':
gen(s, res + 's', pos + 1)
gen(s, res + '$', pos + 1)
else:
res += s[pos]
gen(s, res, pos + 1)

horvthpeter
May 03, 2017 Brute force:
Length of binary representation of a decimal n = floor(log(n, 2)) + 1. Let's call this k
Iterate from i < 0 to floor(k / 2):
if the bit at i is not equal to the bit at k  i  1:
return False
return True
We can check if the bit at i is not equal to the bit at k  i  1 by:
mask = 1 << k  i  1
if !((mask & n == mask) or (mask & n == 0))
(the bits are equal only if both are 1, in which case the first condition is true,
or both are none in which case the second condition is true)
Open Chat in New Window
As @inucoder suggested, reservoir sampling is probably the ideal solution.
 horvthpeter May 22, 2017Another pretty interesting one would be to shuffle the array in place using Knuthshuffle in O(n), get the max using O(n) and return the first index of a max element. O(n)
Total time complexity: O(n), space complexity: O(1)