[algogeeks] Re: Amazon Question
it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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.
[algogeeks] Re: Amazon Question
it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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] Re: Amazon Question
If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.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.
[algogeeks] Intel Question
In order to make their newest microcontroller as cheap as possible, the ACME Widget Company designed it with a very simple cache. The processor is connected to a slow memory system that contains n bytes, numbered 0 to n - 1. The cache holds a copy of k of these bytes at a time, for fast access. It has a base address (referred to as base below), and it holds a copy of the bytes numbered base, base+1, ..., base+k-1. When a program reads a byte, the cache controller executes the following algorithm: 1. Find a new range of k bytes which contains the requested byte, such that the difference between the old and new base addresses is minimized. Note that if the requested byte was already in the cache, then the base address will not change. 2. Update the cache to the new range by reading from the memory system any bytes that are in the new range but not the old range, and discarding any bytes that were in the old range but not the new range. 3. Return the requested byte to the program. To analyze the performance of a program, you wish to know how many bytes are read from the memory system. The numbers of the bytes that the program reads are given in addresses, in the order that they are read. When the program starts, the base address is 0. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Call for Papers Sessions: The 2011 International Conference on Frontiers in Education: Computer Science and Computer Engineering (FECS'11), USA, July 18-21, 2011
CALL FOR PAPERS and Call For Workshop/Session Proposals FECS'11 The 2011 International Conference on Frontiers in Education: Computer Science and Computer Engineering Date and Location: July 18-21, 2011, USA http://www.world-academy-of-science.org/ Location: See the above web site for venue/city You are invited to submit a full paper for consideration. All accepted papers will be published in the FECS conference proceedings (in printed book form; later, the proceedings will also be accessible online). Those interested in proposing workshops/sessions, should refer to the relevant sections that appear below. SCOPE: Topics of interest include, but are not limited to, the following: O Accreditation and assessment O Student recruitment and retention methods O Promoting multi-disciplinary initiatives - impact on curriculum O Capstone research projects: examples and case studies O Distance learning; methods, technologies and assessment O Innovative degree programs and certificates O Innovative uses of technology in the classroom O Collaborative learning O Learning models and learning from mistakes O Computer and web-based software for instruction O Ethics in computer science and engineering O Incorporating writing into CS and CE curriculum O Preparing graduates for academia O Preparing graduates for industry O Partnerships with industry and government O Team projects and case studies O Undergraduate research experiences O Student observation and mentoring strategies O Advising methods O Evaluation strategies (professors, students, ...) O Transition to graduate studies O Integrating gender and culture issues into computer science and engineering curriculum O The balance between course-work and research O Issues related to the choice of first programming language O Debugging tools and learning O Projects, software engineering, programming issues, and laboratory practices O Computer science and computer engineering curriculum O Active learning tools O Undergraduates as teaching assistants O Funding opportunities for curriculum development and studies O Pilot studies O STEM (Science, Technology, Engineering Mathematics) promising initiatives O Teaching methods O Recruiting methods to attract graduate students O Proposed methods for ranking CS and CE departments O The role of visualization and animation in education O Academic dishonesty in a high-tech environment O Using the web O Factors that lead to success in CS and CE USEFUL WEB LINKS: To see the DBLP list of accepted papers of FECS 2009, go to: http://www.informatik.uni-trier.de/~ley/db/conf/fecs/fecs2009.html The DBLP list of accepted papers of FECS 2010 will soon appear at: http://www.informatik.uni-trier.de/~ley/db/conf/fecs/fecs2010.html FECS 2011 URL: http://www.world-academy-of-science.org/worldcomp11/ws/conferences/fecs11 IMPORTANT DATES: March 10, 2011: Submission of papers (about 5 to 7 pages) April 03, 2011: Notification of acceptance (+/- two days) April 24, 2011: Final papers + Copyright/Consent + Registration July 18-21, 2011: The 2011 International Conference on Frontiers in Education: Computer Science and Computer Engineering (FECS'11) ACADEMIC CO-SPONSORS: Currently being prepared - The Academic sponsors of the last offering of FECS (2010) included research labs and centers affiliated with (a partial list): University of California, Berkeley; University of Southern California; University of Texas at Austin; Harvard University, Cambridge, Massachusetts; Georgia Institute of Technology, Georgia; Emory University, Georgia; University of Minnesota; University of Iowa; University of North Dakota; NDSU-CIIT Green Computing Comm. Lab.; University of Siegen, Germany; UMIT, Austria; SECLAB (University of Naples Federico II + University of Naples Parthenope + Second University of Naples, Italy); National Institute for Health Research; World Academy of Biomedical Sciences and Technologies; Russian Academy of Sciences, Russia; International Society of Intelligent Biological Medicine (ISIBM); The International Council on Medical and Care Compunetics; Eastern Virginia Medical School the American College of Surgeons, USA. SUBMISSION OF PAPERS: Prospective authors are invited to submit their papers by uploading them to the evaluation web site at: http://world-comp.org Submissions must be uploaded by March 10, 2011 and they must be in either MS doc (but not docx) or pdf formats (about 5 to 7 pages - single space, font size of 10 to 12). All reasonable typesetting formats are acceptable (later, the authors of accepted papers will be asked to follow a particular typesetting format to prepare their final papers for publication.) Papers must not have been previously published or currently
[algogeeks] Re: Amazon Question
No,no extra space is needed. Right children which are NULL pointers are replaced with pointer to successor. On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote: If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.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] Re: Amazon Question
@ritu how would you find a successor without extra space if you dont have a parent pointer ? for Instance from the right most node of left subtree to the parent of left subtree(root) ? @Juver++ Internal stack does count as extra space !! On Wed, Jan 26, 2011 at 3:02 PM, ritu ritugarg.c...@gmail.com wrote: No,no extra space is needed. Right children which are NULL pointers are replaced with pointer to successor. On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote: If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] Re: Prime Numbers
Hey Dave On 25 January 2011 18:17, Dave dave_and_da...@juno.com wrote: The most efficient approach is to google millionth prime number and select the first hit. Good one. But it was asked to me in an interview. The trivial approach would be to check for every number to be a prime an continue till the count of prime no reaches 1 million. Another approach according to me would be to use gcd approach for the same but it doesn't guarantees the order of primes I guess (correct me if I am wrong) The interviewer still wanted a better approach. I know of better approaches if a range is given, but what to do in this case. Dave On Jan 25, 6:00 am, siddharth srivastava akssps...@gmail.com wrote: Hi Its an easy one but still I am looking for the most efficient approach. Find first 1 million prime numbers. -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- 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. -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- 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.
[algogeeks] Re: 2 d matrix
As Navies it can be done in O(n^2) Make numbers by using every elements in the row in array row[]. Similarly convert column elements into numbers and put them in array col[]. Now compare both the arrays where the number matches print the index of both row[] and col[] array... eg:- 2, 3, 4 3, 4, 5 6, 5, 1 col[] contains 236, 345, and 451 and row[] contains 234, 345, and 651. On Comparison both has 345 as common total with index (1,1) and is the desired answer. use 2d matrix..makes it easy Time Complexity is at Most O(n^2) Thanks Regards Shashank Mani Best Way to Escape From the Problem is to Solve It -- 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
@Algoose I said ..*.For every node x,go to the last node in its left subtree and mark the right child of that node as x.* it is to be repeated for all nodes except leaf nodes. to apply this approach ,you need to go down the tree.No parent pointers required. for every node say x whose left sub tree is not null ,go to the largest node in left sub-tree say y. Set y-right = x y is the last node to be processed in left sub-tree of x hence x is successor of y. On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.com wrote: @ritu how would you find a successor without extra space if you dont have a parent pointer ? for Instance from the right most node of left subtree to the parent of left subtree(root) ? @Juver++ Internal stack does count as extra space !! On Wed, Jan 26, 2011 at 3:02 PM, ritu ritugarg.c...@gmail.com wrote: No,no extra space is needed. Right children which are NULL pointers are replaced with pointer to successor. On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote: If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.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] Re: arrays
you can also go through the array printing the indexes, but what if I want to know the indexes of some certain elements? 2010/12/30 siva viknesh sivavikne...@gmail.com: if we sort the first array along with the indexes ...in the next pass we can directly print the indexes as result no why should we do binary search in the next pass considering that 2nd array is also sorted??? On Dec 29, 11:38 am, Abioy Sun abioy@gmail.com wrote: Hello, 2010/12/29 Anand anandut2...@gmail.com: if I already have a structure indicating the position of the element in the array. Then why do we need to sort. Question is to provide index of element in O(nlogn). You do not have a structure before preprocessing the data, whose complexity is O(nlogn) via qsort. Once you zip the zip the two array, and sort the new array as @Wladimir and @juver++ mention, you can provide each certain element's index in O(logn) via bsearch. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Question
@Ritu, Right ! I misread you post On Wed, Jan 26, 2011 at 3:44 PM, Ritu Garg ritugarg.c...@gmail.com wrote: @Algoose I said ..*.For every node x,go to the last node in its left subtree and mark the right child of that node as x.* it is to be repeated for all nodes except leaf nodes. to apply this approach ,you need to go down the tree.No parent pointers required. for every node say x whose left sub tree is not null ,go to the largest node in left sub-tree say y. Set y-right = x y is the last node to be processed in left sub-tree of x hence x is successor of y. On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.comwrote: @ritu how would you find a successor without extra space if you dont have a parent pointer ? for Instance from the right most node of left subtree to the parent of left subtree(root) ? @Juver++ Internal stack does count as extra space !! On Wed, Jan 26, 2011 at 3:02 PM, ritu ritugarg.c...@gmail.com wrote: No,no extra space is needed. Right children which are NULL pointers are replaced with pointer to successor. On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote: If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.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.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
Re: [algogeeks] Re: Prime Numbers
I think one can use an elimination method . List out all the numbers
. Keep on eliminating the multiples of 2{excluding 2} , then multiples
of 3 , then multiples of 5 , then 7 , the denseness of the numbers
eliminated will get less . And obviouslly you will get the numbers .
On 1/25/11, siddharth srivastava akssps...@gmail.com wrote:
Hey Dave
On 25 January 2011 18:17, Dave dave_and_da...@juno.com wrote:
The most efficient approach is to google millionth prime number and
select the first hit.
Good one. But it was asked to me in an interview.
The trivial approach would be to check for every number to be a prime an
continue till
the count of prime no reaches 1 million.
Another approach according to me would be to use gcd approach for the same
but it doesn't guarantees the order of primes I guess (correct me if I am
wrong)
The interviewer still wanted a better approach. I know of better approaches
if a range is given, but what to do in this case.
Dave
On Jan 25, 6:00 am, siddharth srivastava akssps...@gmail.com wrote:
Hi
Its an easy one but still I am looking for the most efficient approach.
Find first 1 million prime numbers.
--
Siddharth Srivastava
When you have learned to snatch the error code from the trap frame, it
will
be time for you to leave.
--
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.
--
Siddharth Srivastava
When you have learned to snatch the error code from the trap frame, it will
be time for you to leave.
--
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.
--
Rahul K Rai
rahulpossi...@gmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Question
I don't seem to understand ur solution . [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. Go to the largest node in the left subtree .This means go to the left subtree and keep on going to the right until it becomes null , in which case , you make y-right as x . This means effectively , that y is the predecessor of x , in the tree . Considering a very good code , it may take O(1) space , but you will still need additional pointers. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? Now using inorder traversal with a count , I will start at 1-left , 2- left = 1 , then 2 ... then 2-right = 1 again . then 1 , and then 1- right=3 ...clearly , this will not give us a solution . A reverse inorder looks just fine to me . On Jan 26, 3:14 pm, Ritu Garg ritugarg.c...@gmail.com wrote: @Algoose I said ..*.For every node x,go to the last node in its left subtree and mark the right child of that node as x.* it is to be repeated for all nodes except leaf nodes. to apply this approach ,you need to go down the tree.No parent pointers required. for every node say x whose left sub tree is not null ,go to the largest node in left sub-tree say y. Set y-right = x y is the last node to be processed in left sub-tree of x hence x is successor of y. On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.com wrote: @ritu how would you find a successor without extra space if you dont have a parent pointer ? for Instance from the right most node of left subtree to the parent of left subtree(root) ? @Juver++ Internal stack does count as extra space !! On Wed, Jan 26, 2011 at 3:02 PM, ritu ritugarg.c...@gmail.com wrote: No,no extra space is needed. Right children which are NULL pointers are replaced with pointer to successor. On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote: If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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%2Bunsubscribe@googlegroups .com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252Bunsubscribe@googleg roups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252Bunsubscribe@googleg roups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252Bunsubscribe@goo glegroups.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.comalgogeeks%2Bunsubscribe@googlegroups .com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252Bunsubscribe@googleg roups.com .
Re: [algogeeks] Re: Prime Numbers
Generate primes numbers for the range 1..10^7 using sieve. Than apply sieve bigger range using these prime numbers. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Question
Well the solution is pretty simple.
What you have to do is just do inoder traversal of tree in reverse
order.
Here goes my C++ code for that
int ith_order(Tree *root,int i)
{
static int c;
static int ans;
if(root)
{
ith_order(root-right,i);
++c;
if(c==i)
return ans=root-data;
ith_order(root-left,i);
}
return ans;
}
please correct me if i am wrong :)
On Jan 26, 5:01 pm, sankalp srivastava richi.sankalp1...@gmail.com
wrote:
I don't seem to understand ur solution .
[quote] For every none leaf node , go to the last node in it's left
subtree and mark the right child of that node as x [\quote]. How are
we going to refer to the right child now ??We have removed it's
reference now !!
It is to be repeated for every node except the non leaf nodes . This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's root
makes n-2 , and so on.
Go to the largest node in the left subtree .This means go to the left
subtree and keep on going to the right until it becomes null , in
which case , you make y-right as x . This means effectively , that y
is the predecessor of x , in the tree . Considering a very good code ,
it may take O(1) space , but you will still need additional pointers.
Take the case below .
1
2 3
1 1.5 2.5 4
for node 2 , you will go to 1 , which is the successor of 2 , you make
2-right=1 but what about node 1.5 ???
same is the case with node 3 ... 3-right=2.5 . How will we refer to 4
now ??
Now using inorder traversal with a count , I will start at 1-left , 2-left
= 1 , then 2 ... then 2-right = 1 again . then 1 , and then 1-
right=3 ...clearly , this will not give us a solution .
A reverse inorder looks just fine to me .
On Jan 26, 3:14 pm, Ritu Garg ritugarg.c...@gmail.com wrote:
@Algoose
I said ..*.For every node x,go to the last node in its left subtree and mark
the right child of that node as x.*
it is to be repeated for all nodes except leaf nodes.
to apply this approach ,you need to go down the tree.No parent pointers
required.
for every node say x whose left sub tree is not null ,go to the largest node
in left sub-tree say y.
Set y-right = x
y is the last node to be processed in left sub-tree of x hence x is
successor of y.
On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.com wrote:
@ritu
how would you find a successor without extra space if you dont have a
parent pointer ?
for Instance from the right most node of left subtree to the parent of
left
subtree(root) ?
@Juver++
Internal stack does count as extra space !!
On Wed, Jan 26, 2011 at 3:02 PM, ritu ritugarg.c...@gmail.com wrote:
No,no extra space is needed.
Right children which are NULL pointers are replaced with pointer to
successor.
On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote:
If you convert the given binary tree into right threaded binary tree,
won't
you be using extra space while doing so? Either the given tree should
already be right-threaded (or with parent pointers at each node) or
internal
stack should be allowed for recursion but no extra space usage apart
from
that.
On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote:
it can be done in O(n) time using right threaded binary tree.
1.Convert the tree to right threaded tree.
right threaded tree means every node points to its successor in
tree.if right child is not NULL,then it already contains a pointer to
its successor Else it needs to filled up as following
a. For every node x,go to the last node in its left subtree and
mark the right child of that node as x.
It Can be done in O(n) time if tree is a balanced tree.
2. Now,Traverse the tree with Inorder Traversal without using
additional space(as successor of any node is available O(1) time) and
keep track of 5th largest element.
Regards,
Ritu
On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote:
Theoretically, the internal stack used by recursive functions must
be
considered for space complexity.
On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com
wrote:
internal stack != extra space
--
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%2Bunsubscribe@googlegroups
.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252Bunsubscribe@googleg
roups.com
[algogeeks] Puzzle
You have four numbers 1 , 1 , 9 ,9 . Now using these four and operator + , - , * ,/ and parentheses(if required) your have to get 10. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Sparse Matrix multiplication
A nxn matrix is sparse if the number of non-zero entries in the matrix is much less than n^2. Multiply 2 nxn matrices containing L1, L2, non- zero entries is O(L1L2). -- 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
@Priyanka - what exactly is the difference between extra space and auxiliary
space? As far as the algorithm is concerned, it does use space whose order
of growth is a function of the input size and that is all that matters here.
On Wed, Jan 26, 2011 at 7:55 AM, may.I.answer may.i.answ...@gmail.comwrote:
Well the solution is pretty simple.
What you have to do is just do inoder traversal of tree in reverse
order.
Here goes my C++ code for that
int ith_order(Tree *root,int i)
{
static int c;
static int ans;
if(root)
{
ith_order(root-right,i);
++c;
if(c==i)
return ans=root-data;
ith_order(root-left,i);
}
return ans;
}
please correct me if i am wrong :)
On Jan 26, 5:01 pm, sankalp srivastava richi.sankalp1...@gmail.com
wrote:
I don't seem to understand ur solution .
[quote] For every none leaf node , go to the last node in it's left
subtree and mark the right child of that node as x [\quote]. How are
we going to refer to the right child now ??We have removed it's
reference now !!
It is to be repeated for every node except the non leaf nodes . This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's root
makes n-2 , and so on.
Go to the largest node in the left subtree .This means go to the left
subtree and keep on going to the right until it becomes null , in
which case , you make y-right as x . This means effectively , that y
is the predecessor of x , in the tree . Considering a very good code ,
it may take O(1) space , but you will still need additional pointers.
Take the case below .
1
2 3
1 1.5 2.5 4
for node 2 , you will go to 1 , which is the successor of 2 , you make
2-right=1 but what about node 1.5 ???
same is the case with node 3 ... 3-right=2.5 . How will we refer to 4
now ??
Now using inorder traversal with a count , I will start at 1-left ,
2-left = 1 , then 2 ... then 2-right = 1 again . then 1 , and then 1-
right=3 ...clearly , this will not give us a solution .
A reverse inorder looks just fine to me .
On Jan 26, 3:14 pm, Ritu Garg ritugarg.c...@gmail.com wrote:
@Algoose
I said ..*.For every node x,go to the last node in its left subtree and
mark
the right child of that node as x.*
it is to be repeated for all nodes except leaf nodes.
to apply this approach ,you need to go down the tree.No parent pointers
required.
for every node say x whose left sub tree is not null ,go to the largest
node
in left sub-tree say y.
Set y-right = x
y is the last node to be processed in left sub-tree of x hence x is
successor of y.
On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.com
wrote:
@ritu
how would you find a successor without extra space if you dont have a
parent pointer ?
for Instance from the right most node of left subtree to the parent
of left
subtree(root) ?
@Juver++
Internal stack does count as extra space !!
On Wed, Jan 26, 2011 at 3:02 PM, ritu ritugarg.c...@gmail.com
wrote:
No,no extra space is needed.
Right children which are NULL pointers are replaced with pointer to
successor.
On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote:
If you convert the given binary tree into right threaded binary
tree,
won't
you be using extra space while doing so? Either the given tree
should
already be right-threaded (or with parent pointers at each node)
or
internal
stack should be allowed for recursion but no extra space usage
apart
from
that.
On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com
wrote:
it can be done in O(n) time using right threaded binary tree.
1.Convert the tree to right threaded tree.
right threaded tree means every node points to its successor in
tree.if right child is not NULL,then it already contains a
pointer to
its successor Else it needs to filled up as following
a. For every node x,go to the last node in its left subtree
and
mark the right child of that node as x.
It Can be done in O(n) time if tree is a balanced tree.
2. Now,Traverse the tree with Inorder Traversal without using
additional space(as successor of any node is available O(1)
time) and
keep track of 5th largest element.
Regards,
Ritu
On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com
wrote:
Theoretically, the internal stack used by recursive functions
must
be
considered for space complexity.
On Mon, Jan 24, 2011 at 5:40 AM, juver++
avpostni...@gmail.com
wrote:
internal stack != extra space
--
You received this message because
Re: [algogeeks] Puzzle
11-(9/9) On Wed, Jan 26, 2011 at 7:42 PM, may.I.answer may.i.answ...@gmail.comwrote: You have four numbers 1 , 1 , 9 ,9 . Now using these four and operator + , - , * ,/ and parentheses(if required) your have to get 10. -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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] Puzzle
is it neccesary to use all four operators or we can use any combination?? i mean...can we use an operator twice?? On Wed, Jan 26, 2011 at 7:42 PM, may.I.answer may.i.answ...@gmail.comwrote: You have four numbers 1 , 1 , 9 ,9 . Now using these four and operator + , - , * ,/ and parentheses(if required) your have to get 10. -- 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.
[algogeeks] Re: 2 d matrix
@above person ur solution is O(n^3) in worst case !let's say the row[] and col[] arrays formed are col[]=123 124 125 126 row[]=127 , 128, 129,126 every element of row[] traverses through n elements of the array col[] and and makes O(n) comparisons in the worst case . Thus , each traversal requires O(n^2) time , and there can be O(n^3) traversals , so , time taken will be O(n^3). However sorting one of these arrays ,makes the time complexity as O(n^2log n) On Jan 26, 3:03 pm, bittu shashank7andr...@gmail.com wrote: As Navies it can be done in O(n^2) Make numbers by using every elements in the row in array row[]. Similarly convert column elements into numbers and put them in array col[]. Now compare both the arrays where the number matches print the index of both row[] and col[] array... eg:- 2, 3, 4 3, 4, 5 6, 5, 1 col[] contains 236, 345, and 451 and row[] contains 234, 345, and 651. On Comparison both has 345 as common total with index (1,1) and is the desired answer. use 2d matrix..makes it easy Time Complexity is at Most O(n^2) Thanks Regards Shashank Mani Best Way to Escape From the Problem is to Solve It -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find a line
@dave , There is a proof for it .
Let's say there is a point x0 , y0 .. and I claim that between any two
points ... x1,y1 and x2,y2 assuming they are non-collinear having a
line b/w them a line of some slope passes somewhere b/w them .This
collinearity does not affect our result .
Let's say a point x',y' divides this line into ratio m:n , this is the
point where this line is intersected by the line from x0 , y0 .. as
x1 ,y1 and x2,y2 are non-collinear , this point will always exist .
The slope of this line can be determined from the points x0,y0 and
x',y' , which is always real .hope this makes sense to u !!
On Jan 26, 7:11 am, Dave dave_and_da...@juno.com wrote:
@Sankalp: So what is your code? And what is the equation of the line?
As I said, you can't always use a line through the origin.
Dave
On Jan 25, 5:49 am, sankalp srivastava richi.sankalp1...@gmail.com
wrote:
@dave
In this case , I could just shift my origin to the lowermost point :)
On Jan 25, 10:14 am, Dave dave_and_da...@juno.com wrote:
@Sankalp: I wanted a point far enough outside the region that a line
from any point in the region could not contain any other point in the
region. There are several implications: 1) if the point is to the left
of the region, it can't have an integer y coordinate between 0 and B.
That is where the 0.5 comes from. Second, it seemed reasonable, but
not necessary, to put Y near the middle of the range [0, B]. Then I
just solved for an X that guaranteed that the slope of the line from
any point in the region to the point (X, Y) had slope m satisfying -1/
A m 1/A. Then a line through any point (x1,y) could not intersect
any point (x2,y-1) or (x3,y+1) within the region.
Regarding your algorithm: What does it do with A = B = 5 and points
{(1,1), (2,2), (3,3), (4,4), (1,4)}. This example shows that you can't
always use a line through (0,0).
Dave
On Jan 24, 10:15 pm, sankalp srivastava richi.sankalp1...@gmail.com
wrote:
@
Dave
How did you come up with this solution?
Also Y=floor(B)/2+.5 , X=-A*(B-Y) or X=-AB +AY or Y=X/A+B . this is
the equation of a line with slope 1/A and an intercept of B on Y
axis .I don't quite get this.!!Please elaborate .
Meanwhile , this is my approach .
The slope of the line wil be between the maximum's of the two points
i.e in the case of (10,0)..(10,10)...It will be between 0 and 90
degrees as all the points lie between them . Now we can just binary
search over this slope checking for the slope values . The slope and
set cardinality is also a monotonic function , so I guess binary
search approach will work , but the time taken will be nlog n . Please
correct me if I'm wrong .
#includeiostream
struct point
{
int x ;
int y ;};
using namespace std ;
// the given points
point p[100];
int main()
{
int n;
cinn;//number of points
for(int i=0;in;i++)
{
cinp[i].xp[i].y;
}
int high=90;
int low=0;
int mid;
//the line is supposed to start from 0,0
while(low=high)
{
mid=(high+low)/2;
if(haspoints(mid)0)
//upper has less points than below
low=mid+1;
else if(haspoints(mid)0)
//lower has more points than upper
high=mid-1;
else
{//we found our answer
coutmidendl;
return 0;
}
}
return 0;
}
On Jan 24, 9:30 am, Dave dave_and_da...@juno.com wrote:
Generalizing the problem, let there be n points (x_i, y_i), where x_i
and y_i are integers with 1 = x_i = A and 1 = y_i = B. A line
separating the points into two sets of equal cardinality can be found
as follows: Let Y = floor(B/2) + 0.5, and let X = -A * (B - Y). Find
the slopes of the lines from the point (X, Y) to each (x_i, y_i). The
point (X, Y) is constructed so that each of these slopes will be
distinct. Find the median M of these slopes. Then the line
y = M(x - X) + Y
will separate the points as desired. It will pass through exactly one
of the points if n is odd, and will miss all of the points if n is
even. This is O(n) in time and O(n) in space, where n is the number of
points.
Dave
On Jan 21, 11:45 pm, Divya Jain sweetdivya@gmail.com wrote:
assume the region to be (0,0) , (10,0), (0,10), (10,10)
On 22 January 2011 08:33, Dave dave_and_da...@juno.com wrote:
@Divya: The coordinates of the points are between 0 and 1 and are
integers. That can't be right.
Dave
On Jan 21, 1:46 pm, divya
[algogeeks] Re: Prime Numbers
Use a seive . it's complexity is O(nlog n) 1 million is 1*10^7 , this will run within time limit ... assuming u optimize ur code enough !! On Jan 26, 5:48 pm, juver++ avpostni...@gmail.com wrote: Generate primes numbers for the range 1..10^7 using sieve. Than apply sieve bigger range using these prime numbers. -- 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: Prime Numbers
@rahul, juver++,sankalp Though this can be solved using incrementing the range in sieve. But due to this incremental approach how much the efficiency can be improved, any guesses :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Prime Numbers
@above One million is 10^6. Problem wants 1 million of prime numbers. Not the prime numbers in range 1..1000. So, you should use two sieves. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find a way
@above How can you calculate dp[n][0] with above recursive eq?? On Jan 23, 5:40 pm, sankalp srivastava richi.sankalp1...@gmail.com wrote: @ above In that case , it will be a simple dynamic programming based recursion assuming the total distance one has to cover is n ; d[i][j]=minimum number of fuel stations to stop at in order to cross i stations and with j miles still to go . dp[n][0]= minimum number of fuel stations to stop at in order cross n stations and with 0 miles still to go (Assuming the nth stop coincides with the destination B .In case it does not , we can answer something like dp[n][p] , where p is the distance to go from nth stop to A) The recursion dp[i][k]= min(dp[i+1][k- distance b/w the ith and (i+1)th fuel station] , dp[i+1][k- distance +lk]+1)(lk= distance we can cover on this stop) base case dp[0][j]=0;(for each j )// we have to cover no more stations therefore On Jan 22, 9:40 pm, Divya Jain sweetdivya@gmail.com wrote: if u can take only a certain amount of fuel from a particaular station ie station xi can provide li amoutn of fuel.. then wat? On 22 January 2011 13:46, Terence technic@gmail.com wrote: Greedy-Approach. Refueling only when you have to. On 2011-1-22 15:59, snehal jain wrote: Suppose you want to travel from city A to city B by car, following a fixed route. Your car can travel m miles on a full tank of gas, and you have a map of the n gas stations on the route between A and B that gives the number of miles between each station. Design an algorithm to find a way to get from A to B without running out of gas that minimizes the total number of refueling stops, in O(n) time. -- 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%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Puzzle
9/.9 + 1 - 1 On Jan 26, 8:12 am, may.I.answer may.i.answ...@gmail.com wrote: You have four numbers 1 , 1 , 9 ,9 . Now using these four and operator + , - , * ,/ and parentheses(if required) your have to get 10. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find a line
@Sankalp: Whoa! My complaint is that the code you presented in
http://groups.google.com/group/algogeeks/msg/9ab2623efeb73311 requires
the line to go through (0,0). I presented an example where it is
impossible to divide the points with a line through (0,0). You
responded by saying that you would just move the origin to the
lowermost point. I reiterated that that would not do. Now you offer a
proof of some unstated proposition that, to me, seems unrelated to
whether you can always divide a set of points into two equal-sized
subsets by a line through the origin.
Dave
On Jan 26, 7:43 am, sankalp srivastava richi.sankalp1...@gmail.com
wrote:
@dave , There is a proof for it .
Let's say there is a point x0 , y0 .. and I claim that between any two
points ... x1,y1 and x2,y2 assuming they are non-collinear having a
line b/w them a line of some slope passes somewhere b/w them .This
collinearity does not affect our result .
Let's say a point x',y' divides this line into ratio m:n , this is the
point where this line is intersected by the line from x0 , y0 .. as
x1 ,y1 and x2,y2 are non-collinear , this point will always exist .
The slope of this line can be determined from the points x0,y0 and
x',y' , which is always real .hope this makes sense to u !!
On Jan 26, 7:11 am, Dave dave_and_da...@juno.com wrote:
@Sankalp: So what is your code? And what is the equation of the line?
As I said, you can't always use a line through the origin.
Dave
On Jan 25, 5:49 am, sankalp srivastava richi.sankalp1...@gmail.com
wrote:
@dave
In this case , I could just shift my origin to the lowermost point :)
On Jan 25, 10:14 am, Dave dave_and_da...@juno.com wrote:
@Sankalp: I wanted a point far enough outside the region that a line
from any point in the region could not contain any other point in the
region. There are several implications: 1) if the point is to the left
of the region, it can't have an integer y coordinate between 0 and B.
That is where the 0.5 comes from. Second, it seemed reasonable, but
not necessary, to put Y near the middle of the range [0, B]. Then I
just solved for an X that guaranteed that the slope of the line from
any point in the region to the point (X, Y) had slope m satisfying -1/
A m 1/A. Then a line through any point (x1,y) could not intersect
any point (x2,y-1) or (x3,y+1) within the region.
Regarding your algorithm: What does it do with A = B = 5 and points
{(1,1), (2,2), (3,3), (4,4), (1,4)}. This example shows that you can't
always use a line through (0,0).
Dave
On Jan 24, 10:15 pm, sankalp srivastava richi.sankalp1...@gmail.com
wrote:
@
Dave
How did you come up with this solution?
Also Y=floor(B)/2+.5 , X=-A*(B-Y) or X=-AB +AY or Y=X/A+B . this is
the equation of a line with slope 1/A and an intercept of B on Y
axis .I don't quite get this.!!Please elaborate .
Meanwhile , this is my approach .
The slope of the line wil be between the maximum's of the two points
i.e in the case of (10,0)..(10,10)...It will be between 0 and 90
degrees as all the points lie between them . Now we can just binary
search over this slope checking for the slope values . The slope and
set cardinality is also a monotonic function , so I guess binary
search approach will work , but the time taken will be nlog n . Please
correct me if I'm wrong .
#includeiostream
struct point
{
int x ;
int y ;};
using namespace std ;
// the given points
point p[100];
int main()
{
int n;
cinn;//number of points
for(int i=0;in;i++)
{
cinp[i].xp[i].y;
}
int high=90;
int low=0;
int mid;
//the line is supposed to start from 0,0
while(low=high)
{
mid=(high+low)/2;
if(haspoints(mid)0)
//upper has less points than below
low=mid+1;
else if(haspoints(mid)0)
//lower has more points than upper
high=mid-1;
else
{//we found our answer
coutmidendl;
return 0;
}
}
return 0;
}
On Jan 24, 9:30 am, Dave dave_and_da...@juno.com wrote:
Generalizing the problem, let there be n points (x_i, y_i), where
x_i
and y_i are integers with 1 = x_i = A and 1 = y_i = B. A line
separating the points into two sets of equal cardinality can be
found
as follows: Let Y = floor(B/2) + 0.5, and let X = -A * (B - Y). Find
the slopes of the lines from the point (X, Y) to each (x_i, y_i).
The
Re: [algogeeks] Re: Puzzle
@neha yeah you can use them as per your choice On Wed, Jan 26, 2011 at 9:31 PM, Dave dave_and_da...@juno.com wrote: 9/.9 + 1 - 1 On Jan 26, 8:12 am, may.I.answer may.i.answ...@gmail.com wrote: You have four numbers 1 , 1 , 9 ,9 . Now using these four and operator + , - , * ,/ and parentheses(if required) your have to get 10. -- 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] Puzzle
19-(9/1). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: merging 2 search trees
after adding the T' as right sub tree of largest element of T ,height of new tree should be h= (lg m + lg n)/2 perform left rotations starting from root till hth node in rightmost path of T On Jan 21, 7:41 pm, Divya Jain sweetdivya@gmail.com wrote: @ above height will not be balanced then On 21 January 2011 19:15, nishaanth nishaant...@gmail.com wrote: Find the node in T which is the maximum(which is either the root or the rightmost in the right subtree). After finding this node, just make the right child of this node point to the root of T'. Correct me if i am wrong On Fri, Jan 21, 2011 at 2:43 PM, snehal jain learner@gmail.comwrote: You are given two height balanced binary search trees T and T’, storing m and n elements respectively. Every element of tree T is smaller than every element of tree T’. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)? -- 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.
[algogeeks] Re: Largest BST in Binary Tree
Do the inoreder traversal of the tree ,find for maximum continous increasing sequence in that.find start and end of the elements in that sequence in the tree,move upto their common ancestoer which is BST On Jan 15, 6:32 pm, Decipher ankurseth...@gmail.com wrote: Find the largest BST in a binary tree ? What's the complexity of your algo (Amazon Question). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] number of brackets
How do we solve the problem http://www.spoj.pl/problems/SQRBR/ using dynamic programming? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: young tableaus
Hook Length Formula A formula for the number of Young tableaux associated with a given Young diagram. In each box, write the sum of one plus the number of boxes horizontally to the right and vertically below the box (the hook length). The number of tableaux is then n! divided by the product of all hook lengths. The NumberOfTableaux in the Mathematica package Combinatorica` function implements the hook length formula. http://mathworld.wolfram.com/HookLengthFormula.html On Jan 22, 2:04 pm, snehal jain learner@gmail.com wrote: . Given n distinct elements, how many Young tableaus can you make? i think the ans is 1!*2!*3!...sqrt(n)!*...*3!*2!*1! plz correct me if i 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 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] Puzzle
9 + 1 - ( 1 / 9 ) On Wed, Jan 26, 2011 at 10:29 PM, satish satish@gmail.com wrote: 19-(9/1). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- 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] Intel Question
I understand the algorithm, but what is the question? On Wed, Jan 26, 2011 at 10:10 AM, bittu shashank7andr...@gmail.com wrote: In order to make their newest microcontroller as cheap as possible, the ACME Widget Company designed it with a very simple cache. The processor is connected to a slow memory system that contains n bytes, numbered 0 to n - 1. The cache holds a copy of k of these bytes at a time, for fast access. It has a base address (referred to as base below), and it holds a copy of the bytes numbered base, base+1, ..., base+k-1. When a program reads a byte, the cache controller executes the following algorithm: 1. Find a new range of k bytes which contains the requested byte, such that the difference between the old and new base addresses is minimized. Note that if the requested byte was already in the cache, then the base address will not change. 2. Update the cache to the new range by reading from the memory system any bytes that are in the new range but not the old range, and discarding any bytes that were in the old range but not the new range. 3. Return the requested byte to the program. To analyze the performance of a program, you wish to know how many bytes are read from the memory system. The numbers of the bytes that the program reads are given in addresses, in the order that they are read. When the program starts, the base address is 0. Thanks Regards Shashank -- 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.
[algogeeks] Microsoft Written Test Questions
Hey all...Can anyone provide me with the recent (/most common) written test questions(or links ) of Microsoft IDC and Microsoft IT SDE positions...?? Thanks in advance.. Regards, Ankit. -- 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: Finding elements near the median
a) Find the median - O(n) b) remove the element and again find the median c) conitnue b until you get k-1 elements time complexity - kO(n) On Wed, Jan 26, 2011 at 9:55 PM, ritu ritugarg.c...@gmail.com wrote: solution is nice!!but How to keep track of k closet numbers? On Jan 23, 9:22 pm, ritesh riteshcseit...@gmail.com wrote: 1.) find x= median in o(n) 2.) subtract x from each number of the array 3.) find the k smallest number using o(n) algrithm On Jan 21, 4:04 am, snehal jain learner@gmail.com wrote: Given an unsorted array A of n distinct numbers and an integer k where 1 = k = n, design an algorithm that finds the k numbers in A that are closest in value to the median of A in O(n) time. -- 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.
