MESSAGE TO FUTURE VIEWERS: Sorry it's hard to see the code for this problem. This is my very first video and I messed up the screen resolution as I still didn't know the best way to record these videos. Here is the code in case you cannot see it: class Solution: def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]: res = collections.defaultdict(list) def dfs(node, layer): if not node: return layer left = dfs(node.left, layer) right = dfs(node.right, layer) layer = max(left, right) res[layer].append(node.val) return layer + 1 dfs(root, 0) return res.values()
Got this question today for my Google interview. I hadn't seen this video yet, but it was pretty easy to see it was Post-Order traversal, but when I said that, my interviewer struck me down and said it wouldn't work. He also said it would only work iteratively. So I absolutely bombed, because I couldn't think of a solution that didn't involve Post-Order traversal. He said near the end that I had to get the reverse height of the tree (so leaves are zero), and then delete the leaves that way, but iteratively. Couldn't figure it out.
Wow, Google interviewers are STILL total dickheads. Honesty an interview there is either going to be an assessment of your problem solving/communication abilities or a dick measuring content where the interviewer tries to show off how smart he/she is by wanting some obscure solution. Unfortunately you got the later. It shouldn’t matter how you solve the question. The recursive solution isn’t exactly trivial so the fact they don’t accept it is just laughable. As long as you can explain your logic clearly and concisely and write a bug free solution, that should be enough. Go interview at Meta when the hiring freeze is over. Their bar is much more reasonable
@@crackfaangyeah I still can’t figure out how to do this iteratively lmao. I think they were interviewing me with no intent of passing me because it was like week 6 of their two week hiring freeze. Probably would hurt their stock value if people found out it was an indefinite freeze so they kept “interviewing” people.
Amazing explanation, Thanks for the content . Here is one more easy solution : Idea : Group the nodes with same height Steps: 1.Find the height of a given node 2.add a simple dictionary to append the values with same height. Solution: ans=collections.defaultdict(list) def maxDepth(node): nonlocal ans if node==None: return 0 lh=maxDepth(node.left) rh=maxDepth(node.right) height=max(lh,rh)+1 ans[height].append(node.val) return height maxDepth(root) return ans
Can we use a topological sorting here? I mean we can create with edges from child node to parent node and essentially do level order topological sort! Please correct me if I am wrong here!
Ever since Python 3.6 all standard dictionaries are basically OrderedDicts under the hood aka they preserve insertion order so when you call .values() it should return them in the order they were added to the dictionary.
Leetcode has a feature where it shows you the most frequently asked questions in interviews by company. These are user reported, though they tend to be accurate for pretty much all the top tech companies.
MESSAGE TO FUTURE VIEWERS: Sorry it's hard to see the code for this problem. This is my very first video and I messed up the screen resolution as I still didn't know the best way to record these videos. Here is the code in case you cannot see it:
class Solution:
def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
res = collections.defaultdict(list)
def dfs(node, layer):
if not node:
return layer
left = dfs(node.left, layer)
right = dfs(node.right, layer)
layer = max(left, right)
res[layer].append(node.val)
return layer + 1
dfs(root, 0)
return res.values()
I just played the code part in fullscreen, its visible like that.
Got this question today for my Google interview. I hadn't seen this video yet, but it was pretty easy to see it was Post-Order traversal, but when I said that, my interviewer struck me down and said it wouldn't work. He also said it would only work iteratively. So I absolutely bombed, because I couldn't think of a solution that didn't involve Post-Order traversal. He said near the end that I had to get the reverse height of the tree (so leaves are zero), and then delete the leaves that way, but iteratively. Couldn't figure it out.
Wow, Google interviewers are STILL total dickheads. Honesty an interview there is either going to be an assessment of your problem solving/communication abilities or a dick measuring content where the interviewer tries to show off how smart he/she is by wanting some obscure solution. Unfortunately you got the later.
It shouldn’t matter how you solve the question. The recursive solution isn’t exactly trivial so the fact they don’t accept it is just laughable. As long as you can explain your logic clearly and concisely and write a bug free solution, that should be enough. Go interview at Meta when the hiring freeze is over. Their bar is much more reasonable
@@crackfaangyeah I still can’t figure out how to do this iteratively lmao. I think they were interviewing me with no intent of passing me because it was like week 6 of their two week hiring freeze. Probably would hurt their stock value if people found out it was an indefinite freeze so they kept “interviewing” people.
the walkthrough helped a lot with conceptualization of your solution! thank you so much
No problem! Glad you found the content useful
This is amazing! Perfect walkthrough with an example!
Thanks for the kind words. This was my first video and I can definitely look back at how nervous and bad at explaining things I was haha
I love the layer explanation, really cool, thank you
Amazing explanation, Thanks for the content .
Here is one more easy solution :
Idea : Group the nodes with same height
Steps:
1.Find the height of a given node
2.add a simple dictionary to append the values with same height.
Solution:
ans=collections.defaultdict(list)
def maxDepth(node):
nonlocal ans
if node==None:
return 0
lh=maxDepth(node.left)
rh=maxDepth(node.right)
height=max(lh,rh)+1
ans[height].append(node.val)
return height
maxDepth(root)
return ans
Thanks! this is very intuitive
great explaination with a code walk thru, you deserve move views. way too many youtubers just read the question and code it up and call it a day.
Thank you for the kind words! Let me know if there’s any videos you’d like me to make and subscribe so you don’t miss future uploads
Can we use a topological sorting here? I mean we can create with edges from child node to parent node and essentially do level order topological sort!
Please correct me if I am wrong here!
does map preserves correct ordering
Thank you for uploading this. This is amazing. Very clean and detailed the real interview-like video.
I’m glad you enjoyed the video! This was my first one and definitely a bit nervous on this one haha
great explanation!
dictionaries are hash tables. isn't the return value of res.values() random?
Ever since Python 3.6 all standard dictionaries are basically OrderedDicts under the hood aka they preserve insertion order so when you call .values() it should return them in the order they were added to the dictionary.
Your explanation is soo clear! Thank you!
Glad it was helpful!
Thanks for this! Super clear explanation.
super a plus explnation love it
Thank you for the kind words! Let me know if there’s any videos you’d like me to make and subscribe so you don’t miss future uploads
'layer' param not needed, when you reach a null node just return 0
Great explaination! Thanks. Please zoom in on the code..its hard to read that.
Thanks for the support! This was my first video and I messed up the resolution. I’ll post the code in the comments soon
Cool 😎
great explanation. clean code. Thanks a lot!
Thanks for your support! Make sure to subscribe so you don’t miss future videos
amazing
Such an amazing explanation. Thank you!
Thanks, glad you enjoyed the video
Explanation of recursion is quite good...could u plz enhance the quality of the video? It's hardly visible
Sorry about that, check the pinned comment for the video. I've copy pasted the code
A+ explaination
thank you for amazing explanation.
Thanks for the kind words! Let me know if there’s any videos you’d like to see and subscribe so you don’t miss future uploads
nice reverse engineering solution but I don't think i can do all these in the interview lol
perfect!
Thanks for the video. I am curious as to how you know that this question is Google's most asked? Is there a source for frequently asked questions?
Leetcode has a feature where it shows you the most frequently asked questions in interviews by company. These are user reported, though they tend to be accurate for pretty much all the top tech companies.
screen is too small in leetcode page
Ah yes apologies it was my first video uploaded and I recorded in 1440p instead of 1080p. When I get home from vacation I’ll post you the code
I hardly can u the code in the end of the video :S sorry
First video sorry, I zoom in more now