[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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] amazon
considering nk pop the element k times; for every pop we will save the swaps we have done in array(swap here means when we put the last element in the top of array and bubble down the heap then swaps at that time); now after finding kth smallest simply back track using path saved in th eprevious 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 to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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 will do different thing from previous step. I have not proofed it rigorously. It seems to be a solution to me comments appreciated... -- regards Jitendra -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Longest palindrome in a given str (less than O(n^2) )
@Ankit Narang Think about your algo it is not a O(n). First of all you wont get solution comparing start of str1 and end of str2 Their is solution in O(n) other than suffix tree Here is the link http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/ -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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) {
printf(,);
serialize(tmp-right);
}
printf());
}
}
--
Regards
Jitendra
--
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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] common question(amazon)
this question discuused before with a proper conclusion... please search the forum On Sat, Jul 3, 2010 at 11:31 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: Let an array contain values : a1,a2,... ,an, b1,b2,..., bn Write a program to change this array to : a1,b1,a2,b2, ..., an,bn in O(n) time and in O(1) space. i did it by shiftng of elements which is not much efficient.. any better way ? -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 jitendra.th...@gmail.comwrote: it will be half... On Sun, Jul 4, 2010 at 4:18 PM, Piyush Verma 114piy...@gmail.com wrote: In a village in each family they give birth to children till they get a boy. IF girl child they try again. What is the ratio of boys to girls. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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++;
if(ilen)
swap(arr[j], arr[i]);
else break;
}
for (int k = 0; k len; ++k)
cout arr[k] ;
cout endl;
return 0;
}
check out this code
O(n) time complexity and O(1) space
It iks stable for the first set of numbers and non stable for series of 0
numbers
--
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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] microsoft
@jalaj just think 0 as one array and other numbers as other array the problem is into converted in zero one array which have to be sorted now sort the array in O(n) with no extra space. keep a pointer on left most 0 and find the next number in the sequence when next number found then swap 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 to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] towers of hanoi O(1) time
when we get a different bit from the previous one, four condition arises defining position of the bit : consider this bit form : 1001 (from left, 1 is at odd position, then 0 at even, then next 0 at odd, and so on) now four conditions are(except for 1st bit because it has no previous bit) : 1. previous bit is 1and current bit is 0 and previous bit is at odd position then move disk to right of current position of that disk 2. previous bit is 1and current bit is 0 and previous bit is at even position then move disk to left of current position of that disk 3. previous bit is 0and current bit is 1 and previous bit is at odd position then move disk to left of current position of that disk 4. previous bit is 0and current bit is 1 and previous bit is at even position then move disk to left of current position of that disk for first bit if it is zero means biggest disk is at initial position else at final position. you try it for 3 disk write binary form 000 (initial position) to 111(final position) make the moves and try to figure out. You will definately come 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Stack Space for Quick Sort vs Merge Sort.
quicsort takes a bit of memory during recursion calls. it depends how many variable you pass in each function and number of variables defined inside the function.so most of the time we don't consider quicksort inplace In worst case quicksort take O(n) extra space correct me if i am wrong -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[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: http://en.wikipedia.org/wiki/Nearest_neighbor_search#Space_partitioning can anybody give a pseudo code or commented C code to impliment it. I do not understood how to implement it. this is a google interview question and its variation is a amazon's question. :) -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] towers of hanoi O(1) time
Dear Anuj, Its easy to do. lets take an example say we have 4 disks. We will require 2^4-1 = 15 steps to solve it. Now suppose we are at 6th step.. write it binary form using 4 bits(since we have 4 disks) 0110 now from left 0 means 4th disk is on initial peg second bit 1 means disk 3 is on left of the previous disk third bit 1 means it is above previous disk fourth bit 0 means it is on right of previuos disk so the solution is something like 1: 4|1 2: 3: 3|2 1: is initial peg (left of 1 means 3 and right means 2) 2: is final peg hope it is clear how to solve this in O(no_of_disk) 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 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 :
You cant find the unique element in a unsorted array any less than O(n).
Minimum complexity will be O(n).
One have to traverse the whole array atleast once to find the distinct
element
comments are welcomed...
--
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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] stack
Stack can be sorted in O(n^2). @sankalp: Stack can always be sorted. Why do you think it cant be in some cases ? One can think like insertion sort algo : 1. for i in (1,n) 2. Pop up the top n-1 element and keep nth element in global variable say hold 3. while pushing get the position 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, 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] level order traversal
@Terence : Consider your algo for the tree 1 /\ 2 3 /\ / \ 4 56 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 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] level order traversal
@sharad : In which order you will make the tree into doubly linklist ?? another algorithm: 1. keep root value as 0 2. when moving left decrement this value and assign to node 3. when moving right increment the value and assign to node 4. now sort the nodes on this number basis and if this number is same then on level basis eg: 1 /\ 2 3 / \/ \ 45 67 1 - 0 2 - -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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] sum to x
trivial solution will be exponential where we check for each selection nC1+nC2...nCn = 2^n we can optimise time by taking some memory. It can be solved by subset sum where we will require extra memory of maximum sum possible. refer this link for subset sum problem: http://en.wikipedia.org/wiki/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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] max sum
this can done by dyanamic programming At every point keep the maximum sum including the current element and excluding the current element At last the maimum will be max of both the maximum pseudo code : max1 = max2 = 0 for i in 1 to n temp = max2 max1 = MAX(max1, max2+array[i]) 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, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[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, ((x|x-1)+1)%3 );
return 0;
}
i am not able to get how(xx-1)%3, ((x|x-1)+1)%3is able to
produce the output.What is the logic behind.
Can anybody explain it???
--
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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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 parent. If i am not wrong the child uses text and data area of parent till a exec is not been called in the child. Here in the program parent and child are not doing any tweak with the text area then how can we explain the loop behaviour of the program. -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find Max Number of Elephants
@Amit : Query 1 : It can be solved in O(n) by checking which elephants life span contain the given year Query 2 : Picking up the fact that a elephant die only after its birth we can find the second query in O(nlogn) ALGO: 1. sort in increasing order birth year and death year seperately 2. increment the birth year till we get a value of year which is equal to first death year, keep count of current elephant alive in a value MAX_ELE. 3. Now as one element died decrement one count and increment till we get a year value in birth list which is greater or equal to second death date, keep track of elephents alive and if it is greater than previous,update MAX_ELE with current elephant count 4. continue till birth list empty sorting will require O(nlogn) and finding year in which max elephents were alive will take O(n).Total complexity 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Valid permutation of the brackets
@senthilnathan : You are right. the growth of number is exponetial nth Catalan number is approx Cn ~ (4^n) / ( sqrt(pi) * ( n^(3/2) ) ) : http://en.wikipedia.org/wiki/Catalan_number so the pruned exponential solution is the best one. We cant find algo any less than exponential. On Thu, Jun 3, 2010 at 10:03 PM, Senthilnathan Maadasamy senthilnathan.maadas...@gmail.com wrote: @Jitendra: Catalan number grows at least exponentially: http://mathworld.wolfram.com/CatalanNumber.html -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Valid permutation of the brackets
@rohit: Here we have to print not only number of possible valid bracket but also how they look (eg : ()()() ) If we need to print only number of brackets then then using the recurrence relation of catalan number we can find it easily. According to your point, can you suggest a memoization 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 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[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 like this
1. Try '(' and ')' in every position and print the correct
permutation.Neglect all other permutation
As catalon number is far less then exponential growth ,can anybody
suggest some better algorithm
--
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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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 according the usage. For example lets say out of 3 stack we know the growth of 2nd stack more closely and we know its variations boundary of 2nd stack more clearly than others two. In such case make stack 2 static giving it its particular location. For the rest two apply same as implementation of two stack | stack2 |1st 3rd---| __ for n stacks make n/2 such intervals. If n is odd, one interval will be for a single stack. -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 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+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Implementing 2 stacks within a single linear array
Start the first stack from the starting of the array and the second array from the end as shown below -- 0 n now for underflow condition will be stack 1 if (top1 == 0) stack 2 if (top2 == n) and overflow condition will be if (top2-top1+1 == 0) thats it correct me if anything wrong On Tue, Jun 1, 2010 at 2:11 PM, Raj N rajn...@gmail.com wrote: Hi all, Can someone suggest me an efficient way to implement 2 stacks within a single linear array assuming neither of the stack overflows and an entire stack is never shifted to a different location within the array. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Convert a Binary tree into spike.
This can be done with level order traversal of the tree Algorithm count = count2 = 0 1. Push the root in the queue. 2. keep count at each level for root count =1 3. while(queue not empty) 4. push all childs of node at the top of queue in queue 5. count2 += (number of childs of node 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, 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] question
The solution given by Afroz will work having O(N) extra memory.But in that case the collision in the will increase. If you want to remove collision totally than a hash of O(max_element_in_array) memory will be required. if you want to solve without extra memory then 1. sort the array O(N) 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 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 then it is possible that one of the pointer go out of boundry of 1 to N in worst case. On Mon, May 3, 2010 at 6:48 PM, Varun Nagpal varun.nagp...@gmail.comwrote: @Jitendra I dont think so.Try these 2 examples to check: A[1..n] :20 10 0 B[1..n] :18 13 5 Ans :38 33 28 A[1..n] :20 10 0 B[1..n] :18 17 16 Ans :38 37 36 My conjecture is: In the worst case, instead of combination of 1st element of first array with all elements of second array, we need to instead choose 2 elements from first array and than take combination with all elements of second array. Also before doing this we need to choose from which array should these 2 elements be extracted. I have already suggested before how to do this. -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 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+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: a google question
The Question only ask to print first n number and each array array is of size n So in the worst case we will take combination of 1st element of first array with all the element of second array. my above code runs in O(n) taking this considerations... any comments or test case where it fails??? 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 email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: a google question
@divya
I try to simulate what you said for the given array
index : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
array1:8, 7, 4 ,3 , 2, 1, 1, 1, 1, 1
^ ^
p11 p12
*p11 = 8 and *p12 = 3
index : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
array2:34, 23, 21, 19, 15, 13, 11, 8, 4, 2
^^
p21 p22
*p21 = 34 and *p22 = 23
a = 8 + 34 = 41//arr1[0] + arr2[0]
b = 8 +23 = 31//arr1[0] + arr2[1]
c = 34 + 3 = 37 //arr1[4] + arr2[0] greatest !!!
d = 7 +23 = 30 //arr1[1] + arr2[1]
arr1[0] + arr2[2] = 29 which is less than c..
here is my output
arr1[0] + arr2[0] = 42
arr1[1] + arr2[0] = 41
arr1[2] + arr2[0] = 38
arr1[3] + arr2[0] = 37
arr1[4] + arr2[0] = 36
arr1[5] + arr2[0] = 35
arr1[6] + arr2[0] = 35
arr1[7] + arr2[0] = 35
arr1[8] + arr2[0] = 35
arr1[9] + arr2[0] = 35
i have attached the code try with replacing arr1 and arr2 with
following.and the case u wanted to point out will be taken throught in
following test case..(arr1[0] + arr2[1] = 9+27 = 36 will be taken before
arr1[6] + arr2[0] = 1+34 = 35 )
int arr1[N] = {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 to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
#include cstdio
#includeiostream
using namespace std;
#define N 10
int main(void)
{
int arr1[N] = {8,7,4,3,2,1,1,1,1,1};
int arr2[N] = {34,23,21,19,15,13,11,8,4,2};
int *p11,*p12,*p21,*p22;
int w=0,x=0,y=0,z=0;
p11 = p12 = arr1;
p21 = p22 = arr2;
int f1;
f1 = 0;
for(int i=0;iN;i++) {
int ans=0;
int a,b,c,d;
a = *p11 + *p21;
b = *p11 + *p22;
c = *p21 + *p12;
d = *(p11+1) + *(p21+1);
//printf(a=%d b=%d c=%d d=%d\n,a,b,c,d); //debug
if(f1==0)ans = a ,p12++ , p22++ , f1=1 , printf( arr1[%d] + arr2[%d] = ,w,y),x++,z++;
else if(b = c b = d )ans = b , p22++ , printf( arr1[%d] + arr2[%d] = ,w,z),z++;
else if(c = b c = d )ans = c , p12++ , printf( arr1[%d] + arr2[%d] = ,x,y),x++;
elseans = d , p11++ , p21++ , printf( arr1[%d] + arr2[%d] = ,w,y),w++,y++;
printf(%d\n,ans);
}
}
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, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] a google question
Here is a solution of O(n) , taking 4 pointers 2 for each array
#include cstdio
#includeiostream
using namespace std;
#define N 10
int main(void)
{
int arr1[N] = {8,7,4,3,2,1,1,1,1,1};
int arr2[N] = {34,23,21,19,15,13,11,8,4,2};
int *p11,*p12,*p21,*p22;
p11 = p12 = arr1;
p21 = p22 = arr2;
int f1;
f1 = 0;
for(int i=0;iN;i++) {
int ans=0;
int a,b,c,d;
a = *p11 + *p21;
b = *p11 + *p22;
c = *p21 + *p12;
d = *(p11+1) + *(p21+1);
//printf(a=%d b=%d c=%d d=%d\n,a,b,c,d); //debug
if(f1==0)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 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+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
