Re: [algogeeks] google
This question was already discussed.
On 14 October 2010 15:36, Manish K manish.ag...@gmail.com wrote:
Hi,
Take an example :
Array A: {a1,a2,a3,a4,a5}- (sorted decreasingly)
Array B :{b1,b2,b3,b4,b5}- (sorted decreasingly)
First pair is(a1,b1) .
Now for Second pair Compare the sum of (b1,a2) and (a1,b2) whichever is
greater .
if (a1,b2) is the second pair then now compare (b1,a2) and (a1,b3) .
Repeat the above process till u will get first n pairs.
Complexity O(n).
Thanks
Manish
On Thu, Oct 14, 2010 at 3:24 PM, arun raghavendar arun.s...@gmail.comwrote:
Start merging A and B from the tail end for N elements, just like the way
you would do it for a merge sort but with a different constraint based on
the sum a[i] and b[i]
This should work for any value of N, I just hard-coded it for simplicity.
#includestdio.h
#define N 6
struct OutputType {
int a;
int b;
int value;
};
int main() {
int a[N] = {1,8,13,24,25,30};
int b[N] = {5,6,17,28,29,29};
struct OutputType s[N];
int i, a_candidate_1 = N-1, a_candidate_2=N-2, b_candidate_1=N-1,
b_candidate_2=N-2;
s[0].a = a[N-1];
s[0].b = b[N-1];
s[0].value = a[N-1] + b[N-1];
for (i=1;iN;i++) {
if ((a[a_candidate_1]+b[b_candidate_2]) =
(a[a_candidate_2]+b[b_candidate_1])) {
s[i].a = a[a_candidate_1];
s[i].b = b[b_candidate_2];
s[i].value = a[a_candidate_1]+b[b_candidate_2];
b_candidate_2--;
if (b_candidate_2 0) { a_candidate_1--; }
} else {
s[i].a = a[a_candidate_2];
s[i].b = b[b_candidate_1];
s[i].value = a[a_candidate_2]+b[b_candidate_1];
a_candidate_2--;
if (a_candidate_2 0) { b_candidate_1--; }
}
}
for (i=0;iN;i++) printf((%d,%d)=%3d , s[i].a, s[i].b,
s[i].value);
return 0;
}
-Arun
On Thu, Oct 14, 2010 at 1:25 PM, Harshal hc4...@gmail.com wrote:
Given two sorted postive integer arrays A[n] and B[n] (W.L.O.G, let's
say they are decreasingly sorted), we define a set S = {(a,b) | a \in A
and b \in B}. Obviously there are n^2 elements in S. The value of such
a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
Harshal Choudhary,
III Year B.Tech Undergraduate,
Computer Engineering Department,
National Institute of Technology Surathkal, Karnataka
India.
--
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.
--
Thanks and Regards,
N. Ravikanth
--
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: BST
I think we can solve this problem by changing the right sub tree of the root
in to linked list in the following way. Here is an example
5
4 7
2 3 89
5
4 9
2 3 8
7
This gives us access to the lowest number and the highest number in the
tree. We can start with the left most child and first right child of the
root.
On 27 July 2010 07:06, Gene gene.ress...@gmail.com wrote:
Look up threaded tree in wikipedia.
On Jul 26, 9:12 pm, Snoopy Me thesnoop...@gmail.com wrote:
Hey could you please give a very brief on what is meant by threads in
bst?
On Jul 27, 5:17 am, Gene gene.ress...@gmail.com wrote:
You don't thread the tree when you're ready to search it. Rather you
maintain the threads as it's built, which adds nothing to the
asymptotic run time. Parent pointers are a simpler way to get the
same result. However, both solutions require O(n) extra memory for
tag bits or pointers. You're better off just using iterators with
O(log n) stacks. I don't think there's a way to solve this problem
in
O(n) time with less than O(log n) memory.
On Jul 26, 6:18 am, rahul patil rahul.deshmukhpa...@gmail.com wrote:
@ Gene
Your solution seems great and most appropriate one.
Just need to create threads in BST first.What will be time complexity
for that?
On Jul 25, 11:08 pm, Gene gene.ress...@gmail.com wrote:
You'd know how to do this if you had a sorted array A, right?
Start a
pointer at each end. Call the L and R.
L = 0;
R = length(A) - 1
while (L R) {
while (L R A[L] + A[R} k) --R;
if (A[L] + A[R} == k) return L, R;
++L;}
return failed
Since you have a BST, just replace L and R with iterators that scan
from left to right and right to left through the tree. The
ammortized
cost of an iterator call is O(1), and there are clearly O(n) calls,
where n = lengh(A).
The iterators can each contain a O(log n) stack, but you seem
willing
to ignore log n stack space. You could get rid of the stacks by
threading the tree.
On Jul 24, 12:03 am, Priyanka Chatterjee dona.1...@gmail.com
wrote:
Given a binary search tree of n nodes, find two nodes whose sum
is equal to
a given number k in O(n) time and constant space.
(ignoring recursion stack space)
I have got O(nlogn) time , O(1) space and O(n) time, O(n) space.
Please
help me out with O(n) time and O(1) space.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
Indiahttp://priyanka-nit.blogspot.com/
--
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 and Regards,
N. Ravikanth
--
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] You have 2 arrays of integer. You have to write a function, which take an integer as input and returns bool. Example array 1 has {1,5,10} array 2 has {2,5,9}. Func(3) should return t
If arrays are sorted, Merge Array A and B then use the algorithm to find a
pair whose sum equals required number.
On 24 July 2010 18:49, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
hmm.
thnxx for the case
On Sat, Jul 24, 2010 at 3:17 PM, Algoose chase harishp...@gmail.comwrote:
@jalaj
TRY
A:16, 12, 10, 6 ,2
B:11, 10,7, 2, 1
num: 26
On Sat, Jul 24, 2010 at 5:13 AM, jalaj jaiswal jalaj.jaiswa...@gmail.com
wrote:
Take two pointers both at the start of each array...
i=0,j=0
let the size of sorted arrays be m and n
int func(int num,int m,int n){
int i=0,j=0;
while (imjn){
if((num=a[i])||(num=a[j])||num(a[i]+b[j]))
return 0;
if(num==(a[i]+b[j]))
return 1;
if(numa[i]+b[j]){
if(a[i]b[j]) j++;
else i++;
}
}
return 0;
}
O(m+n) complexity
Ps. i'm returning true if the number equals a[i]+b[j] and not just when
it equals a single element in any array
On Fri, Jul 23, 2010 at 9:22 AM, Shafi Ahmad shafi.ah...@gmail.comwrote:
Let argument of function Func is k.
Case 1: If at least on of the array is sorted (say array1) then.
For each number in array2, do
1. binary search for (k - array1[i]) in array1
2. if found
return true.
else
return false
case 2: Arrays are not sorted then
1. Sort one array and apply algo for case 1.
Time complexity will be sizeof(unsortedarray)log (sizeofsortedarray).
Regards,
Shafi
On Fri, Jul 23, 2010 at 12:01 AM, vijay auvija...@gmail.com wrote:
You have 2 arrays of integer. You have to write a function, which take
an integer as input and returns bool. Example array 1 has {1,5,10}
array 2 has {2,5,9}. Func(3) should return true, since 1 (from array
1) +2 (from array 2) =3 ( i.e summation of 2 numbers (1 from each
array) is equal to 3). Func(13) should return false
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Shafi Ahmad
The difficult we do immediately, the impossible takes a little
longerUS Army
--
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.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks and Regards,
N. Ravikanth
--
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.
