[algogeeks] Re: AMAZON Interview Question

It is counting the inversion counts use merge sort and count the inversions for each element O(nlogn) time and O(n) space -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To

Re: [algogeeks] amazon

step time complexity : O(KlogN) space complexity : O(KlogN) any better solution or idea to minmize the space -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email

Re: [algogeeks] Re: adobe problem---array

@anand Your code wont work for many of the cases int arr[]= {5,3,1,11,5,7,11,5,8}; please check the correctness before posting any solution -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group

Re: [algogeeks] Re: Amazon: sort array

@souravsain Consider your algo for the case int arr[] = {10,20,30,40,50,23,27}; everytime when you increment the j you are missing on element i.e j-1 for further comparison -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google

Re: [algogeeks] Amazon Puzzle

Seems tough to do as every time we dont know which coins we flipped in the previous move We can perform all the four operation one by one in circular fashion and we will have probabilitty of getting all head up at some time. this is because even if table rotated at random, each of the for step

Re: [algogeeks] Need help

can you specify the question name or link of question on topcoder -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe

Re: [algogeeks] adobe problem---array

Any boundation on the range of elements?? -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send

Re: [algogeeks] Re: median of array

do quicksort like operation to find the pivot till you get the pivot of n/2 position recursively. Complexity will be O(n) -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group

Re: [algogeeks] Longest palindrome in a given str (less than O(n^2) )

/ -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com

Re: [algogeeks] Need good hashing implementations in Linux (C/C++)

What about STL map I have used it. but for small data.. It is a standard one and should work for bigger set of data also -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group

Re: [algogeeks] amazon question

here is the code which take the root and print the tree in serialized format void serialize(tree *tmp) { if(!tmp) return; printf(%d,tmp-data); if(tmp-right || tmp-left) { printf((); if(tmp-left) serialize(tmp-left); if(tmp-right) {

Re: [algogeeks] common question(amazon)

to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Jitendra

Re: [algogeeks] cops n robber

Offcourse it is possible if cops have higher speed. Incase if same speed : We can say when the when the thief is at one corner the cops will also be in some corner and since only two cops, and thief have three ways possible to move from one edge he can escape always. -- Regards Jitendra Kushwaha

Re: [algogeeks] Re: amazon

@jalaj Solution for subsequence is straight O(N). I think the question is about substring -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge

Re: [algogeeks] Re: Yahoo

ya i mean half girl and half boys i.e. 1:1 ratio of boys to girl On Sun, Jul 4, 2010 at 5:25 PM, peeyush peeyush...@gmail.com wrote: It can not be determined. On Jul 4, 4:27 pm, Amit Jaspal amitjaspal...@gmail.com wrote: it will be 1:1 On Sun, Jul 4, 2010 at 4:50 PM, Jitendra Kushwaha

Re: [algogeeks] Re: microsoft

#include iostream #include cstring #includealgorithm using namespace std; int main () { int arr[] = {1,0,2,0,3,0,0,4,5,6,7,0,0,0}; int i=0,j=0; int len = sizeof(arr)/sizeof(int); while(1) { while(jlen arr[j]!=0) j++; i=j; while(ilen arr[i]==0)i++;

Re: [algogeeks] microsoft

the number with left most 0 and increment the pointer of leftmost 0 just one linear walk through the array is required. -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email

Re: [algogeeks] 23 candies among 7 kids

coefficient of x^23 in (1 + x + x^2 + x^3 + ... + x^23) ^ 7 i.e. 29C23 -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com

Re: [algogeeks] max of 2 numbers

given numbers are p and q then max = q ^ ( (p^q) * (pq) ); -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from

Re: [algogeeks] towers of hanoi O(1) time

to this result best of luck -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr

Re: [algogeeks] Stack Space for Quick Sort vs Merge Sort.

-- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com

Re: [algogeeks] Towers of hanoi

Even your own stack will give TLE :) Try solving this question with binary solution of tower of hanoi and you will definately pass the time limit. -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group

[algogeeks] finding nearest neighbour

Given n points in the space. Now given a new point you have to find the nearest neigbour to it from initial n points This can be done in O(n), a trivial solution. This can also be accomplished in O(logn) by space partioning. here is a link:

Re: [algogeeks] Re: unique number in an array

Using Hashing space : O(n) time : O(n) Using sorting space : O(1) time : O(nlogn) special case: (all elements are of the range of the array then using count sort) space : O(1) time : O(n) any better solutions??? -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You

Re: [algogeeks] towers of hanoi O(1) time

) complexity you can refer this link : http://britton.disted.camosun.bc.ca/jbhanoi.htm http://britton.disted.camosun.bc.ca/jbhanoi.htm comment for any related doubts :) -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups

Re: [algogeeks] Re: unique number in an array

@Sathaiah : offcourse XOR have problem . All tha other numbers are not repeated even nuber of times so its not necessary that they cut out to give 0 for eg a[]={1,3,4,1,4,5,6,1,5,6} XOR will give output as 1^3 which is not done If every other element is repeated even times then XOR is OK @jalaj

Re: [algogeeks] stack

for hold and push it there for loop will take O(n) and step 2 will take take O(n) time. So overall O(n^2) complexity Program can be done with recursion using a variable (hence O(1) space). But it will use system stack :) Any comments OR better solution is welcomed?? -- Regards Jitendra Kushwaha MNNIT

Re: [algogeeks] level order traversal

7 / / 8 9 According to your algo , first we print 8 4 2 1 ( while(! is_empty(vstack)) ) . But 9 should come before 1. i.e 8 4 2 9 1 5 6 3 7 am I correct??? -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You

Re: [algogeeks] Array Increment Problem

This is direct question of segment tree. read the topcoder's tutorial for segment tree -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge

Re: [algogeeks] level order traversal

- -1 3 - 1 4 - -2 5 - 0 6 - 0 7 - 2 sort : 4 2 1 5 6 3 7 any comments??? -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com

Re: [algogeeks] level order traversal

@Anurag: Check your approach for non balanced tree alsoeg take 8 nodes and try. -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge

Re: [algogeeks] sum to x

/Subset_sum_problem -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr

Re: [algogeeks] max sum

]) max2 = MAX(temp,max1) final_max = MAX(max1,max2) -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group

