[algogeeks] Contiguous Sub sequence
Given an unsorted integer array. Find the contiguous sub sequences whose sum is 0. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/pFvfWQjVrnkJ. To post to this group, send email to algogeeks@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] Contiguous Sub sequence
1. Calculate the sum of every prefix of the array O(n) 2. Store as pairs (sum, index) and sort by sum using a stable sort. Observation: Sum of every factor can be expressed as the difference between the sum of 2 prefixes. 3. for each entry search for the corresponding difference such the index found is greater than original index. Works for any sum, not just 0. Takes O(n log n) On 2 September 2012 14:22, Navin Kumar algorithm.i...@gmail.com wrote: Given an unsorted integer array. Find the contiguous sub sequences whose sum is 0. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/pFvfWQjVrnkJ. To post to this group, send email to algogeeks@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 algogeeks@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] Contiguous Sub sequence
Can you provide O(n) algo? On Sun, Sep 2, 2012 at 1:36 PM, Carl Barton odysseus.ulys...@gmail.comwrote: 1. Calculate the sum of every prefix of the array O(n) 2. Store as pairs (sum, index) and sort by sum using a stable sort. Observation: Sum of every factor can be expressed as the difference between the sum of 2 prefixes. 3. for each entry search for the corresponding difference such the index found is greater than original index. Works for any sum, not just 0. Takes O(n log n) On 2 September 2012 14:22, Navin Kumar algorithm.i...@gmail.com wrote: Given an unsorted integer array. Find the contiguous sub sequences whose sum is 0. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/pFvfWQjVrnkJ. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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 ouput
@Rahul kumar Dubey
#includestdio.h
double fn(char *a , int b , char c)
{
return (1.1);
}
int main()
{
int it = 2;
char ct = 'c';
char a[30];
printf(%d\n,(sizeof(fn)));
}
why it is always giving output as 1 irrespective of the return type of
function ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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] Microsoft written test question
help to solve the following.. Question: Two of the nodes of a BST are swapped. Correct the BST (taken from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd online test 3rd question) -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] Find all interesting sets(Google written test)
You have been given a large set of numbers S,(say, a 1 million number array). Write code to find (a)One interesting set from it (b)All interesting sets from it. An interesting set S' is any subset of S having following two properties: 1. S' has exactly 30 elements 2. No other 30 element subset of S has the sum of its elements same as the sum of elements of S' -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/U7NpnSgd7FcJ. To post to this group, send email to algogeeks@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] Contiguous Sub sequence
@pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 written test question
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
correctBST(root-left);
if(!temp1 prev root-data prev-data) {
temp1 = prev;
temp2 = root;
swap((temp1-data), (temp2-data));
flag = 1;
prev = temp1;
}
else if(!temp3 prev root-data prev-data) {
temp3 = root;
swap((temp1-data), (temp2-data));
swap((temp1-data), (temp3-data));
found = 1;
return;
}
if(!flag)
prev = root;
correctBST(root-right);
}
}
On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle patlerahulku...@gmail.com
wrote:
help to solve the following..
Question: Two of the nodes of a BST are swapped. Correct the BST (taken
from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd
online test 3rd question)
--
Thanks and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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 algogeeks@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] Contiguous Sub sequence
Your approach sounds like the optimal (and linear) algorithm for the submass finding problem. But if I recall correctly that only works in linear time if the input is entirely positive integers? Maybe I'm being stupid but wont checking that array be quadratic? On 2 September 2012 20:02, Navin Kumar algorithm.i...@gmail.com wrote: @pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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 ouput
@Rajat Dubey
Actually C forbids the use of sizeof() operator to a function name .(you
can see the warning using gcc -pedantic option of gcc )
so by writing
printf(%d,sizeof(fn) ); // u r trying to get the size of function fn
which in no way legal .
and output 1 is compiler dependent .
compile above program with g++ (that is in C++ ) you will get Error as it
has been made illegal in c++ now. and applyiong sizeof to an expression
of funtion type is illegal.
// but printf(%d\n,sizeof(fn())); here its the sizeof return value of
function call
On Sun, Sep 2, 2012 at 11:12 AM, RAJAT DUBEY rajatdubey2...@gmail.comwrote:
@Rahul kumar Dubey
#includestdio.h
double fn(char *a , int b , char c)
{
return (1.1);
}
int main()
{
int it = 2;
char ct = 'c';
char a[30];
printf(%d\n,(sizeof(fn)));
}
why it is always giving output as 1 irrespective of the return type of
function ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
*RAHUL KUMAR DUBEY*
*BTech-3rd year *
*Computer Science Engineering *
*Motilal Nehru National Institute Of Technology*
*Allahabad[211004],UP.*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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] Contiguous Sub sequence
@navin : hashMap can be used to do it in O(n) time. On 9/2/12, Carl Barton odysseus.ulys...@gmail.com wrote: Your approach sounds like the optimal (and linear) algorithm for the submass finding problem. But if I recall correctly that only works in linear time if the input is entirely positive integers? Maybe I'm being stupid but wont checking that array be quadratic? On 2 September 2012 20:02, Navin Kumar algorithm.i...@gmail.com wrote: @pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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] Contiguous Sub sequence
@carl : if it would work only for entirely positive integers , then i aux[] array created will never contain 0 or repeated elements... correct me if i am wrong... On 9/2/12, atul anand atul.87fri...@gmail.com wrote: @navin : hashMap can be used to do it in O(n) time. On 9/2/12, Carl Barton odysseus.ulys...@gmail.com wrote: Your approach sounds like the optimal (and linear) algorithm for the submass finding problem. But if I recall correctly that only works in linear time if the input is entirely positive integers? Maybe I'm being stupid but wont checking that array be quadratic? On 2 September 2012 20:02, Navin Kumar algorithm.i...@gmail.com wrote: @pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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] Contiguous Sub sequence
No you're correct. I was doubting it would work :P For hashing you would need perfect hashing to ensure O(n) wouldn't you? On 2 September 2012 23:21, atul anand atul.87fri...@gmail.com wrote: @carl : if it would work only for entirely positive integers , then i aux[] array created will never contain 0 or repeated elements... correct me if i am wrong... On 9/2/12, atul anand atul.87fri...@gmail.com wrote: @navin : hashMap can be used to do it in O(n) time. On 9/2/12, Carl Barton odysseus.ulys...@gmail.com wrote: Your approach sounds like the optimal (and linear) algorithm for the submass finding problem. But if I recall correctly that only works in linear time if the input is entirely positive integers? Maybe I'm being stupid but wont checking that array be quadratic? On 2 September 2012 20:02, Navin Kumar algorithm.i...@gmail.com wrote: @pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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] Can somebody suggest me AO* algo that convert a number n into strigs of 1's
Can somebody suggest me AO* algorithm that convert a number n into strigs of 1's n- (n-1)+1; n-ceil(n/2)+floor(n/2) h(n)=n and h(1)=0 Please help.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/P50j5K65iasJ. To post to this group, send email to algogeeks@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] Contiguous Sub sequence
@atul : suppose if all element of input array is zero then i think hashing will also produce n^2 output. so worst case time complexity would be O(n^2). On Sun, Sep 2, 2012 at 9:18 PM, Carl Barton odysseus.ulys...@gmail.comwrote: No you're correct. I was doubting it would work :P For hashing you would need perfect hashing to ensure O(n) wouldn't you? On 2 September 2012 23:21, atul anand atul.87fri...@gmail.com wrote: @carl : if it would work only for entirely positive integers , then i aux[] array created will never contain 0 or repeated elements... correct me if i am wrong... On 9/2/12, atul anand atul.87fri...@gmail.com wrote: @navin : hashMap can be used to do it in O(n) time. On 9/2/12, Carl Barton odysseus.ulys...@gmail.com wrote: Your approach sounds like the optimal (and linear) algorithm for the submass finding problem. But if I recall correctly that only works in linear time if the input is entirely positive integers? Maybe I'm being stupid but wont checking that array be quadratic? On 2 September 2012 20:02, Navin Kumar algorithm.i...@gmail.com wrote: @pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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] Contiguous Sub sequence
@navin : this case can be avoided by checking input array first , if it contain all zero or notwhich will be O(n). On 9/2/12, Navin Kumar algorithm.i...@gmail.com wrote: @atul : suppose if all element of input array is zero then i think hashing will also produce n^2 output. so worst case time complexity would be O(n^2). On Sun, Sep 2, 2012 at 9:18 PM, Carl Barton odysseus.ulys...@gmail.comwrote: No you're correct. I was doubting it would work :P For hashing you would need perfect hashing to ensure O(n) wouldn't you? On 2 September 2012 23:21, atul anand atul.87fri...@gmail.com wrote: @carl : if it would work only for entirely positive integers , then i aux[] array created will never contain 0 or repeated elements... correct me if i am wrong... On 9/2/12, atul anand atul.87fri...@gmail.com wrote: @navin : hashMap can be used to do it in O(n) time. On 9/2/12, Carl Barton odysseus.ulys...@gmail.com wrote: Your approach sounds like the optimal (and linear) algorithm for the submass finding problem. But if I recall correctly that only works in linear time if the input is entirely positive integers? Maybe I'm being stupid but wont checking that array be quadratic? On 2 September 2012 20:02, Navin Kumar algorithm.i...@gmail.com wrote: @pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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] Contiguous Sub sequence
@atul: what if n-1 contiguous 0's are there?? Can't we have some mechanism in hash such that it will avoid O(n^2) ?? On Mon, Sep 3, 2012 at 12:29 AM, atul anand atul.87fri...@gmail.com wrote: @navin : this case can be avoided by checking input array first , if it contain all zero or notwhich will be O(n). On 9/2/12, Navin Kumar algorithm.i...@gmail.com wrote: @atul : suppose if all element of input array is zero then i think hashing will also produce n^2 output. so worst case time complexity would be O(n^2). On Sun, Sep 2, 2012 at 9:18 PM, Carl Barton odysseus.ulys...@gmail.comwrote: No you're correct. I was doubting it would work :P For hashing you would need perfect hashing to ensure O(n) wouldn't you? On 2 September 2012 23:21, atul anand atul.87fri...@gmail.com wrote: @carl : if it would work only for entirely positive integers , then i aux[] array created will never contain 0 or repeated elements... correct me if i am wrong... On 9/2/12, atul anand atul.87fri...@gmail.com wrote: @navin : hashMap can be used to do it in O(n) time. On 9/2/12, Carl Barton odysseus.ulys...@gmail.com wrote: Your approach sounds like the optimal (and linear) algorithm for the submass finding problem. But if I recall correctly that only works in linear time if the input is entirely positive integers? Maybe I'm being stupid but wont checking that array be quadratic? On 2 September 2012 20:02, Navin Kumar algorithm.i...@gmail.com wrote: @pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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
[algogeeks] MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
-- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/aLuPUOKxmaoJ. To post to this group, send email to algogeeks@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] BST to DLL code: whats wrong with this code........
Hi
I am trying to convert the BST to doubly linked list but I am getting
desired output with this code Plz correct this code.
#includestdio.h
#includestdlib.h
typedef struct tree mytree;
struct tree
{
int data;
mytree* left;
mytree* right;
};
void insert(mytree** root,int data)
{
if(*root==NULL)
{
mytree* node=(mytree*)malloc(sizeof(mytree));
if(node==NULL)
return;
else
{
node-data=data;
node-left=NULL;
node-right=NULL;
}
*root=node;
return;
}
else
{
if((*root)-data =data)
insert((*root)-left,data);
else
insert((*root)-right,data);
}
}
void traverse(mytree* ptr)
{
if(ptr==NULL) return;
traverse(ptr-left);
printf(%d\t,ptr-data);
traverse(ptr-right);
}
void traversell(mytree* ptr)
{
if(ptr==NULL) return;
while(ptr!=NULL)
{
printf(%d\t,ptr-data);
ptr=ptr-right;
}
}
void bst22ll(mytree** tree,mytree** head)
{
static mytree* prev=NULL;
if(*tree==NULL) return;
mytree* ptr=*tree;
if((*tree)-left!=NULL)
bst22ll((*tree)-left,head);
*tree=ptr;
if(*head==NULL)
{
*head=*tree;
(*head)-left==NULL;
}
else
{
prev-right=*tree;
(*tree)-left=prev;
}
prev=*tree;
if((*tree)-right!=NULL)
{
bst22ll((*tree)-right,head);
}
}
void bst2ll(mytree** tree)
{
if(tree==NULL) return;
mytree* head=NULL;
mytree* prev=NULL;
bst22ll(tree,head);
*tree=head;
}
int main()
{
mytree* tree=NULL;
insert(tree,50);
insert(tree,40);
insert(tree,60);
insert(tree,30);
insert(tree,70);
insert(tree,65);
insert(tree,45);
insert(tree,34);
traverse(tree);
bst2ll(tree);
printf(\n);
traversell(tree);
printf(\n);
}
should print : 30 34 40 45 50 60 65 70
but printing: 30 34 40 45 50 60 70
Thank you
Shubham
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/XXMvBSg0t08J.
To post to this group, send email to algogeeks@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 written test question
@navin: can u explain ur algorithms in words pls..
On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar algorithm.i...@gmail.comwrote:
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
correctBST(root-left);
if(!temp1 prev root-data prev-data) {
temp1 = prev;
temp2 = root;
swap((temp1-data), (temp2-data));
flag = 1;
prev = temp1;
}
else if(!temp3 prev root-data prev-data) {
temp3 = root;
swap((temp1-data), (temp2-data));
swap((temp1-data), (temp3-data));
found = 1;
return;
}
if(!flag)
prev = root;
correctBST(root-right);
}
}
On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
help to solve the following..
Question: Two of the nodes of a BST are swapped. Correct the BST (taken
from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd
online test 3rd question)
--
Thanks and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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 algogeeks@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.
--
Thanks and Regards:
Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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 matching problem
http://www.geeksforgeeks.org/archives/19267 On Mon, Sep 3, 2012 at 7:41 AM, Amitesh Singh singh.amit...@gmail.comwrote: Given a array, find the largest contiguous sub-array having its sum equal to N. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
convert BST to sorted DLL.. now it is a double linked list , so we can find 2 number in O(n) time by keeping 2 pointers(one at start and one at end) from sorted DLL. now convert DLL to BST. On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar algorithm.i...@gmail.comwrote: -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/aLuPUOKxmaoJ. To post to this group, send email to algogeeks@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 algogeeks@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:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
@Atul007: No need to destroy the BST. Perform two simultaneous inorder traversals of the BST, one from left to right (the usual direction) and one from right to left. At any stage you have selected two nodes. If the sum is less than the given number, advance the left-to-right traversal; If the sum is greater, advance the right-to-left traversal. Quit with success when the sum equals the given number or with failure when the two traversals have reached the same node. Dave On Sunday, September 2, 2012 11:00:42 PM UTC-5, atul007 wrote: convert BST to sorted DLL.. now it is a double linked list , so we can find 2 number in O(n) time by keeping 2 pointers(one at start and one at end) from sorted DLL. now convert DLL to BST. On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar algorit...@gmail.comjavascript: wrote: MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/oizd-5CSfuoJ. To post to this group, send email to algogeeks@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 matching problem
@atul: question is to find the largest continuous sub array .. not just continuous sub array .. we can do this with same logic as mentioned in the above link.. we have to traverse whole array.. even if we get the solution .. whenever we get the solution,update the largest_subarray_start_index and largest_subarray_end_index based on previous length of the solution sub array . On Mon, Sep 3, 2012 at 9:26 AM, atul anand atul.87fri...@gmail.com wrote: http://www.geeksforgeeks.org/archives/19267 On Mon, Sep 3, 2012 at 7:41 AM, Amitesh Singh singh.amit...@gmail.comwrote: Given a array, find the largest contiguous sub-array having its sum equal to N. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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.
