Tulley
BAN USER@KV: Correct. I didn't think of this kind of input. It can be corrected by modifying the if condition in the two inner while loop as
1. Original : if (pArray [index1] == num1)
modified : if ((pArray [index1] == num1)&&(index1 != (index2-1)))
2. Original : if (pArray [index2] == num2)
modified : if ((pArray [index2] == num2)&&((index1-1) != index2))
Its not necessary that u'll end up with leaf while inserting and also its not linear. its O(mlogn) where m=|A| and n=|B| and worst is O(mn) if both the tree are right skewed having root of A is greater then rightmost child of B. or both tree are left skewed and root of A is smaller than leftmost child of B.
- Tulley March 27, 2011Its a DP solution of O(n).
SUM=MAX{CURRENT SUM + A[i], A[i]} where 1<=i<=N
void maxSum (int* pArray, int size)
{
int sum=pArray[0], curSum=pArray[0], startInd=0, endInd=0, index=0;
for(index=1; index<size; index++)
{
if((curSum + pArray[index])> pArray[index])
{
curSum = curSum + pArray[index];
}
else
{
curSum = pArray[index];
if(sum<0)
{
startInd = endInd;
}
else
{
startInd=index;
}
}
if(sum<=curSum)
{
sum=curSum;
endInd = index;
}
}
printf("[Start Index]:%d\n[End Index ]:%d\n", startInd, endInd);
printf("[MaxSum ]:%d\n", sum);
}
Here the idea is to first find the indexes of given numbers then c which index is behind then move only that index and keep on updating the difference between these two indexes. Repeat this till array ends.
Time: O(N), Space O(1)
void minDistance (int* pArray, int size, int num1, int num2, int* firstIndex, int* secIndex)
{
int curDst=0, minDst=0x7FFFFFFF, index1=0, index2=0;
int moveFirst=1, moveSec = 1;
while ((index1<size) && (index2<size))
{
while ((index1 < size) && (moveFirst))
{
if (pArray [index1] == num1)
{
index1 ++;
break;
}
index1 ++;
}
while ((index2 < size) && (moveSec))
{
if (pArray [index2] == num2)
{
index2 ++;
break;
}
index2 ++;
}
if (index1 > index2)
{
moveFirst = 0;
moveSec = 1;
curDst = index1 - index2;
if (curDst < minDst)
{
minDst = curDst;
*firstIndex = index2-1;
*secIndex = index1-1;
}
}
else
{
moveFirst = 1;
moveSec = 0;
curDst = index2 - index1;
if (curDst < minDst)
{
minDst = curDst;
*firstIndex = index1-1;
*secIndex = index2-1;
}
}
}
}
int main ()
{
int array [] = {2,2,4,1,8,3,2,5,6,7,5,6,6,4,7,5};
int index1=0, index2=0;
minDistance (array, 16, 6, 2, &index1, &index2);
printf ("Index1 = %d, Index2 = %d\n", index1, index2);
printf ("Minimum distance b|w given num = %d\n", index2-index1);
return 0;
}
void findLocalMinima (int* pGivenArray, int* localMinArray, int* minimaCount, int start, int end)
{
int mid;
if (end-start >= 2)
{
mid = (end+start)/2;
if ((pGivenArray [mid-1] >= pGivenArray [mid]) &&
(pGivenArray [mid] <= pGivenArray [mid+1]))
{
localMinArray [++(*minimaCount)] = pGivenArray [mid];
}
findLocalMinima (pGivenArray, localMinArray, minimaCount, start, mid);
findLocalMinima (pGivenArray, localMinArray, minimaCount, mid, end);
}
}
int main ()
{
int givenArray [] = {9,1,11,12,16,13,14,15,16,17,18,19,20,25,2,22};
int minimaArray [10] = {0};
int minimaCount = -1, i;
findLocalMinima (givenArray,minimaArray,&minimaCount,0,15);
while(minimaCount >= 0)
{
printf ("[%d]", minimaArray[minimaCount--]);
}
printf ("\n");
return 0;
}
typedef struct
{
void* data;
struct node* next;
struct node* any; /*Pointing to any arbitrary node/NULL/itself in list*/
}node;
Here the idea is to manipulate the "any" pointer of original list to point to new nodes of new list
during creation of new list and then revert back to original form.
initial call:
node* srcHead = GivenHead;
node* dstHead = NULL;
makeCopy (srcHead, &dstHead);
void makeCopy (node* srcHead, node** dstHead)
{
node* tempNode1 = NULL, *tempNode2 = NULL;
node* tempSrcHead = srcHead;
node* tempDstHead = *dstHead;
while (tempSrcHead)
{
tempNode1 = (node*)malloc (sizeof(node));
tempNode1->next = NULL;
tempNode1->data = tempSrcHead->data;
tempNode2 = tempSrcHead->any;
tempSrcHead->any = tempNode1;
tempNode1->any = tempNode2;
if (*dstHead == NULL)
{
*dstHead = tempNode1;
tempDstHead = tempNode1;
}
else
{
tempDstHead->next = tempNode1;
tempDstHead = tempDstHead->next;
}
tempSrcHead = tempSrcHead->next;
}
tempNode1 = NULL;
tempSrcHead = srcHead;
tempDstHead = *dstHead;
while (tempSrcHead) /*maintain the original and new list*/
{
tempNode1 = tempDstHead->any;
if (tempDstHead->any)
{
tempDstHead->any = tempDstHead->any->any;
}
tempSrcHead->any = tempNode1;
tempSrcHead = tempSrcHead->next;
tempDstHead = tempDstHead->next;
}
}
Frog can take a leap of 1 or 2 at any time therefore if number of rock is N then total number of paths will be Nth Fibonacci number. Below is the code to print all the paths:
void printFrogLeap (int* pArray, int num, int count)
{
if(count > num)
{
return;
}
if(count == num)
{
int i;
if(pArray[count-1] == 1) /*path is complete or not*/
{
for (i=0; i < num; i++)
{
if (pArray[i] == 1)
{
printf ("[%d]", i+1);
}
}
printf ("\n");
}
return;
}
pArray [count] = 1;
printFrogLeap (pArray, num, count+1);
if(count+1 < num)
{
pArray [count+1] = 0;/*exclude this entry from path, since its used*/
}
printFrogLeap (pArray, num, count+2);
if(count+2 < num)
{
pArray [count+2] = 0;/*exclude this entry from path, since its used*/
}
}
int main ()
{
int *array, num;
printf ("Enter num of rocks: ");
scanf ("%d", &num);
array = (int*)malloc (sizeof(int)*num);
memset (array,0x00,num);
printf ("Total paths: \n");
printFrogLeap (array, num, 0);
free (array);
return 0;
}
Do binary search where lower bound is 1 and upper bound is number itself (since array is sorted therefore the given number cant go beyond the upper bound and array is infinite therefore this upper bound wont cause any harm).
Time Complexity:
As we know binary search time complexity is log(N) where N is array size but here N is infinity so log(infinity)doesn't make any sense.
So in this case given number will act as length of the array for each search. So the complexity will be log(GivenNumber).
Do inorder traversal:
int outNum = 0;
findSmaller (root,&outNum,givenNum)
void findSmaller (node* root, int* outNum, int givenNum)
{
if (root)
{
findSmaller (root->left, outNum, givenNum);
if (root->data < givenNum)
{
*outNum = root->data;
}
findSmaller (root->right, outNum, givenNum);
}
}
@Kishore: LCM is 90 for your example. I got similar kind of idea after looking your approach.
1. Minheapify the array.
2. Divide all the elements of array till first element becomes 1 at the same time maintain count for all prime divisors.
3. exchange 1st element to last and decrease array size.
4. if array size is is not zero go to 1 else stop.
So after step 1 - 4 if we have count n1,n2,n3 for primes p1,p2,p3 then the LCM is
LCM=p1*p1*..n1times * p2*p2*..n2 times, p3*p3*...n3times.
e.g.
Array = 10, 9 15, size is 3.
step 1 9,10,15 size 3 prime divisor none
step 2 3,10,5 size 3 prime divisors 3-->1
step 2 1,10,5 size 3 prime divisors 3-->2
step 3 5,10,1 size 2 prime divisors 3-->2
step 4 go to 1.
step 1 5,10,1 size 2 prime divisors 3-->2
step 2 1,2,1 size 2 prime divisors 3-->2 5-->1
step 3 2,1,1 size 1 prime divisors 3-->2 5-->1
step 4 go to 1
step 1 2,1,1 size 1 prime divisors 3-->2 5-->1
step 2 1,1,1 size 2 prime divisors 3-->2 5-->1 2-->1
step 3 1,1,1 size 0
step 4 STOP
LCM = 3*3*2*5 = 90
complexity 2^n*(logn +1). 2^n we cant avoid but can we avoid additional logn factor???
int main ()
{
char set [] = {'a','b','c'};
int setSize = 3; /*As per above array*/
int totalSubset = 1<<3;
int i,j,k;
printf ("{{}");
for (i = 1; i < totalSubset; i++)
{
printf("{");
k=i;
j = 0;
while (k)
{
if (k&1)
{
printf ("%c", set[j]);
}
j ++;
k = k>>1;
}
printf ("}");
}
printf ("}\n");
}
Well said Om.
Lets see like this.
Loop size is y+z. suppose p1 iterates the loop n times before meeting p2. So in this case p2 will do 2n iterations. So when both p1 and p2 meets total node traveled by p1 is x+n(y+z) and total distance traveled by p2 is x+z+2n(y+z)
so we have (p2 is twice as fast as p1)
2p1 = p2
2(x+n(y+z))=x+z+2n(y+z)
=>x=z
1. let pointer p1 and p2 and p3 are pointing to the head of linked list.
2. move p1 by one node and p2 by two node.
3. if loop exists p1 and p2 will meet at some node.
4. now start moving p3 and p1(or p2) by one node. p3 and p1(or p2) will meet at the node from where loop starts.
Proof:
let x=number of nodes from head to the node from where loop starts.
let y=number of nodes from the node from where the loop starts to the node where p1 and p2 meets.
let z=number of nodes from the node on which p1 and p2 meets to the node where loop starts.
Number of node traveled by p1 is x+y.
Number of node traveled by p2 is x+y+z+y.
since p2 is as fast as twice of p1 therefore
2(x+y) = x+y+z+y
=>x=z.
Thus the node from which loop starts is equidistant from the head and the node where p1 and p2 meets.
There are couple of things that we need to take care while implementing atoi
1. The number system in which conversion is expected.
2. Its not only a matter of printing the digits. We need to get the integer corresponding to the given string.
e.g. string is: "12345678" then the corresponding integer value is 12345678. We cant just print and go away as above.
3. We need to take care of overflow.
To sort a linked list merge sort is good in comparison to other sorts because
1.QuickSort: In linked list choosing a pivot is not O(1) also arranging the elements against pivot is O(n^2).
2. Similar comparison can be drawn for other sorts on the basis of accessing an element in Araay (O(1)) and Linked list (O(n)).
Here, merging is in place and of O(n) at each level of recursion.
Although choosing mid is again not of O(1) as compare to array. Even though the time complexity is O(nlogn).
Apart from that with the use of extra space we can use generic Qsort function to sort.
e.g.
We can create an array of pointer of the nodes and sort this array with a compare function like
int compare_func(const void* node1, const void* node2)
{
const node* keyNode1 = (node*)node1;
const node* keyNode2 = (node*)node2;
return (keyNode1->data - keyNode2->data)
}
After sorting finishes we can re-make the list using this array.
- Tulley February 23, 2011Method 1:
1. Make a concatenated string of S2 using some delimiter. Say dot (.)
e.g. ConcatS2 = ".Kelos.Dragi.Matt.Ven.Pssi."
2. Pick a word from S1 add delimiter at end and start. Use KMP to serach this pattern in ConcatS2.
e.g. Pick first word "Albert", make pattern as ".Albert." and search in ConcatS2.
**Asumption delimiter is not used in any of original S1 and S2 as a character.
Time Complexity: If S1 contains m number of words and total length of S2 is N then it is m*O(N). Average case will be less than this (Words are Unique)
Method2:
1. Make a trie of S2. Look for each word of S1 if it exist in trie.
Time Complexity: O(length of S1).
@BM: when N=7 total number of structurally different full binary trees will be 5.
0
0 0
0 0 0 0
0
0 0
0 0
0 0
0
0 0
0 0
0 0
0
0 0
0 0
0 0
0
0 0
0 0
0 0
@arun:
The idea behind this deduction is that successive applications of a binary operator can be represented in terms of a full binary tree.If there are n binary operators then there will be n+1 operands and total number of representations (which will be full binary trees) will be equal to Catalan number for 'n'.
e.g. if we take nodes as a,b,c and +,+. Then total number of nodes is 5 and total number of binary operator is 2 so total number of structurally different full binary trees is 2.
So if we simulate in the same way that how many structurally different full binary trees can be created for a given N (total number of nodes) we can observe that
N = n (number of operator) + (n+1) (number of operands)
so n = (N-1)/2
Now get the corresponding Catalan number for n, which is the answer to this question.
node* root;
bool isBalanced = TRUE;
call isBalancedTree (root,&isBalanced)
int isBalancedTree (node* root, bool* isBalanced)
{
int leftHight = 0;
int rightHight = 0;
if (root)
{
leftHight = isBalancedTree (root->lChild, isBalanced);
rightHight = isBalancedTree (root->rChild, isBalanced);
if (leftHight - rightHight > 1 || leftHight - rightHight < -1)
{
*isBalanced = FALSE;
}
if (rightHight > leftHight)
{
return rightHight +1;
}
else
{
return leftHight + 1;
}
}
else
{
return 0;
}
}
@Anon: Thanks for pointing out the mistake. I am not able to find any mistake in your code :)
- Tulley March 28, 2011I was more concern about printing the start and end index of the array. I have corrected the my prev code now.