Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Same Tree

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 3 years ago

When multiple threads are updating ***isSame*** variable

isSame &= isSameTreeMultiThreaded(p.left, q.left, numThreads/2);
SIMILAR TO
isSame = isSame & isSameTreeMultiThreaded(p.left, q.left, numThreads/2);
  1. It reads isSame which is thread safe gives latest value due to primitive
  2. & operator with isSame variable ( one more, by the time it evaluates through recursive function, isSame variable could be outdated )
  3. Updating isSame variable which is thread safe due to primitive

But, All the above 3 steps together is not atomic.

Consider the scenario:

isSame is true by default,

  1. Thread-1 reads as true
  2. Thread-2 reads as true
  3. Thread-1 receives false from recursive function and updates it with *false
A

Anonymous

· 4 years ago

For the Space Complexity of the non-multi-threaded solution, why does the stack take O(N) space but to store nodes we need O(H)? O(N) and O(H) should be the same, right?

A

Anonymous

· 4 years ago

As a non-Java user, I expect other language solutions (python, JS, etc) presented here since they are present in the other chapters & courses. Thank you

A

Anonymous

· 4 years ago

Where is python :((

A

Anonymous

· 4 years ago

I would love a C++ solution for the thread safe questions!

Show 1 reply

Reading Progress

0%

Vote for new content