Re: [algogeeks] Re: perfect square condition checking....
@Don, Can u explain with an Example...? With regards, Balasubramanian Naagarajan, Chettinad College of Engg Tech. On Sat, Jan 5, 2013 at 1:48 PM, Malathi malu@gmail.com wrote: Check this. It might help. http://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-number-is-a-square/ On Sat, Jan 5, 2013 at 1:47 AM, Don dondod...@gmail.com wrote: start with a guess y. If you can arrange for y to be about half the -- With Regards, Malathi -- --
Re: [algogeeks] direct i online test
Can u please explain ur code..!!! -- 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: candies - interviewstreet -- how to go about solving this problem
can u explain ur algorithm for the sequence * 5 4 3 2 1* -- 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: determine if a string if of form pZq
why am i getting run time error.?
problem=https://www.spoj.pl/problems/DCEPC206/
my code:
#includestdio.h
int main()
{
short t;
long n,i,c,prev;
long a;
scanf(%d,t);
while(t--)
{
c=0;
scanf(%ld,n);
scanf(%ld,prev);
c=prev;
for(i=1;in;i++)
{
scanf(%ld,a);
if(a==prev);
else if(aprev)
c=c+(a-prev);
else
c+=a;
prev=a;
}
printf(%ld\n,c);
}
//scanf(%d);
return 0;
}
--
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] how to solve
I dont know if it can be solved in O(n). But O(nlogn) can be done using BIT. Refer topcoder tutorial for Binary indexed trees. On Mon, Apr 9, 2012 at 10:56 AM, tarun chabarwal admin20...@gmail.comwrote: how should i approach this problem https://www.spoj.pl/problems/DCEPC206/ can it be solved in O(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] google
sorry dude it came to ITBHU with tag of marketing so i could not be helpful to u in this case. On 4/1/12, Deepak Garg deepakgarg...@gmail.com wrote: hey guys! google is coming to our college, their main requirements is from operating systems and computer networks. can some one post the sample questions for it.. thanks Deepak -- 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] Cliched 'k' largest elements in billion numbers: Heaps or median-of-medians?
Hey group, This is kind of a cliched question but given a file with billion numbers and the task is to compute 'k' largest numbers from this file, what approach is preferred? 1) Using heaps 2) Using Median-of-median algorithm. Have read few links which prefer heaps but clearly median of median algorithm has a linear time complexity and don't see how its any less if not better than using heaps? Any thought? -- 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: Linear time Binary tree re-construction
The in-order and pre-order traversal are already given. So, there is no way to do what you are saying if I understand you completely. On Sun, Nov 27, 2011 at 8:19 AM, Ankuj Gupta ankuj2...@gmail.com wrote: Hint : try with prestoring the preorder traversal element position in inorder traversal before constructing the tree -- 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] Finding the repeated element
*Assumptions*: - All positive elements in the array - All elements in array are in range 0 to (n-1) [ n - # of elements] 1) Scan the array. For every element A[i], negate the value stored in A[A[i]]. 2) If you encounter an element already negated, then that represents the duplicate element. On Thu, Nov 24, 2011 at 12:02 AM, kumar raja rajkumar.cs...@gmail.comwrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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] Problem
Given a set of values..in which there are some dependencies.. Eg.. x y z a b Dependencies: x,y a,z Note that dependency is not transitive..Is it possible to separate these elements into sets such that no two elements in the same set are dependant and we should end up with the least number of sets.. I could not find a good solution for this..Please help me.. Regards, Bharathwajan -- 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] Amazon - Coding Round-2 Qn
Can anyone please explain the logic instead of the actual code?
Sent from iPhone.
On Aug 31, 2011, at 4:16 AM, aditya kumar aditya.kumar130...@gmail.com wrote:
@rohit : else return (check(tree-left) || check(tree-right)); should be
else return (check(tree-left) check(tree-right));
we need both the left and the right to be true .
On Wed, Aug 31, 2011 at 4:18 PM, rohit raman.u...@gmail.com wrote:
Q1.
NODE* head //points to the bst(if it exists)
void exist_bst(NODE *tree)
{
if(tree != NULL)
{
if(tree-left-info tree-info tree-right-info = tree-info)
{
if(check(tree))
head = tree;
}
else
{
exist_bst(tree-left);
exist_bst(tree-right);
}
}
}
int check(NODE *root)
{
if(root-left == NULL root-right == NULL)
return TRUE;
if(tree-left-info = tree-info || tree-right-info tree-info)
return FALSE;
else return (check(tree-left) || check(tree-right));
}
I havn't run this on system and this code is subject to more optimisation.
This was just to give you a fair idea
--
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/-/0YV_4hilHhkJ.
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]
Sukran, There's a thread I started recently which asks about binary tree isomorphism. But to sum it all up here, isomorphism refers to same structure. Though isomorphism is used pretty flexibly w.r.t to binary trees, here's what I have read from different sources. - 2 binary trees are isomorphic (or strictly isomorphic) if they have the same structure, i.e. the same left/right sub-trees. The values of the nodes themselves can be different. - 2 binary trees are quasi-isomorphic if either of the trees can be transformed into the other to become strictly isomorphic. Transformation refers to flipping the left/right sub-trees any number of time. - 2 binary trees are mirror images of each other if the right-sub tree of tree 1 is the left sub-tree of tree 2 and the left sub-tree of tree 1 is the right sub-tree of tree 2, essentially a lateral inversion of a tree is its mirror image. Note, however that the values of the nodes must match in this case. Few people use the term isomorphic even if the trees are actually quasi-isomorphic. On Tue, Aug 30, 2011 at 8:08 AM, sukran dhawan sukrandha...@gmail.comwrote: what is the difference between a binary tree being isomorhic and the mirror image of a binary tree ? -- 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: 2 Binary trees are isomorphic?
Would this work:
boolean IsQuasiIsomorphic(Node x, Node y)
{
if (x == null y == null) return true // both null
if (x == null || y == null) return false // exactly one null
//Else, the left sub-tree of tree 1 is isomorphic to the left or right
subtree of tree 2
return ( ( IsQuasiIsomorphic(x.left, y.left) OR
IsQuasiIsomorphic(x.left, y.right)) AND ( IsQuasiIsomorphic(x.right,
y.right) OR IsQuasiIsomorphic(x.right, y.left) ))
}
On Mon, Aug 29, 2011 at 12:53 PM, bugaboo bharath.sri...@gmail.com wrote:
@Dave: thanks. Knew it wasn't as simple as that. Any other solution
you can think of?
On Aug 29, 12:46 pm, Dave dave_and_da...@juno.com wrote:
@Bugaboo: No. Consider these trees:
a
/ \
b c
/ \
d e
/ \
fg
a
/ \
b c
/ \
d e
/ \
fg
Dave
On Aug 29, 10:37 am, bugaboo bharath.sri...@gmail.com wrote:
The question I originally asked was meant for strict isomorphic trees.
Now, let's assume the trees can be quasi-isomorphic, i.e 2 binary
trees are called quasi-isomorphic if they have the same structure
after flipping any of the right/left sub-trees any number of times.
How do you do it?
My initial solution which appears seemingly simple but can't come up
with a test case that fails.
- Count the number of nodes at every level for both trees. If they are
the same, then they are quasi-isomorphic. I know this is a necessary
condition but is this sufficient as well?
On Aug 29, 7:37 am, bugaboo bharath.sri...@gmail.com wrote:
The definition is interpreted as either strictly isomorphic or quasi-
isomorphic but technically (technically) isomorphic binary trees do
not require any transformation themselves. See below link:
http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/
Bharath.
On Aug 28, 11:53 pm, muthu raj muthura...@gmail.com wrote:
In Amazon written test Isomorphic trees were defined as those in
which a
series of flips can transform one tree to another.
*Muthuraj R
IV th Year , ISE
PESIT , Bangalore*
On Sun, Aug 28, 2011 at 11:52 AM,bugaboobharath.sri...@gmail.com
wrote:
@Navneet,
What you are talking about are quasi-isomorphic trees where
trees
can be changed a bit (flip right/left sub-trees to be precise) to
make
them isomorphic. An isomorphic tree does not need any
transformation, they are similar in structure by themselves.
On Aug 28, 1:44 pm, Navneet navneetn...@gmail.com wrote:
@Dave,
From the definition of isomorphic trees(not in ques given),
what i
know of is that one can be transformed into another. The above
three
are then isomorphic to each other.
@Bugaboo, can you clarify what exactly do you mean by
isomorphic
here?
On Aug 28, 9:25 pm, Dave dave_and_da...@juno.com wrote:
@Naveet: So we have a question of semantics. Do these three
trees have
the same structure:
a
/
b
/
c
and
a
\
b
\
c
and
a
\
b
/
c
I say no, but perhaps you say yes.
Dave
On Aug 28, 9:35 am, Navneet navneetn...@gmail.com wrote:
Dave, that is why i have an OR condition between. Each side
of OR has
two calls with AND in between.
Basically at any node, you will have to invoke with two
combinations
((left,left) AND (right,right) OR (left,right) AND
(right,left))
Let me know if you think that's not required.
On Aug 28, 6:02 pm, Dave dave_and_da...@juno.com wrote:
@Navneet: Don't we want both subtrees to be isomorphic?
Dave
On Aug 28, 6:40 am, Navneet navneetn...@gmail.com
wrote:
Dave,
I think the last condition should be
return (AreIsomorphic(tree1-left, tree2-left)
AreIsomorphic(tree1-right,tree2-right)) ||
(AreIsomorphic(tree1-left, tree2-right)
AreIsomorphic(tree1-right,tree2-left))
On Aug 28, 3:39 pm, Ankur Garg ankurga...@gmail.com
wrote:
Daves solution looks cool to me...shud work :)
Nice one Dave :)
Regards
Ankur
On Sun, Aug 28, 2011 at 4:08 PM, Ankur Garg
ankurga...@gmail.com wrote:
cant we just count the no of nodes in each level
and compare
them with the
second one..
if the numbers are same trees can be said to be
isomorphic
On Sun, Aug 28, 2011 at 3:54 AM, Dave
dave_and_da...@juno.com wrote:
@Bugaboo: Use recursion. Assuming
struct tree_node {
tree_node
[algogeeks] Re: 100th Fibonacci number using LL
@Amit: Thanks for the solution but I have seen this approach. I was
wondering how this can be solved using linked lists without using
bignum libraries.
Bharath
On Jul 31, 12:38 pm, amit karmakar amit.codenam...@gmail.com wrote:
Since long long cannot store the 100th Fibonacci number, you need to
implement or use an existing library for bignum.
You may use linked lists to solve this problem.
Read about bignum
herehttp://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
Here is my implementation for solving this problem,
#include cstdio
#include algorithm
#include cstring
using namespace std;
#define REP(i, n) for(int i = 0; i (n); i++)
#define FILL(c, v) memset(c, v, sizeof(c))
const int MX = 10;
int prv1[MX], prv2[MX], cur[MX], l1, l2, lcur;
int main() {
FILL(prv1, 0); FILL(prv2, 0); FILL(cur, 0);
int n;
scanf(%d, n);
prv1[0] = 0; l1 = 1;
prv2[0] = 1; l2 = 1;
cur[0] = 0; lcur = 1;
REP(i, n) {
int mx = max(l1, l2);
int carry = 0;
REP(j, mx) {
int imd = prv1[j]+prv2[j]+carry;
cur[j] = imd%10;
carry = imd/10;
}
if(carry) {
cur[mx++] = carry;
}
lcur = mx;
REP(j, l1) prv2[j] = prv1[j]; l2=l1;
REP(j, lcur) prv1[j] = cur[j]; l1=lcur;
}
REP(i, lcur) printf(%d, cur[lcur-i-1]); printf(\n);
}
On Jul 31, 9:31 pm, bharath sriram bharath.sri...@gmail.com wrote:
Since both the normal recursive (stack overflow) and non-recursive (data
type overflow) versions fails, is there a way one can use linked lists to
solve this problem?
Bharath.
--
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: 100th Fibonacci number using LL
@Saurabh: :)
Well, I could think of a way of solving this without using other
libraries.
Use iterative version of fibonacci numbers but when adding the ith and
(i+1)st values, use circular linked lists (or doubly linked lists) to
add these 2 values. Since the question of integer overflow does not
come into picture when 2 big numbers are added, there is no problem.
As an optimization, one can use linked lists for addition only when
values get close to max integer value.
Bharath.
On Jul 31, 8:38 pm, saurabh singh saurab...@gmail.com wrote:
By creating a bugnum library using link list:)
On Sun, Jul 31, 2011 at 11:12 PM, bharath bharath.sri...@gmail.com wrote:
@Amit: Thanks for the solution but I have seen this approach. I was
wondering how this can be solved using linked lists without using
bignum libraries.
Bharath
On Jul 31, 12:38 pm, amit karmakar amit.codenam...@gmail.com wrote:
Since long long cannot store the 100th Fibonacci number, you need to
implement or use an existing library for bignum.
You may use linked lists to solve this problem.
Read about bignum herehttp://
en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
Here is my implementation for solving this problem,
#include cstdio
#include algorithm
#include cstring
using namespace std;
#define REP(i, n) for(int i = 0; i (n); i++)
#define FILL(c, v) memset(c, v, sizeof(c))
const int MX = 10;
int prv1[MX], prv2[MX], cur[MX], l1, l2, lcur;
int main() {
FILL(prv1, 0); FILL(prv2, 0); FILL(cur, 0);
int n;
scanf(%d, n);
prv1[0] = 0; l1 = 1;
prv2[0] = 1; l2 = 1;
cur[0] = 0; lcur = 1;
REP(i, n) {
int mx = max(l1, l2);
int carry = 0;
REP(j, mx) {
int imd = prv1[j]+prv2[j]+carry;
cur[j] = imd%10;
carry = imd/10;
}
if(carry) {
cur[mx++] = carry;
}
lcur = mx;
REP(j, l1) prv2[j] = prv1[j]; l2=l1;
REP(j, lcur) prv1[j] = cur[j]; l1=lcur;
}
REP(i, lcur) printf(%d, cur[lcur-i-1]); printf(\n);
}
On Jul 31, 9:31 pm, bharath sriram bharath.sri...@gmail.com wrote:
Since both the normal recursive (stack overflow) and non-recursive
(data
type overflow) versions fails, is there a way one can use linked lists
to
solve this problem?
Bharath.
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
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] Recursive version of reversing linked list
Can anyone give the recursive version of reversing a linked list. Please post the reverse function code snippet and not the entire .c file since it just hampers readability. Bharath. -- 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] Word count using linked lists
The subject has the problem description. What are some efficient ways of doing this. As always, the approach description is more useful than the actual code itself. Thanks! Bharath. -- 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: how to calculate the complexity
Master's theorem is for recursive programs only. In general, there is no golden rule to calculate time complexity. Few pointers are to identify the key operations (eg - loops) and analyze the estimated running time based on a input size. On Jul 27, 2:46 pm, rajeev bharshetty rajeevr...@gmail.com wrote: Masters Theoremhttp://en.wikipedia.org/wiki/Master_theorem On Thu, Jul 28, 2011 at 1:14 AM, NITIN SHARMA coolguyinat...@gmail.comwrote: Can anybody explain the basic steps that how to calculate the complexity of an algo so that i would be able to find complexity of any program -- 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. -- Regards Rajeev N B http://www.opensourcemania.co.cc *Winners Don't do Different things , they do things Differently* -- 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: interview ques
@Puneet, to store anything on a machine, you will need to have a pointer to it else there is no question of accessing it. I am guessing the question emphasized on reducing the size of the B+ tree. Also, with B+ trees, you have sequence pointers at the data record level. Therefore, if these data records are stored in a single chunk, bringing the chunk into memeory is good enough. An additional storage structure will not be required. On Jul 28, 1:27 am, Puneet Gautam puneet.nsi...@gmail.com wrote: @bharath: To store the bunch of records together also, we gonna need another useful ds like linked list or array which again points to the problem of excessive storage or excessive pointers... correct me if am not..! On 7/28/11, bharath bharath.sri...@gmail.com wrote: @Dumanshu: A B+ tree is a multi-level index. It indexes the index until the final level is small enough to fit into a data block that can fit in memory. On Jul 27, 10:11 pm, Dumanshu duman...@gmail.com wrote: Use multilevel indexing On Jul 27, 11:07 pm, himanshu kansal himanshukansal...@gmail.com wrote: if u hv say 20 million records and u have to create a b+ tree then you might be storing 20 million pointers at the leaf levelhow can u optimize this(using b+ tree only)??? -- 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: interview ques
A B+ tree would have one pointer for every data record at the leaf level. You could additionally group a bunch of data records together and have a single pointer from leaf to the data block. The trade-off is that you will have to fetch the data block and sequentially parse it to search for an element. On Jul 27, 1:07 pm, himanshu kansal himanshukansal...@gmail.com wrote: if u hv say 20 million records and u have to create a b+ tree then you might be storing 20 million pointers at the leaf levelhow can u optimize this(using b+ tree only)??? -- 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: interview ques
@Dumanshu: A B+ tree is a multi-level index. It indexes the index until the final level is small enough to fit into a data block that can fit in memory. On Jul 27, 10:11 pm, Dumanshu duman...@gmail.com wrote: Use multilevel indexing On Jul 27, 11:07 pm, himanshu kansal himanshukansal...@gmail.com wrote: if u hv say 20 million records and u have to create a b+ tree then you might be storing 20 million pointers at the leaf levelhow can u optimize this(using b+ tree only)??? -- 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] Redundant parentheses
Given an expression (A+(B*C)), remove redundant parentheses. Output in this case should be A+B*C. My initial solution: (1) Convert expression from infix to postfix (or prefix) [This way, all parentheses are removed] (2) Now, convert postfix (or prefix) expression back to infix. Is there a better way of doing this? -- 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: Redundant parentheses
Ah! a good friend just pointed out that step (2) is not quite simple. A postfix expression bases precedence by the operator position due to lack of parentheses. I am not sure about the code to convert from postfix to infix. It *has* to insert parentheses generously to add to the precedence information lost. So, it will eventually again return back (A+(B*C)). So, my approach will not work. Any solutions then? On Jul 26, 3:26 pm, bharath bharath.sri...@gmail.com wrote: Given an expression (A+(B*C)), remove redundant parentheses. Output in this case should be A+B*C. My initial solution: (1) Convert expression from infix to postfix (or prefix) [This way, all parentheses are removed] (2) Now, convert postfix (or prefix) expression back to infix. Is there a better way of doing this? -- 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: Redundant parentheses
Well, the answer should still be in infix except without 'redundant' parantheses. So, just converting it to prefix/postfix will not do. If we were to scan the array and remove parentheses, you might end up deleting relevant ones. Eg: ((A+B)*C) should output (A+B)*C. So, the key point here is to remove superfluous parentheses. -- 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/-/GjgpYW3LKS8J. 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: AMAZON Q
We can use count sort to solve this. Assuming each element is the array is in range 1-k (k=O(n)). for (i=0 to n) C[A[i]]=C[A[i]]+1 for (i=1 to k) C[i]=C[i]+C[i-1] Array 'C' will have the resultant array. On Jul 26, 9:20 pm, Rajeev Kumar rajeevprasa...@gmail.com wrote: * Algorithm : 1)Conside original array a[] 2)Construct a sorted list with the array elements(O(nlogn)) 3)Traverse across all elements of the original array 'a' and find it's position(right occurence) in the sorted list using binary search. -position in the sorted list returns the number of elements in the less than the current element on right side. -after remove the current element from the sorted list. PS: list is preferred datastructure because there are so many insertion and deletion operations. check this link :http://rajeevprasanna.blogspot.com/2011/07/count-number-of-min-elemen... * On Tue, Jul 26, 2011 at 11:08 AM, ankit sambyal ankitsamb...@gmail.comwrote: @vivin : Your algo seems to be wrong. Plz take an example and explain. I may hv misunderstood u .. -- 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. -- Thank You Rajeev Kumar -- 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: AMAZON Q
Oops, my bad. I missed that lowest in a[i+1...n] part. On Jul 26, 10:17 pm, ankit sambyal ankitsamb...@gmail.com wrote: @bharath :I think array C is not the resultant array. Take an example and explain -- 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: Lucky numbers
This is the extended Josephus problem. More details and solution formulation here: http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf On Jul 26, 11:04 pm, Nikhil Gupta nikhilgupta2...@gmail.com wrote: Please suggest a good algo for this : You have numbers 1 to n (consider them arranged in a circular order) Then starting from the first number, all alternate numbers are deleted. Once the entire range is traversed with this procedure, the same is performed from the beginning again (as they are circularly arranged). This action is done until only one number is left. So given a range of numbers, you have to use an algo to tell which number will be left in the end. Example : 1 2 3 4 5 6 7 8 9 10 11 12 ... 1 3 5 7 9 11 13 15 17 19 . 1 5 9 13 17 21 25 . and so on. -- Nikhil Gupta Senior Co-ordinator, Publicity CSI, NSIT Students' Branch NSIT, New Delhi, India -- 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: Redundant parentheses
I think I figured out a solution. Please correct me if I missed anything. *Example:* Input: ((A+B)*C) Expected output: (A+B)*C *Assumptions:* - Peek (queue) just tells the element in front end of queue without deleting it. - precedence( ) is a function which looks a precedence table of operators *Pseudo code below:* 1) Convert infix expression to postfix AB+C* 2) Insert only operators in queue 'Q' (front)+ *(rear) 3) Parse postfix expression 4) If operand, push to stack 'S' 5) If operator 5.1) y=Delete(Q) 5.2) If precedence(y) precedence(peek(Q)), then Push (S, Pop(S) y Pop(S)) 5.3) If precedence(y) precedence(peek(Q)), then Push (S, ( Pop(S) y Pop(S) )) 6) Final result on top 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/-/RGom9z_GybEJ. 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] Reverse a List with Recursion
node * reverse(node *head)
{
if(head-next)
{
node * temp=reverse(head-next);
head-next-next=head;
head-next=NULL;
return temp;
}
return head;
}
On Sun, Jul 17, 2011 at 4:57 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
*node *reverse(node *head)
{
if(head==NULL)
return head;
if(head-next==NULL)
return head;
node *temp = reverse(head-next);
head-next-next = head;
head-next = NULL;
return (temp);
}*
On Sun, Jul 17, 2011 at 4:30 PM, Anika Jain anika.jai...@gmail.comwrote:
initial call to this will be rev(head);
On Sun, Jul 17, 2011 at 4:28 PM, Anika Jain anika.jai...@gmail.comwrote:
node *listing::rev(node *p)
{
if(p-next==NULL)
{
head=p;
return p;
}
else
{
node *t=rev(p-next);
t-next=p;
p-next=NULL;
tail=p;
return p;
}
}
On Sun, Jul 17, 2011 at 3:21 PM, Nishant Mittal
mittal.nishan...@gmail.com wrote:
void rev_recursion(NODE **head)
{
if(*head==NULL)
return;
NODE *first, *rest;
first=*head;
rest=first-next;
if(!rest)
return;
rev_recursion(rest);
first-next-next=first;
first-next=NULL;
*head=rest;
}
On Sun, Jul 17, 2011 at 2:53 PM, vaibhav shukla
vaibhav200...@gmail.com wrote:
struct node *reverse_recurse(struct node *start)
{
if(start-next)
{
reverse_recurse(start-next);
start-next-next=start;
return(start);
}
else
{
head=start;
}
}
in main
if(head)
{
temp = reverse_recurse(head);
temp-next =NULL;
}
head and temp are global
On Sun, Jul 17, 2011 at 2:42 PM, Navneet Gupta
navneetn...@gmail.comwrote:
Hi,
I was trying to accomplish this task with the following call , header
= ReverseList(header)
I don't want to pass tail pointer or anything and just want that i get
a reversed list with new header properly assigned after this call. I
am getting issues in corner conditions like returning the correct node
to be assigned to header.
Can anyone give an elegant solution with above requirement? Since it
is with recursion, please test for multiple scenarios (empty list, one
node list, twe nodes
list etc) before posting your solution. In case
of empty list, the procedure should report that.
--
Regards,
Navneet
--
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.
--
best wishes!!
Vaibhav Shukla
DU-MCA
--
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.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-7483122727*
* https://www.facebook.com/profile.php?id=10655377926 NEVER SAY
NEVER
*
--
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] given a bst and a value x.find pair of nodes in the tree that sum upto x
HI Do an inorder traversal on that bst n form a sorted array...then u can search for that 2 elements in O(n) On Mon, Jun 27, 2011 at 2:01 PM, manish kapur manishkapur.n...@gmail.comwrote: -- 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 Bharath -- 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: given a bst and a value x.find pair of nodes in the tree that sum upto x
@ankit, sorry i was mistaken its O(nlogn) for searching the two elements... On Mon, Jun 27, 2011 at 8:04 PM, Swathi chukka.swa...@gmail.com wrote: Dave, Can you provide the psuedo code for this.. Thanks, Swathi On Mon, Jun 27, 2011 at 7:30 PM, Dave dave_and_da...@juno.com wrote: @Sunny. Mea culpa. You are correct. Revised (and correct) algorithm. Do two inorder traversals, one in the usual (descend to the left before descendung to the right) direction and the other in the reversed(descend to the right before descending to the left) direction. Let u and r be the current nodee of the two traversals, respectively. If u + r x, then advance the usual traversal and repeat the comparison. If u + r x, advance the reverse traversal and repeat the comparison. If u + r = x, and if u != r, then terminate with success. If u = r, then terminate with failure. Dave On Jun 27, 7:53 am, sunny agrawal sunny816.i...@gmail.com wrote: @Dave i think your solution won't work consider inorder traversal of a BST is 1 6 7 8 15 and x = 14 initially both u,v (1,1) according to u your algorithm will proceed like (1,1) - (1,6) - (1,7) - (1,8) - (1,15) - (6,15) - (15,15) and clearly in second step of your solution if (u+v) x after advancing u still u+v will be greater than x so something is wrong I think your solution will work in case we need to find 2 nodes with difference x. correct me if i am wrong.!! On Mon, Jun 27, 2011 at 6:13 PM, Dave dave_and_da...@juno.com wrote: @Nishant: No need to store the data in an array. Do two inorder traversals simultaneously. Let u and v be the current nodes of the two traversals, respectively. If u + v x, then advance the v traversal. If u + v x, advance the u traversal. Dave On Jun 27, 3:40 am, Nishant Mittal mittal.nishan...@gmail.com wrote: do inorder traversal of tree and store values in an array. Now find pairs by applying binary search on array.. On 6/27/11, manish kapur manishkapur.n...@gmail.com wrote: -- 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.-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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee- 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. -- 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 Bharath -- 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] SPOJ problem-BRCKTS
i already mentioned the link where i got this approach..
//from spoj forum
I have tried this problem with the following approach:-
1. any expression can be expressed as ))...)+a_correct_expression+((...(
2.at each node i am storing 1.no_of ')' at start and 2.no_of '(' at end of
expression that the node is holding (ignoring the correct part)..
3.whenever u r merging two nodes to form its parent, it looks like
following:-
left_child[))...)((..(]++right_child[))..)((..(]
=))...)++((..())..)++((..(
=[))..)++))..)]++((..( OR, ))..)++[((..(++((..(]
i.e. comparing the no_of '(' in the left and no_of ')' in the right , u can
recalculate the no_of ')' and no_of '(' for the parent node)
4.for the leaf node, if the character is '(' =no_of '('=1 and no_of ')'=0,
otherwise just the opposite case
5.finally, if the whole expression is correct , there will be 0,0 entry in
the root node, otherwise whole expression is not correct...
i guess it explains all.. :)
On Sat, Mar 26, 2011 at 6:32 PM, sukhmeet singh sukhmeet2...@gmail.comwrote:
Bharath can u tell me how u came with the combine function ??? I can't
understand the logic behind it ... do reply
On Wed, Mar 16, 2011 at 10:24 PM, Bharath 2009503507 CSE
bharathgo...@gmail.com wrote:
i am new to segment trees..i tried this problem in spoj..
http://www.spoj.pl/problems/BRCKTS
am getting WA..
pls help...
code:
#includeiostream
#includevector
#includecstdio
#includecmath
#includestring
using namespace std;
class pi
{
public:
int a,b;
pi(){a=0;b=0;}
pi(int x,int y) {a=x;b=y;}
};
vectorpi tree;
string str;
pi combine(pi a,pi b)
{
pi x;
if(a.b==b.a)
{
x.a=a.a;
x.b=b.b;
}
else if(a.b b.a)
{
x.a=a.a;
x.b=a.b-b.a+b.b;
}
else
{
x.b=b.b;
x.a=b.a-a.b+a.a;
}
return x;
}
void build(int node,int b,int e)
{
if(b==e)
{
if(str[b]=='(')
{
tree[node].a=0;
tree[node].b=1;
}
else
{
tree[node].a=1;
tree[node].b=0;
}
return;
}
// coutnode\n;
int mid=(b+e)/2;
build(node*2,b,mid);
build(node*2+1,mid+1,e);
tree[node]=combine(tree[node*2],tree[node*2+1]);
}
void update(int node,int b,int e,int index)
{
if(index b || index e) return;
if(b==e)
{
if(tree[node].a==1)
tree[node].a=0;
else
tree[node].a=1;
if(tree[node].b==1)
tree[node].b=0;
else
tree[node].b=1;
return;
}
int mid=(b+e)/2;
update(node*2,b,mid,index);
update(node*2+1,mid+1,e,index);
tree[node]=combine(tree[node*2],tree[node*2+1]);
}
main()
{
for(int test=1;test=10;test++)
{
printf(Test %d:\n,test);
int n;
scanf(%d,n);
if(!n) continue;
int size=(1(int(log10(n)/log10(2))+2));
// coutsize\n;
vectorpi temp(size);
tree=temp;
temp.clear();
string s;
cins;
str=s;
s.clear();
build(1,0,str.size()-1);
int x;
scanf(%d,x);
while(x--)
{
int k;
scanf(%d,k);
if(k==0)
{
if(!tree[1].a !tree[1].b)
printf(Yes\n);
else
printf(No\n);
}
else
update(1,0,str.size()-1,k-1);
}
}
}
Thanks in advace..
Bharath..
--
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
Re: [algogeeks] Re: SPOJ problem-BRCKTS
i found this good.. http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor On Mon, Mar 21, 2011 at 6:02 PM, Anurag atri anu.anurag@gmail.comwrote: yes , please suggest a nice tutorial for segment trees .. On Mon, Mar 21, 2011 at 5:48 PM, cegprakash cegprak...@gmail.com wrote: hey i want to learn segment trees.. suggest me a tutorial plz.. pdf or word anything.. i don't understand wiki page -- 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. -- Regards Anurag Atri -- 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: SPOJ problem-BRCKTS
but..i read this oly after my senior taught me segment trees.. On Wed, Mar 23, 2011 at 4:43 PM, bharath kannan bharathgo...@gmail.comwrote: i found this good.. http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor On Mon, Mar 21, 2011 at 6:02 PM, Anurag atri anu.anurag@gmail.comwrote: yes , please suggest a nice tutorial for segment trees .. On Mon, Mar 21, 2011 at 5:48 PM, cegprakash cegprak...@gmail.com wrote: hey i want to learn segment trees.. suggest me a tutorial plz.. pdf or word anything.. i don't understand wiki page -- 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. -- Regards Anurag Atri -- 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] SPOJ NUMGUESS
I guess you solve it using binary search.. On Wed, Mar 23, 2011 at 6:48 PM, Vishnutej mylavarapu.vishnu...@gmail.comwrote: Hello everyone, Im unable to understand the NUMGUESS problem in SPOJ.Can some one explain what the problem is about? Thanks in advance. -Vishnutej.Mylavarapu -- 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] SPOJ problem-BRCKTS
@murthy:no..the op must be NOits not a valid expression..read the two conditions for a valid expression.. On Sun, Mar 20, 2011 at 8:23 PM, murthy.krishn...@gmail.com murthy.krishn...@gmail.com wrote: @anurag accor to me the output must be YES, correct me if I am wrong On Sun, Mar 20, 2011 at 10:40 AM, bharath kannan bharathgo...@gmail.comwrote: i thot tat i had some mistake in my code and typed it all over again.. finally i noticed this :) On Sat, Mar 19, 2011 at 12:12 AM, Kunal Patil kp101...@gmail.com wrote: Hey.. I also got into same trouble today... I submitted it 6 times..then got bored and de moralised cause i cudnt find flaw in code... When i read your mail and corresponding sorry mail...it just struck me..I also had to print YES and NOand i was printing NO as NoIt got ac den... :P thnx anyway !!! -- 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] Re: SPOJ problem-BRCKTS
http://www.spoj.pl/forum/viewtopic.php?f=3t=5240p=20667hilit=BRCKTS#p20667 if u know d basics of segment tree..then this thread will help for solving this prob :) On Sun, Mar 20, 2011 at 2:11 AM, murthy.krishn...@gmail.com murthy.krishn...@gmail.com wrote: can any 1 explain why we have 2 use segment trees ?? I am under the impression that in order to distinguish correct bracket expressions, we can just count the number of left brackets and compare that with the number of right brackets, if they are equal then it is a correct bracket expression. can u please correct me with an example if I am wrong Thanks, Krishna. On Sat, Mar 19, 2011 at 4:13 PM, cegprakash cegprak...@gmail.com wrote: could someone plz help me with a pdf for learning segment tree? i don't understand the wiki page -- 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] SPOJ problem-BRCKTS
i thot tat i had some mistake in my code and typed it all over again.. finally i noticed this :) On Sat, Mar 19, 2011 at 12:12 AM, Kunal Patil kp101...@gmail.com wrote: Hey.. I also got into same trouble today... I submitted it 6 times..then got bored and de moralised cause i cudnt find flaw in code... When i read your mail and corresponding sorry mail...it just struck me..I also had to print YES and NOand i was printing NO as NoIt got ac den... :P thnx anyway !!! -- 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] SPOJ problem-BRCKTS
sorry guyz...
Had to print YES n NO..
i printed as Yes n No...
Got ac..
Sorry for the trouble..
On Wed, Mar 16, 2011 at 10:24 PM, Bharath 2009503507 CSE
bharathgo...@gmail.com wrote:
i am new to segment trees..i tried this problem in spoj..
http://www.spoj.pl/problems/BRCKTS
am getting WA..
pls help...
code:
#includeiostream
#includevector
#includecstdio
#includecmath
#includestring
using namespace std;
class pi
{
public:
int a,b;
pi(){a=0;b=0;}
pi(int x,int y) {a=x;b=y;}
};
vectorpi tree;
string str;
pi combine(pi a,pi b)
{
pi x;
if(a.b==b.a)
{
x.a=a.a;
x.b=b.b;
}
else if(a.b b.a)
{
x.a=a.a;
x.b=a.b-b.a+b.b;
}
else
{
x.b=b.b;
x.a=b.a-a.b+a.a;
}
return x;
}
void build(int node,int b,int e)
{
if(b==e)
{
if(str[b]=='(')
{
tree[node].a=0;
tree[node].b=1;
}
else
{
tree[node].a=1;
tree[node].b=0;
}
return;
}
// coutnode\n;
int mid=(b+e)/2;
build(node*2,b,mid);
build(node*2+1,mid+1,e);
tree[node]=combine(tree[node*2],tree[node*2+1]);
}
void update(int node,int b,int e,int index)
{
if(index b || index e) return;
if(b==e)
{
if(tree[node].a==1)
tree[node].a=0;
else
tree[node].a=1;
if(tree[node].b==1)
tree[node].b=0;
else
tree[node].b=1;
return;
}
int mid=(b+e)/2;
update(node*2,b,mid,index);
update(node*2+1,mid+1,e,index);
tree[node]=combine(tree[node*2],tree[node*2+1]);
}
main()
{
for(int test=1;test=10;test++)
{
printf(Test %d:\n,test);
int n;
scanf(%d,n);
if(!n) continue;
int size=(1(int(log10(n)/log10(2))+2));
// coutsize\n;
vectorpi temp(size);
tree=temp;
temp.clear();
string s;
cins;
str=s;
s.clear();
build(1,0,str.size()-1);
int x;
scanf(%d,x);
while(x--)
{
int k;
scanf(%d,k);
if(k==0)
{
if(!tree[1].a !tree[1].b)
printf(Yes\n);
else
printf(No\n);
}
else
update(1,0,str.size()-1,k-1);
}
}
}
Thanks in advace..
Bharath..
--
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] SPOJ problem-BRCKTS
i am new to segment trees..i tried this problem in spoj..
http://www.spoj.pl/problems/BRCKTS
am getting WA..
pls help...
code:
#includeiostream
#includevector
#includecstdio
#includecmath
#includestring
using namespace std;
class pi
{
public:
int a,b;
pi(){a=0;b=0;}
pi(int x,int y) {a=x;b=y;}
};
vectorpi tree;
string str;
pi combine(pi a,pi b)
{
pi x;
if(a.b==b.a)
{
x.a=a.a;
x.b=b.b;
}
else if(a.b b.a)
{
x.a=a.a;
x.b=a.b-b.a+b.b;
}
else
{
x.b=b.b;
x.a=b.a-a.b+a.a;
}
return x;
}
void build(int node,int b,int e)
{
if(b==e)
{
if(str[b]=='(')
{
tree[node].a=0;
tree[node].b=1;
}
else
{
tree[node].a=1;
tree[node].b=0;
}
return;
}
// coutnode\n;
int mid=(b+e)/2;
build(node*2,b,mid);
build(node*2+1,mid+1,e);
tree[node]=combine(tree[node*2],tree[node*2+1]);
}
void update(int node,int b,int e,int index)
{
if(index b || index e) return;
if(b==e)
{
if(tree[node].a==1)
tree[node].a=0;
else
tree[node].a=1;
if(tree[node].b==1)
tree[node].b=0;
else
tree[node].b=1;
return;
}
int mid=(b+e)/2;
update(node*2,b,mid,index);
update(node*2+1,mid+1,e,index);
tree[node]=combine(tree[node*2],tree[node*2+1]);
}
main()
{
for(int test=1;test=10;test++)
{
printf(Test %d:\n,test);
int n;
scanf(%d,n);
if(!n) continue;
int size=(1(int(log10(n)/log10(2))+2));
// coutsize\n;
vectorpi temp(size);
tree=temp;
temp.clear();
string s;
cins;
str=s;
s.clear();
build(1,0,str.size()-1);
int x;
scanf(%d,x);
while(x--)
{
int k;
scanf(%d,k);
if(k==0)
{
if(!tree[1].a !tree[1].b)
printf(Yes\n);
else
printf(No\n);
}
else
update(1,0,str.size()-1,k-1);
}
}
}
Thanks in advace..
Bharath..
--
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] please help..
a small modification in normal knapsack algo ll do :) On Thu, Feb 24, 2011 at 4:06 PM, Akshata Sharma akshatasharm...@gmail.comwrote: http://www.spoj.pl/problems/PIGBANK/ can anyone give me an idea how to solve this problem...?? I dont think the knapsack algo would be of help here as here we need to find minimum value..please refer to the link and if anyone can help, i would be very thankful. regards, aksha -- 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] SPOJ PROBLEM-pour1
i tried solving this prob... http://www.spoj.pl/problems/POUR1/ i tried using BFS...getting TLE in judge.. pl suggest some optimisation or better solution.. Thanks in advance.. Code: http://ideone.com/qIgcU -- 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] help
machi use this..
Define *m*[*i*,*w*] to be the maximum value that can be attained with weight
less than or equal to *w* using items up to *i*.
We can define *m*[*i*,*w*] recursively as follows:
- [image: m[0,\,w]=0]
- [image: m[i,\,0]=0]
- [image: m[i,\,w]=m[i-1,\,w]] if [image: w_iw\,\!] (the new item is
more than the current weight limit)
- [image: m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+v_i)] if [image: w_i
\leqslant w].
return m[n,W] where W is the input
On Fri, Dec 17, 2010 at 11:38 AM, kumar0746 kerth kumar0...@gmail.comwrote:
problem:https://www.spoj.pl/problems/PARTY/
i m getting wrong answer for dis problem.can anyone help me in
finding de mistake..thank u in advance
#includeiostream
//#includeconio.h
#includevector
#includealgorithm
using namespace std;
//int n;
int item(int c[][501],int i,int wt,vectorint w,int ans)
{
//int ans;
if(i==0 || wt==0)
return 0;
else
{
if(c[i][wt]==c[i-1][wt])
item(c,i-1,wt,w,ans);
else if(c[i][wt]==c[i][wt-1])
item(c,i,wt-1,w,ans);
else
{
ans=ans+w[i];
item(c,i-1,wt-w[i],w,ans);
// coutw[i]endl;
// ans+=w[i];
}
}
// return ans;
}
main()
{
int n,tw;
while(cintwn n!=0 tw!=0){
int i,j,ans=0;
//cinn;
vectorint wt(n+1),v(n+1);
v[0]=wt[0]=0;
int c[501][501];
// cintw;
for(i=1;i=n;i++)
cinwt[i]v[i];
for(i=0;i=tw;i++)
c[0][i]=0;
for(i=1;i=n;i++)
{
c[i][0]=0;
for(j=1;j=tw;j++)
{
if(wt[i]=j)
{
int ma=max(c[i-1][j],c[i][j-1]);
if((v[i]+c[i-1][j-wt[i]])ma)
c[i][j]=v[i]+c[i-1][j-wt[i]];
else
c[i][j]=ma;
}
else
c[i][j]=max(c[i-1][j],c[i][j-1]);
}
}
// coutendl;
item(c,n,tw,wt,ans);
coutans c[n][tw]\n ;
// coutmaximum possible value isc[n][tw];
} //getch();
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] coins
refer topcoder tutorials..dp On Wed, Dec 15, 2010 at 12:12 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: how do we find the complexity of DP program ? i know it cn be done using DP states , but the gien complexity is n^2 . i am not sure how to compare that On Tue, Dec 14, 2010 at 11:41 PM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: we can use DP to solve this: dp[i][j] = coins[i][j] + max ( dp[i-1][j] , dp[i][j-1] ) On Tue, Dec 14, 2010 at 7:24 PM, divya sweetdivya@gmail.com wrote: A table composed of N x M cells, each having a certain quantity of coins. You start from the upper-left corner. At each step you can go down or right one cell. Find the maximum number of coins you can collect. Provide an algorithm of O(n^2) solution. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: FINDSR in spoj
I tried solving that prob..here's my code
#includeiostream
#includestring
using namespace std;
main()
{
string s;
cins;
while(1)
{
if(s.size()==1 s[0]=='*')
break;
int length=1,curr=0,start=0,count=1;
for(int i=1;is.size();i++)
{
if(s[i]!=s[curr] s[i]!=s[start])
{
curr=0;
count=1;
length=i+1;
}
else if(s[i]!=s[start] s[i]==s[curr])
{
curr++;
}
else if(s[i]==s[start] s[i]!=s[curr])
{
length=i;
curr=0;
count=1;
i=i-1;
}
else if(s[i]==s[start] s[i]==s[curr])
{
if(i%length==0)
{
count++;
curr++;
}
else
curr++;
}
}
if(s[s.size()-1]==s[length-1])
coutcount\n;
else
cout1\n;
cins;
}
}
I am getting WA..anyone pls tel a testcase where the above code fails..pls..
Thanks in advance..
On Mon, Dec 6, 2010 at 5:44 PM, alexsolo asp...@gmail.com wrote:
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Spoj problem-pigbank
i am a beginner.pl help me with this code.i submitted a solution.it s
giving op for all given testcases.but the judge is giving me a TLE.
code:
#includeiostream
#includemap
#define inf 9
using namespace std;
mapint,int m2;
int func(mapint,int m1,int w)
{
if(m2[w]inf)
return m2[w];
mapint,int::iterator it;
int min=inf;
for(it=m1.begin();it!=m1.end();it++)
{
if((*it).second=w)
{
int x=func(m1,w-(*it).second);
if(x+(*it).first min)
min=x+(*it).first;
}
}
m2[w]=min;
return min;
}
main()
{
int t;
cint;
while(t--)
{
int w1,w2;
cinw1w2;
int w=w2-w1,no,a,b;
cinno;
mapint,int m1;
for(int i=0;ino;i++)
{
cinab;
m1.insert(pairint,int(a,b));
}
m2[0]=0;
for(int i=1;i=w;i++)
m2[i]=inf;
func(m1,w);
if(m2[w]!=inf)
coutThe minimum amount of money in the piggy-bank is
m2[w].\n;
else
coutThis is impossible.\n;
}
}
pl say hw i can improve.
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 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] missing 2 nums in an array
sum of n elements from 1=n(n+1)/2 product from 1 to n=n! calculate dis.. sum=calculated sum-orig sum prod=calculated prod-orig prod with dis form quadratic eq and solve... hope this works... On Tue, Oct 12, 2010 at 12:29 AM, Asquare anshika.sp...@gmail.com wrote: Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers. I know of a solution using another array to store frequency of each number.. But this holds for than 2 nums also.. So Is there any other solution apart from this specific for 2 nums and of lesser complexity..?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Anyone know optimized solution to bytelandian gold coins problem
Recursion and Memoization. On Thu, Sep 23, 2010 at 2:12 AM, Dave dave_and_da...@juno.com wrote: @Venkatakrishna: What is the problem? I don's see a question. Dave On Sep 22, 2:36 pm, venkatakrishna bandla venkatakrishnabt...@gmail.com wrote: You are given a coin, which has an integer number written on it. A coin valued n can be exchanged with me for three coins valued n/2, n/3 and n/4. But these numbers are all rounded down to the integer value. You can sell these coins for American dollars. The exchange rate is 1:1. -- 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. -- Bharath -- 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: point lies inside or outside of triangle..
Find area of Triangle(A) and area of Polygon with these four points(B)
if AB point lies outside triangle
if AB point lies inside triangle
else on if they are equal, it lies on triangle.
On Tue, Sep 21, 2010 at 5:03 PM, jagadish jagadish1...@gmail.com wrote:
Here is the Simplest working solution :)
bool check(int x[],int y[],int n)
{
c=0;
for(int i=0;in;i++) {
j=(i+1)%n;
if( ((y[i]y) != (y[j]y)) (x-x[i]/x[j]-x[i] y-y[i]/y[j]-y[i])
c=!c;
}
return c;
}
On Sep 20, 7:46 pm, umesh kewat umesh1...@gmail.com wrote:
Initially we have given three point A , B, C in plane represent three
nodes
of triangle, now given another point Z which lies in same plane, find
out
whether that point lies on/inside the triangle or outside of
triangletry
to get in min time and space complexity
--
Thanks Regards
Umesh kewat
--
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.
--
Bharath
--
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] Point lies inside or outside of triangle?
Find area of Triangle(A) and area of Polygon with these four points(B) if AB point lies outside triangle if AB point lies inside triangle else on if they are equal, it lies on triangle. On Mon, Sep 20, 2010 at 10:39 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: Method 1: Yes you can do by writing equation of 3 lines taking 2 points at a time and finding the sign with the third point. Suppose: ax+by+c=0 is your first line and (x,y) is the third point then find out the sign of the 3rd point satisfying it on the line. suppose this sign is S (for +ve) Similarly calculate for signs for other 2 lines. Now give a point(p,q) should give the same signs for all the 3 lines .If it gives the same sign for all the 3 lines that means it lies btwn all the 3 lines and all the 3 points.hence proved. Method 2: Area mentioned by praveen Method 3: http://en.wikipedia.org/wiki/Barycentric_coordinates_(mathematics)#Determining_if_a_point_is_inside_a_triangle You can choose the best method. On Mon, Sep 20, 2010 at 9:18 PM, Nicolae Titus nicolaetitu...@gmail.comwrote: there are some approximations involved there, it should be (area(big) - sum(area small)) error a better approach would be to find if the point is on the proper side of each edge take all the edges clockwise and calculate the sinus between each edge and the point, if they are all positive, the point is inside. Titus -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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. -- Bharath -- 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] Amazon Interview
-- One can store the binary equivalent of the number of zeros in each line... and carry on from there -- 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: Amazon Question
What does 50% or more similarity means?? Trie will work only if prefix is equal. On Sun, Sep 12, 2010 at 6:49 PM, Chi c...@linuxdna.com wrote: trie On Sep 12, 3:09 pm, sharad kumar aryansmit3...@gmail.com wrote: pagerank algo On Sun, Sep 12, 2010 at 5:42 PM, Snoopy Me thesnoop...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Bharath -- 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] unique number in an array
Xor works only if a number is repeated is repeated even number of times. It will not work in other case. On Mon, Jun 14, 2010 at 7:02 PM, Priyanka Chatterjee dona.1...@gmail.comwrote: XOR all the elements of array, the remaining value is the required unique number. (XORing two same numbers results in zero) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://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. -- Bharath -- 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: Largest even length palindrome in a string!!
Complexity is O(n3) for both above solutions
Ex:
On Sat, Jun 5, 2010 at 3:27 AM, Minotauraus anike...@gmail.com wrote:
for(int i=0; iword.length-1; i++)
{
if(word[i]==word[i+1]) //for an even palindrome, consecutive letters
at the middle of the string have to be the same
{
palindromeFound=true;
while(n0mword.length) //once you've found the middle of
the palindrome, compare left of and right of, while making sure you
don't go out of bounds
{
if(word[n--]==word[m++])
{
startIndex = n; //overwrite index of the
start and end locations
endIndex = m;
}
else break;
}
}
}
print(Even length-ed Palindrome: +word[startIndex-endIndex], length
= endIndex-startIndex);
Complexity =O(n).
On Jun 5, 2:34 am, Satya satya...@gmail.com wrote:
Hi,
How to find largest palindrome, which is even in length in a string.
Complexity should be lessthan O(n^2).
Ex;- abacbbcababac - Given string.
'abacbbcaba' - is the largest even length palindrome.
Thanks,
Satya
--
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.
--
Bharath
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: another google telephone interview question
Find the median of the values and move the lower values to left and higher
values to the right. This can be done in o(n). now do the same on both the
parts recursively. And the total complexity will be o(nlogk).
On Fri, May 21, 2010 at 1:12 PM, Shachin Sharma shac...@gmail.com wrote:
No heapify will not barf. Here is how it goes:
Whenever you get a node value root value (you have already determined the
root value in first scan) you are sure that this isnt the actual value can't
be in a heap. So determine actual value.
if (pres_node_value root_value say R) //Value keeps frequency and isnt
actual
Call get_actual_value (pres_node_value)
get_actual_value (pres_node_value)
{
frequency_of_occurence = pres_node_value /R = Quotient
actual_value = pres_node_value % R = remainder
So e.g. when 2 is repeated twice and root value is 3 you will store (2
+ 3 +3 = 8). When you see 8 you know it is ROOT = 3 so get_actual_value
(8) will give 8/3 = 2 = frequency and 8% 3 = 2 = actual value.
}
Rest of heapify insertion works as usual. This way nothing in heap changes,
no property. And by the way how can you save bits in an integer ?? It is
always 4 bytes (on most of platforms) whether its = 1 or 1 + 1000 ? If you
said that there could be overflow I would still have agreed but I dont think
you are saving bits. In fact in your solution a whole new 4 byte chunk is
used when you keep something like 2:1 which is O(K) space and violates the
in-place property which says that extra space should have upper bound logn.
Thanks,
Sachin
On Thu, May 20, 2010 at 7:59 PM, Piyush Verma 114piy...@gmail.com wrote:
@shachin,when u add value of root in the child of root then for insertion
of new element when heap is called(so heapify is called) so now this child
becomes root which is not desired..
plzz correct me if i m wrong
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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.
--
Bharath
--
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] Search in a sorted NxN matrix
Bsearch on diagonal elimanates all the submatrix under 9. You are left with only one column and a row.Do BinarySearch on these lists. On Wed, Nov 25, 2009 at 6:07 PM, chitta koushik koushik.infin...@gmail.comwrote: @Bharath I dont think BinSrch on diagnol and then on row works. Can u explain your algo? chk for this matrix 1 2 3 4 5 2 9 12 19 24 3 10 14 18 20 8 13 15 20 23 11 14 16 21 24 Find(8) doesn't give o/p --Koushik C On Wed, Nov 25, 2009 at 5:18 PM, Arun arunm...@gmail.com wrote: how about splitting the matrix into 4 squares and considering the rightmost bottom and comparing it to topmost left corner of each square. in every iteration you will eliminate atleast one square. so worst case, you have to repeat this divide and conquer on the three other squares. not good as as binary search though(in the sense of eliminating 2 squares). On Wed, Nov 25, 2009 at 3:12 AM, Aditya Shankar iitm.adityashan...@gmail.com wrote: On Wed, Nov 25, 2009 at 2:16 PM, Bharath bharath1...@gmail.com wrote: You can actually do it in O(logn) complexity. Binary Search on diagonal and then on a row. Will that always work? 1 2 3 3 5 6 4 7 8 Find(6) fails with the usual binary search algorithm. On Tue, Nov 24, 2009 at 10:33 PM, chitta koushik koushik.infin...@gmail.com wrote: Start from top right or bottom left corner and move according if the element to be searched is lesser or greater than current. --Koushik C Pablo Picassohttp://www.brainyquote.com/quotes/authors/p/pablo_picasso.html - Computers are useless. They can only give you answers. On Tue, Nov 24, 2009 at 7:27 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: A nice problem that i encountered : In O(n) search for a value x in a sorted NxN matrix. Definition of sorted matrix: All rows and all columns are sorted in ascending order. So thought of sharing .. Rohit Saraf Sophomore Computer Science and Engineering IIT Bombay -- 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. -- Bharath -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Bharath -- 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] Finding first and last k digits of n^n
For last k digits
int foo(int n, int k)
{
int m=1;
for(; k 0; k--) m*=10;
int r=1, t=n % m;
while(n)
{
if (n % 2)
r = r * t % m;
t = t * t % m;
n = 1;
}
return r;
}
On Sat, Nov 21, 2009 at 9:44 AM, Siddharth Prakash Singh
sps...@gmail.comwrote:
Can anybody suggest an algorithm to find first and last k digits of
n^n.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=.
--
Bharath
--
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=.
[algogeeks] Re: Matrix Toggling
Nice explanation MrM. Thanks a lot. On Sat, Sep 19, 2009 at 6:24 PM, MrM maleki...@gmail.com wrote: its a beautiful classical problem :) first its easier to find which blocks needs to be toggled ! (it can be done by xor) so your initial matrix changes to : 1 1 0 0 0 1 0 0 1 now we want to set all blocks to 0. its obvious that if we toggle a row or column twice, the result is as same as do nothing ! so we can conclude that each block can be toggled at most twice (once by its row and once by its column). the point in this problem is that there cannot be more than 2 way to change the initial matrix to final matrix ! because if you toggle the first row, you can find that which columns should be toggled (by their common block with first row), and then you can denote the status of remaining rows ! so once you toggle first row and once not ! another point is that both this ways, are the same ! it means if you reached the final state by toggling X rows and columns, you will reach the final state by toggling the remaining 2*N-X rows and columns too ! if you couldn't reach the final state with this way, you can be sure that its impossible to reach the final state ! and if you made it, the minimal number if moves is equal to MIN (X, 2*N - X) you can also use this method for an M*N matrix ! Hope it helps ^-^ On Sep 19, 3:02 pm, Bharath Kumar bharath1...@gmail.com wrote: Given two square matrices(initial and final) consisting of elements either 1 or 0. Using minimum number of toggles change the initial to final matrix. You can toggle either a single row or column at a time. If ith row is toggled all 1's become 0 and vice versa in that row. What will be the correct algorithm for this? For example |0 0 1| |1 1 1| |1 0 1| to |1 1 1| |1 1 0| |1 0 0| would require 1st row and last column toggle. -- Bharath --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: selection from infinite tape
This problem is 'Reservoir Sampling Problem. http://gregable.com/2007/10/reservoir-sampling.html On Thu, Sep 17, 2009 at 1:20 PM, manish bhatia mb_mani...@yahoo.com wrote: There is an infinite tape running, churning out numbers. You are able to see these numbers one by one, but not allowed to store all of them, but you should be ready with k numbers whenever prompted, such that all have been selected with equal probability. Say, when you were prompted, n numbers have already passed, each of your selected k numbers should have 1/n as the selection probablity. Of course, you can store k numbers from that tape as the tape is progressing, so that you can present them when prompted. -- Try the new Yahoo! India Homepage. Click herehttp://in.rd.yahoo.com/tagline_metro_1/*http://in.yahoo.com/trynew . -- Bharath --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: N number apples needs to distribute across M num baskets of varying capacity in balanced way
What does optimal balance mean? In your example case, if you have 10 apples, put 2 in basket1, 4 in basket2, 4 in basket3 and basket4 gets nothing. If you have to make sure that, each basket gets at least one apple, then start distributing apples one by one to each basket until it reaches its max capacity. But approach may differ upon the definition of optimality. On Wed, Sep 9, 2009 at 11:54 AM, Sandeep .A.S. reachtosand...@gmail.comwrote: Hi, Please let me know is there any standard algorithm to solve the below mentioned problem. Problem statement: I am having 10 apples and 4 basket each basket capacity is as mentioned below: Basket1 : capacity can hold maximum of 2 apples Basket2 : capacity can hold maximum of 4 apples Basket3 : capacity can hold maximum of 6 apples Basket4 : capacity can hold maximum of 8 apples I want to distribute the apples based on percentage contribution of each basket to total number of apples can accommodate by all the basket For the above example the 10 apples can be distributed as follows: 1 apple for basket1 (10% = (basket1 capacity/ total of all basket capacity) *100 = (2/20) *100) 2 apple for basket1(20% =(basket2 capacity/ total of all basket capacity) *100 = (4/20) *100) 3 apples for basket 3(30% = (basket3 capacity/ total of all basket capacity) *100 = (6/20) *100) 4 apples for basket 4(40% = (basket4 capacity/ total of all basket capacity) *100 = (8/20) *100) In the above example what if I have 13 apples? What is the best approach to solution which is near to optimal balance? I request you to provide the idea to resolve this problem. Thanks Regards, Sandeep -- Bharath --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: DS question
You can use a hash map. What do u mean by preserving order? Keep inserting the characters into hash, whenever u find a duplicate, delete it. The order is maintained still. Can you please elaborate on what is mean by preserving order? On Sep 8, 10:47 am, yash yashpal.j...@gmail.com wrote: wap a program in efficient manner to remove all occurrence of duplicate character in the word and all occurrence of duplicate word in the file. i break the problem in two section( this is my approach it may be better one ) wap to remove all duplicate character in the word. (order is important) [i don't know which DS we use for this program your suggestion has highly appreciated] wap to remove all duplicate word in the file. (order is important)[we use tries to remove all duplicate word in the file] input in file we welcome your feedback, suggestions comment to make better your world After run the above compression algo output will be we welcom your fedback, sugtion coment to make betr world -- Kind Regards ^_^ Yashpal Jain Software Developer-IDC Risk PayPal - an ebay company --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: linked list questions
yeah a[i] == a[n-i] will work if you know the length of the list in advance.
What if we dont know the length in advance. One has to to make two passes on
a list ,first to find the length or midpoint and another pass for
comparison.
Can we do it in a single pass?
On Tue, Sep 8, 2009 at 9:01 PM, ankur aggarwal ankur.mast@gmail.comwrote:
@barath
u r using extra space..
wat is new about this sol
change to array..
then do as simple
using a[i]==a[n-i] ???
On Tue, Sep 8, 2009 at 8:04 PM, Bharath bharath1...@gmail.com wrote:
Q: Check whether given singly linked list is palindrome or not in
single pass.
Instead of making two passes, can we do it in single pass on a list?
One method i can think of is, hashing character to its postion and
check for the sum.
abccba
123456
a: 1+6=7
b: 2+5=7
c: 3+4=7
On Sep 8, 5:33 pm, ankur aggarwal ankur.mast@gmail.com wrote:
for 1st
use hare and tortoise algo to find the mid point of the linklist ...
and reverse the other end
like
a-b--c-d-v-u
a-b--c-d-v-u
pointer 1 will point to a and other pointer will point to u
then it is done ..
u can check..
2nd
for(p = original; p != null; p = p-next-next)
p-next-random = p-random-next;
(i) insert one new node in original list for every node .
(ii) then change random links of newly inserted nodes
i.e; for every new node (p-next)
p-next-random = p-random-next
(iii)then split 2 lists
Now Split the Lists
code is
for( q =original-next,r = original-next,p = original; p != null; p =
p-next,q=q-next)
{ p-next = p-next-next;
q-next = q-next-next;
}
--
Bharath
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: minimum difference.
If the range of numbers is known, sort the array using radix sort and compare difference of adjacent elements. On Sep 2, 2:33 pm, Varun S V varun...@gmail.com wrote: Sorry this doesnt work. The difference between any other two sets can be lesser than the difference between two min numbers. On Wed, Sep 2, 2009 at 2:57 PM, Varun S V varun...@gmail.com wrote: Since we difference between two minumum elements should suffice, how about finding the min and second minimum element in the array in single scan and returning their difference. This should take not more than O(N) time. Regards, -Varun. On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal 1987.shis...@gmail.comwrote: Sort the array and find the minimum of difference of adjacent values of the sorted array. Time Complexity : O(nlogn), Space Complexity : O(1) On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal ankur.mast@gmail.comwrote: given a array of length n. find 2 number such that their differnce is minimum. -- Shishir Mittal Ph: +91 9936 180 121 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
