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!

@shrad6611

3 жыл бұрын

but JusPay ask same question that if it we can make it a thread safe

@QuanticDev

3 жыл бұрын

@@shrad6611 I guess this was an interview for a database heavy position. If you type the question, I can give you an answer.

@shrad6611

3 жыл бұрын

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

@shrad6611

3 жыл бұрын

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)

@QuanticDev

3 жыл бұрын

@@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.

@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?

@QuanticDev

3 жыл бұрын

In 4:26, you can watch me asking the same question than answering it in details.

can you plz give the javascript code for upgrade function as well

How to make it thread safe ??

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.

Very well explained, thank you!

@harshsharma4351

2 жыл бұрын

Sir if you have time could you please explain this question.

What if we call two nodes, will we encounter any inconsistency in this code??

@QuanticDev

3 жыл бұрын

My sample code is for single-threaded use only. You could implement thread-safety with some simple read/write mutexes though.

Can u please share a thread safe version of the code

@QuanticDev

3 жыл бұрын

You can find it in other comments of the video. Thread-safe implementation will greatly depend on the question.

how to make it thread safe without using synchronous?

@oswinrozario7442

Жыл бұрын

did you get the solution?

Nice, informative video! How much time would you expect to give a candidate to solve this?

@QuanticDev

4 жыл бұрын

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:)

Hey loved it, would be great if you can roll out an article or video on how to make it thread safe

@QuanticDev

2 жыл бұрын

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.

@pankajkaushik913

2 жыл бұрын

Makes sense! Somehow this question is coming in a lot of interviews in india

@QuanticDev

2 жыл бұрын

@@pankajkaushik913 Is it a database developer company? Or a big-data company maybe?

@pankajkaushik913

2 жыл бұрын

@@QuanticDev nope it's a fintech company, and they are asking this question from fresher's

@pankajkaushik913

2 жыл бұрын

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

could you please convert the code into python or c++?

@QuanticDev

3 жыл бұрын

I created a task here and will do it when I have the time: github.com/soygul/QuanticDev/issues/48

@harshsharma4351

2 жыл бұрын

Ma'am 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?

@CodeMap01

2 жыл бұрын

can you please give me hint how to do thread safe in lock ?

@CodeMap01

2 жыл бұрын

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?

That's really helpful thank you 😁👍

@harshsharma4351

2 жыл бұрын

Sir if you have time could you please explain this question.

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

@iamritam

2 жыл бұрын

did you able to solve it?

@mickyman753

2 жыл бұрын

have you uploaded it somewhere

@ankitakataria4114

Жыл бұрын

Can you share it now

can u give a thread-safe solution to the problem if u have solved it..

@QuanticDev

3 жыл бұрын

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

Can you provide this code in C++ please

@QuanticDev

3 жыл бұрын

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.

@rajkrishnabolisetty2596

3 жыл бұрын

@@QuanticDev sir this code is not working for the siblings condition , what to do for that please help me out

@QuanticDev

3 жыл бұрын

Sibling condition? There is no condition for siblings in the question.

Explained well but can you write the code in C++?

@QuanticDev

3 жыл бұрын

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.

All heroes don't wear capes.

@QuanticDev

3 жыл бұрын

I'm kinda amazed that companies are still using this question.

@MadForCs16

3 жыл бұрын

@@QuanticDev Yes. I was preparing for Juspay where I encountered this question.

@MadForCs16

3 жыл бұрын

Btw I am finding your series very helpful. Thank you very much.

@QuanticDev

3 жыл бұрын

My pleasure.

@subbareddy285

3 жыл бұрын

@@MadForCs16 bro can i contact u for details of juspay hackathon