Re: [algogeeks] If anyone have this book please mail me Thanks in advance
Yes please delete the links and stop asking for books which are not free On 30 April 2011 21:24, Varun Nagpal varun.nagp...@gmail.com wrote: Please refrain from sharing such links and engaging in piracy. I kindly request the admin of this forum to delete all such posts and to warn the users on the forum for possible barring in case they are found to use this forum for piracy and malpractices. On Sat, Apr 30, 2011 at 12:09 PM, Charles Turner chtu...@gmail.comwrote: This doesn't look legal to me. Has the author allowed you to redistribute their book? I can't see any such evidence. If you don't have permission to redistribute the book, you're breaking the law. This is a serious offence. You are lowering the reputation of this list. -- 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 Regards, Priyanka Chatterjee Final 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 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: Amazon Question
1do reverse inorder and increment count variable it uses internal stack... 2 otherwise modify morris traversal I agree with* juver++*...internal stack!=extra space.internal stack=auxillary space On 26 January 2011 12:53, juver++ avpostni...@gmail.com wrote: @abovew NO! -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Priyanka Chatterjee Final 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 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: post and pre increment operators
@harshal, sundi: Use some compiler to check, i checked on gcc , it gives 13,14,14 On 9 January 2011 11:44, Harshal hc4...@gmail.com wrote: hey i am also getting the output as 12,13,13,13.. -- 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, Priyanka Chatterjee Final 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] post and pre increment operators
b=(11++)+ (++10)=11+11=22 a=12 in printf the control goes to right first , i.e. ++a , so ++a =(++12), (a becomes 13 but ++a is not printed) then control moves to a but as the next expression pushed in stack is of the same variable so control moves to a++. without printing a a++= 13++, (now a becomes 14) , the control moves now to a=14, the control moves to ++a now as the value of a is changed ++a=14 (it evaluates a from all expressions and then prints) the expressions are popped from stack ( right to left) and printed left to right . as a++=13,a= 14, ++a=14 I hope now things get clearer to you On 9 January 2011 11:16, priya mehta priya.mehta...@gmail.com wrote: ok but the output of int a=10,b; b=a++ + ++a; printf(%d,%d,%d,%d,b,a++,a,++a); is 22 13 14 14 howz that then? On Sun, Jan 9, 2011 at 11:11 AM, kartheek muthyala kartheek0...@gmail.com wrote: Yeah you might be knowing how the expression evaluators work using stack right. printf also uses the same approach On Sun, Jan 9, 2011 at 11:06 AM, priya mehta priya.mehta...@gmail.comwrote: @kartheek so does it use stack for that? On Sun, Jan 9, 2011 at 11:03 AM, priya mehta priya.mehta...@gmail.comwrote: ok i got that On Sun, Jan 9, 2011 at 11:01 AM, kartheek muthyala kartheek0...@gmail.com wrote: small correction printf evaluation starts from right to left. On Sun, Jan 9, 2011 at 10:59 AM, kartheek muthyala kartheek0...@gmail.com wrote: @priya, Generally printf evaluation starts from left to right so first a++ using post increments assign the value of 3rd %d to be 2 then a++gets evaluated , now a value is 3 2nd %d takes a value as 3 1st %d takes a value as 3 if it is a preincrement like ++a in the third place the output will be 3,3,3... got it i guess... Thanks, Kartheek. On Sun, Jan 9, 2011 at 10:38 AM, priya mehta priya.mehta...@gmail.com wrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind this? -- 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. -- 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, Priyanka Chatterjee Final 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] uva toolkit
http://xrds.acm.org/ http://www.comp.nus.edu.sg/~stevenha/programming/acmoj.html http://www.uvatoolkit.com/problemssolve.php Thanks Regards, Priyanka Chatterjee Final 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: uva toolkit
sorry please discard the above mail On 13 September 2010 21:11, Priyanka Chatterjee dona.1...@gmail.com wrote: http://xrds.acm.org/ http://www.comp.nus.edu.sg/~stevenha/programming/acmoj.html http://www.uvatoolkit.com/problemssolve.php Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- Thanks Regards, Priyanka Chatterjee Final 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Help with Increment Operators in C!
output is 18
1. control goes to ++x =6 ,x=6
2. control goes to both x++, i.e. both x++ are evaluated together, therefore
x++ + ++x + x++= 6 +6+6 =18 x=7
On 28 August 2010 17:05, jagadish jagadish1...@gmail.com wrote:
I ran this code..
int main() { int x=5;
printf(%d,(x++ + ++x + x++));
}
The output printed was 18 instead of 19.. Should it not be 19?
--
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,
Priyanka Chatterjee
Final 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Problem
@algoboy: If you want to use extra space go with sharad's algo: do inorder traversal , store in a buffer and use 2 pointer method. T(n) =O(n) , S(n)=O(n) If you don't want to use extra space , convert BST into circular DLL or DLL and use 2 pointer algorithm. (conversion of BST into DLL is a simple algo, already discussed) T(n)=O(n) , S(n) =O(1). The only problem is you change the structure . (There probably exists a working algo to convert a DLL to BST , i haven't tried that yet although) -- Thanks Regards, Priyanka Chatterjee Final 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
@Algoboy , its pretty difficult to find the duplicate in constant space unless u mention the range of numbers. Do the numbers lie between [1,n] ??? Unless some other information is given i don't think it is possible to come out with a proper solution. -- Thanks Regards, Priyanka Chatterjee Final 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
@Anand, you are partly correct, thanks for modifying my code
On 31 July 2010 00:01, Anand anandut2...@gmail.com wrote:
I highlighted the code which I feel need a change. Do let me know if it
correct.
LinkNode *levelOrderTraversal(node *root, int level)
{
LinkNode *ptr1, *ptr2, temp;
if(root == NULL)
return NULL;
if(level == 1)
return createLinkNode(root);
else
{
ptr1 = levelOrderTraversal(root-left, level-1);
ptr2 = levelOrderTraversal(root-right, level-1);
if(ptr1 == NULL ptr2 == NULL)
return NULL;
else if(ptr1 == NULL) // why do you need else if constructs??? i used
return statement after each if
return ptr2;
else if(ptr2 == NULL)
return ptr1;
else
{
* temp = ptr1;
while(ptr1-next)
ptr1= ptr1-next;
ptr1-next = ptr2;
*
/* this is significant modification, i missed it in my code*/
*
return temp;* (Will always return the head of the linked list to
store it in the array)
}
}
}
On Fri, Jul 30, 2010 at 8:18 AM, vineel yalamarth
vineelyalamar...@gmail.com wrote:
Dude, yeah I got the algo, but can u write java code for that
On Fri, Jul 30, 2010 at 6:03 PM, karthik ramanathan
nathankart...@gmail.com wrote:
Do a BFS, by having a queue and keep inserting the nodes into it.
You should know how many nodes are there in each level, for which you can
have a variable to count the number of nodes in each level.
The when you remove from your queue do connect these nodes till your
count. You may need to use one more temp variable to not to lose the
previous level node count when you compute the next level node count.
Repeat the same for all the level.
RK
On Fri, Jul 30, 2010 at 11:21 AM, Amit Agarwal lifea...@gmail.comwrote:
A simple queue implementation will do.
-Regards
Amit Agarwal
blog.amitagrwal.com
On Fri, Jul 30, 2010 at 9:22 AM, Priyanka Chatterjee
dona.1...@gmail.com wrote:
On 30 July 2010 02:59, Priyanka Chatterjee dona.1...@gmail.comwrote:
Algo: 1. find height of tree
2. do level order traversal
i at each level store the address of each tree node in
the data part of a linked node and form linked list of the nodes
ii store the header of a linked list at a certain level
in an array
3. return array.// gives final structure
complexity - T(n) =O(n)
S(n)=O(h+n ) //h=height of tree
//CODE
//tree structure
struct node {
int data;
struct node * left, *right};
// linked list structure
struct linkNode{
struct node * data;
struct linkNode * next;
}
struct linkNode** func(struct node * root){
struct linkNode ** array;
int i, h=height(root);
for(i=1;i=h;i++)
array[i-1]=levelOrderTraversal(root, i);
return array;// final tree structure
}
//max height of tree
int height(struct node *root){
int hL=height(root-left);
int hR=height(root-right);
return 1+ HRHL?HR:HL;
}
struct nodelink* levelOrderTraversal(struct node*root, int level){
if(root==NULL) return NULL;
if (level==1)
return createLinkNode(root); // create a node of a singly l
struct LinkNode *ptr;
if(level1){
struct nodeLink * ptr1, *ptr2;
ptr1=levelOrderTraversal(root-left,level-1);
ptr2=levelOrderTraversal(root-right,level-1);
if(ptr1==NULL ptr2==NULL) return NULL;
if(ptr1==NULL) return ptr2;
if(ptr2==NULL) return ptr1;
ptr1-next=ptr2;
return ptr2;
}
}
struct linkNode * createLinkNode(struct node * root){
struct linkNode* newNode=(struct linkNode*) malloc(sizeof(struct
linkNode));
newNode-data=root;
newNode-next=NULL;
}
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
Thanks Regards,
Priyanka Chatterjee
Final 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.
--
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
Re: [algogeeks] Amazon Placement Question
Algo: 1. find height of tree
2. do level order traversal
i at each level store the address of each tree node in the
data part of a linked node and form linked list of the nodes
ii store the header of a linked list at a certain level in an
array
3. return array.// gives final structure
complexity - T(n) =O(n)
S(n)=O(h+n ) //h=height of tree
//CODE
//tree structure
struct node {
int data;
struct node * left, *right};
// linked list structure
struct linkNode{
struct node * data;
struct linkNode * next;
}
struct linkNode** func(struct node * root){
struct linkNode ** array;
int i, h=height(root);
for(i=1;i=h;i++)
array[i-1]=levelOrderTraversal(root, i);
return array;// final tree structure
}
//max height of tree
int height(struct node *root){
int hL=height(root-left);
int hR=height(root-right);
return 1+ HRHL?HR:HL;
}
struct nodelink* levelOrderTraversal(struct node*root, int level){
if(root==NULL) return NULL;
if (level==1)
return createLinkNode(root); // create a node of a singly l
struct LinkNode *ptr;
if(level1){
ptr=levelOrderTraversal(root-left,level-1);
ptr-next=levelOrderTraversal(root-right,level-1);
}
return ptr;
}
struct linkNode * createLinkNode(struct node * root){
struct linkNode* newNode=(struct linkNode*) malloc(sizeof(struct linkNode));
newNode-data=root;
newNode-next=NULL;
}
--
Thanks Regards,
Priyanka Chatterjee
Final 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
On 30 July 2010 02:59, Priyanka Chatterjee dona.1...@gmail.com wrote:
Algo: 1. find height of tree
2. do level order traversal
i at each level store the address of each tree node in the
data part of a linked node and form linked list of the nodes
ii store the header of a linked list at a certain level in an
array
3. return array.// gives final structure
complexity - T(n) =O(n)
S(n)=O(h+n ) //h=height of tree
//CODE
//tree structure
struct node {
int data;
struct node * left, *right};
// linked list structure
struct linkNode{
struct node * data;
struct linkNode * next;
}
struct linkNode** func(struct node * root){
struct linkNode ** array;
int i, h=height(root);
for(i=1;i=h;i++)
array[i-1]=levelOrderTraversal(root, i);
return array;// final tree structure
}
//max height of tree
int height(struct node *root){
int hL=height(root-left);
int hR=height(root-right);
return 1+ HRHL?HR:HL;
}
struct nodelink* levelOrderTraversal(struct node*root, int level){
if(root==NULL) return NULL;
if (level==1)
return createLinkNode(root); // create a node of a singly l
struct LinkNode *ptr;
if(level1){
struct nodeLink * ptr1, *ptr2;
ptr1=levelOrderTraversal(root-left,level-1);
ptr2=levelOrderTraversal(root-right,level-1);
if(ptr1==NULL ptr2==NULL) return NULL;
if(ptr1==NULL) return ptr2;
if(ptr2==NULL) return ptr1;
ptr1-next=ptr2;
return ptr2;
}
}
struct linkNode * createLinkNode(struct node * root){
struct linkNode* newNode=(struct linkNode*) malloc(sizeof(struct
linkNode));
newNode-data=root;
newNode-next=NULL;
}
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
Thanks Regards,
Priyanka Chatterjee
Final 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find The Kth min in a binary search tree
void kSmallestBST(struct node * root,int k){
static int count=0;
if(!root) return;
kSmallestBST(root-left,k);
if(++count==k) {coutroot-data; return;}
kSmallestBST(root-right,k);
}
--
Thanks Regards,
Priyanka Chatterjee
Final 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST
@Rahil: you are correctthanks
On 24 July 2010 18:33, rahul patil rahul.deshmukhpa...@gmail.com wrote:
1 convert the BST into a sorted doubly linklist.(increasing order) It
will take O(n) time.
2 Now find two nodes in a link list whose sum is k(given no)
to find sum in linklist. take two pointers ptr1= head ptr2=tail of
linlist.
now find sum of ptr1-data + ptr2- data
while(ptr1-data ptr2- data){
if ((ptr1-data + ptr2- data )k)
ptr2= ptr2-prev;
else if ((ptr1-data + ptr2- data )k)
ptr1= ptr1-next;
else if ((ptr1-data + ptr2- data ) == k){
print_data_of_ptr1_and_ptr2;
ptr2= ptr2-prev;
ptr1= ptr1-next;
}
}
the 2nd step will take O(n) time.No added space complexity
On Jul 24, 9:29 am, Priyanka Chatterjee dona.1...@gmail.com wrote:
Given a binary search tree of n nodes, find two nodes whose sum is equal
to
a given number k in O(n) time and constant space.
(ignoring recursion stack space)
I have got O(nlogn) time , O(1) space and O(n) time, O(n) space.
Please
help me out with O(n) time and O(1) space.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
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.
--
Thanks Regards,
Priyanka Chatterjee
Final 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] BST
Given a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space. (ignoring recursion stack space) I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please help me out with O(n) time and O(1) space. -- Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST
Given a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space. (ignoring recursion stack space) I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please help me out with O(n) time and O(1) space. -- Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] microsoft.
I totally agree with Umesh's algo which gives O(K+1) time and an inplace
solution. The only point is the first K+1 numbers may get negated and the
array is modified. In that case after finding the duplicate we can traverse
the array again for the first k+1 no.s and make the negative numbers
positive.
code is -(considering array contains only positive numbers)
for(i=0;ik+1;i++){
if(A[abs(A[i])])0) return abs(A[i]); //1st duplicate, abs is absolute
function
A[abs(A[i])]*=(-1);
}
I am explaining Umesh's solution with an example
let k=6 , kn
A= 1,6,4,5,2,6,3,..
A[0]-1st element, a[k]-k+1 element in array
now A[0]=1; and A[1]=6 now A[1]= -6
A[1]=6 and A[6]=3 now A[6]=-3
A[2]=4 and A[4]=2 now A[4]=-2
A[3]=5 and A[5]=6 now A[5]=-6
A[4]=-2 and A[abs(-2)]=4 now A[2]=-4
A[5]=-6 and A[abs(-6]0 therefore return 6
time complexity=O(k+1) and very much inplace solution .
--
Thanks Regards,
Priyanka Chatterjee
Final 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] microsoft.
@Ashish :Firstly your code will never run in O(k) time and also fails to
provide correct answer.
In your code the index of first negative encountered is
returned
test for this sample: k=5 ,A=2,3,5,4,1,3. your code returns 2
while answer is 3.
alternate way is to check for a ring
//***
int count =0; int i =0;
while (count ++ n){
if (i==a[i]) {i++;continue;}
if (a[i] 0) return i;
i=a[i];
a[i] *=-1;
}
return -1;
//**
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Jul 8, 2010 at 1:32 PM, Priyanka Chatterjee
dona.1...@gmail.comwrote:
I totally agree with Umesh's algo which gives O(K+1) time and an inplace
solution. The only point is the first K+1 numbers may get negated and the
array is modified. In that case after finding the duplicate we can traverse
the array again for the first k+1 no.s and make the negative numbers
positive.
code is -(considering array contains only positive numbers)
for(i=0;ik+1;i++){
if(A[abs(A[i])])0) return abs(A[i]); //1st duplicate, abs is absolute
function
A[abs(A[i])]*=(-1);
}
I am explaining Umesh's solution with an example
let k=6 , kn
A= 1,6,4,5,2,6,3,..
A[0]-1st element, a[k]-k+1 element in array
now A[0]=1; and A[1]=6 now A[1]= -6
A[1]=6 and A[6]=3 now A[6]=-3
A[2]=4 and A[4]=2 now A[4]=-2
A[3]=5 and A[5]=6 now A[5]=-6
A[4]=-2 and A[abs(-2)]=4 now A[2]=-4
A[5]=-6 and A[abs(-6]0 therefore return 6
time complexity=O(k+1) and very much inplace solution .
--
Thanks Regards,
Priyanka Chatterjee
Final 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.
--
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,
Priyanka Chatterjee
Final 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: adobe problem---array
@Anand: Awesome solution ,it works even if more than 1 number repeats
once...
On 9 July 2010 01:10, Anand anandut2...@gmail.com wrote:
One more approach using XOR to find the element repeated thrice.
Complexity: O(n).
Space :0
http://codepad.org/p82TGhjR
main()
{
int arr[]= {5,3,3,1,5,5,7,7,8,8};
int len, set_bit_no, x,y,i;
int xor, prev;
len = sizeof(arr)/sizeof(arr[0]);
xor = arr[0];
x = y=0;
for(i=1;ilen;i++)
{
xor ^= arr[i];
}
printf(xor:%d\n,xor);
for(i=0;ilen;i++)
{
xor ^= arr[i];
if(xor == 0 prev == arr[i])
{
printf(Found:%d\n, arr[i]);
break;
}
prev = arr[i];
}
}
On Thu, Jul 8, 2010 at 6:46 AM, jalaj jaiswal
jalaj.jaiswa...@gmail.comwrote:
@ any solution less then nlogn would do + O(1) space
On Thu, Jul 8, 2010 at 12:38 AM, souravsain souravs...@gmail.com wrote:
@jalaj
Are we looking for a better than )(nlogn) time and O(1) space
solution? What if our target?
If a solution is required simple, then as mentioned by Satya, sort the
numbers in O(nlogn) time and scan once in O(n) time. So we get the
number repeated 3 times in O(nlogn) time and O(1) space.
Sourav
On Jul 7, 7:36 pm, Priyanka Chatterjee dona.1...@gmail.com wrote:
I am sceptical whether any XOR solution exits for your question. But
if
the question is modified as :
*Only one number repeats once,* some no.s repeat twice and only one
number
repeat thrice, here is the XOR solution for that.
suppose the sample array is A[]={1, 3,3,5,5,5, 7,7,8,8}
in the example 1 repeats once and 5 repeats thrice.
1let T= XOR( all elements)= 1^5. (all elements occurring even no of
times
nullify) -O(N)
( let x=1, y=5
As we know the no. repeating once and the no. repeating thrice are
unequal,
there must exist some bit 'k' such that x[k]!=y[k]. There may be more
than
such bits in x and y. But one such bit certainly yields T[k]=1 after
x^y)
2 Now traverse along each bit of T( in binary) from left or right
and
consider T[i] =1 which is encountered first. store it . let b=i;
(O(M) time and O(M) space to store binary if M is the bit length of
T.)
3 T1= XOR(all elements in given array having bit b as 1). (O(N)
time
and O(M) space) ( time is O(MN) but as M=32 , complexity remain
O(N))
4 T0= XOR( all elements in given array having bit b as 0) (O(N) time
and
O(M) space)
One of (T1,T0) gives the no. that repeats once and the other gives
the no
that repeats thrice.
6 Now traverse the along array A and compute count for T1 and T0.
The
count that equals 3 gives the corresponding no. repeating thrice.
-O(N)
Time complexity is O(N+M) . Linear
space complexity is O(M) to store binary form.
But this algo certainly fails if more than one no. repeats once.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
Indiahttp://priyanka-nit.blogspot.com/- 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards,
Priyanka Chatterjee
Final 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] microsoft.
@Ashish: i could not get the answer -3 as well . It is indeed a tough
question. :)
On 9 July 2010 10:31, Ashish Goel ashg...@gmail.com wrote:
@Priyanka : using my logic,
2,-3,5,4,1,3...
2,-3,-5,4,1,3..
2,-3,-5,4,-1,3..
-2,-3,-5,4,-1,3..
now -3 implies 3 is the answer
to be honest, i hate to ask or be asked such question in interviews :)
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Jul 8, 2010 at 9:53 PM, Priyanka Chatterjee
dona.1...@gmail.comwrote:
@Ashish :Firstly your code will never run in O(k) time and also fails to
provide correct answer.
In your code the index of first negative encountered is
returned
test for this sample: k=5 ,A=2,3,5,4,1,3. your code returns 2
while answer is 3.
alternate way is to check for a ring
//***
int count =0; int i =0;
while (count ++ n){
if (i==a[i]) {i++;continue;}
if (a[i] 0) return i;
i=a[i];
a[i] *=-1;
}
return -1;
//**
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Jul 8, 2010 at 1:32 PM, Priyanka Chatterjee dona.1...@gmail.com
wrote:
I totally agree with Umesh's algo which gives O(K+1) time and an inplace
solution. The only point is the first K+1 numbers may get negated and the
array is modified. In that case after finding the duplicate we can traverse
the array again for the first k+1 no.s and make the negative numbers
positive.
code is -(considering array contains only positive numbers)
for(i=0;ik+1;i++){
if(A[abs(A[i])])0) return abs(A[i]); //1st duplicate, abs is absolute
function
A[abs(A[i])]*=(-1);
}
I am explaining Umesh's solution with an example
let k=6 , kn
A= 1,6,4,5,2,6,3,..
A[0]-1st element, a[k]-k+1 element in array
now A[0]=1; and A[1]=6 now A[1]= -6
A[1]=6 and A[6]=3 now A[6]=-3
A[2]=4 and A[4]=2 now A[4]=-2
A[3]=5 and A[5]=6 now A[5]=-6
A[4]=-2 and A[abs(-2)]=4 now A[2]=-4
A[5]=-6 and A[abs(-6]0 therefore return 6
time complexity=O(k+1) and very much inplace solution .
--
Thanks Regards,
Priyanka Chatterjee
Final 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.
--
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,
Priyanka Chatterjee
Final 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.
--
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,
Priyanka Chatterjee
Final 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Need help
Firstly it is srm 475, the following link has the problem http://www.topcoder.com/stat?c=problem_statementpm=10878rd=14156 @crazysaikat : Sorry for misconstruing you. As this group is public it is better not to post problems of a srm while it is running. Apart from discussing it here, if you need more help on the problem, you can access it under competitionsalgorithms statisticsMatch editorials on the topcoder website. The analysis will be uploaded shortly. -- Thanks Regards, Priyanka Chatterjee Final 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Need help
Contest in running and you are posting the 550 points problem? Its unfair.
Ask after it gets over.
On 6 July 2010 17:30, crazysaikat crazysai...@gmail.com wrote:
Hey anyone doing topcoder srm 375, please help me out in medium
question, question is..
Rabbits often feel lonely, so one group of rabbits decided to gather
together and play a game. The game is played on a horizontal row of N
cells (N = 2), numbered 0 to N - 1 from left to right. Each cell is
colored white, black or red. You are given a string field of length N,
where the i-th character is the color of cell i ('W' for white, 'B'
for black and 'R' for red). There are r rabbits playing the game. The
rabbits choose their starting cells randomly such that no two rabbits
are on the same cell. Each subset of r distinct cells has the same
probability of being chosen as their starting cells. The size of the
field is the number of cells it contains (which is initially N). The
following is repeated while the size of the field is greater than 2:
Each rabbit steps onto a neighboring cell. Since each cell potentially
has up to two neighboring cells, the following rules are used to
determine which cell the rabbit will choose:
If a rabbit is on cell 0, she must step onto cell 1.
If a rabbit is on cell size - 1 or size - 2, she must step onto the
left neighboring cell.
All other rabbits choose which neighboring cell to step onto according
to the color of the cell they are currently on:
White: She must step onto the left neighboring cell.
Black: She must step onto the right neighboring cell.
Red: If this is her first move, she must step onto the left
neighboring cell. Otherwise, she must return to the cell she was on
immediately before she was on the current cell.
After all rabbits finished their steps, for each cell that contains
more than one rabbit, all rabbits on that cell will be removed from
the field.
The rightmost cell will disappear (causing the size of the field to
decrease by 1). By the rules above, this cell will always be empty.
When the game ends, 0, 1 or 2 rabbits will remain on the field. Return
the expected number of rabbits left on the field when the game ends.
Samples :
WRBRW
4
Returns: 0.8
The initial positions of the rabbits are cells { 0, 1, 2, 3 }, { 0, 1,
2, 4 }, { 0, 1, 3, 4 }, { 0, 2, 3, 4 }, or { 1, 2, 3, 4 }. For
example, if { 0, 1, 2, 4 } is chosen, they will step as follows and 2
rabbits will remain on the field:
1)
WWB
2
Returns: 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.
--
Thanks Regards,
Priyanka Chatterjee
Final 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] addition using bitwise
nothing is wrong.i wrote sorry in my third mail On 1 July 2010 14:04, anand verma anandandymn...@gmail.com wrote: @Priyanka.can u plz explain what is wrong in SHRINIVAS' code?? -- 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, Priyanka Chatterjee Final 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] addition using bitwise
On 29 June 2010 20:31, Priyanka Chatterjee dona.1...@gmail.com wrote:
int add(int a, int b)
{
do
{
a=a^b;// sum without carry
b=((a^b)b)1;// carry without addition
} while(b);//when carry equal to 0 a contains the sum
return(a);
}
Explanation:
We can add 2 no.s in the following way:
let the numbers be a=243, b=798
now add the no.s without considering the carry in each bit position,
i.e. 243+798=931
now considering the carry for each bit position you get *0110*
now add 931+0110=1041
now add 243 and 798 using '+' operator u get same answer as above 1041
so the algorithm is
start a loop
1. xor the binary no.s to find the sum without carry, because in this
case bit[k] =0 in the result only if bit[k[] in both a and b are 0 and
bit[k]=1 in the result only if bit[k] in a and b are different.
so this is clearly XOR operation
2. if we want carry only , then bit[k]=1 in result only if bit[k-1]=1 in
both a and b = (1 1)1=10 , so this operation is AND followed by LEFT
SHIFT.
3. finally the loop ends when b=0 = iterate until nothing to carry
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] addition using bitwise
int add(int a, int b)
{
do
{
a=a^b;// sum without carry
b=((a^b)b)1;// carry without addition
} while(b);//when carry equal to 0 a contains the sum
return(a);
}
Explanation:
We can add 2 no.s in the following way:
let the numbers be a=243, b=798
now add the no.s without considering the carry in each bit position, i.e.
243+798=931
now considering the carry for each bit position you get 1110
now add 931+0110=1041
now add 243 and 798 using '+' operator u get same answer as above 1041
so the algorithm is
start a loop
1. xor the binary no.s to find the sum without carry, because in this case
bit[k] =0 in the result only if bit[k[] in both a and b are 0 and bit[k]=1
in the result only if bit[k] in a and b are different.
so this is clearly XOR operation
2. if we want carry only , then bit[k]=1 in result only if bit[k-1]=1 in
both a and b = (1 1)1=10 , so this operation is AND followed by LEFT
SHIFT.
3. finally the loop ends when b=0 = iterate until nothing to carry
--
Thanks Regards,
Priyanka Chatterjee
Final 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] unique number in an array
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] First k smallest elements
On 12 April 2010 23:57, souri datta souri.isthe...@gmail.com wrote: Why only median of median? @Souri: It's because using order statistics (randomized select) , you have an expected time complexity of theta(n) . But the upper bound is n^2 even to find the smallest element. So to ensure selection of no.s in linear time in the worst case, we use medians of medians. @ Rohit: Your BST algo is good but not the best. On Mon, Apr 12, 2010 at 7:51 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Find the kth element using order statistics - O(n)As far as i know , u will have to use median of medians selection algorithm for this... Rest is fine.. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Mon, Apr 12, 2010 at 3:20 PM, souri datta souri.isthe...@gmail.comwrote: Steps: 1. Find the kth element using order statistics - O(n) 2. In one pass over the array, get all the elems less than the kth element. Let me know if this is not correct. On Mon, Apr 12, 2010 at 1:57 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: I have already given an O(n) solution. See above ! The BST solution is O(nlogn) but is practically more nice. :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Mon, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: are yaar... i meant BST... i thought that was obvious ! sry if i confused you @rohit It's ok.Actually in this group people come up with very different and non-common solutions so its risky to take things 'obviously'. Rotation algo has a complexity of O(nlogn)[for constructing a BST] +O(n) [for rotating n times]=O(nlogn) . Till now best algo we have is using heaps which give rise to complexity = O(n+klogn) Please pass on algos having better runtime complexity. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Hey rohit.You were referring to Binary tree.Search keyword was missing.Because rotation makes no sense in binary tree.Please note binary tree and BST are different. On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Read the slides i uploaded. They explain what rotation does in a BST. Also you might like to refer to Red Black Trees in CLRS that chapter explains rotations. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: but still the binary tree solution is of more practical use.i will explain the solution once i reach my comp On 4/11/10, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Time complexity is O(n log n). But the last solution I gave has O(n). What did u not understand abt thesolution @Rohit Please explain how that Binary tree solution works. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee dona.1...@gmail.com wrote: On 11 April 2010 10:46, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Construct a binary tree from the data (maintain the size of subtree under each node). Do rotations till the left subtree does not have size k. Rotation is a constant time operation. Please prove the correctness of your algorithm with the time complexity -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.com wrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth
Re: [algogeeks] First k smallest elements
On 11 April 2010 10:46, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Construct a binary tree from the data (maintain the size of subtree under each node). Do rotations till the left subtree does not have size k. Rotation is a constant time operation. Please prove the correctness of your algorithm with the time complexity -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.comwrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above procedure for all n elements in an array At last you will get k smallest elements and root is kth smallest element in the array this is O(nlogk) CHERUVU JAANU REDDY M.Tech in CSIS On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.com wrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So any suggestions ? Thanks On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond patidarc...@gmail.comwrote: there are better solution of O(n) are posted in the thread...[?]. using order statices On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3) Return the smallest of temp[] Time Complexity: O((n-k)*k). try it ..for this problem[?] -- 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. -- BL/\CK_D!AMOND -- 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. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You
Re: [algogeeks] First k smallest elements
On 11 April 2010 21:56, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Time complexity is O(n log n). But the last solution I gave has O(n). What did u not understand abt the solution Median of medians is a decent algorithm for extracting the kth element( an element of kth rank ). I asked to find all elements with rank 1 to k (kth smallest elements) which would take O(kn). I was looking forward to innovative approaches other than what stated in Cormen. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee dona.1...@gmail.comwrote: On 11 April 2010 10:46, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Construct a binary tree from the data (maintain the size of subtree under each node). Do rotations till the left subtree does not have size k. Rotation is a constant time operation. Please prove the correctness of your algorithm with the time complexity -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.comwrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above procedure for all n elements in an array At last you will get k smallest elements and root is kth smallest element in the array this is O(nlogk) CHERUVU JAANU REDDY M.Tech in CSIS On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.com wrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So any suggestions ? Thanks On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond patidarc...@gmail.comwrote: there are better solution of O(n) are posted in the thread...[?]. using order statices On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3) Return the smallest of temp[] Time Complexity: O((n-k)*k). try it ..for this problem[?] -- 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. -- BL/\CK_D!AMOND -- 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. -- BL/\CK_D!AMOND -- 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
Re: [algogeeks] First k smallest elements
...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. 338.gif361.gif
[algogeeks]
Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
The list of N integers is not sorted. The solution is asked for a particular query. @Abhijit Reddy: Can you elaborate more on* Binary Indexed Trees* or *Segment Interval trees*. May be you opted for the correct data structure. Please give the algorithm. @All: Doing a sorting for O(n logn) and then binary search for x1 and x2 in O(logn) will be less efficient than the simple solution of O(n). Think on the data structure that can optimize it. Is it possible in time complexity O(n)? -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] First k smallest elements
Design the most efficient algorithm to find the first k smallest elements in an array ? -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] First k smallest elements
On 28 March 2010 11:44, sharad kumar aryansmit3...@gmail.com wrote: i feel heapify the array to get a min heap and keep extracting root k times.any further optimisations??? This algorithm works in O(n+k logn) time. It is good . Can this be done using randomized selection algorithm in linear time in the worst case? On Sun, Mar 28, 2010 at 11:33 AM, Priyanka Chatterjee dona.1...@gmail.com wrote: Design the most efficient algorithm to find the first k smallest elements in an array ? -- 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. -- 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, 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Interview question.Provide the solution as per the constraints.
I think you surely can modify the data structure On 8 March 2010 17:04, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: can we assume that we have the sizes of subtree rooted at all nodes in our datastructure.? -Rohit On Mon, Mar 8, 2010 at 5:02 PM, sharad kumar aryansmit3...@gmail.comwrote: @gaurav :ur sol u mean like tk the mem loc for each node and make it as array ? On Mon, Mar 8, 2010 at 8:42 AM, gaurav gupta 1989.gau...@googlemail.comwrote: Median of BST means : median of Sorted array of elements? is it? Convert BST into Hight Balance Search Tree then root node will be your median. On Sun, Mar 7, 2010 at 2:42 AM, Nik_nitdgp nikhil.bhoja...@gmail.comwrote: Given a BST (Binary search Tree) how will you find median in that? Constraints: -No extra memory. Algorithm should be efficient in terms of complexity. Write a solid secure code for it. No extra memory--u cannot use stacks to avoid recursion. No static,global--u cannot use recursion and keep track of the elements visited so far in inorder. -- 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. -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
