Re: [algogeeks] Median of BST
@Dhilip
Is it tested ? I doubt your code won't work ?
@Rohit
Can we anyways modify Morris Inorder Traversal process? We can have two
pointers slow(increments once) and fast(increments twice), so that if fast
reaches end or fast-next is end, we can have the median @ slow ?
Correct me If I am wrong.
Thanks and Regards
Kaushik
On Tue, May 18, 2010 at 4:05 PM, dhilip dhilip.i...@gmail.com wrote:
1)do inorder and reverse inorder traversal
2)They will meet at one point or they will cross each other
3)That point is the median
4)Code for the same.
while(true)
{
//inorder traversal
while(count1=count2 flag1)
{
if(root)
{
push(root);
root=root-lptr;
}
else
{
if(!isEmpty(stack1))
t=pop();
else
flag1=false;
var1=t-data;
count1++;
root=t-rptr;
}
if(count1==count2)
{
if(var1=var2)
return var2;
}
}
//reverse inorder
while(count2=count1 flag2)
{
if(root1)
{
push(root1);
root1=root1-rptr;
}
else
{
if(!isEmpty(stack2))
t1=pop();
else
flag2=false;
var2=t1-data;
count2++;
root1=t1-lptr;
}
if(count1==count2)
{
if(var1=var2)
return var2;
}
}
}
--
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] String Problems
I'm trying to solve some string problems somewat efficiently. Can someone tell me what would be efficient DS for solving these problems http://acm.jlu.edu.cn/joj/showproblem.php?pid=1014 http://acm.jlu.edu.cn/joj/showproblem.php?pid=1873 Thanks, Regards, Vignesh -- There are two kinds of people. Those who care for others and The others -- 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: another google telephone interview question
@aarthi, Its seems like ur worried only about frequency, not the sorting. If its a count sort you're trying to explain,then it requires huge space.. And i guess there is no O(n) sort except count sort, which won't be a gr8 soln. for the original problem Regards, Vignesh On May 19, 4:09 pm, Aarthi Thangamani aarthi.thangam...@gmail.com wrote: If you are using an extra space to count, why need a heap? An array of size k can be used to first count the occurances. Then run through the original array of size N and fill it according to the count our occirances using the constant k size array. Space O(k) and time O(N) is the best thing I think of. :( On Tue, May 18, 2010 at 7:11 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: Here u r using extra space to store count values.. CHERUVU JAANU REDDY M.Tech in CSIS On Tue, May 18, 2010 at 7:01 PM, Jagadish M jagadis...@gmail.com wrote: On May 18, 8:29 am, Terence technic@gmail.com wrote: How do you maintain the heap? Could you explain in detail for the following example: 1 2 3 3 2 1 1 1 2 3 (n=10, k=3) Basically, in each node we maintain the key and its count. Initially, heap has the first element. 1:1 Search for 2 and insert( since its not found) 1:1 / 2:1 Search for 3 and insert ( since its not found). 1:1 / \ 2:1 3:1 Search for 3; since 3 is already there increment its count by 1. 1:1 / \ 2:1 3:2 Search for 2; since 2 is already there increment its count by 1. 1:1 / \ 2:2 3:2 and so on... Since, there are only k distinct keys the heap size will at most be k; so each search/insert/increment operation takes O(log k) time. Jagadish http://www.cse.iitb.ac.in/~jagadish On 2010-5-17 22:38, Jagadish M wrote: The best algorithm I can think of is to maintain a heap of k elements. Takes O(n log k) time. Is anything told about the values of the keys? If the keys have values less than N, then it is possible to do what you say, i.e sort them in place. -Jagadish http://www.cse.iitb.ac.in/~jagadish On May 13, 7:06 pm, divyasweetdivya@gmail.com wrote: This problem was asked in google phone interview. We have N element array with k distinct keys(No relation between k N given so assume kN) What is the best method to sort this array without using any extra memory? Please elaborate. -- 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 athttp:// 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 athttp:// 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 athttp://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] General issues about ACM (uva.onlinejudge.org) tasks and problem 103
Hi.
First: I'm new in ACM. 2 day took me to find out how to read and write
data in the tasks. There should be some sample code for beginners for
this.
Second: For me it is not clear what should be done, even if I read the
text of the tasks few times. I wonder if I am so intellectually
limited or it has to be so, but I don't know how to bite it.
Third: I sit on problem
103 Stacking Boxes. I sorted input rows (each box lengths
increasingly). Then I thought I have to sort boxes by the capacity or
something like that. So I sorted boxes by perimeter increasingly. And
then check if boxes nest to each other starting from the smallest one.
For sample input data from uva.onlinejudge.org and www.algorithmist.com
it works fine. For my data too. But it has to be wrong cause' of
Wrong answer if I submit the code. I would like my algorithm to
work.
Fourth: Solution from
http://cmagical.blogspot.com/2010/01/dowloads-1submitted-solutions-to...
works but I found place which I don't really understand:
#includestdio.h
#includestdlib.h
const int MAX = 33;
int boxes[MAX][12];
int rawIndex[MAX], v[MAX];
int path[MAX], rawsNumber, dimention;
int compare(const void *a, const void *s) {
return *(int *)a - *(int *)s;
}
int compareRaws(int n, int m){
for (int i = 0; i dimention; i++) {
if (boxes[n][i] = boxes[m][i]) {
return 0;
}
}
return 1;
}
void sortIndexes() {
for (int i = 0; i rawsNumber - 1; i++) {
for (int j = i + 1; j rawsNumber; j++) {
if (compareRaws(rawIndex[i], rawIndex[j])) {
rawIndex[i] ^= rawIndex[j] ^= rawIndex[i] ^=
rawIndex[j];
}
}
}
}
void print(int n){
if (path[n] == -1) {
printf(%d, rawIndex[n] + 1);
return;
}
print(path[n]);
printf( %d, rawIndex[n] + 1);
}
void solveCase() {
int max, indexSize = 0, last;
int par;
sortIndexes();
-- THIS PLACE I
DON'T UNDERSTAND
for (int i = 0; i rawsNumber; i++) {
max = 0;
par = -1;
for (int j = i - 1; j = 0; j--) {
if (compareRaws(rawIndex[i], rawIndex[j])) {
if (v[j] max) {
max = v[j];
par = j;
}
}
}
path[i] = par;
v[i] = max + 1;
if (v[i] indexSize) {
indexSize = v[i];
last = i;
}
}
printf(%d\n, indexSize);
print(last);
putchar('\n');
}
void readCase(){
for (int i = 0; i rawsNumber; i++) {
rawIndex[i] = i;
for (int j = 0; j dimention; j++) {
scanf(%d, boxes[i][j]);
}
qsort(boxes[i], dimention, sizeof(int), compare); // sorting
every read raw
}
}
int main(int argc, char *argv[]) {
while (scanf(%d%d, rawsNumber, dimention) == 2) {
readCase();
solveCase();
}
return 0;
}
It's kind of sorting indexes of raws by comparing values of two fields
i and j for each i and j. Rest of it is the algorithm I can imagine.
So any suggestions or reply to my rubbishy writing pleased welcome.
--
You received this message because you are subscribed to the Google
Groups acm_solver group.
To post to this group, send email to acm_sol...@googlegroups.com.
To unsubscribe from this group, send email to acm_solver
+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/acm_solver?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: another google telephone interview question
i think we can use sorting algorithm like insertion sort, in insertion sort whenever we are putting the element into it's proper position we can check whether this elements already exists don't put otherwise insert into into it's proper position (element) -- Prashant Kulkarni || Lokaha Samastaha Sukhino Bhavanthu || || Sarve Jana Sukhino Bhavanthu || On Wed, May 19, 2010 at 4:09 AM, Aarthi Thangamani aarthi.thangam...@gmail.com wrote: If you are using an extra space to count, why need a heap? An array of size k can be used to first count the occurances. Then run through the original array of size N and fill it according to the count our occirances using the constant k size array. Space O(k) and time O(N) is the best thing I think of. :( On Tue, May 18, 2010 at 7:11 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: Here u r using extra space to store count values.. CHERUVU JAANU REDDY M.Tech in CSIS On Tue, May 18, 2010 at 7:01 PM, Jagadish M jagadis...@gmail.com wrote: On May 18, 8:29 am, Terence technic@gmail.com wrote: How do you maintain the heap? Could you explain in detail for the following example: 1 2 3 3 2 1 1 1 2 3 (n=10, k=3) Basically, in each node we maintain the key and its count. Initially, heap has the first element. 1:1 Search for 2 and insert( since its not found) 1:1 / 2:1 Search for 3 and insert ( since its not found). 1:1 / \ 2:13:1 Search for 3; since 3 is already there increment its count by 1. 1:1 / \ 2:13:2 Search for 2; since 2 is already there increment its count by 1. 1:1 / \ 2:23:2 and so on... Since, there are only k distinct keys the heap size will at most be k; so each search/insert/increment operation takes O(log k) time. Jagadish http://www.cse.iitb.ac.in/~jagadishhttp://www.cse.iitb.ac.in/%7Ejagadish On 2010-5-17 22:38, Jagadish M wrote: The best algorithm I can think of is to maintain a heap of k elements. Takes O(n log k) time. Is anything told about the values of the keys? If the keys have values less than N, then it is possible to do what you say, i.e sort them in place. -Jagadish http://www.cse.iitb.ac.in/~jagadishhttp://www.cse.iitb.ac.in/%7Ejagadish On May 13, 7:06 pm, divyasweetdivya@gmail.com wrote: This problem was asked in google phone interview. We have N element array with k distinct keys(No relation between k N given so assume kN) What is the best method to sort this array without using any extra memory? Please elaborate. -- 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 athttp:// 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 athttp:// 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.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: number calculation
http://code.google.com/codejam/contest/dashboard?c=32016#s=aa=2 2010/5/19 Adrian kri...@gmail.com The only solution I can think of is to use the binomial theorem (http://en.wikipedia.org/wiki/Binomial_theorem) to expand (3+sqrt(5))^n . Then you only need to take into the account the terms where y (sqrt(5)) has an odd power because all others are integers and won't affect the decimals. Then after adding them up you'll end up with something like n * sqrt(5) where n is the total of the coeficients of sqrt(5) and then just do the math and find out the 3 decimals. -- 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. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- 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] General issues about ACM (uva.onlinejudge.org) tasks and problem 103
After ordering, you can solve it like the Longest Increasing Sequence (LIS)
problem, using Dynamic Programming.
2010/5/19 bob198107 robertosp...@gmail.com
Hi.
First: I'm new in ACM. 2 day took me to find out how to read and write
data in the tasks. There should be some sample code for beginners for
this.
Second: For me it is not clear what should be done, even if I read the
text of the tasks few times. I wonder if I am so intellectually
limited or it has to be so, but I don't know how to bite it.
Third: I sit on problem
103 Stacking Boxes. I sorted input rows (each box lengths
increasingly). Then I thought I have to sort boxes by the capacity or
something like that. So I sorted boxes by perimeter increasingly. And
then check if boxes nest to each other starting from the smallest one.
For sample input data from uva.onlinejudge.org and www.algorithmist.com
it works fine. For my data too. But it has to be wrong cause' of
Wrong answer if I submit the code. I would like my algorithm to
work.
Fourth: Solution from
http://cmagical.blogspot.com/2010/01/dowloads-1submitted-solutions-to...
works but I found place which I don't really understand:
#includestdio.h
#includestdlib.h
const int MAX = 33;
int boxes[MAX][12];
int rawIndex[MAX], v[MAX];
int path[MAX], rawsNumber, dimention;
int compare(const void *a, const void *s) {
return *(int *)a - *(int *)s;
}
int compareRaws(int n, int m){
for (int i = 0; i dimention; i++) {
if (boxes[n][i] = boxes[m][i]) {
return 0;
}
}
return 1;
}
void sortIndexes() {
for (int i = 0; i rawsNumber - 1; i++) {
for (int j = i + 1; j rawsNumber; j++) {
if (compareRaws(rawIndex[i], rawIndex[j])) {
rawIndex[i] ^= rawIndex[j] ^= rawIndex[i] ^=
rawIndex[j];
}
}
}
}
void print(int n){
if (path[n] == -1) {
printf(%d, rawIndex[n] + 1);
return;
}
print(path[n]);
printf( %d, rawIndex[n] + 1);
}
void solveCase() {
int max, indexSize = 0, last;
int par;
sortIndexes();
-- THIS PLACE I
DON'T UNDERSTAND
for (int i = 0; i rawsNumber; i++) {
max = 0;
par = -1;
for (int j = i - 1; j = 0; j--) {
if (compareRaws(rawIndex[i], rawIndex[j])) {
if (v[j] max) {
max = v[j];
par = j;
}
}
}
path[i] = par;
v[i] = max + 1;
if (v[i] indexSize) {
indexSize = v[i];
last = i;
}
}
printf(%d\n, indexSize);
print(last);
putchar('\n');
}
void readCase(){
for (int i = 0; i rawsNumber; i++) {
rawIndex[i] = i;
for (int j = 0; j dimention; j++) {
scanf(%d, boxes[i][j]);
}
qsort(boxes[i], dimention, sizeof(int), compare); // sorting
every read raw
}
}
int main(int argc, char *argv[]) {
while (scanf(%d%d, rawsNumber, dimention) == 2) {
readCase();
solveCase();
}
return 0;
}
It's kind of sorting indexes of raws by comparing values of two fields
i and j for each i and j. Rest of it is the algorithm I can imagine.
So any suggestions or reply to my rubbishy writing pleased welcome.
--
You received this message because you are subscribed to the Google
Groups acm_solver group.
To post to this group, send email to acm_sol...@googlegroups.com.
To unsubscribe from this group, send email to acm_solver
+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/acm_solver?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.
--
Mario Ynocente Castro
Undergraduate Student of System Engineering
National University of Engineering, Peru
http://sites.google.com/site/ycmario
--
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] String Problems
I don't think 1014 needs any special algorithm, if we've got an H x W matrix, then we've got (4H+4W-2) strings in which you must look, and you can do this with a greedy strategy. 2010/5/19 vignesh radhakrishnan rvignesh1...@gmail.com I'm trying to solve some string problems somewat efficiently. Can someone tell me what would be efficient DS for solving these problems http://acm.jlu.edu.cn/joj/showproblem.php?pid=1014 http://acm.jlu.edu.cn/joj/showproblem.php?pid=1873 Thanks, Regards, Vignesh -- There are two kinds of people. Those who care for others and The others -- 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. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- 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: number calculation
let @=3+sqrt(5) so @^n = (3+sqrt(5))^n =(an+bn*sqrt(5)) @^(n-1)=(3+sqrt(5))*(an+bn*sqrt(5)) so an+1=3an+5bn bn+1=an+3bn so [an bn]= A [an-1 bn -1] = A^n [a0 b0] where a0=1 and b0=0 where a= [ 3 5,1 3] calculate an and bn in each step and devide it by 1000 for next an and bn at end step ans=(an + bn*sqrt(5)) mod 1000 -- 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.
