Flying Machine
BAN USERGeek in the making
- 0of 0 votes
AnswersGiven a Task List of the form:
- Flying Machine
typedef struct task* task_ptr;
struct Task {
int Priority;
int *Dependency;
task_ptr next;
}
No of tasks range from 1 to N. (N know at run time)
Priority ranges from 1 to N
Dependency ranges from 0 to N. 0 means it doesnt have dependency on any other tasks. Each task can have dependency on more than 1 task.
So if task 2 has Dependency array as {1,3,5} it means it can be dequeued only after 1,3,5 are removed
You were to write two functions
1) void enqueue( task* head_list, task *T);
Which enqueues a task in the list
2) struct task* dequeue(task* head_list);
Which dequeues the task with highest priority 1st, given it has no dependency or all the dependent tasks have already been dequeued.!
Write the function in C/C++ for optimal insertion and deletion .You are allowed to use any data structure you want.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
Answersstruct Object {
- Flying Machine
// THESE FIELDS ARE ALREADY DEFINED; YOU MAY NOT MODIFY THEM
Object* next_ptr; // Next object in list; NULL if end of
list.
unsigned int ID; // unique identifier for this object.
unsigned int parent_ID; // 0, if object is root of tree.
// THESE FIELDS REPRESENT THE TREE WHICH NEED TO BE FILLED
Object* parent_ptr; // Initialized as NULL.
unsigned int child_count; // Initialized as 0.
Object** child_ptr_array; // Initialized as NULL.
} ;
Need to implement the method:
Object* convert_List_To_Tree (Object* list_head);
This returns the pointer to the root node| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Algorithm
This should run in O(n) time.
The code Anurag have told takes O(n2) time which is not acceptable
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. !
- Flying Machine March 10, 2008