Solving My Amazon Phone Interview Question

In this video I solve the question I was given during a phone interview with Amazon. The position was for an SDE 1 with AWS. Cheers!

#keeponcoding #tech #programming

DISCLAIMER: Links included in this description might be affiliate links. If you purchase a product or service with the links that I provide I may receive a small commission. There is no additional charge to you! Thank you for supporting so I can continue to provide you with free content!

[KeepOnCoding]

Let me know if you'd like to see more of these. Thinking about doing videos for Facebook, Google, and Airbnb.

[Fmus]

I would say my biggest criticism of this approach is that it leaks out of the abstraction. You have multiple static methods in this class that share a list object that is getting mutated. So, first you build a list, then you remove items from it in another function, then you check the size of the list. This makes it much harder to prove that this code is correct, and makes it a lot harder to extend. A better approach would be to make one function that takes both TreeNode roots in, and return a boolean for whether they have the same in-order traversal or not. Keep all of the state inside of this function, instead of spread out across three functions (through your lists).

[darkwoodmovies]

If you sacrifice the comforts of recursion and just use a stack, you can run the traversal in parallel on both trees and if the top of your stacks is ever mismatched, return false.

[jayeshbhoi]

Technical phone interview not only contain coding question but also have behavioral questions as per amazon LP.

[mohammedalmukhtar]

Thank you for this video, man. It's really helpful.

[ogunsanmimichael]

What about a simultaneous inorder traversal on the two trees with each tree element being compared for each iteration. If the values are not equal then return false immediately. If one tree returns no element (in the event of end of treeNodes) and the other tree still has nodes then return false too. Otherwise return true. That way you potentially reduce the number of iterations in some cases

[Zzznmop]

Could you explain why the two trees are being traversed simultaneously? It seems like the whole tree one is processed first, then using the list you populated check the second tree for the values. I realize this would not effect the big OH complexity, but it would definitely be an optimization.

Also, if anyone wants to discuss: I think worst case time complexity is linear if you traverse the longer tree first and it’s a degenerate tree, then n >m, and that means m+n < 2n, and 2n simplifies to big OH of n. The improvement reduces the worst case space complexity from O(m+n) to O(max(m, n))

[abhishekdubey]

The complexity to remove an element and rearranging the list is O(n) right?? If so then time complexity in increase with second approach. It'll be O(n*m)

[VedranGrudenic]

Not sure about iterators in Java, but in C# you would simply yield items one by one (i.e. the traversal method would return IEnumerable<Node>) and use Linq to compare the streams while they are being lazily generated. This would mean O(logN + logM) space complexity.

[georgetribiani]

Hello, nice video, just like your other videos. Any way we can find you on a LinkedIn or Twitter?

[aaronliu]

You don't need a data structure... You can just recurse through both trees.

[toekneema]

Can you explain something: since the two trees are built differently, wouldn't it reach null at different times and then throw off that base case in the inOrderCheck method?

[afsarahamad]

As we are removing 0th element every time from ArrayList will that not take O(n) for shifting elements?. I guess this algorithm will run in polynomial time not in linear, We could use LinkedList with double pointer I guess. Or with just golable index without removing from list.

[curtkeeling]

Seriously - I've been doing the software development dance for nearly 35 years. Can you explain to me what the questions around binary trees, depth first, breadth first graph traversal algorithm crap means in the real world?

[MrFTW]

I wonder if you could use threads to avoid the need of having a list 🤔. Or maybe an iterator :0

[vigneshsoap]

Shouldn't the space complexity be o(n + n+ m) since we are storing the elements from first tree in a separate list?

[riyadshauk]

I think you could be more optimal and do this in one pass, though still with the same big-O complexity, by using a slightly adapted iterative DFS using two stacks (one for each tree), and both checking that the two current nodes are equal and that neither stack is empty (else return false) inside some inOrderEquivalence(tree1, tree2) function (and after loop, return true), right? I haven't coded it, but I thought about it by drawing out the idea, and the added complexity would be in having an activeStack and a waitingStack. Whenever waitingStack is null, push onto activeStack and in-order process activeStack and waitingStack, until the waitingStack can't pop anymore either, then swap active and waiting stack with each other and continue in this manner.

[vadimkokielov]

Hey,
Have they ever asked you to describe best and worst case complexities? And to distinguish between upper bounds (O) and lower bounds (omegae) or tight bounds (theta)? Theoretical algorithmists use those precise notations but it seems to me as though in the real world they rarely need that level of precision
Thanks for the videos

[yKaramawy]

the remove from the list takes o(n)? if am not mistaken that should be o(N^2) time complixity

[sweetiea]

phone interviews are usually voice calls or video calls?