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
@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)
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)
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 Knuth-shuffle 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)