Hackathon part A solution
Please visit Hackathon part A solution link and go through that, upvote that and come back (so that it will be easy to track the discussion).
Hackathon part B
Interviewer shared Hackthon part A solution that was submitted by me during Hackathon Part A.
Question1 : Explain the logic that you used to solve Hackathon part A question and its time and space complexity?
Ans :
Time complexity
(1) lock operation -> O(logm(n)) -> log n base m
logic -> we will check all descendants are locked or not (in O(1) means constant time) and ancestors are locked or not by exploring each ancestor one by one (in logm(n)) time
(2) unlock -> O(logm(n)) -> log n base m
logic -> if given node is locked and locked by same id then we will inform all anesctors about its unlocking in logm(n) by exploring
each ancestor one by one.
(3) upgrade -> O(no of locked descendants*logm(n))
logic -> check one or more than one descendants are locked by same Id or not (if 5 descendants are locked then we can check in O(5) time)
check 0 ancestors are locked or not in O(logm(n)) time
lock the node in O(logm(n)) time and unlock all descendants in O(no of locked descendants*logm(n)) time
Space complexity
O(n)Question2 : Can you improve these complexities?
Ans :
in this TreeNode structure we are using set here we can use unordered-set to optimise its time complexity.
Question3 : Yes. So what will be the final complexity after this change? Same or different
ans: Time complexity will be same but code will be faster.
Question4 : Part-B Question :
Let’s say you are running the lock/unlock in a multi core machine. Now you want to let multiple threads to run lock() As we saw in part A, 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. -Try to make the critical sections more granular.
ie. don’t create any big atomic/synchronised blocks that will make parallelism suffer.
Consider each operation is atomic.
I asked one question
--(1) we will run lock method only using multiple thread and what about remaining 2 methods unlock and upgrade?
--(1) ans : we just care about lock method in part B hackathon
Ans: we can lock complete tree and we can run any method using multithread.
interviewer : you are not allowed to lock complete tree
interviewee : using synchronized we can lock lock method only.
interviewer: multiple threads should be allowed to lock different nodes of the tree and if you are making the function synchronised , you are eventually not allowing other threads to work on tree. But in our case, all the threads should be allowed to work at the same time
interviewee: If we lock particular TreeNode then this may cause race condition so we can’t lock Particular TreeNode (Particular TreeNode menas node that we want to lock) so we have to define some critical section.
interviewer: in which cases there will be a race condition?
interviewee: Particular node will inform all its ancestor about its locking and 2 descendants are locked at same time and informing the same ancestor (this may cause race condition)
interviewer: ok, any other case where there will be race condition?
interviewee: 2 diff nodes are being locked then they will always have atleast one common ancestor (so i think informing its ancestor is the only one race condition according to my code)
interviewer: ok so just one race condition?
interviewee: and in lock method we are also checking either any descendant is locked or not and this may also cause race condition so till now i can think 2 race condition only
interviewer: Ok think about solving those conditions and we will meet after lunch (time was around 1:00 PM)
interviewee:
1st solution
we can lock complete Tree
2nd solution
lock the critical section using mutex lock.interviewer: Mutex will eventually introduce a lag in operations, so we are not allowed to use mutex/semaphores
interviewee: we can implement our own mutex
interviewer : how you will do that?
interviewee: i implemented own mutex using builtin atomic method __sync_lock_test_and_set, __sync_lock_release
#include<unistd.h>
class Mutex{
public:
Mutex{
isLocked= UNLOCKED_VALUE;
}
void lock(){
while(__sync_lock_test_and_set(&isLocked, LOCKED_VALUE)==LOCKED_VALUE);
// while(1){
// if(isLocked==UNLOCKED_VALUE){ // 17 and 18 must be atomic
// isLocked=LOCKED_VALUE;
// return;
// }
// }
}
void unlock(){
__sync_lock_release(&isLocked);
// isLocked=UNLOCKED_VALUE;
}
bool try_lock(){
return __sync_lock_test_and_set(&isLocked, LOCKED_VALUE)!=LOCKED_VALUE;
// if(isLocked==UNLOCKED_VALUE){
// isLocked=LOCKED_VALUE;
// return true;
// }
// return false;
}
private:
int LOCKED_VALUE =1;
int UNLOCKED_VALUE=0;
volatile int isLocked;
};implemented using spinlock
Interviewer switched back to the previous question and asked, Implement thread safe concurrent lock method without using any atomic method, mutex, semaphores, synchronized keywork
interviewer gave some hints then we reached to the below code.
struct TreeNode{
string name;
int lockedBy;
int lockedCount; // changes isLocked ( bool) to lockedCount(int)
vector<TreeNode*> childs;
TreeNode* parent;
set<TreeNode*> lockedDescendents;
}
bool lock(string name, int id){
TreeNode* r= nameToTreeNodeMapping[name];
if(r->lockedCount>0 || r->lockedDescendents.size())return false;
r->lockedCount++;
if(r->lockedCount>1){
r->lockedCount--;
return false;
}
TreeNode* par= r->parent;
while(par){
if(par->lockedCount>0 || r->lockedDescendents.size()>0){
r->lockedCount--;
TreeNode *par1= r->parent;
while(par1!=par){
par1->lockedDescendents.erase(r);
par1=par1->parent;
}
return false;
}
par->lockedDescendents.insert(r);
par=par->parent;
}
r->lockedBy=id;
return true;
}Interviewer said this solution is thread safe and it will work without any issue.
I said, i think this will create some issue, can you please give me some time to think about it?
Interviewer said okay, you can take time.
i found out many bugs in this code and asked about these bugs but i didn’t receive any response from interviewer.
Bug-1
bool lock(string name, int id){
TreeNode* r= nameToTreeNodeMapping[name];
if(r->lockedCount>0 || r->lockedDescendents.size())return false; // condition1
// point1
r->lockedCount++;//line 2
// point2
if(r->lockedCount>1){//condition3
// point3
r->lockedCount--;
return false;
}
TreeNode* par= r->parent;
while(par){
if(par->lockedCount>0 || r->lockedDescendents.size()>0){
r->lockedCount--;
TreeNode *par1= r->parent;
while(par1!=par){
par1->lockedDescendents.erase(r);
par1=par1->parent;
}
return false;
}
par->lockedDescendents.insert(r);
par=par->parent;
}
r->lockedBy=id;
return true;
}
################Code##########################
above solution will not work in below case
suppose 2 thread t1,t2 are running single core processor
threadName optype node name id
t1-> 1, india, 5
t2-> 1, india, 5
expected ans-> yes, No or No, yes ( one thread will lock india but other can’t ) but above solution may give race condition(No, No)
why expected ans is yes, No?
ans: no need to explain this
why expected ans is No, yes?
ans: t1 lock india and before returing true if context switching take place and (cpu will pick t2) t2 will check india but it is already lock so return false then t1 will return true.
steps :-
1-> t1 check condition1 (r->lockedCount>0 || r->lockedDescendents.size()) and it will become false and come to the point1
2-> than context switching take place (at point1)
3-> t2 check condition1 (r->lockedCount>0 || r->lockedDescendents.size()) it will also become false and come to the point1
4-> than context switching take place (at point1)
means both are at point1
5-> t1 run line2 (r->lockedCount become 0 to 1) and come to the point2
6-> than context switching take place (at point2)
7-> t2 run line2 (r->lockedCount become 1 to 2) and come to the point2
8-> than context switching take place (at point2)
means both are at point2
9-> t1 check condition3 it (r->lockedCount>1-> 2>1) will become true and come to the point3
10-> than context switching take place (at point3)
11-> t2 check condition3 it (r->lockedCount>1 -> 2>1) will also become true and come to the point3
12-> than context switching take place (at point3)
means both are at point3
now both will decrease r->lockedCount by 1 and return false;Bug-2
bool lock(string name, int id){
TreeNode* r= nameToTreeNodeMapping[name];
if(r->lockedCount>0 || r->lockedDescendents.size())return false; // condition1
// point1
r->lockedCount++;
if(r->lockedCount>1){
r->lockedCount--;
return false;
}
TreeNode* par= r->parent;
while(par){
if(par->lockedCount>0 || r->lockedDescendents.size()>0){ // condition2
r->lockedCount--;
TreeNode *par1= r->parent;
while(par1!=par){
par1->lockedDescendents.erase(r);
par1=par1->parent;
}
return false;
}
// point2
par->lockedDescendents.insert(r);
par=par->parent;
}
r->lockedBy=id;
return true;
}
2nd bug (major bug)
threadName optype nodeName id
t1-> 1, world, 5
t2-> 1, Asia, 5
suppose 2 thread t1,t2 are running on single core processor
expected ans-> (yes, No Or No, yes) but it may return (Yes, Yes).
1-> t1 check condition1 (r->lockedCount>0 || r->lockedDescendents.size()) and it will become false and come to the point1
2-> than context switching take place (at point1)
3-> t2 comes and enter in while loop (par pointer will point to the "world" node)// asia->parent will be world
4-> t2 will check condition2 (par->lockedCount>0 || r->lockedDescendents.size()>0) and it will become false and come to the "point2"
5-> than context switching take place (at point2)
means t1 will be at point1 and t2 will be at point2
6-> now t1 start its execution and first time while loop condition will be false ("world" node parent will be NULL) so set the value of r->lockedBy and return true
7-> t2 will run below 2 line and next time par will be NULL so it will come out from while loop.
par->lockedDescendents.insert(r);
par=par->parent;
8-> will set r->lockedBy=id; and also return true;
this may cause race condition by returning yes,yesye question bina thread locking (using mutex, semaphore etc..) ke solve hi nhi ho skta.
Now i am waiting for the interview results ...
Please upvote it and fell free to put your thoughts
thanks!!
