Re: [algogeeks] repeating numbers in an array
One possible solution would be to create an array of pointers to the list.. array index indicates how many times the element occurs and the list gives the elements. On Sun, Oct 3, 2010 at 11:22 AM, sharad kumar aryansmit3...@gmail.comwrote: it will take same amount of memory nakey value is element and vaule is the amount of times element occurs. On Sun, Oct 3, 2010 at 11:11 AM, mac adobe macatad...@gmail.com wrote: i think hash map takes lots of memory ... please correct me if i am wrong here .. anyways its a soluton but i would like to have a different solution .. :) --mac On Sun, Oct 3, 2010 at 10:55 AM, sharad kumar aryansmit3...@gmail.comwrote: cant u use a hash map buddy??? On Sun, Oct 3, 2010 at 10:35 AM, mac adobe macatad...@gmail.comwrote: You are given a very long array of integers . Some number in this integer array come 1 time , some 2 times some 3 times . create 3 different arrays . Array 1 will have numbers with numbers comming only1 time , Array 2 will have numbers with numbers comming 2 times, Array 3 will have numbers with numbers repearting 3 times , Can you extend the solution to create array_x with elements repeating x times ? thanks --mac -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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. -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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. -- Rgds, Kusuma S -- 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] repeating numbers in an array
In hash map insertion and seach take O(logn) time but less space. So according to sharad insert all elements in hash map which will take O(nlogn) time and 0(n) space. But if you are sure about the range of numbers which would appear in the list, you can use counting mechanism. Like if you know number will be 1 - 1000. Then have an array of size 1000. So space complexity will be O(k) ( k = largest number ) and time complexity for all insertion would be O(n) and time complexity for generating 3 arrays by checking each element would be O(k) space = O(k) time = O(n+k) On Sun, Oct 3, 2010 at 11:22 AM, sharad kumar aryansmit3...@gmail.comwrote: it will take same amount of memory nakey value is element and vaule is the amount of times element occurs. On Sun, Oct 3, 2010 at 11:11 AM, mac adobe macatad...@gmail.com wrote: i think hash map takes lots of memory ... please correct me if i am wrong here .. anyways its a soluton but i would like to have a different solution .. :) --mac On Sun, Oct 3, 2010 at 10:55 AM, sharad kumar aryansmit3...@gmail.comwrote: cant u use a hash map buddy??? On Sun, Oct 3, 2010 at 10:35 AM, mac adobe macatad...@gmail.comwrote: You are given a very long array of integers . Some number in this integer array come 1 time , some 2 times some 3 times . create 3 different arrays . Array 1 will have numbers with numbers comming only1 time , Array 2 will have numbers with numbers comming 2 times, Array 3 will have numbers with numbers repearting 3 times , Can you extend the solution to create array_x with elements repeating x times ? thanks --mac -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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. -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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. -- Thanks Regards, Gaurav Gupta Associate Software Engineer IBM Software Lab |India Email: gauravgu...@in.ibm.com Ph No. : +91-7676-999-350 Quality is never an accident. It is always result of intelligent effort - John Ruskin -- 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] repeating numbers in an array
@kusuma main concern is how will you create the list which are coming once. you have to check the current value with all values you pushed into the list and if match occures you have to delete the element from existing list and insert in next list having index greater by one. and if duplication not found you will push into first list. In worst case time complexity of generation of these array would be O(n^2). or if I misinterpreted the solution, correct me. On Sun, Oct 3, 2010 at 11:31 AM, kusuma sanjeev kushina...@gmail.comwrote: One possible solution would be to create an array of pointers to the list.. array index indicates how many times the element occurs and the list gives the elements. On Sun, Oct 3, 2010 at 11:22 AM, sharad kumar aryansmit3...@gmail.comwrote: it will take same amount of memory nakey value is element and vaule is the amount of times element occurs. On Sun, Oct 3, 2010 at 11:11 AM, mac adobe macatad...@gmail.com wrote: i think hash map takes lots of memory ... please correct me if i am wrong here .. anyways its a soluton but i would like to have a different solution .. :) --mac On Sun, Oct 3, 2010 at 10:55 AM, sharad kumar aryansmit3...@gmail.comwrote: cant u use a hash map buddy??? On Sun, Oct 3, 2010 at 10:35 AM, mac adobe macatad...@gmail.comwrote: You are given a very long array of integers . Some number in this integer array come 1 time , some 2 times some 3 times . create 3 different arrays . Array 1 will have numbers with numbers comming only1 time , Array 2 will have numbers with numbers comming 2 times, Array 3 will have numbers with numbers repearting 3 times , Can you extend the solution to create array_x with elements repeating x times ? thanks --mac -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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. -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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. -- Rgds, Kusuma S -- 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. -- Thanks Regards, Gaurav Gupta Associate Software Engineer IBM Software Lab |India Email: gauravgu...@in.ibm.com Ph No. : +91-7676-999-350 Quality is never an accident. It is always result of intelligent effort - John Ruskin -- 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] repeating numbers in an array
Sorting : O(nlogn) time So hash map solution will also same time. I guess one can customize it according to the requirements and constraints. On Sun, Oct 3, 2010 at 11:50 AM, kusuma sanjeev kushina...@gmail.comwrote: array elements: 1 2 9 8 7 5 2 3 1 1 4 2 6 2 3 sort: 1 1 1 2 2 2 2 3 3 4 5 6 7 8 9 compare the element with the next , if its same then increment the count. repeat until v find all the occurrences of tat element then insert tat element into arr[count] (if arr[count] is null else traverse the list to insert @ the right postion) create another array say arr arr[0] some sentinal/ garbage arr[1] pointer_list1 - 4 - 5 - 6 - 7 - 8 - 9 arr[2] pointer_list2 - 3 arr[3] pointer_list3 - 1 arr[4] pointer_list4 - 2 . . . . On Sun, Oct 3, 2010 at 11:37 AM, mac adobe macatad...@gmail.com wrote: how will this give me array_1 which lists all numbers comming 1 time , array_2 which lists all numbers comming 2 time etc ? On Sun, Oct 3, 2010 at 11:31 AM, kusuma sanjeev kushina...@gmail.comwrote: One possible solution would be to create an array of pointers to the list.. array index indicates how many times the element occurs and the list gives the elements. On Sun, Oct 3, 2010 at 11:22 AM, sharad kumar aryansmit3...@gmail.comwrote: it will take same amount of memory nakey value is element and vaule is the amount of times element occurs. On Sun, Oct 3, 2010 at 11:11 AM, mac adobe macatad...@gmail.comwrote: i think hash map takes lots of memory ... please correct me if i am wrong here .. anyways its a soluton but i would like to have a different solution .. :) --mac On Sun, Oct 3, 2010 at 10:55 AM, sharad kumar aryansmit3...@gmail.com wrote: cant u use a hash map buddy??? On Sun, Oct 3, 2010 at 10:35 AM, mac adobe macatad...@gmail.comwrote: You are given a very long array of integers . Some number in this integer array come 1 time , some 2 times some 3 times . create 3 different arrays . Array 1 will have numbers with numbers comming only1 time , Array 2 will have numbers with numbers comming 2 times, Array 3 will have numbers with numbers repearting 3 times , Can you extend the solution to create array_x with elements repeating x times ? thanks --mac -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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. -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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. -- Rgds, Kusuma S -- 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. -- thanks --mac -- 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. -- Rgds, Kusuma S -- 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,
[algogeeks] Re: Sort in Linear time O(n)
thanx, to correct me. yes..radix sort takes O(d(n+k)) time. On Oct 3, 4:17 am, Gene gene.ress...@gmail.com wrote: Radix sort _is_ dependent on the length of keys. If the radix is R, then the sort must make ceiling(log_R(k)) passes over the data. Increasing the R to decrease the number of passes has a storage cost: you need R buckets. On Oct 2, 3:04 pm, Mridul Malpani malpanimri...@gmail.com wrote: Radix sort is independent of the range and only depends on the number of items. here k=max value= n^3. since , radix sort is independent of k, so here also it sorts n integers in O(n). On Oct 2, 10:38 pm, Harshal ..Bet oN iT!! hc4...@gmail.com wrote: this theorem is true for comparision sorts only! counting sort is not a comparison sort. -- 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] Re: apple problem
@anand: the greedy appoach will not work in this test case:
{2,10,25,
1,20,10,
100, 5, 100}
i think use DP. create an 'max matrix of same order.
max[i,j]= maximum( max[i-1][j] + a[i][j], max[i][j-1]+a[i][j] );
max[n-1][n-1] will be the answer.
Tell me if i m wrong.
On Oct 2, 10:29 pm, Anand anandut2...@gmail.com wrote:
Since in our case starting point is fixed ie top left corner so dynamic
programmng will not make any difference. Dynamic programing makes difference
only when starting point is not fixed. Solution from Greedy and Dynamic
programming will be same in this case. Correct me if I am wrong
On Sat, Oct 2, 2010 at 8:27 AM, Mridul Malpani malpanimri...@gmail.comwrote:
@ anand: the code u have given is an greedy approach. it will not
work.
On Oct 1, 12:34 am, Anand anandut2...@gmail.com wrote:
Here is a code for solving the problem using DP.
http://codepad.org/AoPtCmwA
On Thu, Sep 30, 2010 at 3:01 AM, Modeling Expert
cs.modelingexp...@gmail.com wrote:
recurssion...
At any point X
val_t getMax( position X){
( ! End of Table )
sum = GetApples[X] + MAX ( getMax(X_down) , getMax
( X_right) ) ;
returnn sum ;
}
--
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.
--
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] Re: iTS aLL gOOGLE- iNTERVIEW
Will u plz elaborate ur solution. give the algo to how to find all binary trees. On Oct 2, 9:51 pm, Harshal ..Bet oN iT!! hc4...@gmail.com wrote: 2) We need to find the all complete binary trees using 3 of the (+,*,/,-) at a time as internal nodes and n1,n2,n3,n4 as leaves, and then inorder traversal of the tree. If it is 24 then success. 3)You can view the problem as contructing a binary tree at each stage, either down or right. Count the number of leaf nodes formed for goal state, it will be equal to number of paths taken to reach the goal. -- 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: iTS aLL gOOGLE- iNTERVIEW
they will be integers in q2... On 10/2/10, swayambhoo jain swayambhoo.j...@gmail.com wrote: Are the four numbers in question #2 integers or they can be anything? On Sat, Oct 2, 2010 at 10:03 AM, swayambhoo jain swayambhoo.j...@gmail.comwrote: What about the case when we have repeated numbers in a sequence. On Sat, Oct 2, 2010 at 8:30 AM, bittu shashank7andr...@gmail.com wrote: If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those numbers? answer should be as the maximum bounds isfor simple mobile phone 6 key are having 3 character so n!*(3*n) and 2 keys has 4 charcater so 2!*n ..correct me if i am wrong -- 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. -- Swayambhoo jain, Graduate Student, MSEE Electrical and Computer Engineering Dept. University of Minnesota, Twin Cities -- Swayambhoo jain, Graduate Student, MSEE Electrical and Computer Engineering Dept. University of Minnesota, Twin Cities -- 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. -- 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] Re: clear screen in mysql
Check this out: http://www.linuxask.com/questions/clear-screen-in-mysql-client On Sep 14, 2:27 pm, Ayush Mittal ayushmittal2...@gmail.com wrote: what is the command to clear screen in mysql..? -- 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] Re: Sort in Linear time O(n)
Use counting Sorting Algorithm...i am givin the code below ..it sort
the array in O(n) but uses xtra memory space (n+k)...we have to pay
eother memory or time
#include stdlib.h
#includestdio.h
#includeconio.h
int main()
{
int array[]={4,2,2,2,4,5,9,5,10};
int size=10;
int min,max;
max=min=array[0];
int i=0;
//clrscr();
for(i = 1; i size; i++)
{
if (array[i] min)
min = array[i];
else if (array[i] max)
max = array[i];
}
int range = max - min + 1;
int *count =(int *) malloc(range * sizeof(int));
for(i = 0; i size; i++)
count[i] = 0;
for(i = 0; i size; i++)
count[array[i]]++;
int pos=0;
for(i=0;isize;i++)
{
for(int j=0;jcount[i];j++)
{
array[pos]=i;
pos++;
}
}
//free(count);
for(int i=0;isize;i++)
printf(%d \n ,array[i]);
getch();
}
Regard's
Shashank Mani Narayan Don't Be Evil U Can Earn While U learn
Computer Science Engineering
Birla Institute of Technology,Mesra
Cell No. +91-9166674831
--
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] Re: iTS aLL gOOGLE- iNTERVIEW
If-a-person-dials-a-sequence-of-numbers-on-the-telephone-what- possible- words-strings-can-be-formed-from-the-letters finally i have found the anwer i though about it that it sould be (3*k1)! for 1=k1=6 and (4*k2)! for 2 keys dat is nothing but the all the permutation of character on the keys.. future ordr of pressing the key doesn't matter because we hav already calculated teh permutation correct me if i am wrong. Regard's Shashank Mani Narayan Don't Be Evil U Can Earn While U learn Computer Science Engineering Birla Institute of Technology,Mesra Cell No. +91-9166674831 -- 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] Re: iTS aLL gOOGLE- iNTERVIEW
If we are pressing n numbers, the it should be (26)^N. As each time we press the number it is going to be any character. -- 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: Sort in Linear time O(n)
@harshal :
range of integers are given from 1 to n^3-1,,there are total n integers
only.
also:-Treat the numbers as 2-digit numbers in radix n. Each digit ranges
from 0 to n^3 -1.
Sort these 2-digit numbers with radix sort.
There are 2 calls to counting sort, each taking (n + n) = (n) time, so
that the
total time is (n).
On Sun, Oct 3, 2010 at 4:00 PM, bittu shashank7andr...@gmail.com wrote:
Use counting Sorting Algorithm...i am givin the code below ..it sort
the array in O(n) but uses xtra memory space (n+k)...we have to pay
eother memory or time
#include stdlib.h
#includestdio.h
#includeconio.h
int main()
{
int array[]={4,2,2,2,4,5,9,5,10};
int size=10;
int min,max;
max=min=array[0];
int i=0;
//clrscr();
for(i = 1; i size; i++)
{
if (array[i] min)
min = array[i];
else if (array[i] max)
max = array[i];
}
int range = max - min + 1;
int *count =(int *) malloc(range * sizeof(int));
for(i = 0; i size; i++)
count[i] = 0;
for(i = 0; i size; i++)
count[array[i]]++;
int pos=0;
for(i=0;isize;i++)
{
for(int j=0;jcount[i];j++)
{
array[pos]=i;
pos++;
}
}
//free(count);
for(int i=0;isize;i++)
printf(%d \n ,array[i]);
getch();
}
Regard's
Shashank Mani Narayan Don't Be Evil U Can Earn While U learn
Computer Science Engineering
Birla Institute of Technology,Mesra
Cell No. +91-9166674831
--
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.
--
best wishes!
vaibhav
--
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] Re: Sort in Linear time O(n)
Doesn't this use O(n^3) space and the time complexity will also be
O(n^3) (passing through n^3 different possible values).
Use Radix Sort with radix/base equal to n, meaning that instead of
using the digits of numbers in base 10, find the digits in base n.
On Oct 3, 1:30 pm, bittu shashank7andr...@gmail.com wrote:
Use counting Sorting Algorithm...i am givin the code below ..it sort
the array in O(n) but uses xtra memory space (n+k)...we have to pay
eother memory or time
#include stdlib.h
#includestdio.h
#includeconio.h
int main()
{
int array[]={4,2,2,2,4,5,9,5,10};
int size=10;
int min,max;
max=min=array[0];
int i=0;
//clrscr();
for(i = 1; i size; i++)
{
if (array[i] min)
min = array[i];
else if (array[i] max)
max = array[i];
}
int range = max - min + 1;
int *count =(int *) malloc(range * sizeof(int));
for(i = 0; i size; i++)
count[i] = 0;
for(i = 0; i size; i++)
count[array[i]]++;
int pos=0;
for(i=0;isize;i++)
{
for(int j=0;jcount[i];j++)
{
array[pos]=i;
pos++;
}
}
//free(count);
for(int i=0;isize;i++)
printf(%d \n ,array[i]);
getch();
}
Regard's
Shashank Mani Narayan Don't Be Evil U Can Earn While U learn
Computer Science Engineering
Birla Institute of Technology,Mesra
Cell No. +91-9166674831
--
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: Sort in Linear time O(n)
* lets have another approach,tell me if it works Notice that the number of digits used to represent an n^3 different numbers in a k-ary number system is d= log(n^3) base k. Thus considering then 3 numbers as radix n numbers gives us that: d=log (n^3)base n= 3logn(n)= 3 Radix sort will then have a running time ofΘ(d(n+ k)= Θ(3(n+ n)) = Θ(n) * -- 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: apple problem
@Mridul
Thats correct. You can however optimize on space complexity. At any point of
time you need only current max row and previous max row, so you can manage
with only 2 rows (in fact just 1 if you optimize furthure).
On Sun, Oct 3, 2010 at 1:02 PM, Mridul Malpani malpanimri...@gmail.comwrote:
@anand: the greedy appoach will not work in this test case:
{2,10,25,
1,20,10,
100, 5, 100}
i think use DP. create an 'max matrix of same order.
max[i,j]= maximum( max[i-1][j] + a[i][j], max[i][j-1]+a[i][j] );
max[n-1][n-1] will be the answer.
Tell me if i m wrong.
On Oct 2, 10:29 pm, Anand anandut2...@gmail.com wrote:
Since in our case starting point is fixed ie top left corner so dynamic
programmng will not make any difference. Dynamic programing makes
difference
only when starting point is not fixed. Solution from Greedy and Dynamic
programming will be same in this case. Correct me if I am wrong
On Sat, Oct 2, 2010 at 8:27 AM, Mridul Malpani malpanimri...@gmail.com
wrote:
@ anand: the code u have given is an greedy approach. it will not
work.
On Oct 1, 12:34 am, Anand anandut2...@gmail.com wrote:
Here is a code for solving the problem using DP.
http://codepad.org/AoPtCmwA
On Thu, Sep 30, 2010 at 3:01 AM, Modeling Expert
cs.modelingexp...@gmail.com wrote:
recurssion...
At any point X
val_t getMax( position X){
( ! End of Table )
sum = GetApples[X] + MAX ( getMax(X_down) , getMax
( X_right) ) ;
returnn sum ;
}
--
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
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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
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.
--
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: Sort in Linear time O(n)
Thanks guys, i got 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] Re: apple problem
yeah Mirdul.
you are correct.
http://codepad.org/qYuXmPyB
http://codepad.org/qYuXmPyB
On Sun, Oct 3, 2010 at 7:08 AM, ravindra patel ravindra.it...@gmail.comwrote:
@Mridul
Thats correct. You can however optimize on space complexity. At any point
of time you need only current max row and previous max row, so you can
manage with only 2 rows (in fact just 1 if you optimize furthure).
On Sun, Oct 3, 2010 at 1:02 PM, Mridul Malpani malpanimri...@gmail.comwrote:
@anand: the greedy appoach will not work in this test case:
{2,10,25,
1,20,10,
100, 5, 100}
i think use DP. create an 'max matrix of same order.
max[i,j]= maximum( max[i-1][j] + a[i][j], max[i][j-1]+a[i][j] );
max[n-1][n-1] will be the answer.
Tell me if i m wrong.
On Oct 2, 10:29 pm, Anand anandut2...@gmail.com wrote:
Since in our case starting point is fixed ie top left corner so
dynamic
programmng will not make any difference. Dynamic programing makes
difference
only when starting point is not fixed. Solution from Greedy and Dynamic
programming will be same in this case. Correct me if I am wrong
On Sat, Oct 2, 2010 at 8:27 AM, Mridul Malpani malpanimri...@gmail.com
wrote:
@ anand: the code u have given is an greedy approach. it will not
work.
On Oct 1, 12:34 am, Anand anandut2...@gmail.com wrote:
Here is a code for solving the problem using DP.
http://codepad.org/AoPtCmwA
On Thu, Sep 30, 2010 at 3:01 AM, Modeling Expert
cs.modelingexp...@gmail.com wrote:
recurssion...
At any point X
val_t getMax( position X){
( ! End of Table )
sum = GetApples[X] + MAX ( getMax(X_down) , getMax
( X_right) ) ;
returnn sum ;
}
--
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
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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
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.
--
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.
--
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: iTS aLL gOOGLE- iNTERVIEW
for the first one it is permutation with repetition because the order matters n = no of digits When you have *n* things to choose from ... you have *n* choices each time! So when choosing *r* of them, the permutations are: *n × n × ... (r times) = nr* correct me if am wrong -- 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: iTS aLL gOOGLE- iNTERVIEW
here r is numbers we choose usually we have 10 numbers(in case of cell phone) we have 10[0.9] digits so 10^10 numbers are there...correct me if am wrong -- 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] Re: iTS aLL gOOGLE- iNTERVIEW
for question 2. it seems awful but; Since there are no paranthesis and /,* preceeds +,- if there is an * or / , the leftmost one should be performed before the others. First check the case if no *,/ occurs by checking all the sums n1,n2,n3,n4; -n1,n2,n3,n4 (there are 2^4, either negative or positive, since summation is commutative order doesnt matter) if one of them equals to 24 then we return true and we are done. Then for each n1*n2, n1*n3... make a recursive call for the 3 remaining numbers (replacing two multiplied original numbers with the result, for example n1*n2 replacing n1 and n2; so the recursive call is for n1*n2, n3, n4) there are 6 pairs like that (12 more when / is checked as its not commutative). Execute the same algorithm for 3 numbers and for 2 numbers, when there is only one number left, if it is not 24 return false, if it is 24 return true. I guess the brute force approach requires 4!*4^4, this seems to narrow the search space by exploiting the precedance and commutative rule of summation and multiplication. On Oct 2, 4:00 pm, bittu shashank7andr...@gmail.com wrote: If-a-person-dials-a-sequence-of-numbers-on-the-telephone-what-possible- words-strings-can-be-formed-from-the-letters We are given 4 numbers say n1, n2, n3, n4. We can place them in any order and we can use mathematical operator +, -, *, / in between them to have final result as 24. Write an algorithm for this, it will take 4 numbers and return false or true whether final result 24 is possible with any combination. Pretend there is a robot that has to navigate a maze (N x M). The robot can only move down or right and the maze can contain walls. Write an algorithm to determine the number of paths the robot can take. If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those 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.
[algogeeks] Re: Directi question-centre of the tree
I don't understand what you mean when you say minimum among all the nodes in the graph. In any case, your definition of centre of tree looks similar to the closeness centrality measure - http://www.faculty.ucr.edu/~hanneman/nettext/C10_Centrality.html#Closeness I doubt you can do it in O(N)... On Sep 29, 12:41 pm, jayapriya surendran priya7...@gmail.com wrote: In graph theory, a tree is defined as a graph on N nodes,and (N-1) un-directed edges such that there are no cycles in the graph.Each node has a single unique path to every other node. Let D(u,v) be the number of edges in the unique path from node 'u' to node 'v' (or from node 'v' to 'u' since the edges are un-directed).D(u,u) is 0 for all nodes 'u'. M(u)=MAX(D(u,i):for all nodes i) The center of a tree is the node (or nodes) 'u',for which M(u) is minimum among all the nodes in the graph. You'll be given a graph which has N nodes (1=N=20).The nodes are labeled 1,2,3,..N.You will be provided with N-1 edges in the form of a b pairs where 1=a,b=N.No edge will be repeated.You can assume that the edges are specified such that the graph is a valid tree as defined above. Output the node labels of the center(or centers) of the tree. Sample Input: 6(value of N) 1 3 (edges) 1 4 1 2 2 5 2 6 Sample Output 1 2 Expected:O(N) complexity algo can anyone plz help me out with O(N) algo? -- 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] Re: iTS aLL gOOGLE- iNTERVIEW
For the third problem, involving the maze: There must be N moves down and M moves to the right. Thus, there is a total of M+N moves, and the number of these is the binomial coefficient (M+N) choose M, which of course equals the binomial coefficient (M+N) choose N. This contradicts the answer involving Catalan Numbers. Dave On Oct 2, 8:00 am, bittu shashank7andr...@gmail.com wrote: If-a-person-dials-a-sequence-of-numbers-on-the-telephone-what-possible- words-strings-can-be-formed-from-the-letters We are given 4 numbers say n1, n2, n3, n4. We can place them in any order and we can use mathematical operator +, -, *, / in between them to have final result as 24. Write an algorithm for this, it will take 4 numbers and return false or true whether final result 24 is possible with any combination. Pretend there is a robot that has to navigate a maze (N x M). The robot can only move down or right and the maze can contain walls. Write an algorithm to determine the number of paths the robot can take. If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those 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.
