Re: [algogeeks] Re: Finding closest double in a Btree
ignore my post...its working fine , there are no bugs On Tue, Feb 21, 2012 at 11:34 AM, atul anand atul.87fri...@gmail.comwrote: @above : typo mistake : in the given example inorder of BST = 10 20 30 40 50 key = 27 output: floor= 20 -- 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] Re: Finding closest double in a Btree
I was fairly certain that the poster was asking about binary search
trees. I realized that he did not say that, but I also realized that
there is nothing to the problem if it is not a binary search tree. So
I answered the problem which I believed the poster was asking. That
might not fly in school, but in industry that is called anticipating
the customer's needs.
Don
On Feb 20, 6:28 pm, Dave dave_and_da...@juno.com wrote:
@Don: By that measure, it also is trivial if the tree is a BST. You
just find the largest node x and the smallest one x and choose
between them.
But since the original problem did not specify a BST, your solution is
non-responsive. If I were grading a test, I'd have to count your
solution as wrong, figuring that you do not know the difference
between a binary tree and a binary search tree.
Dave
On Feb 20, 5:13 pm, Don dondod...@gmail.com wrote:
Yes, I am assuming a binary search tree. The problem is trivial
otherwise.
If it is just a binary tree, you visit each node and keep track of the
closest.
Don
On Feb 20, 5:02 pm, Dave dave_and_da...@juno.com wrote:
@Don: Aren't you assuming a binary _search_ tree? Only a binary tree
was specified by the OP.
Dave
On Feb 20, 10:44 am, Don dondod...@gmail.com wrote:
Supraja,
I think that your solution will work, but it does more work than is
necessary. You don't need to traverse the entire tree.
node findClosest(node root, double k)
{
node result = root;
double diff = fabs(root-value - k);
for(node loc = root; loc; loc = (loc-value k) ? loc-left :
loc-right)
{
double newDiff = fabs(loc-value - k);
if (newDiff diff)
{
result = loc;
diff = newDiff;
}
}
return result;
}
On Feb 20, 5:24 am, Supraja Jayakumar suprajasank...@gmail.com
wrote:
Hi
Question is given a binary tree and a key K, code to find the node
with the
closest value.
I'd be happy to receive some feedback about my solution too.
Pls find the code below:
class FindingClosestNodeInTree {
private static double difference = 0.0;
private static doule key = 0.0;
int main() {
BinaryTree bt;
bt.insert(20.43);
bt.insert(12.78);
bt.insert(19.89);
bt.insert(32.69);
bt.insert(2.54);
cout Please provide the key value endl;
cin key;
const Node closestNode = closestValue(bt);
cout Node that has the closest value to
closestNode.value;
return 1;}
const Node closestValue(const BinaryTree node) {
if(node==null)
return;
int val = node.value;
int currDiff = val key ? val-key:key-val;
difference = currDiff difference ? currDiff:difference;
if(node.left!=null)
closestValue(node.left);
if(node.right!=null)
closestValue(node.right);
return difference;
}
}
Thanks
Supraja J- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
--
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] Re: Finding closest double in a Btree
Supraja,
You asked for feedback on your solution.
First of all, difference is a static class member which is set to
zero. There is nothing to reset difference for each time you call your
function. Therefore, if you call the function more than once, the old
value will still be there.
Second, you ask for the node with the value closest to k. Your code
sets difference to the largest value, not the smallest.
Third, you ask for the node, and your function is written to return a
node, but it actually returns the value of difference. In another
place it returns nothing. I don't think a compiler would accept that.
Putting main inside a class will not work either.
Don
On Feb 20, 5:24 am, Supraja Jayakumar suprajasank...@gmail.com
wrote:
Hi
Question is given a binary tree and a key K, code to find the node with the
closest value.
I'd be happy to receive some feedback about my solution too.
Pls find the code below:
class FindingClosestNodeInTree {
private static double difference = 0.0;
private static doule key = 0.0;
int main() {
BinaryTree bt;
bt.insert(20.43);
bt.insert(12.78);
bt.insert(19.89);
bt.insert(32.69);
bt.insert(2.54);
cout Please provide the key value endl;
cin key;
const Node closestNode = closestValue(bt);
cout Node that has the closest value to
closestNode.value;
return 1;}
const Node closestValue(const BinaryTree node) {
if(node==null)
return;
int val = node.value;
int currDiff = val key ? val-key:key-val;
difference = currDiff difference ? currDiff:difference;
if(node.left!=null)
closestValue(node.left);
if(node.right!=null)
closestValue(node.right);
return difference;
}
}
Thanks
Supraja J
--
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] MODULUS
how can we take mod by a very large number for example 100283 int mod = 100283; ans % mod is not working Please Help -- 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] Re: MODULUS
A 32-bit integer can not store numbers that large, so you need to use something with more than 32 bits. For your example, a 64-bit integer should work. Try using type long long int. Some compilers call it __int64. If you need something larger than your compiler provides, you can use an extended precision library such as NTL. Don On Feb 21, 8:40 am, Anurag Gupta anurag.gupta...@gmail.com wrote: how can we take mod by a very large number for example 100283 int mod = 100283; ans % mod is not working Please Help -- 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] MODULUS
Why you expect it should work...? the constant you assigned to mod is not within int range declare it as long long mod = 100283LL; and it would work. On Tue, Feb 21, 2012 at 8:10 PM, Anurag Gupta anurag.gupta...@gmail.comwrote: how can we take mod by a very large number for example 100283 int mod = 100283; ans % mod is not working Please Help -- 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. -- -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@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.
[algogeeks] Re : Any hints[kth smallest contiguous sum] ?
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/ -- 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] Re : Any hints[kth smallest contiguous sum] ?
i dont know if a better solution exists but here is one with complexity O(N*logS)... N = no of elements in array S = max sum of a subarray that is sum of all the elements as all are positive algo goes as follows do a binary search in range 0-S, for each such candidate sum find how many sums are smaller than candidate sum there is also need to take care of some cases when there are exactly k-1 sums less than candidate sum, but there is no contigious where sum = candidate sum. On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote: Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/ -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] use of sentinel in linked list
How to implement a linked list using sentineli mean sentinel will be having some non-null address.then how would u identify it except remembering the address. -- 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] Re : Any hints[kth smallest contiguous sum] ?
didn't get you, how to check for subsequences which doesn't start from the beginning ? can you explain for that same example... should we check for all contiguous subsequences of some particular length? On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal sunny816.i...@gmail.comwrote: i dont know if a better solution exists but here is one with complexity O(N*logS)... N = no of elements in array S = max sum of a subarray that is sum of all the elements as all are positive algo goes as follows do a binary search in range 0-S, for each such candidate sum find how many sums are smaller than candidate sum there is also need to take care of some cases when there are exactly k-1 sums less than candidate sum, but there is no contigious where sum = candidate sum. On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote: Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/ -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Re : Any hints[kth smallest contiguous sum] ?
if i am getting it right input has only positive number then if k = N (number of elements) , then it would similar to finding kth smallest element in the array. because we can consider each element in the input as a sub array. now if k N , then we need to find (k-N)th smallest element which should be sum two or more elements. On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal sunny816.i...@gmail.comwrote: i dont know if a better solution exists but here is one with complexity O(N*logS)... N = no of elements in array S = max sum of a subarray that is sum of all the elements as all are positive algo goes as follows do a binary search in range 0-S, for each such candidate sum find how many sums are smaller than candidate sum there is also need to take care of some cases when there are exactly k-1 sums less than candidate sum, but there is no contigious where sum = candidate sum. On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote: Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/ -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Re: use of sentinel in linked list
What are you using the sentinel for? A marker for the end of the list?
A common way to implement a linked list is to use a sentinal as the
head of a circularly linked list.
Thus, an empty list is a pointer to the sentinal which is linked to
itsself.
The advantage is that there are fewer special cases to consider when
you need to insert or delete an item from the list.
For example, to delete an item from the list, you don't need a special
case to handle deleting the first item.
For instance:
class node
{
public:
int data;
struct node *next;
};
class list
{
public:
list() // Construct an empty list
{
_head = new node;
_head-next = _head;
_head-data = 0;
}
bool isEmpty() { return _head == _head-next; }
void insert(int n) // Insert n at head of list
{
node *tmp = new node;
tmp-data = n;
tmp-next = _head-next;
_head-next = tmp;
}
void delete(int n) // Delete first node with value n
{
node *p;
for(p = _head; p != _head; p = p-next)
{
if (p-next-data == n)
{
node *tmp = p-next;
p-next = tmp-next;
delete tmp;
break;
}
}
etc...
}
private:
node *_head;
};
On Feb 21, 12:00 pm, karthikeya s karthikeya.a...@gmail.com wrote:
How to implement a linked list using sentineli mean sentinel will
be having some non-null address.then how would u identify it
except remembering the address.
--
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] Re : Any hints[kth smallest contiguous sum] ?
can you do it for some example where k N... i am confused On Wed, Feb 22, 2012 at 12:22 AM, atul anand atul.87fri...@gmail.comwrote: if i am getting it right input has only positive number then if k = N (number of elements) , then it would similar to finding kth smallest element in the array. because we can consider each element in the input as a sub array. now if k N , then we need to find (k-N)th smallest element which should be sum two or more elements. On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal sunny816.i...@gmail.comwrote: i dont know if a better solution exists but here is one with complexity O(N*logS)... N = no of elements in array S = max sum of a subarray that is sum of all the elements as all are positive algo goes as follows do a binary search in range 0-S, for each such candidate sum find how many sums are smaller than candidate sum there is also need to take care of some cases when there are exactly k-1 sums less than candidate sum, but there is no contigious where sum = candidate sum. On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote: Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/ -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Re : Any hints[kth smallest contiguous sum] ?
we need to find how many sums are less than candidate Sum chosen in one
iteration of binary search in range 0-S
To count this, for each i we try to find how many sums ending at i are
lesser than candidate sum !!
lets say for some i-1 sum[0 - i-1] candidate sum then we can say that
i*(i-1)/2 sums are less than candidate sum.
now lets say after adding a[i] again sum[0 - i] candidateSum then u can
add (i+1) to previous count because all sums [0 - i], sum[1 - i],
. sum[i - i] will be lesser than candidate sum
or if adding a[i] causes sum[0 - i] candidateSum then u have to find a
index g such that sum[g - i] candidate sum, and increase the count by
((i)-(g) +1).
eg lets say your candidate sum is 7 (for the given example{1,2,3,4,5}) k =
3 n = 5
initially g = 0
sum = 0;
candidateSum = 7;
count = 0
iteration one:
sum[0 - 0] = 1 7 so count += 0-0+1;
iteration 2
sum[0-1] = 3 7, count += 1-0+1
iteration 3
sum[0-2] = 6 7 count += 2-0+1;
iteration 4
sum[0,3] = 10 7 so now increment g such that sum[g,i] 7
so g = 3count += 3-3+1;
iteration 5
sum[3 - 4] = 9 7
new g = 4 count += 4-4+1
final count = 8, so there are 8 sums less than 7
On Wed, Feb 22, 2012 at 12:16 AM, shady sinv...@gmail.com wrote:
didn't get you, how to check for subsequences which doesn't start from the
beginning ? can you explain for that same example... should we check for
all contiguous subsequences of some particular length?
On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
i dont know if a better solution exists
but here is one with complexity O(N*logS)...
N = no of elements in array
S = max sum of a subarray that is sum of all the elements as all are
positive
algo goes as follows
do a binary search in range 0-S, for each such candidate sum find how
many sums are smaller than candidate sum
there is also need to take care of some cases when there are exactly k-1
sums less than candidate sum, but there is no contigious where sum =
candidate sum.
On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote:
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] Re : Any hints[kth smallest contiguous sum] ?
great solution :D
thanks.
On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal sunny816.i...@gmail.comwrote:
we need to find how many sums are less than candidate Sum chosen in one
iteration of binary search in range 0-S
To count this, for each i we try to find how many sums ending at i are
lesser than candidate sum !!
lets say for some i-1 sum[0 - i-1] candidate sum then we can say that
i*(i-1)/2 sums are less than candidate sum.
now lets say after adding a[i] again sum[0 - i] candidateSum then u can
add (i+1) to previous count because all sums [0 - i], sum[1 - i],
. sum[i - i] will be lesser than candidate sum
or if adding a[i] causes sum[0 - i] candidateSum then u have to find a
index g such that sum[g - i] candidate sum, and increase the count by
((i)-(g) +1).
eg lets say your candidate sum is 7 (for the given example{1,2,3,4,5}) k =
3 n = 5
initially g = 0
sum = 0;
candidateSum = 7;
count = 0
iteration one:
sum[0 - 0] = 1 7 so count += 0-0+1;
iteration 2
sum[0-1] = 3 7, count += 1-0+1
iteration 3
sum[0-2] = 6 7 count += 2-0+1;
iteration 4
sum[0,3] = 10 7 so now increment g such that sum[g,i] 7
so g = 3count += 3-3+1;
iteration 5
sum[3 - 4] = 9 7
new g = 4 count += 4-4+1
final count = 8, so there are 8 sums less than 7
On Wed, Feb 22, 2012 at 12:16 AM, shady sinv...@gmail.com wrote:
didn't get you, how to check for subsequences which doesn't start from
the beginning ? can you explain for that same example... should we check
for all contiguous subsequences of some particular length?
On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
i dont know if a better solution exists
but here is one with complexity O(N*logS)...
N = no of elements in array
S = max sum of a subarray that is sum of all the elements as all are
positive
algo goes as follows
do a binary search in range 0-S, for each such candidate sum find how
many sums are smaller than candidate sum
there is also need to take care of some cases when there are exactly k-1
sums less than candidate sum, but there is no contigious where sum =
candidate sum.
On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote:
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] Re: Re : Any hints[kth smallest contiguous sum] ?
Here is a possible approach: Use a heap in which each element contains a range and the sum for that range. Initially the heap contains n ranges of size one, one per balloon, where the sum is the score for that one balloon. Then k times you extend the smallest range by one by adding the smaller of the 2 adjacent balloons and downheap. Then the range at the top of the heap is the kth smallest contiguous sum. This is O(k * log n). Since k can be n*(n+1)/2, in the worst case this is O(n^2 log n). Don On Feb 21, 11:32 am, shady sinv...@gmail.com wrote: Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/ -- 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] Re: use of sentinel in linked list
Exactly. The other trick is when maintaining a list in ascending
sorted order, to give the sentinel a key of infinite. This way you
need not check for the end of list at all. The key comparison will
always stop before the last element. I vaguely recall Wirth uses this
example in his book Algorithms + Data Structures = Programs, but I
haven't picked it up for years, so this could be false.
On Feb 21, 2:00 pm, Don dondod...@gmail.com wrote:
What are you using the sentinel for? A marker for the end of the list?
A common way to implement a linked list is to use a sentinal as the
head of a circularly linked list.
Thus, an empty list is a pointer to the sentinal which is linked to
itsself.
The advantage is that there are fewer special cases to consider when
you need to insert or delete an item from the list.
For example, to delete an item from the list, you don't need a special
case to handle deleting the first item.
For instance:
class node
{
public:
int data;
struct node *next;
};
class list
{
public:
list() // Construct an empty list
{
_head = new node;
_head-next = _head;
_head-data = 0;
}
bool isEmpty() { return _head == _head-next; }
void insert(int n) // Insert n at head of list
{
node *tmp = new node;
tmp-data = n;
tmp-next = _head-next;
_head-next = tmp;
}
void delete(int n) // Delete first node with value n
{
node *p;
for(p = _head; p != _head; p = p-next)
{
if (p-next-data == n)
{
node *tmp = p-next;
p-next = tmp-next;
delete tmp;
break;
}
}
etc...
}
private:
node *_head;
};
On Feb 21, 12:00 pm, karthikeya s karthikeya.a...@gmail.com wrote:
How to implement a linked list using sentineli mean sentinel will
be having some non-null address.then how would u identify it
except remembering the address.
--
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] Re : Any hints[kth smallest contiguous sum] ?
@sunny : before moving to your algorithm , i can see wrong output in your
example:-
in you example dere are 8 sums less than 7.
but for given input contiguous sum less than 7 are
1,2,3,4,5 = 4
contiguous sum (1,2) , (2,3) -- these contiguous sum has already been
counted
so output is 4.
correct me if i am wrong...
On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal sunny816.i...@gmail.comwrote:
we need to find how many sums are less than candidate Sum chosen in one
iteration of binary search in range 0-S
To count this, for each i we try to find how many sums ending at i are
lesser than candidate sum !!
lets say for some i-1 sum[0 - i-1] candidate sum then we can say that
i*(i-1)/2 sums are less than candidate sum.
now lets say after adding a[i] again sum[0 - i] candidateSum then u can
add (i+1) to previous count because all sums [0 - i], sum[1 - i],
. sum[i - i] will be lesser than candidate sum
or if adding a[i] causes sum[0 - i] candidateSum then u have to find a
index g such that sum[g - i] candidate sum, and increase the count by
((i)-(g) +1).
eg lets say your candidate sum is 7 (for the given example{1,2,3,4,5}) k =
3 n = 5
initially g = 0
sum = 0;
candidateSum = 7;
count = 0
iteration one:
sum[0 - 0] = 1 7 so count += 0-0+1;
iteration 2
sum[0-1] = 3 7, count += 1-0+1
iteration 3
sum[0-2] = 6 7 count += 2-0+1;
iteration 4
sum[0,3] = 10 7 so now increment g such that sum[g,i] 7
so g = 3count += 3-3+1;
iteration 5
sum[3 - 4] = 9 7
new g = 4 count += 4-4+1
final count = 8, so there are 8 sums less than 7
On Wed, Feb 22, 2012 at 12:16 AM, shady sinv...@gmail.com wrote:
didn't get you, how to check for subsequences which doesn't start from
the beginning ? can you explain for that same example... should we check
for all contiguous subsequences of some particular length?
On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
i dont know if a better solution exists
but here is one with complexity O(N*logS)...
N = no of elements in array
S = max sum of a subarray that is sum of all the elements as all are
positive
algo goes as follows
do a binary search in range 0-S, for each such candidate sum find how
many sums are smaller than candidate sum
there is also need to take care of some cases when there are exactly k-1
sums less than candidate sum, but there is no contigious where sum =
candidate sum.
On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote:
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] Re : Any hints[kth smallest contiguous sum] ?
@atul there are 8 sums less than 7
sum[0 - 0] = 1
sum[1-1] = 2
sum[2 - 2] = 3
sum[3-3] = 4
sum[4-4] = 5
sum[0-1] = 3
sum[0-2] = 6
sum[1-2] = 5
contiguous sum (1,2) , (2,3) -- these contiguous sum has already been
counted ??? where ?
Read problem statement carefully !!
On Wed, Feb 22, 2012 at 9:39 AM, atul anand atul.87fri...@gmail.com wrote:
@sunny : before moving to your algorithm , i can see wrong output in your
example:-
in you example dere are 8 sums less than 7.
but for given input contiguous sum less than 7 are
1,2,3,4,5 = 4
so output is 4.
correct me if i am wrong...
On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
we need to find how many sums are less than candidate Sum chosen in one
iteration of binary search in range 0-S
To count this, for each i we try to find how many sums ending at i are
lesser than candidate sum !!
lets say for some i-1 sum[0 - i-1] candidate sum then we can say that
i*(i-1)/2 sums are less than candidate sum.
now lets say after adding a[i] again sum[0 - i] candidateSum then u can
add (i+1) to previous count because all sums [0 - i], sum[1 - i],
. sum[i - i] will be lesser than candidate sum
or if adding a[i] causes sum[0 - i] candidateSum then u have to find a
index g such that sum[g - i] candidate sum, and increase the count by
((i)-(g) +1).
eg lets say your candidate sum is 7 (for the given example{1,2,3,4,5}) k
= 3 n = 5
initially g = 0
sum = 0;
candidateSum = 7;
count = 0
iteration one:
sum[0 - 0] = 1 7 so count += 0-0+1;
iteration 2
sum[0-1] = 3 7, count += 1-0+1
iteration 3
sum[0-2] = 6 7 count += 2-0+1;
iteration 4
sum[0,3] = 10 7 so now increment g such that sum[g,i] 7
so g = 3count += 3-3+1;
iteration 5
sum[3 - 4] = 9 7
new g = 4 count += 4-4+1
final count = 8, so there are 8 sums less than 7
On Wed, Feb 22, 2012 at 12:16 AM, shady sinv...@gmail.com wrote:
didn't get you, how to check for subsequences which doesn't start from
the beginning ? can you explain for that same example... should we check
for all contiguous subsequences of some particular length?
On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal sunny816.i...@gmail.com
wrote:
i dont know if a better solution exists
but here is one with complexity O(N*logS)...
N = no of elements in array
S = max sum of a subarray that is sum of all the elements as all are
positive
algo goes as follows
do a binary search in range 0-S, for each such candidate sum find how
many sums are smaller than candidate sum
there is also need to take care of some cases when there are exactly
k-1 sums less than candidate sum, but there is no contigious where sum =
candidate sum.
On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote:
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
sum[0-1] = 3 -- (1,2)
sum[0-2] = 6 -- (1,2,3)
sum[1-2] = 5 -- (2,3)
ok...so we can consider 3 , (1,2) as different contiguous.
how did you choose candidate sum for the given input ?? will it not add to
the complexity
On Wed, Feb 22, 2012 at 9:59 AM, sunny agrawal sunny816.i...@gmail.comwrote:
@atul there are 8 sums less than 7
sum[0 - 0] = 1
sum[1-1] = 2
sum[2 - 2] = 3
sum[3-3] = 4
sum[4-4] = 5
sum[0-1] = 3
sum[0-2] = 6
sum[1-2] = 5
contiguous sum (1,2) , (2,3) -- these contiguous sum has already been
counted ??? where ?
Read problem statement carefully !!
On Wed, Feb 22, 2012 at 9:39 AM, atul anand atul.87fri...@gmail.comwrote:
@sunny : before moving to your algorithm , i can see wrong output in your
example:-
in you example dere are 8 sums less than 7.
but for given input contiguous sum less than 7 are
1,2,3,4,5 = 4
so output is 4.
correct me if i am wrong...
On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
we need to find how many sums are less than candidate Sum chosen in one
iteration of binary search in range 0-S
To count this, for each i we try to find how many sums ending at i are
lesser than candidate sum !!
lets say for some i-1 sum[0 - i-1] candidate sum then we can say that
i*(i-1)/2 sums are less than candidate sum.
now lets say after adding a[i] again sum[0 - i] candidateSum then u
can add (i+1) to previous count because all sums [0 - i], sum[1 - i],
. sum[i - i] will be lesser than candidate sum
or if adding a[i] causes sum[0 - i] candidateSum then u have to find a
index g such that sum[g - i] candidate sum, and increase the count by
((i)-(g) +1).
eg lets say your candidate sum is 7 (for the given example{1,2,3,4,5}) k
= 3 n = 5
initially g = 0
sum = 0;
candidateSum = 7;
count = 0
iteration one:
sum[0 - 0] = 1 7 so count += 0-0+1;
iteration 2
sum[0-1] = 3 7, count += 1-0+1
iteration 3
sum[0-2] = 6 7 count += 2-0+1;
iteration 4
sum[0,3] = 10 7 so now increment g such that sum[g,i] 7
so g = 3count += 3-3+1;
iteration 5
sum[3 - 4] = 9 7
new g = 4 count += 4-4+1
final count = 8, so there are 8 sums less than 7
On Wed, Feb 22, 2012 at 12:16 AM, shady sinv...@gmail.com wrote:
didn't get you, how to check for subsequences which doesn't start from
the beginning ? can you explain for that same example... should we check
for all contiguous subsequences of some particular length?
On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
i dont know if a better solution exists
but here is one with complexity O(N*logS)...
N = no of elements in array
S = max sum of a subarray that is sum of all the elements as all are
positive
algo goes as follows
do a binary search in range 0-S, for each such candidate sum find how
many sums are smaller than candidate sum
there is also need to take care of some cases when there are exactly
k-1 sums less than candidate sum, but there is no contigious where sum =
candidate sum.
On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote:
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
Yes, read my first post
On Wed, Feb 22, 2012 at 10:19 AM, atul anand atul.87fri...@gmail.comwrote:
sum[0-1] = 3 -- (1,2)
sum[0-2] = 6 -- (1,2,3)
sum[1-2] = 5 -- (2,3)
ok...so we can consider 3 , (1,2) as different contiguous.
how did you choose candidate sum for the given input ?? will it not add
to the complexity
On Wed, Feb 22, 2012 at 9:59 AM, sunny agrawal sunny816.i...@gmail.comwrote:
@atul there are 8 sums less than 7
sum[0 - 0] = 1
sum[1-1] = 2
sum[2 - 2] = 3
sum[3-3] = 4
sum[4-4] = 5
sum[0-1] = 3
sum[0-2] = 6
sum[1-2] = 5
contiguous sum (1,2) , (2,3) -- these contiguous sum has already been
counted ??? where ?
Read problem statement carefully !!
On Wed, Feb 22, 2012 at 9:39 AM, atul anand atul.87fri...@gmail.comwrote:
@sunny : before moving to your algorithm , i can see wrong output in
your example:-
in you example dere are 8 sums less than 7.
but for given input contiguous sum less than 7 are
1,2,3,4,5 = 4
so output is 4.
correct me if i am wrong...
On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal sunny816.i...@gmail.com
wrote:
we need to find how many sums are less than candidate Sum chosen in one
iteration of binary search in range 0-S
To count this, for each i we try to find how many sums ending at i are
lesser than candidate sum !!
lets say for some i-1 sum[0 - i-1] candidate sum then we can say that
i*(i-1)/2 sums are less than candidate sum.
now lets say after adding a[i] again sum[0 - i] candidateSum then u
can add (i+1) to previous count because all sums [0 - i], sum[1 - i],
. sum[i - i] will be lesser than candidate sum
or if adding a[i] causes sum[0 - i] candidateSum then u have to find
a index g such that sum[g - i] candidate sum, and increase the count by
((i)-(g) +1).
eg lets say your candidate sum is 7 (for the given example{1,2,3,4,5})
k = 3 n = 5
initially g = 0
sum = 0;
candidateSum = 7;
count = 0
iteration one:
sum[0 - 0] = 1 7 so count += 0-0+1;
iteration 2
sum[0-1] = 3 7, count += 1-0+1
iteration 3
sum[0-2] = 6 7 count += 2-0+1;
iteration 4
sum[0,3] = 10 7 so now increment g such that sum[g,i] 7
so g = 3count += 3-3+1;
iteration 5
sum[3 - 4] = 9 7
new g = 4 count += 4-4+1
final count = 8, so there are 8 sums less than 7
On Wed, Feb 22, 2012 at 12:16 AM, shady sinv...@gmail.com wrote:
didn't get you, how to check for subsequences which doesn't start from
the beginning ? can you explain for that same example... should we check
for all contiguous subsequences of some particular length?
On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
i dont know if a better solution exists
but here is one with complexity O(N*logS)...
N = no of elements in array
S = max sum of a subarray that is sum of all the elements as all are
positive
algo goes as follows
do a binary search in range 0-S, for each such candidate sum find how
many sums are smaller than candidate sum
there is also need to take care of some cases when there are exactly
k-1 sums less than candidate sum, but there is no contigious where sum =
candidate sum.
On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote:
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] Microsoft IT-Operations Interview
Hello, Please let me know if anyone knows anything about Microsoft IT- Operations Interview procedure or the type of questions asked.. Also which areas one should focus on. Any help will be highly appreciated. Thank you all. cheers, Mihir Kulkarni Graduate Student University of California, Irvine http://goo.gl/CvRcG -- 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] ARICENT PATTERN
Aricent will not conduct test by itself. They'll have other organization who will conduct the exams. There are many test to be conducted in the time period of 2 or more. i just forgot the time limit limit. But the exams on apptitute, c language/java language either of one, technical test, verbal reasoning, and many more but easy. So just have basic concepts clear, and have strong hand on c... On Wed, Feb 22, 2012 at 10:24 AM, vivek kumar kumarvivek1...@gmail.comwrote: hey guys plzz help me .. ARICENT is coming in my campus.. plzz provide me some info .. Thanks in Advance!! -- 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] ARICENT PATTERN
written exam - will contain aptitude question + c question (focus on pointers) basic data structure tree , stach ,queue ,linked list. memory layout of a given program some basic question abt how to add elements node to the middle of the linked list. what are big and small endien , write Fibonacci ,factorail code recursively. OS question on scheduling , paging , finding number of page fault for given scheme , dealoack detection n/w questions On Wed, Feb 22, 2012 at 10:24 AM, vivek kumar kumarvivek1...@gmail.comwrote: hey guys plzz help me .. ARICENT is coming in my campus.. plzz provide me some info .. Thanks in Advance!! -- 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] Re: ARICENT PATTERN
is it aspiring minds?? can u tell me the level of resning and apptitude -- 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] Re: ARICENT PATTERN
thanks bro ... plz tell me no of question in each section -- 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] Re : Any hints[kth smallest contiguous sum] ?
*NO, u r getting it wrong*
*given a value x, we can find how many contiguous sums are lesser than x
using the above mentioned algorithm in O(N)*
*so we are searching a x in range 0-S such that, x has exactly k-1 sums
lesser than x and x is kth*
*
*
*Algorithm: *
*for
*
On Wed, Feb 22, 2012 at 10:41 AM, atul anand atul.87fri...@gmail.comwrote:
/*
algo goes as follows
*do a binary search in range 0-S*, for each such candidate sum find how
many sums are smaller than candidate sum
*/
do a binary search in range 0-S-- to search what??
acc to the complexity , O(N *log S) it seems that you are searching each
element in given input array from range 0-S
for given input = 1,2,3,4,5
S= 15
please clarify . sorry but i am not getting it ...
On Wed, Feb 22, 2012 at 10:25 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
Yes, read my first post
On Wed, Feb 22, 2012 at 10:19 AM, atul anand atul.87fri...@gmail.comwrote:
sum[0-1] = 3 -- (1,2)
sum[0-2] = 6 -- (1,2,3)
sum[1-2] = 5 -- (2,3)
ok...so we can consider 3 , (1,2) as different contiguous.
how did you choose candidate sum for the given input ?? will it not add
to the complexity
On Wed, Feb 22, 2012 at 9:59 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
@atul there are 8 sums less than 7
sum[0 - 0] = 1
sum[1-1] = 2
sum[2 - 2] = 3
sum[3-3] = 4
sum[4-4] = 5
sum[0-1] = 3
sum[0-2] = 6
sum[1-2] = 5
contiguous sum (1,2) , (2,3) -- these contiguous sum has already been
counted ??? where ?
Read problem statement carefully !!
On Wed, Feb 22, 2012 at 9:39 AM, atul anand atul.87fri...@gmail.comwrote:
@sunny : before moving to your algorithm , i can see wrong output in
your example:-
in you example dere are 8 sums less than 7.
but for given input contiguous sum less than 7 are
1,2,3,4,5 = 4
so output is 4.
correct me if i am wrong...
On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal
sunny816.i...@gmail.com wrote:
we need to find how many sums are less than candidate Sum chosen in
one iteration of binary search in range 0-S
To count this, for each i we try to find how many sums ending at i
are lesser than candidate sum !!
lets say for some i-1 sum[0 - i-1] candidate sum then we can say
that i*(i-1)/2 sums are less than candidate sum.
now lets say after adding a[i] again sum[0 - i] candidateSum then u
can add (i+1) to previous count because all sums [0 - i], sum[1 - i],
. sum[i - i] will be lesser than candidate sum
or if adding a[i] causes sum[0 - i] candidateSum then u have to
find a index g such that sum[g - i] candidate sum, and increase the
count
by ((i)-(g) +1).
eg lets say your candidate sum is 7 (for the given
example{1,2,3,4,5}) k = 3 n = 5
initially g = 0
sum = 0;
candidateSum = 7;
count = 0
iteration one:
sum[0 - 0] = 1 7 so count += 0-0+1;
iteration 2
sum[0-1] = 3 7, count += 1-0+1
iteration 3
sum[0-2] = 6 7 count += 2-0+1;
iteration 4
sum[0,3] = 10 7 so now increment g such that sum[g,i] 7
so g = 3count += 3-3+1;
iteration 5
sum[3 - 4] = 9 7
new g = 4 count += 4-4+1
final count = 8, so there are 8 sums less than 7
On Wed, Feb 22, 2012 at 12:16 AM, shady sinv...@gmail.com wrote:
didn't get you, how to check for subsequences which doesn't start
from the beginning ? can you explain for that same example... should we
check for all contiguous subsequences of some particular length?
On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
i dont know if a better solution exists
but here is one with complexity O(N*logS)...
N = no of elements in array
S = max sum of a subarray that is sum of all the elements as all
are positive
algo goes as follows
do a binary search in range 0-S, for each such candidate sum find
how many sums are smaller than candidate sum
there is also need to take care of some cases when there are
exactly k-1 sums less than candidate sum, but there is no contigious
where
sum = candidate sum.
On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote:
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
[algogeeks] Re: use of sentinel in linked list
@don,@gene: i know the pros of using it.but pbm occurs when we see pbm LIST-SEARCH(l,k) x - next[nil[l]] //nil[l] denotes the sentinel node while x != nil[l] and key[x] != k x - next[x] return x here to eliminate extra comparison (x != nil[l] ) in while loop , we will use sentinel and will put value to search in data field of sentinel...but if value to be searched is not found in ll then it will return the address of sentinel which is non-null. So how will i diff. whether value is found or not except to remember the address of sentinel. -- 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.
