Cisco Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Semaphore availableSem = 1000;
Semaphore usedSem = 0;
int A[1000] = {1001, 1002, ,,,, 2000};
int start = 0;
int end = 999;
int allocate_token()
{
int retToken = 0;
p(availableSem);
retToken = A[start];
start = (start+1)%1000;
v(usedSem);
}
void free_token(int token)
{
p(usedSem);
end = (end+1)%1000;
A[end] = token;
v(availableSem);
}
take 2 semaphores freetoken(initialized to 1000) and allocatedtoken(initialized to zero) one global variable tokennumber(intialized to 1000) and one mutex m to provide mutual exclusion on token number
int allocatetoken()
{
wait(freetoken)
wait(m)
return tokennumber++;
signal(m)
sigal(allocatedtoken)
}
void freetoken()
{
wait(allocatedtoken)
wait(m)
return --tokennumber;
signal(m)
sigal(freetoken)
}
I think its producer consumer problem variation only
I think the buffer should be considered as circular queue.
Initialise the tokennumber with -1.
and inside allocatetoken()
tokennumber=(++tokennumber)%1000 + 1001.
Say all tokens are allocated and now token no. 1002 is freed, how will you reallocate this token?
@manan...it will check in allocatetoken to find out which token is free ..use for loop to check which token is free.... u can use for loop in wait() function only...
It is a variation of producer-consumer problem.
How about this.
Use a Hashtable with two fields.
(Token Number range(1001,2000) and Status(Free or Busy))
hashtable ht;
- razorf9 July 05, 2012