Re: [algogeeks] Re: ds

here is a sel explainatory algo given: abcd1234 abc1d234 ab1c2d34 a1b2c3d4 here is the link for the code : http://codepad.org/SZnufGc6 -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post

[algogeeks] Tower of Hanoi Iterative Solution

Below iterative solution of the tower of hanoi problem... #include stdio.h #include stdlib.h int main() { int n, x; printf( How many disks? ); scanf( %d, n ); printf(\n); for (x=1; x (1 n); x++) printf( move from tower %i to tower %i.\n, (xx-1)%3,

Re: [algogeeks] Explain the output

changing vfork with fork gives the correct output but in case of vfork the loop behaviour is unpredictable @harit : I guess the child is simply reading the value of i from the same data area of the parent. First time it showed a garbage, after which it shows the value inputted in the

Re: [algogeeks] Find Max Number of Elephants

O(nlogn) Correct me anything wrong -- Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com

Re: [algogeeks] Valid permutation of the brackets

Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks

Re: [algogeeks] Valid permutation of the brackets

which can handle the problem of printing of bracket arrangement also. Any such algo can make the solution polynomial. -- Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm

[algogeeks] Valid permutation of the brackets

The question is that you have to print all the valid permutations of the given number of brackets for example for input 3 we have the output 1 ((())) 2 (()()) 3 (())() 4 ()(()) 5 ()()() total five valid permutation this can be solved in O( 2^(2n) ) where n is number of brackets . Algo will be

Re: [algogeeks] Implementing 2 stacks within a single linear array

@Raj N : You are right overflow is top2-(top1+1)==0 @Anand : The oveflow condition is dependent how underflow condition are implemented. Considering underflow above condition for overflow suffice For 3 stacks a efficient algo is not easy to think in a single array , yet we can optimise

Re: [algogeeks] Re: partion of array

Using subset sum method we can solve this. It actually DP check out Paybill question and its solution on topcoder website link : http://www.topcoder.com/stat?c=problem_statementpm=3114rd=5865 you will have a better understanding of subset sum problem after this -- Regards Jitendra Kushwaha

Re: [algogeeks] Implementing 2 stacks within a single linear array

Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email

Re: [algogeeks] Convert a Binary tree into spike.

at the top) 6. print the top node of queue and dequeue it 7. count -= 1 8. if (count == 0) 9.print newline 10. count = count2 11. count2 = 0 any comments are welcomed... -- Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT

[algogeeks] Yahoo coding round question

Find the longest common subsequence of given N strings each having length between 0 to M. Can anybody give a good approach to the solutions -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to

Re: [algogeeks] Re: a google question

@Amit Agarwal you are missing some pairs having larger some than you mentioned.. for example 7 + 49 = 56 which is greater than 53 similarly 7 + 48 7 + 47 (3 + 49 =52) (50 +1 = 51) --- Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- You received

Re: [algogeeks] question

) 2. take each possible pair from array and sum it.O(N^2) 3. binary search the array for the nearest complement of this sum O(logN) So total complexity is O(N^2 * logN) -- Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- You received this message

Re: [algogeeks] Re: a google question

@Varun output for your test cases are as below: arr1[0] + arr2[0] = 38 arr1[0] + arr2[1] = 33 arr1[1] + arr2[0] = 28 arr1[0] + arr2[0] = 38 arr1[0] + arr2[1] = 37 arr1[0] + arr2[2] = 36 what i was talking about worst case was that is if one have to find more than N elements of array c

Re: [algogeeks] 400!

You can do it easily in python...:) Here is the python code n=400 def fact(num): ans = 1 while(num): ans = ans*num num = num-1 return ans print fact(n) #printing 400! even 1000! can be calculated Regards Jitendra Kushwaha Undergradute Student Computer Science

Re: [algogeeks] Re: a google question

??? Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send

Re: [algogeeks] Re: a google question

] = {9,7,4,3,2,1,1,1,1,1}; int arr2[N] = {34,27,21,19,15,13,11,8,4,2}; Regards Jitendra Kushwaha -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email

Re: [algogeeks] Re: a google question

slight change in value of c c = 34 + 2 = 36 //arr1[4] + arr2[0] greatest !!! my mistake.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group,

Re: [algogeeks] a google question

)ans = a ,p12++ , p22++ , f1=1; else if(b = c b = d )ans = b , p22++ ; else if(c = b c = d )ans = c , p12++ ; elseans = d , p11++ , p21++ ,printf(4 ); printf(%d\n,ans); } } Regards Jitendra Kushwaha Undergradute Student Computer