f2003062
BAN USER1. Create an array called index array which stores the indexes of elements of input array. Initialize index[i]=i for i=0 to n-1
2. Now sort the input array and while sorting also maintain the order of indexes in index array corresponds to the each element in the input array. This can be done using O(nlogn) sorting algorithm
3. Now traverse both the input and index arrays and calculate the max length for each element. This can be done on O(n) time.
Time Complexity: O(nlogn)
Space: O(n)
@CodeNameEagle:
Nice approach man. Small correction in your code. You have forgot to add carry to ptr.data in while loop. And also move the ptr to next
while(ptr != null)
{
sum = ptr.data;
ptr.data = sum%10 + carry; // added carry
carry = sum / 10;
ptr = ptr.next; // added
}
bool isBST(struct node* root) {
if(root == NULL)
return true;
if(root->left && root->data < max(root->left)) {
return false;
}
if(root->right && root->data >= min(root->right)) {
return false;
}
return isBST(root->left) && isBST(root->right);
}
int max(struct node* root) {
if(root == NULL) {
return -1;
}
while(root->right) {
root = root->right;
}
return root->data;
}
int min(struct node* root) {
if(root == NULL) {
return -1;
}
while(root->left) {
root = root->left;
}
return root->data;
}
Gr8 idea using min heap. The time complexity for this algo is:
M * O(logM) --> for constructing the initial min heap with first element of each server (M servers)
+
k * O(logM) --> Heapifying k times
= (M + k) O(logM)
Please correct me if I am wrong...! Thank you..!
The answer is 8 times two and 8 times one.. How ..? see below..!
after 1 st call to fork() -> there are 2 processes [printf not executed till now]
after 2 nd call to fork() -> there are 4 processes [printf not executed till now]
after 3 rd call to fork() -> there are 8 processes [printf not executed till now]
Till the time we have called fork() is called thrice which resulted into creating 8 processes. Now we are going to call 4 th fork().
after 4 th call to fork() -> now there are 16 processes...
Now we are going to print. This print will be executed for all 16 processes out of them 8 processes will print one and 8 processes will print two..
The order of printing ones ant twos is not guaranteed. it depends on CPU scheduling.
Please find the code below.. Please correct me if anything goes wrong. I hope it works for for all different inputs.
struct node* correctTheReversedSubListOfSortedList(struct node *root) {
struct node* ptr = root;
struct node* firstSegmentEnd = NULL; // This is the end of the first segment i.e. before the reversed list starts
while(ptr) {
if(ptr->next == NULL) break;
if(ptr->data <= ptr->next->data) {
firstSegmentEnd = ptr;
ptr = ptr->next;
} else {
// reverse the sub linked list
struct node* reverseHead = ptr; // Initially this is the start point where the reversed list start : After reversing done this will be the end of the reversed list
struct node* prev = NULL;
while(ptr && ptr->next && ptr->data > ptr->next->data) {
struct node* temp = ptr->next;
ptr->next = prev;
prev = ptr;
ptr = temp;
}
struct node* lastSegmentStart = ptr->next; // last SegmentStart is the next pointer of where the reversed list ends
ptr->next = prev; // Now ptr contains the corrected reversed list start point
reverseHead->next = lastSegmentStart; //assign the lastSegmentPart to the end of the corrected reversed list
if(firstSegmentEnd) {
firstSegmentEnd->next = ptr; // assign the ptr to firstSegmentPart
} else {
// This case hits when the input list is totally in descending order i.e. entire list is reversed
root = ptr;
}
}
}
return root;
}
Please find the program for iterative post order of a binary tree using two stacks.
One stack(say NodeStack) is for keeping the nodes, the other stack(say FlagStack) is for keeping the flag corresponding to the respective node which is on the NodeStack.
node = root;
while(1)
{
if(node)
{
NodeStack.push(node);
FlagStack.push(false);
node = node->left;
}
else
{
if(NodeStack.isEmpty()) break;
topFlag = FlagStack.pop();
if(topFlag == false)
{
FlagStack.push(true);
node = node->right;
}
else
{
node = NodeStack.pop();
print the node ..
node = NULL;
}
}
}
Note: You may ask me that the above code is using visited flag. Right..!! but here I am not keeping the visited flag in each node of the binary tree which leads to the space complexity of O(N). Here I am using another stack to keep the flags corresponding to the nodes on the first stack.
Iterative version. Slight modification in Morris Traversal.
- f2003062 May 29, 2013