Microsoft Interview Question Software Engineer / Developers
You are forgetting that , the tasks are to be enequed and dequeued at run time ,dynamically. You dont have the entire list to at ur hands to sort as u said. !
Both enque and dequee should be run under lock conditions. Both functions must be mutually exclusive. Since both functions might modify the head if they are not serialized using same lock.
For enque, you have to scan the list anyway in order to reach to the end for inserting this new task to the back of the list. I dont see any problem with enqueue here
1. dequeue - it makes sense to sort the tasks according to the decreasing order of their priorities and hence always eject the first task from the queue. when u eject the task, add its task ID to the end of another list, call it "a completed task list".
2. enqueue -
a) no dependencies for the task at end? traverse the list while the priority of the task at hand is "lesser than or equal to" the tasks being traversed. add it to the present location reached after the aforementioned traversal.
b) task at hand has dependencies?
4 cases:
(i) all dependencies in present queue - easy doncha think? - among all dependencies, get the one with the lowest priority and insert the "task at hand" AFTER it.
(ii) all dependencies in "completed task list" - hell! this is a cakewalk, as described in a) above.
(iii) few here, few there - hmm now it gets interesting - but still its the same as case (ii) .
(iv) few here, few there, few NOT YET entered by user!!!! - woah! u figure it out! no just kiddin! - this will take us back to dequeue operation, we certainly cannot do anything more here, i mean come on!
1. dequeue (modification) - now when we are about to eject a task, we observe all its dependencies, even if ONE of its dependencies is NOT present in "completed task list", i dont have a choice but to block myself and also the rest. when the "task that im dependent on" comes in, i push it the front of the "present queue". this blocking behavior has to be handled by a flag, if the flag is turned on see below.
2. enqueue (addition) - now there will be 5 cases with the latest case becoming our first case.
(v) - if the flag is turned ON AND if the "task at hand" is the reason behind turning the flag ON then I go to the front of the queue.
FOR ALL THIS TO BE HANDLED - I need to know the EXACT NUMBER OF DEPENDENCIES for each task that comes in for the enqueue-ing.
whew!! awesome question by the way...loved it!
editing the 2 cases described in the enqueue operation above, a little bit. forgot to mention one thing -
(i) all dependencies in present queue - easy doncha think? - among all dependencies, get the one with the lowest priority and insert the "task at hand" AFTER it
<edit>ANDDDDD also follow a) above.</edit>
(iii) few here, few there - hmm now it gets interesting - but still its the same as case <edit> (i) as described above </edit>.
sorry about that.
If anyone's interested, i implemented the above algo i described. no error input checking has been done.
#include <stdio.h>
typedef struct node_{
int ID ;
struct node_* next;
int priority;
int *dependency;
int numDeps ;
} node ;
typedef node* node_ptr ;
void display(node_ptr head, int *isCompleted, int N){
if(head==NULL){
printf("\n\nempty present queue\n");
}
else{
node_ptr cur = head ;
printf("\n\nCurrent Queue\n");
while(cur!=NULL){
printf("%d ",cur->ID);
cur=cur->next ;
}
}
printf("\n\nCompleted List\n");
int i, completed=0;
for(i = 0 ; i < N ; i++){
if(*(isCompleted+i) == 1){
printf("%d completed\t",i+1);
completed++ ;
}else{
printf("%d incomplete\t",i+1);
}
}
printf("\n\n");
if(completed==N){
printf("all tasks completed, my job here is done\n\n\n\n\n");
exit(0);
}
}
/*
* This is basically a priority based linked list insertion method
* This method will be called if there are no dependencies for the task at hand.
* Also, will be called when we just want to use a regular linked list insertion at various situations.
*/
void insert(node_ptr *head, node_ptr *T){
node_ptr cur, prev ;
if( (*head) == NULL ){
printf("queue empty, entering task #: %d as the only task in the present queue\n",(*T)->ID);
(*head) = (*T) ;
(*T)->next = NULL ;
}
else {
prev = NULL ;
cur = *head ;
while( cur!=NULL && (*T)->priority >= cur->priority ){
prev = cur ;
cur = cur->next ;
}
if(cur == *head){
printf("inserting task# %d into the front of the queue\n",(*T)->ID);
(*head) = (*T) ;
(*T)->next = cur;
}
else if(cur==NULL){
printf("inserting task# %d into the end of the queue\n",(*T)->ID);
prev->next = (*T) ;
(*T)->next = NULL ;
}
else{
prev->next = (*T) ;
(*T)->next = cur ;
}
}
}
/* This is a method which is similar to the above insertion method. This will be called ONLY when the task
* has one or more dependencies. As a result, those dependencies will result in a different kind of an insertion.
* I call it special insert. Pretty Lame!
*/
void specialInsert(node_ptr *head, node_ptr *T){
int i,lowestPrio=-99999,depID ;
node_ptr cur, prev, start ;
start = NULL ;
for(i=0; i<(*T)->numDeps; i++){
depID = (*((*T)->dependency)+i) ;
cur = *head ;
while(cur != NULL && cur->ID != depID){
cur = cur->next ;
}
if(cur == NULL ){
printf("task #%d has not yet been entered by the user\n",depID);
}
else if(cur->priority > lowestPrio ){
lowestPrio = cur->priority ;
start = cur ;
}
}
if(start==NULL){
printf("some/all of the task id #:%d's dependencies have not been entered or just"
"not found in the present queue, be aware that they may be present in the"
"completed list,it is also possible that the queue may be empty, so doing a regular insert\n",(*T)->ID);
insert(head,T);
}
else{
printf("found the lowest priority dependency to be %d, doing a regular insert after this task\n",start->ID);
prev = NULL ;
if(start->next != NULL){
printf("priority based insertion will now begin....\n");
//very important to save the start node because we might have to insert the current task immediately
//after its lowest priority dependency
prev = start ;
cur = start->next ;
while( cur!=NULL && (*T)->priority >= cur->priority ){
prev = cur ;
cur = cur->next ;
}
if(cur==NULL){
printf("inserting task# %d into the end of the queue\n",(*T)->ID);
prev->next = (*T) ;
(*T)->next = NULL ;
}
else{
prev->next = (*T) ;
(*T)->next = cur ;
}
}
else{
printf("the lowest priority dependency being %d could be the only task in the present queue"
"or could be the last task in the present queue and insertion will take place "
"at the end of the queue\n",start->ID);
start->next = (*T) ;
(*T)->next = NULL ;
}
}
}
/*This method checks if the present queue was blocking due to some task waiting on the task which is being enqueued.
* Among all the tasks dependent on the current task, the task with the highest priority is picked and inserted BEFORE it.
*/
node_ptr checkBlockingInsert(node_ptr *head, node_ptr *T){
if((*head)==NULL){
return NULL ;
}
int i ;
node_ptr cur , prev , bestFit, prevBestFit ;
int highestPrio = 99999 ;
bestFit = NULL ;
prevBestFit = NULL ;
prev = NULL ;
cur = *head ;
while(cur != NULL){
for(i = 0 ; i < cur->numDeps ; i++){
if( *((cur->dependency)+i) == (*T)->ID && cur->priority < highestPrio ){
highestPrio = cur->priority ;
bestFit = cur ;
prevBestFit = prev ;
break ;
}
}
prev = cur ;
cur=cur->next ;
}
if(bestFit == NULL ){
printf("No Task waiting on the present task\n");
return NULL ;
}
printf("found the blocking best fit %d, the task will be inserted before this in the queue\n",bestFit->ID);
if(prevBestFit == NULL ){
printf("inserting task at the front of the queue\n") ;
(*T)->next = bestFit ;
(*head) = (*T) ;
}
else{
prevBestFit->next = (*T) ;
(*T)->next = bestFit ;
}
return bestFit ;
}
void enqueue(node_ptr *head, node_ptr *T, int *isCompleted){
//Check if the present task to be enqueued was blocking the current queue
node_ptr beforeMe = checkBlockingInsert(head, T) ;
if(beforeMe != NULL){
printf("blocking insertion done, it was inserted before task #%d\n",beforeMe->ID) ;
return ;
}
if( (*T)->numDeps == 0 ){
printf("Task#: %d being enqueued has no dependencies\n",(*T)->ID);
insert(head,T);
return ;
}
node_ptr cur = (*head);
int i, count = 0, depID, tempCount = -1;
printf("scanning present queue for dependencies of task #%d\n",(*T)->ID);
while(cur!=NULL ) {
for(i=0; i<(*T)->numDeps; i++){
if( cur->ID == (*((*T)->dependency)+i))
count++ ;
}
cur = cur->next ;
}
//store temporary count, we need to know if all its dependencies are in the completed list or not
tempCount = count ;
if(count == (*T)->numDeps){
printf("all dependencies for task #%d found in the present queue\n",(*T)->ID);
specialInsert(head,T);
return;
}
else if(count < (*T)->numDeps ){
printf("scanning the completed list for dependencies of task #%d\n",(*T)->ID);
for(i=0; i<(*T)->numDeps; i++){
depID = (*((*T)->dependency)+i) ;
//ID's start at 1. so we subtract 1
if(isCompleted[depID-1] == 1)
count++ ;
}
}
if(tempCount == 0 && count == (*T)->numDeps ){
printf("all dependencies for task #:%d were found in the completed list\n",(*T)->ID);
insert(head,T);
}
else if(count < (*T)->numDeps ){
printf("task #%d is waiting for some task which has neither been enqueued nor dequeued\n",(*T)->ID);
printf("among its dependencies we will get the lowest priority for now and insert it after by using the"
"priority linked list insertion method\n ");
specialInsert(head,T);
}
}
void dequeue(node_ptr *head , int *isCompleted){
if((*head)==NULL){
printf("queue underflow\n") ;
return ;
}
int i , depID;
for(i = 0 ; i < (*head)->numDeps ; i++ ){
depID = *( ( (*head)->dependency ) + i );
//ID's start at 1. so we subtract 1
if(isCompleted[depID-1] == 0 ){
printf("Task #:%d needs to wait for Task #:%d, entering blocking mode\n",(*head)->ID, depID);
return ;
}
}
//ID's start at 1. so we subtract 1
isCompleted[(*head)->ID-1] = 1 ;
if((*head)->next==NULL){
printf("Only task, after dequeue of task %d, queue will be empty\n",(*head)->ID) ;
(*head) = NULL ;
return ;
}
printf("Task %d dequeued\n",(*head)->ID) ;
(*head) = (*head)->next ;
}
node_ptr prepareTask(int task_ID, int priority, int numDeps){
node_ptr task = (node_ptr) malloc (sizeof(node)) ;
task->ID = task_ID ;
task->priority = priority ;
task->numDeps = numDeps ;
task->next = NULL ;
task->dependency = (int*) malloc(sizeof(int) * numDeps);
int i;
fflush(stdin);
for(i = 0 ; i < numDeps ; i++){
printf("Enter Dependent #%d\n",i+1);
scanf("%d",(task->dependency+i));
fflush(stdin);
}
return task ;
}
int main(){
printf("Enter number of tasks\n");
int N;
scanf("%d", &N);
fflush(stdin);
int *isCompleted = (int*) calloc (N, sizeof(int)) ;
if(!isCompleted)
exit(1);
node_ptr head = NULL ;
node_ptr task ;
int i, task_ID, numDeps, priority ;
char ch ;
while(1){
fflush(stdin);
printf("Enter \nE for enqueue\nD for Dequeue\nX for exit\n");
scanf("%c",&ch);
fflush(stdin);
if(ch=='x' || ch=='X'){
free(isCompleted);
exit(0);
}
if(ch=='e' || ch == 'E'){
printf("Enter task ID \n");
scanf("%d",&task_ID);
fflush(stdin);
printf("Enter Priority(1-highest %d-lowest) for task id:%d\n",N,task_ID);
scanf("%d",&priority);
fflush(stdin);
printf("Enter Number of dependencies for task id:%d\n",task_ID);
scanf("%d",&numDeps);
fflush(stdin);
task = prepareTask(task_ID, priority, numDeps);
enqueue(&head,&task,isCompleted);
}
else if(ch=='d' || ch=='D'){
dequeue(&head, isCompleted);
}
display(head, isCompleted, N);
}
return 0;
}
does it need to be so complicated?
1)enqueue: sort according to priority. o(n)
2)dequeue: dequeue the one with the highest priority(o(1)), then check all its dependent tasks and use recursion the dequeue them.
I use linked list
Enqueue:-just linear seacrh for itz appropiate pos using itz priority
Dequeue:-check for the current task dependecy list...
take the 1st element in dependency list...
suppose curr event is 1 n 1st dependent task s 4..
transverse the queue till 4 is reached and decrement the priority f each element in the queue.
thus the priority f 4th event becomes 3 nw
insert the curr event aftr this new 3rd event and chng its prority to 4 remove 4 from dependency list,...call enqueue again
if no dependency then perform the curr task...
Its not as easy as it seems.
- Flying Machine March 09, 2008