Note: I forgot to mention that lock/unlock methods do not need to be thread-safe. A real-world implementation of tree locking in databases would mostly have to be thread-safe, but I think it would be very domain-specific to be a general interview question. 6:38 - Space complexity of the "lock()" function is O(1) but space complexity of the entire tree goes up by O(n) during its creation due to the added fields. Don't forget to explain this detail, as I forgot here!
Let's say you are running the lock/unlock in a multi core machine. Now you want to let multiple threads to run lock() simultaneously. As we saw in your part of question , locking a node has multiple validations inside. Will doing lock on two nodes cause a race condition. If yes, how will you solve it. In short, how do make the lock() function thread safe? Multiple threads running it simultaneously shouldn't not affect the correctness. Note that the critical sections should be granular. Don't create any big transaction blocks that will make parallelism suffer. Tomorrow is my hackathon round for the same company can you please send me some solution for this question because they might ask me same question because they doing same from past 4 years
and this question is not database heavy position question this is for freshers Software developer position they ask this question in hackathon every year(hackathon is a second interview round in JusPay)
@@shrad6611 Ok it's not a hard one as I thought it would be. You just need to use read/write mutexes in the branch of the tree that you are trying to lock or checking for lockability. If you are checking to see if anything is locked, use a read mutex. If you are trying to lock something, use a read/write mutex. You only need to lock one branch since as you saw in the video, siblings of a node to be locked is irrelevant to it's lockability.
I am planning to but it's a bit low priority since thread-safe version of this is a database specific topic and not really interesting to general audience.
Would love to get your insights on this, I am stuck on it for 2 days. Most probably it will appear in my interview also. I have checked solutions in other comments but it's not quite clear from it
I will share java version of the code after tomorrow lol because tomorrow is my test and my competitors also watched the code and defeat me hahahaha lol
I would expect about half an hour including discussion + code + tests (optional but good). If I was asking the more complex multi-threaded version of this question, I would expect ~45 minutes. Obviously I would ask a variation of this question so that the candidate would not end up typing everything in 5 minutes from the memory:)
I need help from you. given directed graph as input with two nodes say A, B. Need to find the minimum number of node deletes so that we can not reach A if we start to move from B to A.
I created a task for it: github.com/soygul/QuanticDev/issues/48 I'm planning on adding a code translator tool to do a rough translation of all JS code to everything else for me. We'll see how it goes.
Bro in part B Basically the idea is, if the nodes we wanna lock doesnot intersect that means are not ancestors or descendents of each other, then they can be locked simultaneously. To ensure this we need to synchronize the noed so, that it cannot be accesses by other node.But i cant get the logic behind this solution . can you please give me any hint?
Easy solution is just to use a Read/Write lock (mutex) and prevent concurrent lock attempts. A mutex-free thread-safe implementation would have to be more elaborate so I didn't code anything on that yet. Edit: This looks to be a good implementation which treats the entire tree like an immutable data structure: github.com/npgall/concurrent-trees
Note: I forgot to mention that lock/unlock methods do not need to be thread-safe. A real-world implementation of tree locking in databases would mostly have to be thread-safe, but I think it would be very domain-specific to be a general interview question.
6:38 - Space complexity of the "lock()" function is O(1) but space complexity of the entire tree goes up by O(n) during its creation due to the added fields. Don't forget to explain this detail, as I forgot here!
but JusPay ask same question that if it we can make it a thread safe
@@shrad6611 I guess this was an interview for a database heavy position. If you type the question, I can give you an answer.
Let's say you are running the lock/unlock in a multi core machine. Now you want to let multiple threads to run lock() simultaneously.
As we saw in your part of question , locking a node has multiple validations inside. Will doing lock on two nodes cause a race condition.
If yes, how will you solve it.
In short, how do make the lock() function thread safe?
Multiple threads running it simultaneously shouldn't not affect the correctness.
Note that the critical sections should be granular.
Don't create any big transaction blocks that will make parallelism suffer.
Tomorrow is my hackathon round for the same company can you please send me some solution for this question because they might ask me same question because they doing same from past 4 years
and this question is not database heavy position question this is for freshers Software developer position they ask this question in hackathon every year(hackathon is a second interview round in JusPay)
@@shrad6611 Ok it's not a hard one as I thought it would be. You just need to use read/write mutexes in the branch of the tree that you are trying to lock or checking for lockability. If you are checking to see if anything is locked, use a read mutex. If you are trying to lock something, use a read/write mutex. You only need to lock one branch since as you saw in the video, siblings of a node to be locked is irrelevant to it's lockability.
How to make thread safe, if multiple lock is happen simultaneously
@QuanticDev, can you share any idea how to make lock() and unlock() thread-safe?
Hi @QuanticDev, thank you for the video. I am wondering why you only check for ancestors if we also want to check for descendants?
In 4:26, you can watch me asking the same question than answering it in details.
Hey loved it, would be great if you can roll out an article or video on how to make it thread safe
I am planning to but it's a bit low priority since thread-safe version of this is a database specific topic and not really interesting to general audience.
Makes sense! Somehow this question is coming in a lot of interviews in india
@@pankajkaushik913 Is it a database developer company? Or a big-data company maybe?
@@QuanticDev nope it's a fintech company, and they are asking this question from fresher's
Would love to get your insights on this, I am stuck on it for 2 days. Most probably it will appear in my interview also. I have checked solutions in other comments but it's not quite clear from it
I will share java version of the code after tomorrow lol
because tomorrow is my test and my competitors also watched the code and defeat me hahahaha lol
did you able to solve it?
have you uploaded it somewhere
Can you share it now
Can u please share a thread safe version of the code
You can find it in other comments of the video. Thread-safe implementation will greatly depend on the question.
can you plz give the javascript code for upgrade function as well
How to make it thread safe ??
Nice, informative video! How much time would you expect to give a candidate to solve this?
I would expect about half an hour including discussion + code + tests (optional but good). If I was asking the more complex multi-threaded version of this question, I would expect ~45 minutes. Obviously I would ask a variation of this question so that the candidate would not end up typing everything in 5 minutes from the memory:)
Very well explained, thank you!
Sir if you have time could you please explain this question.
how to make it thread safe without using synchronous?
did you get the solution?
I need help from you.
given directed graph as input with two nodes say A, B. Need to find the minimum number of node deletes so that we can not reach A if we start to move from B to A.
What if we call two nodes, will we encounter any inconsistency in this code??
My sample code is for single-threaded use only. You could implement thread-safety with some simple read/write mutexes though.
could you please convert the code into python or c++?
I created a task here and will do it when I have the time: github.com/soygul/QuanticDev/issues/48
Ma'am if you have time could you please explain this question.
Explained well but can you write the code in C++?
I created a task for it: github.com/soygul/QuanticDev/issues/48
I'm planning on adding a code translator tool to do a rough translation of all JS code to everything else for me. We'll see how it goes.
That's really helpful thank you 😁👍
Sir if you have time could you please explain this question.
Could you share how to implement multithreading in this question without using semaphores or mutex, companies are specifically asking not to use them?
can you please give me hint how to do thread safe in lock ?
Bro in part B Basically the idea is, if the nodes we wanna lock doesnot intersect that means are not ancestors or descendents of each other, then they can be locked simultaneously. To ensure this we need to synchronize the noed so, that it cannot be accesses by other node.But i cant get the logic behind this solution . can you please give me any hint?
Can you provide this code in C++ please
I will add an auto code translator tool. Until then, you can use a JS->C++ converter yourself. You'll have to Google a bit to find a good one.
@@QuanticDev sir this code is not working for the siblings condition , what to do for that please help me out
Sibling condition? There is no condition for siblings in the question.
can u give a thread-safe solution to the problem if u have solved it..
Easy solution is just to use a Read/Write lock (mutex) and prevent concurrent lock attempts. A mutex-free thread-safe implementation would have to be more elaborate so I didn't code anything on that yet.
Edit: This looks to be a good implementation which treats the entire tree like an immutable data structure: github.com/npgall/concurrent-trees
All heroes don't wear capes.
I'm kinda amazed that companies are still using this question.
@@QuanticDev Yes. I was preparing for Juspay where I encountered this question.
Btw I am finding your series very helpful. Thank you very much.
My pleasure.
@@MadForCs16 bro can i contact u for details of juspay hackathon