dhineshkumar007
BAN USER- 0of 0 votes
AnswersGiven a tree as below.
- dhineshkumar007 in India
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
Create a linked list as follows:
1->5->6
2->9->10->12
3->11->13->14
4->NULL
8->NULL
7->NULL
15->NULL| Report Duplicate | Flag | PURGE
Software Engineer / Developer
Magic Number=1
for(i = 1;i<n;i++)
{
temp =MagicNumber;
MagicNumber = temp*10 + temp;
}
Here the timecomplexity is o(n)
- dhineshkumar007 June 03, 20131) Here the sum is always first number in array - last number in array for the subsequent array.
2) So we have to find the first number and last number in the previous array.
3) For that we have to find a magic number which is as follows:
Iteration1: 1
which means 1st number = 1*a[0] ;second number = 1*a[n-1]
Iteration2: 10 +1 =11
which means 1st number = 1*a[0] -1*a[1] ; 2nd Number = 1*a[n-1] -1 *a[n-2];
Iteration3: 110 +11 =121
which means 1st number = 1*a[0] -2*a[1]+1*a[2] ; 2nd Number =1*a[n-1] -2 *a[n-2]+1*a[n-3]
Iteration4: 1210+121 =1331
Return firstnumber - secondnumber;
The tree is {1 }
{ 2 3 }
{ 4 5 6 }
1) Store the tree in an array by using modified BreadthFirstSearch(but dont remove any node from the array).
So the tree {1
2 3
4 5 6}
will be stored as 1 * 2 3* 4 5 6*.
2) Now in the array if the element is not '*' make its rightnode as the next element in the array, if the next element is '*' assign 'NULL.
For the following sequence,
7-8-4-3-6-3-6-3-6-3-6-1-9-12-9-12-9-12-9-12-9-7-8-4-7-8-4 we do not need the maximum page visit but only the sequence. Your algo will get 3,6 and 9 which is not required at all but the seqnce req is 7-8-4
In your algo, sequence 100->11->12 and 1001->1->12 would have the same key. So use any special character b4 each n every page.
- dhineshkumar007 December 20, 2012whitespacecount=0;
string= given string;
Step1: Iterate thro the string by each and every character.
If( string[i]==' ')
{
If (IsNotSplCharacter(string[i-1]))
whitespacecount++;
}
else
string[i-whitespacecount]= string[i];
Complexity is O(n).
For a single user, if there are more than 3 page visits , then calculate the sequence as follows:
1 2 3 4 5
12 3
234
345
Assuming that the log file is sorted by time.
eg:
Time user page
1 dk 2
1 sp 2
2 dk 3
3 dk 5
2 sp 3
3 sp 5
Approach with Minimal memory usage:
Step1 : Find and store all users O(n)
Step2 :For Each user, Iterate through the file. (users * O(n))
Create a string with page seq like A2B3C5
use this string as Hashkey and increment the value for each time the seq occurs.
Step3: In the HashMap, find the key with the highest value and extract the page sequence from the key. eg: 2->3->5 from A2B3C5
For less time complexity,
step1: store all the records in a structure Array { char *name, int page,} , and sort the structure array by name.
Step2 : Iterate through the structure array only once. (O(n))
Create a string with page seq like A2B3C5
use this string as Hashkey and increment the value for each time the seq occurs.
Step3: In the HashMap, find the key with the highest value and extract the page sequence from the key. eg: 2->3->5 from A2B3C5
For the given problem, we have start from the station N and proceed towards n-1,n-2 till 1.
The distance from n to n-1 is always n.
station 5 : Fill 5 litres and travel 5 km towards station 4
station 4: Gas will be over and fill 4 litres and travel 4km towards station 3 .
Likewise repeat till you reach 1.
If the tree is a complete binary tree, then its N!
- dhineshkumar007 December 18, 2012PrintAncestor(tree * node, int Matrix[][], int parentstack[],int n)
{
... int val,temp,i;
... if (node == NULL)
... return;
... else
... {
... ...val = node->val;
... ... for(i=0;i<n;i++)
... ...{
... ... ...temp =parentStack[i];
... ... ...Matrix[temp][val]=1;
... ...}
... ...parentStack[n] = val;
... ...printAncestor(node->left, Matrix[][], ParentStack, n++)
... ...printAncestor(node->right, Matrix[][], ParentStack, n++)
...}
}
Pseudocode:
1) Create a BST.
2) Whenever a node becomes bigger than the parent node, traverse through the tree(which has only left childre) and for all its children print the current node as the next bigger node.
3) Delete all nodes smaller than current node.
4) Repeat the same process.
Eg:
1) 2
... / \
2) 2
... \
... 5
Now print 2 ->5 and delete 2.
3) 5
... /
... 3
... ... \
... ... ... 4
Now print 3->4 and delete 3.
4) 5
... /
...4
5) 5
... / \
... 4 6
Now print 5->6 and 4->6 and delete 5 and 4
Now it becomes,
6) 6
... /
... 1
Now once array becomes null, traverse through the tree and print -1.
We have to traverse the array by summing up till we reach an element that is smaller than the previous element.
- dhineshkumar007 June 19, 2015Then we have to put it in a struct {int lastnum,int sum};
lastnum is the last greatest no in the sequence and sum is the sum of the sequence.
Then after finding the element that is smaller, create another structure and do the same. Now for each element compare with all the structure if the lastnum is smaller than the current no, then update sum and lastnum.
Finally iterate through the structure and return the structure with largest sum.