Re: [algogeeks] Regarding Google recruiting
Any idea about whats the probability of getting rejected by *Hiring* * Committee*? -Regards *Amit Agarwal http:///www.amitagrwal.com* +91-779-822-8765 On Sun, Feb 6, 2011 at 8:38 PM, Badrinath Kulkarni urba...@gmail.comwrote: http://dondodge.typepad.com/the_next_big_thing/2010/09/how-to-get-a-job-at-google-interview-questions-hiring-process.html -- 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] Need - Lotus Notes/Domino/BlackBerry Administrator
Any mentor here who can stop these spams? -Regards *Amit Agarwal http:///www.amitagrwal.com* +91-779-822-8765 On Mon, Jan 24, 2011 at 9:13 PM, Nick smith nick.dwl...@gmail.com wrote: *Need* -* Lotus Notes/Domino/BlackBerry Administrator * *Location:** Pittsburgh, PA* *Duration:** 6+ Months* *Job Description:* *• Provide 3rd line client support for Lotus Notes to helpdesk (1 users) * *• Provide 3rd line client support for Lotus Notes to various clients and helpdesk • Maintain/upgrade server/clients for Lotus Notes and Blackberry • Provide team mentoring for Lotus/Domino/Blackberry support **• Test/support/configure Domino server for e-mail/apps (Domino, Blackberry, 3rd party apps) * *Please send your resumes only to nick@dwlabs.* -- *Thanks Regards Nick Smith* *Technical Recruiter ** *** *Dwlabs Inc* -- 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. -- 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] Find push/pop/min or max in O(1)
yes, on every push/pop there will be max 2 push/pop and 2 comparisons which
is ultimately O(1).
(only in case of 1st element of stack there will be 3 push/pop)
-Regards
Amit Agarwal
blog.amitagrwal.com
On Fri, Oct 8, 2010 at 9:31 AM, saurabh singh saurabh.n...@gmail.comwrote:
yes i too think now that it should work..but on every push/pop we will
need to update the other two stacks also which can be done in constant
time..
On Fri, Oct 8, 2010 at 12:58 AM, tech rascal techrascal...@gmail.comwrote:
I think saurabh gupta is rite.if v take 2 extra stacks ...1 for min
and 1 for max, thn some space wud b saved.
for the above example .max_stack wud b-
top
45 56 66 76 44343
and min_stack wud b-
---top
45 22 3 2 -999
so, here v need 2 save only 5 elements in max_stack, 5 elements in
min_stack and 15 elements in full_stack ( acc 2 above example only), hence
total=25 elements..othrwise if u do it by taking only 1 stack thn u
need space for ..15X3 (45)elements.
tell me if I am wrong..
On Thu, Oct 7, 2010 at 11:49 PM, saurabh singh saurabh.n...@gmail.comwrote:
Sorry but I have still not got the solution u have tried to propose here.
Firstly the space complexity remain O(n) only what I said.
To understand thing u said better lets take an example of stack with
following entries
---top
45 22 56 44 55 3 2 4 -999 4 2 45 66 76 44343
how will your second stack look like and how will the push/pop/min/max
will work here ?
On Thu, Oct 7, 2010 at 11:33 PM, Saurabh Gupta
saurabhgupta1...@gmail.com wrote:
On Tue, Oct 5, 2010 at 9:47 AM, saurabh singh
saurabh.n...@gmail.comwrote:
elaborate plz
For every new element in stack, you need thrice of space to store the
min and max elements also. This has the effect that at state of stack, you
can get the min and max till that point. Instead of this, maintaining a new
stack for min elements would be much more efficient in terms of memory
since
in that all the number of elements would be lesser than the main one.
so, basically in your solution, the size of object will be three times
bigger than the data type which can hold the number otherwise.
On Tue, Oct 5, 2010 at 9:42 AM, Saurabh Gupta
saurabhgupta1...@gmail.com wrote:
In this method, the extra memory is used. In fact, maintaining a
separate stack of min and max would consume lesser memory than this.
On Thu, Sep 30, 2010 at 12:17 AM, saurabh singh
saurabh.n...@gmail.com wrote:
You will just need to see what is min and max available on the
current top before push. in case of pop u dnt need to do anything...
consider this array imp of stack
each array index is stored with this object : {data, min_till_here,
max_till_here}
-Top
[{4,4,4} , {2,2,4}, {7,2,7} , {-6,-6,7}, {1,-6,7}, {9,-6,9}]
So if u push say 20 then at top u see whats max and min till now.
since curr min (-6) is smaller than 20 so min remains unaffected and
since
curr max (9) is smaller than 20 so curr max becomes 20. Hence the
object at
top in stack looks like {20,-6,20}
On Wed, Sep 29, 2010 at 10:18 PM, albert theboss
alberttheb...@gmail.com wrote:
when we pop out something
we need to find the max min again if max or min is popped out...
this ll take again O(n) to find max and min
Correct me if am 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.
--
Thanks Regards,
Saurabh
--
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,
Saurabh
--
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
Re: [algogeeks] remove redundantt parenthesis
1) Recursion has to be used. 2) Stack has to used 3) If any pair of paranthesis doesn't has any operator outside it, remove the pair 4) If low precedence operator is inside the pair of paranthesis than the one surrounding the pair of parenthesis, don't remove paranthesis. 5) If high precedence operator is inside the pair of paranthesis than the one surrounding the pair of parenthesis, remove paranthesis. -Regards Amit Agarwal blog.amitagrwal.com On Fri, Oct 8, 2010 at 11:42 AM, snehal jain learner@gmail.com wrote: write a program to remove redundantt parenthesis from an expression eg input ((a+b)) output a+b input a+(b*c) output a+b*c inputa*(b+c) output a*(b+c) -- 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: arrays
for getting O(n), Counting sort will work but limitation is that you must
know max element possible in the array.
-Regards
Amit Agarwal
blog.amitagrwal.com
On Fri, Oct 8, 2010 at 5:41 AM, Anand anandut2...@gmail.com wrote:
Is there O(n) solution available for it?
On Tue, Sep 28, 2010 at 7:19 AM, Nishant Agarwal
nishant.agarwa...@gmail.com wrote:
#includestdio.h
#includestdlib.h
int main()
{
int a[20],i,n,max,t,j,k;
printf(Enter the no. of elements\n);
scanf(%d,n);
for(i=0;in;i++)
scanf(%d,a[i]);
for(i=0;in-1;i++)
{
j=n-1;
max=0;
k=i;
while(ij)
{
if(a[j]a[i]a[j]=max)
{
max=a[j];
k=j;
j--;
}
else
j--;
}
t=a[i];
a[i]=a[k];
a[k]=t;
}
for(i=0;in;i++)
printf(%d\t,a[i]);
return 0;
}
On Tue, Sep 28, 2010 at 3:43 AM, Chi c...@linuxdna.com wrote:
Move-To-The-Front.
On Sep 27, 11:58 pm, Anand anandut2...@gmail.com wrote:
Given an array of integers, for each index i, you have to swap the
value at
i with the first value smaller than A[ i ] that comes after index i
--
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] Binary tree as threads and weights
1) Suppose the node which you hold is P 2) Navigate on path from P to Root of Tree[Upside] and flip the relationship direction for every edge you encounter on the path 3) Make P as Root of tree 4) redraw(P); -Regards Amit Agarwal blog.amitagrwal.com On Fri, Oct 8, 2010 at 1:29 PM, snehal jain learner@gmail.com wrote: If we consider the edges in binary tree as threads and nodes in the tree as weights hanging from it(it is suspended from the root) then how the tree structure will change when the tree is hung from a particular leaf. -- 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: remove redundantt parenthesis
@Dave I agree, I missed those use cases. let me get back with the revised version. -Regards Amit Agarwal blog.amitagrwal.com On Fri, Oct 8, 2010 at 9:48 PM, Dave dave_and_da...@juno.com wrote: @Amit: There is more to it than that, involving operators of equal precedence. Consider a-(b+c) versus (a-b)+c or a+(b-c), or a/(b*c) versus (a/b)*c or (a*b)/c. In the first case of each set, removing the parentheses is wrong, but in the other cases of each, the parentheses are redundant and can be removed. I don't think this can be solved by choosing different precedences for + and - or for * and / because there is the left-to-right rule for applying sequences of + or - operators or sequences of * and / operators. Dave On Oct 8, 2:46 am, Amit Agarwal lifea...@gmail.com wrote: 1) Recursion has to be used. 2) Stack has to used 3) If any pair of paranthesis doesn't has any operator outside it, remove the pair 4) If low precedence operator is inside the pair of paranthesis than the one surrounding the pair of parenthesis, don't remove paranthesis. 5) If high precedence operator is inside the pair of paranthesis than the one surrounding the pair of parenthesis, remove paranthesis. -Regards Amit Agarwal blog.amitagrwal.com On Fri, Oct 8, 2010 at 11:42 AM, snehal jain learner@gmail.com wrote: write a program to remove redundantt parenthesis from an expression eg input ((a+b)) output a+b input a+(b*c) output a+b*c inputa*(b+c) output a*(b+c) -- 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.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 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] Excellent Compilation of Interview Questions
http://tinyurl.com/2wjnofr -Regards Amit Agarwal On Wed, Sep 15, 2010 at 10:41 AM, saurabh singh saurabh.n...@gmail.comwrote: haha...no one knows now what was the true source of that solutionlot of stuff on same kind of problem is lying on web on tons of web-sitesthe only change in sol i can observe mostly is change in variable names :) On Tue, Sep 14, 2010 at 10:55 PM, TurksHead Education turksheadeducat...@gmail.com wrote: Shame on you.. you have copied the articles as it is from other sites. For example, the article http://www.cracktheinterview.org/2010/08/converting-a-tree-to-a-doubly-linked-list/; is an exact copy-paste from rawkam.com. So much so that the images still point to images of rawkam.com On Sat, Sep 11, 2010 at 1:26 AM, Shashank Krishna sasan...@gmail.comwrote: Excellent Compilation of Interview Questions Visit http://www.cracktheinterview.org/ -- 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, Saurabh -- 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] amezan interview.........
already discussed. On Fri, Aug 6, 2010 at 11:07 PM, UMESH KUMAR kumar.umesh...@gmail.comwrote: how to sort specific order the given array ,Without using extra memory Input:-a1,a2,a3,a4,a5..an,b1,b2,b3,b4,b5..bn. output:-a1,b1,a2,b2,a3,b3,an.bn -- 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] Amazon Placement Question
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.comwrote:
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.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: Trie
Think of a datastructure where you can search any alphabetic string in the X steps (X = number of characters in string). So basically it can be a tree with 27 childs per internal node. So according to binary search rule and help of one simple link list, this tree can fetch you any string in X steps. So this tree is Trie. -Regards Amit Agarwal blog.amitagrwal.com On Thu, Jun 24, 2010 at 3:39 PM, Dhritiman Das dedhriti...@gmail.comwrote: Useful links: http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic7/http://www.cs.mcgill.ca/%7Ecs251/OldCourses/1997/topic7/ http://www.allisons.org/ll/AlgDS/Tree/Trie/ http://www.allisons.org/ll/AlgDS/Tree/Suffix/ On Jun 23, 11:24 pm, Raj N rajn...@gmail.com wrote: Hi, Can anyone explain me the implementation of trie. I would be grateful if one could provide me the link to a good learning resource. Thanks!! -- 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: a google question
1.Suppose you have Array A and B like this. 2.A = [10,7,3,1] , B = [50,49,48,47,46] 3.Arrange/Assume numbers in a three column table such that First n rows are the made up of A[1] and members of B. Rest m rows are made up of B[1] and members of A. Column 3 keeps sum of column 1 and 2. It would look something like this. ⁃10 50 60 ⁃10 49 59 ⁃10 48 58 ⁃10 47 57 ⁃10 46 56 ⁃50 10 60 ⁃50 7 57 ⁃50 3 53 ⁃50 1 51 4.Now sort the rows based on column 3 in O(n) time. Remember its a merge operation of two sorted lists so O(n+m) time. 5. Pick any number of pairs from top. They are in decreasing order of their value. This algorithm takes time in O(n). But there might be space complexity issues if array size is too large. -Regards Amit Agarwal On Mon, May 3, 2010 at 9:48 PM, Jitendra Kushwaha jitendra.th...@gmail.comwrote: @Varun output for your test cases are as below: arr1[0] + arr2[0] = 38 arr1[0] + arr2[1] = 33 arr1[1] + arr2[0] = 28 arr1[0] + arr2[0] = 38 arr1[0] + arr2[1] = 37 arr1[0] + arr2[2] = 36 what i was talking about worst case was that is if one have to find more than N elements of array c then it is possible that one of the pointer go out of boundry of 1 to N in worst case. On Mon, May 3, 2010 at 6:48 PM, Varun Nagpal varun.nagp...@gmail.comwrote: @Jitendra I dont think so.Try these 2 examples to check: A[1..n] :20 10 0 B[1..n] :18 13 5 Ans :38 33 28 A[1..n] :20 10 0 B[1..n] :18 17 16 Ans :38 37 36 My conjecture is: In the worst case, instead of combination of 1st element of first array with all elements of second array, we need to instead choose 2 elements from first array and than take combination with all elements of second array. Also before doing this we need to choose from which array should these 2 elements be extracted. I have already suggested before how to do 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] question
@Sathaiah, I don't think there is any need to store the pairs. Space complexity is O(n). Lets see this. 1. Put a nested for loop on the given array so that it runs in O(n^2) time. 2. Inside body of the inner loop, I have two numbers for that time and then I'll look for the third number in binary tree which makes my total minimal. (Binay tree is already made and stored in seperate array. So this takes O(n)). 3. By the time I am done with nested loops, I'll be having three numbers in my hand along with thier indexes. 4. (For finding the index of third number, you need to keep it in the node value itself so that there is no extra searching for index. So I think, it will eventually take space complexity of O(Cn). Which is again O(n)). [Correct me if I am wrong] 5. So you completed the algorithm in O(n^2)*log(n) time. -Regards Amit Agarwal On Tue, May 4, 2010 at 8:52 AM, Sathaiah Dontula don.sat...@gmail.comwrote: @vivek, Where do you store pairs sum ?, Space is O(N) ... :) Thanks, Sathaiah On Mon, May 3, 2010 at 9:03 PM, vivek bijlwan viv...@gmail.com wrote: copy the array(A) in a different array(B) to store the index info.(space O(n)) sort(A) take each pair's sum ( complexity O(n^2) ) and with that do a binary search for the 3rd element needed.(O(log(n))). Check for the indices in B. i believe it can be done in better time somehow. On Mon, May 3, 2010 at 6:48 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: given an array(unsorted) may contain negative numbers too find the index of three numbers whose sum is closest to zero in O(N2log N) time and O(N) space. P.S -3 is more close to zero then -6 (number line ...) -- 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. -- 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] value of n
yeah, you are right. It comes from 2 to 6. But is there any way to solve it on paper? -Regards Amit Agarwal Contact: 09765348182 www.amitagrwal.com On Mon, May 3, 2010 at 3:02 PM, Sundeep Singh singh.sund...@gmail.comwrote: oops On Sat, May 1, 2010 at 5:50 PM, Sundeep Singh singh.sund...@gmail.comwrote: Hi Amit, here's the answer: (I am assuming in your equation lg implies log to the base 10) n 8 log(n) = n/8 log(n) = 10 ^(n/8) n The final deduction was incorrect!! for log base 10, the answer is: 2 = n = 6 --Sudneep. = n 8 --Sundeep. On Sat, May 1, 2010 at 10:43 AM, Amit Agarwal lifea...@gmail.com wrote: I could not get you properly. This is an equation comes from the problem statement where I need to find out cut-off value of n between insertion and merge sort. I think equation is part of basic mathematics but I don't remember how do I solve it. -Regards Amit Agarwal Contact: 09765348182 www.amitagrwal.com On Sat, May 1, 2010 at 9:13 AM, abhijith reddy abhijith200...@gmail.com wrote: binary search on n On Fri, Apr 30, 2010 at 10:15 PM, Amit Agarwal lifea...@gmail.comwrote: how do I compute n from this equation. n 8lg(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=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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] value of n
how do I compute n from this equation. n 8lg(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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
