A.
BAN USER- 1of 1 vote
AnswersTake a list of integers (left to right order) and return an integer of the number of identical binary trees that can be created from the same list.
- A. in United States
Input: [10, 8, 15, 6, 9, 4, 5]
Output: 24
Input: [12, 6, 19, 15, 5]
Output: 6
Input: [44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64]
Output: 1
I wrote a brute-force 'solution', creating a binary tree for each permutation of the list (with the same root as Input list) and compared each to the binary tree from the Input list. For large input lists (length > 10), my 'solution' is useless.| Report Duplicate | Flag | PURGE
Software Engineer Intern Problem Solving Amazon Algorithm
- 4 Answers Binary Trees?
Take a list of integers (left to right order) and return an integer of the number of identical binary trees that can be created from the same list.
- A. December 04, 2014
Input: [10, 8, 15, 6, 9, 4, 5]
Output: 24
Input: [12, 6, 19, 15, 5]
Output: 6
Input: [44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64]
Output: 1
I wrote a brute-force 'solution', creating a binary tree for each permutation of the list (with the same root as Input list) and compared each to the binary tree from the Input list. For large input lists (length > 10), my 'solution' is way too slow.| Flag | PURGE
1) [10, 15, 8, 9, 6, 4, 5]
2) [12, 19, 15, 6, 5]
Rearranges the numbers in the list so that the root always stays in the same spot and subsequent nodes always come before their child or children. So in the first example, 10 is the root, 15 can go anywhere after 10. Then 8 must come before 6 and 9 (could be 9 then 6), 6 must come after 8, then 4 after 6, 5 after 4.
Second example, 12 is root. 6 and 19 (or 19 then 6) must come after 12, 5 must come after 6, 15 must come after 19.
@yangxh92
The first test case that you doubt the correctness of, I think it is the right number of combinations at 24. You're permutations include four that have the 5 before the 4. But isn't the 5 under the 4? The math is throwing off the other answers. How are you generating/estimating the permutations that stay in the correct order?
@yangxh92
I think you are correct in your description, "we need to know how many permutations exist with constrain root always occur before its children(the order of occurrence of siblings does not matter), we can use some math trick to do that."
I just don't know what this 'math trick' is that you are talking about. You have explained it better than I could though, I will keep searching.
Thanks for your reply.
Python 3
from itertools import groupby
def pattern(num):
patt = '1'
for n in range(num):
patt = (''.join([str(x.count(x[0])) + x[0] for x in
[list(g) for k, g in groupby(patt)]]))
return patt
print([pattern(x) for x in range(6)])
# ['1', '11', '21', '1211', '111221', '312211']
Python 3
def answer(n, m, arr):
return set(range(1, n + 1)).difference(set(arr))
# or...
def answer(n, m, arr):
if m == 0:
return {}
current, cnt = 1, 0
s = set()
for x in arr:
if not current == x:
s.add(current)
if cnt == m:
return s
current = x
cnt += 1
current += 1
return s
print(answer(8, 2, [1, 2, 4, 5, 6, 8])) # {3, 7}
print(answer(2, 0, [1, 2])) # {}
I don't think that is the right answer? The question wasn't to count the number of different binary trees. It was to find the number of combinations that would result in the exact same binary tree as the input list (root as 0 index and so on, left to right order).
- A. December 05, 2014from itertools import zip_longest
def leapfrog(lst):
pos, neg, final = list(), list(), list()
[neg.append(y) if y < 0 else pos.append(y) for y in lst]
for pair in zip_longest(neg, pos):
x, y = pair
if x is not None and y is not None:
final.append(x)
final.append(y)
elif x is not None:
final.append(x)
elif y is not None:
final.append(y)
return final
Repsamuelcsmith700, Accountant at Absolute Softech Ltd
Je suis chef d'équipe de support Office dans une entreprise Action Auto. Je suis également rédacteur de blog. J ...
Repjesselblagg9, Cloud Support Associate at 247quickbookshelp
Hello, I am Jesse and I live in Springfield, USA. I am working in a company as an engineering technician ...
Repcardiroy, Backend Developer at Accolite software
Hi,I am from Taxes, USA. Enthusiastic multilingual translator with years involvement with Spanish-English translations.Looking to additionally improve interpretation ...
You must not have read the description or looked at the test case inputs/outputs or else you would have answered your own question (which basically took the original description and rearranged the words).
- A. December 10, 2014"return an integer of the number of identical binary trees that can be created from the same list"
vs.
"number of permutations which create the same tree as the given input list?"
Thanks for your help.