Re: [algogeeks] stack. Mid element in o(1)
@Prateek Jain : Middle element is nothing but a median ( i.e. middle element in sorted state) Soluton 1. Maintain a sorted stack using an extra stack , pop half of the elements or get the middle and if it's implemented using arrays fetch middle index value (top/2) T(N)= O(n^2) to maintain a sorted stack. Code : stackint SortedStack(Stackint s){ stackint r; int temp; while(!s.empty()) { temp=s.top(): s.pop(); while(!r.empty r.top()temp){ s.push(r.top()); r.pop(); } r.push(temp); } return r; } On Thu, May 23, 2013 at 2:38 PM, Prateek Jain prateek10011...@gmail.comwrote: I think there is no need for such a complex code. use length() method to get the size of the stack and return the middle element i.e. m=S.length() if(m is even) return arr[m/2] else return arr[m+1/2] it can be done in O(const) time On Thu, May 23, 2013 at 12:54 PM, Avi Dullu avi.du...@gmail.com wrote: Code is here http://codebin.org/view/30e9f2c0. Logic is made clear by the variable names. Idea is similar to the one which is used to build a queue using 2 stacks. On Wed, May 22, 2013 at 8:45 AM, MAC macatad...@gmail.com wrote: I think this is only possible if you make sure that at push you store the middle element with the top element as well .. this would mean push would cease to be o(1)become o(n) .. . or is there some other trick ? Veni Vedi Slumber ! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- Thanks Regards Nikhil Agarwal B.Tech. in Computer Science Engineering National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Interview Question based on histogram
Navin , your reply is correct. On Sat, May 19, 2012 at 10:36 PM, Gene gene.ress...@gmail.com wrote: The problem is not so clear, so you must make some assumptions to gat an answer. Since we have water, we have to envision the histogram in 3d. Then assume that the distance between histogram bars is 1 and bar i has height H[i], 0=iN, zero width and unit depth, and the base plane is at zero. Water is held in the pockets between bars. Then the pocket between H[i] and H[i+1] holds min(H[i],H[i+1]). To get the total, just sum these for 0 = i N-1 . On May 17, 1:57 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Imagine that you have an histogram stored in an array. Now imagine that you can pour water on top of your histogram. Describe an algorithm that computes the amount of water that remains trapped among the columns of the graph. Clearly on the edges the water would fall off. Use the language or the pseudocode you prefer. -- Thanks Regards Nikhil Agarwal B.Tech. in Computer Science Engineering National Institute Of Technology, Durgapur,Indiahttp://tech-nikk.blogspot.comhttp:// beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal B.Tech. in Computer Science Engineering National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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] Candy_splitting in GCJ
@Anurag What do you mean by sum of smallest...please explain.In 2 5 5 and 3 3 5 6 On Mon, May 9, 2011 at 12:10 AM, kumar anurag anurag.it.jo...@gmail.comwrote: find xor of all elements - if its equal to zeo then Case has solution otherwise NO for finding the soltuion just sort all the elements and find the (sum of all -sum of smallest).. On Sun, May 8, 2011 at 9:50 PM, Kunal Patil kp101...@gmail.com wrote: Can anybody tell me How to solve candy splitting problem appeared in Google Code Jam Qualification round? I know there is solution, if XOR of all elements comes to be zero. But i wasn't able to proceed from there as I couldn't think of way how to partition that elements. (I have read solutions from other contestants but as expected they are dirty for the one who doesn't know logic behind program) So plz help... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Kumar Anurag -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal B.Tech. in Computer Science Engineering National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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] If any one have algorithms for interviews by adnan aziz ebook... Please mail ...
I don't think soft copy is available.If anyone has please share it. On Tue, Mar 22, 2011 at 10:09 PM, Saravanan T mail2sarava...@gmail.comwrote: ++ On Tue, Mar 22, 2011 at 9:51 PM, Anurag atri anu.anurag@gmail.comwrote: and me too :) On Tue, Mar 22, 2011 at 9:28 PM, Nikhil Mishra mishra00...@gmail.comwrote: count me too On Tue, Mar 22, 2011 at 11:16 AM, kunal srivastav kunal.shrivas...@gmail.com wrote: plz send it to me too On Tue, Mar 22, 2011 at 11:14 AM, D.N.Vishwakarma@IITR deok...@gmail.com wrote: -- *With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department * -- 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. -- thezeitgeistmovement.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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Anurag Atri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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] Directory Structure
1.Create a Tree structure.Each node representing a directory under its respective parent for first N lines. 2.For M lines ,match the maximum possible path with the mth(m E M) directory path.Keep adding the nodes and increase the count. On Thu, Feb 17, 2011 at 6:23 PM, Akshata Sharma akshatasharm...@gmail.comwrote: On Unix computers, data is stored in directories. There is one root directory, and this might have several directories contained inside of it, each with di fferent names. These directories might have even more directories contained inside of them, and so on. A directory is uniquely identified by its name and its parent directory (the directory it is directly contained in). This is usually encoded in a path, which consists of several parts each preceded by a forward slash ('/'). The final part is the name of the directory, and everything else gives the path of its parent directory. For example, consider the path: /home/facebook/people This refers to the directory with name people in the directory described by /home/facebook, which in turn refers to the directory with name facebook in the directory described by the path /home. In this path, there is only one part, which means it refers to the directory with the name home in the root directory. To create a directory, you can use the mkdir command. You specify a path, and then mkdir wi ll create the directory described by that path, but only if the parent directory al ready exists. For example, i f you wanted to create the /home/facebook/people and /home/facebook/tech directories from scratch, you would need four commands: mkdir /home mkdir /home/facebook mkdir /home/facebook/people mkdir /home/facebook/tech Given the full set of directories already existing on your computer, and a set of new directories you want to create if they do not already exist, how many mkdir commands do you need to use? Input The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing two integers N and M, separated by a space. The next N lines each give the path of one directory that already exists on your computer. This list will include every directory already on your computer other than the root directory. (The root directory is on every computer, so there is no need to l ist it explicitly.) The next M lines each give the path of one directory that you want to create. Each of the paths in the input is formatted as in the problem statement above. Speci fically, a path consists of one or more lower - case alpha-numeric strings (i .e., strings containing only the symbols 'a'-'z' and '0'-'9'), each preceded by a single forward slash. These alpha-numeric strings are never empty. Output For each test case, output one l ine containing Case #x: y, where x is the case number (starting from 1) and y is the number of mkdir you need. Note: If a directory is listed as being on your computer, then its parent directory will also be listed, unless the parent is the root directory. INPUT 2 1 2 /chicken /chicken/egg /chicken 1 3 /a /a/b /a/c /b/b OUTPUT Case #1: 1 Case #2: 4 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: Implement Syntax Highlighter ......................Will Stuck!!!!!!!!!!
Either we can hash all the syntax and once we encounter them in an IDE we can change the color.This is good if number of syntax are few.If we have too many syntaxes suggested trie is a good idea.-O(N) complexity On Tue, Feb 22, 2011 at 11:09 AM, ritu ritugarg.c...@gmail.com wrote: whts the purpose of using trie? Simple array ll do ... Syntax highlighting part can be achived through regular automata. On Feb 20, 8:15 pm, vaibhav agrawal agrvaib...@gmail.com wrote: Use a Trie, which is a tree constructed using individual characters: b-red / a \ c-green using the above structure 'ab' keyword can be highlighted by red and 'ac' by green. On Sun, Feb 20, 2011 at 7:54 PM, bittu shashank7andr...@gmail.com wrote: Write an Algorithm to Implement the Syntax highlighter what will be the complexity of algo. Which data Structure You Will Use fro that then Write a Program to Implement the Syntax highlighter Constraints: As You Type in the Editor Your Input String color should change according to slandered syntax highlighter it should happens parallel e.g as you type color automatically should change means you don't have option to say that first i will search a pattern that i have to highlight using such as KMP any String Matching Algorithm then i will highlight that part ..no interviewer don't allow it... Again only thing to say that he is strict that it should happens simultaneously for example turbo C, Eclipse etc. Thanks Regards Shashank The 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.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: first larger element in unsorted array...
. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com algogeeks%2Bunsubscribe@googlegroups.com algogeeks%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 algogeeks%2Bunsubscribe@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+ unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: Invitation for CodeCracker'11 , Online Coding Competition
On Tue, Feb 1, 2011 at 7:42 PM, Umer Farooq the.um...@gmail.com wrote: Hello, it's really nice to see such a world wide online programming competition being organized after Google CJ. I have got a three questions 1- Can we use Dev C++ (which we have been using on windows platform). If we are allowed to use dev C++, then do we have to submit .cpp files only or .cpp and .dev files (both)? 2- Can we use java? Java is also a platform independent? 3- How many rounds are there? Will there be any on sight rounds? Check http://codecracker.in/faq.php?t=1296635105 .I hope this will solve all your confusions. On Tue, Feb 1, 2011 at 6:55 PM, Navin Agarwal navin0...@gmail.com wrote: @veenus : The contest is open to everyone, but only students are eligible for prizes. -- Navin Agarwal -- 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. -- Umer -- 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 Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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 duplicate element in an array
do you have the range of elements in the array? On Sun, Jan 16, 2011 at 8:51 AM, nphard nphard nphard.nph...@gmail.comwrote: Given an array of integers of size 'n' - consisting of 'n-2' unique integers and 1 integer with a duplicate, find the repeated element in O(n). Note: This is a converse of finding the unique element in an array consisting of duplicates - which can be solved with the XOR technique - but I am not sure if the same/similar technique can be applied here. -- 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 Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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 duplicate element in an array
So we have either time O(n) and space O(n) [hash and find if duplicate] O(nlogn) time O(1) space [sort and check]. I cannot give any XOR solution. On Sun, Jan 16, 2011 at 10:58 AM, nphard nphard nphard.nph...@gmail.comwrote: No. On Sat, Jan 15, 2011 at 11:06 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: do you have the range of elements in the array? On Sun, Jan 16, 2011 at 8:51 AM, nphard nphard nphard.nph...@gmail.comwrote: Given an array of integers of size 'n' - consisting of 'n-2' unique integers and 1 integer with a duplicate, find the repeated element in O(n). Note: This is a converse of finding the unique element in an array consisting of duplicates - which can be solved with the XOR technique - but I am not sure if the same/similar technique can be applied here. -- 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 Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: Longest increasing subsequence
I guess this has already been discussed here many times.Please check in the group archives. On Fri, Dec 31, 2010 at 2:14 PM, Anand anandut2...@gmail.com wrote: Longest increasing subsequence using segment tree with O(nlogn) http://anandtechblog.blogspot.com/2010/12/longest-increasing-subsequence-using.html On Thu, Dec 30, 2010 at 11:27 PM, juver++ avpostni...@gmail.com wrote: And of course simple binary search. -- 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 Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Longest increasing subsequence
https://groups.google.com/group/algogeeks/browse_thread/thread/b20cd8160a8e8f92?hl=en On Fri, Dec 31, 2010 at 10:18 PM, Anand anandut2...@gmail.com wrote: @Nikhil, I searched through the group for the answer but didn't find one so I stated again. On Fri, Dec 31, 2010 at 1:39 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: I guess this has already been discussed here many times.Please check in the group archives. On Fri, Dec 31, 2010 at 2:14 PM, Anand anandut2...@gmail.com wrote: Longest increasing subsequence using segment tree with O(nlogn) http://anandtechblog.blogspot.com/2010/12/longest-increasing-subsequence-using.html On Thu, Dec 30, 2010 at 11:27 PM, juver++ avpostni...@gmail.com wrote: And of course simple binary search. -- 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 Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Ranking Problem
@ankur can you hint your nlogn solution? On Thu, Dec 23, 2010 at 9:08 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: it is just like 0/1 knapsack problem with maximum weight of knapsack as 40. but in this case that is minimum that we have to calculate. calculate marks/time for every element . then try finding the elements with max value/time to fulfill the quota of marks. i dont know if this can be done in O(n) but it can be certainly done in nlogn. any other views ? On Thu, Dec 23, 2010 at 9:03 PM, Davin dkthar...@googlemail.com wrote: Thanks for reply. I am looking for O(n) for solution. Davin On Dec 23, 8:29 pm, snehal jain learner@gmail.com wrote: hint : use dp On Thu, Dec 23, 2010 at 8:30 PM, Davin dkthar...@googlemail.com wrote: Marks for Questions(1,6): {10,15,20,25,10,20} Time for Each Questions(1,6) : { 2, 4,3,4, 2,4} Passing Marks : 40 Out of 100 Find Questions with minimum time to pass the exam? On Dec 23, 7:04 pm, juver++ avpostni...@gmail.com wrote: Please clarify the problem statement. Provide example. From the first view problem seems to be unclear. -- 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. -- 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 Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: difference x
Divya and saurabh please post your working solution different from that of Bhupen's. On Thu, Dec 23, 2010 at 1:04 PM, jai gupta sayhelloto...@gmail.com wrote: make another array(B) from (A) with all elements negated now find one element from B and one from A whose sum is x or -x. This can ofcourse be done in O(n). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Ranking Problem
@Ankur Now its clear.:) On Thu, Dec 23, 2010 at 10:25 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: i will try to elaborate or rewrite tat part On Thu, Dec 23, 2010 at 10:25 PM, Ankur Khurana ankur.kkhur...@gmail.com wrote: wverything i mentioned above can be done in O(n) but sorting part is nlogn . so that is what i was saying. can you specify where i was not clear ? On Thu, Dec 23, 2010 at 9:22 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: @ankur can you hint your nlogn solution? On Thu, Dec 23, 2010 at 9:08 PM, Ankur Khurana ankur.kkhur...@gmail.com wrote: it is just like 0/1 knapsack problem with maximum weight of knapsack as 40. but in this case that is minimum that we have to calculate. calculate marks/time for every element . then try finding the elements with max value/time to fulfill the quota of marks. i dont know if this can be done in O(n) but it can be certainly done in nlogn. any other views ? On Thu, Dec 23, 2010 at 9:03 PM, Davin dkthar...@googlemail.com wrote: Thanks for reply. I am looking for O(n) for solution. Davin On Dec 23, 8:29 pm, snehal jain learner@gmail.com wrote: hint : use dp On Thu, Dec 23, 2010 at 8:30 PM, Davin dkthar...@googlemail.com wrote: Marks for Questions(1,6): {10,15,20,25,10,20} Time for Each Questions(1,6) : { 2, 4,3,4, 2,4} Passing Marks : 40 Out of 100 Find Questions with minimum time to pass the exam? On Dec 23, 7:04 pm, juver++ avpostni...@gmail.com wrote: Please clarify the problem statement. Provide example. From the first view problem seems to be unclear. -- 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. -- 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 Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the element with more than n/k occurrences
@saurabh : This solution is applicaiton to some special K .Not in general .sorry. On 12/22/10, Saurabh Koar saurabhkoar...@gmail.com wrote: @Nikhil: What if the array is 1 2 3 4 9 6 6 6 5 and k=3 ? -- 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] HP Question
IMHO 1.When books are nearly sorted : Insertion sort and can be incorporated with Shell sort technique @ O(n^1.5) provided number of books are in '000s 2.If number of books are huge in millons so its Heap sort will be better and taking the burden of coding build heap @ O(N) is justified.This gives O(NlogN) On Tue, Dec 21, 2010 at 6:49 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: insertion sort in IMHO On Tue, Dec 21, 2010 at 5:44 PM, bittu shashank7andr...@gmail.com wrote: Which one is the efficient sorting technique for arranging the books in a library? a) Bubble Sort b) Selection Sort c) Insertion Sort d) Heap Sort 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 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 Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the element with more than n/k occurrences
There can be a simple check. For any element to occur n/k times or more .It has occur atleast once in every subset of (n/k)+1 size.So we take a window of n/k+1 size and set the hash of every number equal to 1.These are the only probable elements which can occur n/k times or more. We move the window by n/k+1 step and increase the count of only those elements which occured in the first window.The element which has occured at least once in all the windows will be occuring atleast n/k times. Complexity: Total windows: =k, window size is (n/k)+1.Gives O(k*n/k)=O(n) time and space complexity = O((n/k)+1). On Tue, Dec 21, 2010 at 10:02 PM, Saurabh Koar saurabhkoar...@gmail.comwrote: Use count sort logic.It will be O(n). Bt space complexity matters there. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] array partition
@saurabh Sum of all the elements of subset. On Tue, Dec 21, 2010 at 11:42 PM, Saurabh Koar saurabhkoar...@gmail.comwrote: sum of both the sub set is minimum means sum of subset1+sum of subset = constant(=sum of the total array) When one decreases the other increases. Plzz give an example. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Minimum Triplet Distance
@Swapnil I got a counter example for my approach.By O(8) i mean O(c) c: a constant leading to O(1). On Tue, Dec 21, 2010 at 2:10 AM, Saurabh Koar saurabhkoar...@gmail.comwrote: @yq: Can u plzz inform what was ur approach/logic while deriving the condition that index will be increased of that array which contains minimum of three elements to get the desired ans? It will be very helpful.Thanks in advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Interview Question about Linked Lists
@Saurabh You used an extra pointer compared to shiva's code ,you can avoid that. :) On Mon, Dec 20, 2010 at 8:24 PM, Saurabh Koar saurabhkoar...@gmail.comwrote: @Rishi:I think Shiva's code is also fine.U can access the list easily by using down pointer in his code. Because he is assigning temp-down=temp2 and then he is making temp-fwd=NULL. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] fibonacci problem
You need to keep generating Fibonacci numbers until you meet the condition.Check for even valued term by using TERM%2==0 and sum up.Fibonacci series grows exponentially so n wont be very high.Take care that it doesn't overflow integer range. On Mon, Dec 20, 2010 at 8:36 PM, Shalini Sah shalinisah.luv4cod...@gmail.com wrote: Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Find the sum of all the even-valued terms in the sequence which do not exceed four million. I'm just a beginner..plz help. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Minimum Triplet Distance
On Mon, Dec 20, 2010 at 11:18 AM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: I have a solution.I cant prove the correctness but by intuition I can conclude.This is O(1) solution. As we have 3 sorted arrays A,B,C.So only first and last element of these 3 lists will be contributing for min/max tuple.Rest elements will be varying from that max to min. Suppose a={-1,-1,0} b={-1,3,7,8,10} c={0,1,2,3,4,5} so -1,0 of A ,-1,10 of B and 0,5 of C will be contributing .So we find all possible 8 tuples.In this case its for (x,y,z)=(-1,-1,0) giving a tuple 1 [max(-2,-1,1)] and so on. Find minimum of these tuples i.e. 1.That will be the answer.Solution if O(8) equilvalent to O(1).Please provide counter if you can find. On Mon, Dec 20, 2010 at 10:54 AM, yq Zhang zhangyunq...@gmail.com wrote: This question is equivalent to finding the minimum window contains 3 words in a document given the position of appearance of each word in the document by array A, B, C. This could be solved by a typical sliding window algorithm which is O(n). Thanks On Sun, Dec 19, 2010 at 9:06 PM, Saurabh Koar saurabhkoar...@gmail.comwrote: @yq: Plz explain your algorithm. On 12/20/10, yq Zhang zhangyunq...@gmail.com wrote: Are A, B, C sorted? If so, I believe there is a O(n1+n2+n3) solution for this question. Thanks On Sun, Dec 19, 2010 at 9:57 AM, Saurabh Koar saurabhkoar...@gmail.comwrote: You are given 3 integer arrays A, B and C of length n1, n2 and n3 respectively. All arrays are sorted. We define triplet of these 3 arrays as (x,y,z) where x is any integer from A, y from B and z from C. We define distance of triplet as maximum difference among triplet elements, i.e. Maximum of x – y, y – z or z – x. Write a program to find minimum triplet distance. (means there are n1*n2*n3 number of possible triplets are possible...among all triplets which triplet has minimum distance...Give only distance, but not triplet elements). Your program must be as much efficient as possible. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Minimum Triplet Distance
I have a solution.I cant prove the correctness but by intuition I can conclude.This is O(1) solution. As we have 3 sorted arrays A,B,C.So only first and last element of these 3 lists will be contributing for min/max tuple.Rest elements will be varying from that max to min. Suppose a={-1,-1,0} b={-1,3,7,8,10} c={0,1,2,3,4,5} so -1,0 of A ,-1,10 of B and 0,5 of C will be contributing .So we find all possible 8 tuples.In this case its for (x,y,z)=(-1,-1,0) giving a tuple 1 [max(-2,-1,1)] and so on. Find minimum of these tuples i.e. 1.That will be the answer.Solution if O(8) equilvalent to O(1).Please provide counter if you can find. On Mon, Dec 20, 2010 at 11:43 AM, yq Zhang zhangyunq...@gmail.com wrote: ok. Suppose you have 3 pointers i, j, k point to the element in A, B, C respectively. Initialize i = j =k = 0. for each step, you will compare A[i], B[j], C[k]. if A[i] is the smallest, i++ if B[j] is the smallest, j++ if C[k] is the smallest, k++ (this assumes numbers in A,B,C are unique, you should be able to eliminate this restriction by changing above logic a little bit.) for each step compute the current triple distance and keep the minimum. Thanks On Sun, Dec 19, 2010 at 9:51 PM, Saurabh Koar saurabhkoar...@gmail.comwrote: @yq: Heyy yq..I m not interested in what is equivalent to what and what is not not equivalent to what..I m interested to a specific optimized algorithm for the specific problem stated above.If u can figure out equivalence u can also devise the algorithm for the above problem.Nw would u please state that??or provide any link?? -- 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 Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Minimum Triplet Distance
I have a solution.I cant prove the correctness but by intuition I can conclude.This is O(1) solution. As we have 3 sorted arrays A,B,C.So only first and last element of these 3 lists will be contributing for min/max tuple.Rest elements will be varying from that max to min. Suppose a={-1,-1,0} b={-1,3,7,8,10} c={0,1,2,3,4,5} so -1,0 of A ,-1,10 of B and 0,5 of C will be contributing .So we find all possible 8 tuples.Find minimum of these tuples.That will be the answer.Solution if O(8) equilvalent to O(1).Please provide counter if you can find. On Mon, Dec 20, 2010 at 10:54 AM, yq Zhang zhangyunq...@gmail.com wrote: This question is equivalent to finding the minimum window contains 3 words in a document given the position of appearance of each word in the document by array A, B, C. This could be solved by a typical sliding window algorithm which is O(n). Thanks On Sun, Dec 19, 2010 at 9:06 PM, Saurabh Koar saurabhkoar...@gmail.comwrote: @yq: Plz explain your algorithm. On 12/20/10, yq Zhang zhangyunq...@gmail.com wrote: Are A, B, C sorted? If so, I believe there is a O(n1+n2+n3) solution for this question. Thanks On Sun, Dec 19, 2010 at 9:57 AM, Saurabh Koar saurabhkoar...@gmail.comwrote: You are given 3 integer arrays A, B and C of length n1, n2 and n3 respectively. All arrays are sorted. We define triplet of these 3 arrays as (x,y,z) where x is any integer from A, y from B and z from C. We define distance of triplet as maximum difference among triplet elements, i.e. Maximum of x – y, y – z or z – x. Write a program to find minimum triplet distance. (means there are n1*n2*n3 number of possible triplets are possible...among all triplets which triplet has minimum distance...Give only distance, but not triplet elements). Your program must be as much efficient as possible. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Interview Question
@gene: can you do dry run a test case: a[0]-a[n-1] 0 1 2 31 34 135 and if u c On Tue, Dec 7, 2010 at 8:55 AM, Gene gene.ress...@gmail.com wrote: I should have mentioned that this problem only makes sense if the array values must be unique. On Dec 6, 8:20 pm, Gene gene.ress...@gmail.com wrote: You guys are working too hard. Think about the sequence of numbers [ A[i] - i | i = 0,1,2,...n-1 ]. You are trying to probe this sequence to find the number of zeros. If you think about it for a while, you will see that this sequence is non-decreasing. It must be a segment of zero or more negative numbers followed by a segment of zero or more zeros followed by a segment of zero or more positive numbers. Therefore you can easily use two binary searches to find the index of the leftmost and rightmost zeros. This identifies all the elements where A[i]=i in O(2 log n) = O(log n) time. Of course if the searches fail, you have no elements at all where A[i]=i. On Dec 5, 9:46 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: @Divesh I have updated my algo and Array A[1,2,3.n] is sorted with unique elements.CALL FIND_EQUAL(A,1,n) int FIND_EQUAL(A,start,end) 1.Go to the middle element 2. If A[mid]mid) 3. if(start==mid) 4 return mid-1; 5return FIND_EQUAL(A,1,mid-1); 6 if(A[mid]=mid) 7if(mid==end) 8 return mid; 9return FIND_EQUAL(A,mid+1,end); On Sun, Dec 5, 2010 at 7:36 PM, coolfrog$ dixit.coolfrog.div...@gmail.comwrote: @Nikhil run you algo .. on test case index - 1 2 3 4 5 value - 1 2 3 4 5 ouput is mid+1= 3+1=4 but it should be 5... correct me if i am wrong... and u have assumed all are positive, hence base index should be 1 On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: If All the elements are unique and sorted in ascending order then we can design an algorithm for O(lgn) and all nos are positive. Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] FIND_EQUAL(A,start,end) 1.Go to the middle element 2.If A[mid]==mid) return mid+1; if(A[mid]mid) then FIND_EQUAL(A,start,mid-1) else FIND_EQUAL(A,mid+1,end) Runs in O(lgn) On Sun, Dec 5, 2010 at 12:20 PM, jai gupta sayhelloto...@gmail.com wrote: Any algorithm must in worst case lead to O(n) if the elements are not unique. Take the case: 1 2 3 4 5 6 as all the elements satisfy the condition of of key==index . we must go someway to each element. Hence O(n). This may be somehow made less if the element are given to be unique by using heap. -- 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile -- 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,Indiahttp://tech-nikk.blogspot.comhttp:// beta.freshersworld.com/communitie... -- 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
Re: [algogeeks] Re: Amazon Interview Question
@Divesh I have updated my algo and Array A[1,2,3.n] is sorted with unique elements.CALL FIND_EQUAL(A,1,n) int FIND_EQUAL(A,start,end) 1.Go to the middle element 2. If A[mid]mid) 3. if(start==mid) 4 return mid-1; 5return FIND_EQUAL(A,1,mid-1); 6 if(A[mid]=mid) 7if(mid==end) 8 return mid; 9return FIND_EQUAL(A,mid+1,end); On Sun, Dec 5, 2010 at 7:36 PM, coolfrog$ dixit.coolfrog.div...@gmail.comwrote: @Nikhil run you algo .. on test case index - 1 2 3 4 5 value - 1 2 3 4 5 ouput is mid+1= 3+1=4 but it should be 5... correct me if i am wrong... and u have assumed all are positive, hence base index should be 1 On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: If All the elements are unique and sorted in ascending order then we can design an algorithm for O(lgn) and all nos are positive. Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] FIND_EQUAL(A,start,end) 1.Go to the middle element 2.If A[mid]==mid) return mid+1; if(A[mid]mid) then FIND_EQUAL(A,start,mid-1) else FIND_EQUAL(A,mid+1,end) Runs in O(lgn) On Sun, Dec 5, 2010 at 12:20 PM, jai gupta sayhelloto...@gmail.comwrote: Any algorithm must in worst case lead to O(n) if the elements are not unique. Take the case: 1 2 3 4 5 6 as all the elements satisfy the condition of of key==index . we must go someway to each element. Hence O(n). This may be somehow made less if the element are given to be unique by using heap. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Interview Question
If All the elements are unique and sorted in ascending order then we can design an algorithm for O(lgn) and all nos are positive. Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] FIND_EQUAL(A,start,end) 1.Go to the middle element 2.If A[mid]==mid) return mid+1; if(A[mid]mid) then FIND_EQUAL(A,start,mid-1) else FIND_EQUAL(A,mid+1,end) Runs in O(lgn) On Sun, Dec 5, 2010 at 12:20 PM, jai gupta sayhelloto...@gmail.com wrote: Any algorithm must in worst case lead to O(n) if the elements are not unique. Take the case: 1 2 3 4 5 6 as all the elements satisfy the condition of of key==index . we must go someway to each element. Hence O(n). This may be somehow made less if the element are given to be unique by using heap. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Interview Question
@ashim please refer my post.I posted an o(lgn) algo.i.e. I am copying again below with an update If All the elements are unique and sorted in ascending order then we can design an algorithm for O(lgn) and all nos are positive. Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] FIND_EQUAL(A,start,end) 1.Go to the middle element 2.If A[mid]==mid||mid==0) { if(mid==0A[0]!=0) return 0; return mid+1; } if(A[mid]mid) then FIND_EQUAL(A,start,mid-1) else FIND_EQUAL(A,mid+1,end) Runs in O(lgn) On Sat, Dec 4, 2010 at 8:08 PM, Ashim Kapoor ashimkap...@gmail.com wrote: yaar I can use simple O(n) sweep to find out who all are equal, I think it can't be less than this On Sat, Dec 4, 2010 at 8:05 PM, Abioy Sun abioy@gmail.com wrote: 2010/12/4 ankit sablok ankit4...@gmail.com: as all the elements are sorted in the array make a min heap of the array elements and as min heap is a tree of keys querying a min heap or a binary search tree requires operations with time equal to the height of the tree which is log(n) hence time for querying a min heap I think you might be use a log(n) time to find out a element whose value is equal to some certain index, so the complexity could be n*log(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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Socket programming problem
I know it's odd to discuss assignments here but I am in a problem.The problem is on socket programming. Please check Link- http://www.scribd.com/doc/37550963/Assignment-3 If anybody has already solved this problem or can do it please reply in this thread. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] spoj problem - LASTDIG
check the source file size.It is talking about that. On Fri, Oct 15, 2010 at 1:55 PM, Vishnutej mylavarapu.vishnu...@gmail.comwrote: Hello everyone.. I tried solving the last digit problem in spoj but I'm getting an error that that the max limit is 700 bytes. What does this mean??..the problem specifies that the source limit is 700 B. I get the same thing when I try to solve KAMIL in challenge probs of SPOJ. Thanks in advance.. -Vishnutej Mylavarapu -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: missing 2 nums in an array
@Asquare : Please check the following example: Given: an array of numbers ranging from 1-n A[]= 3,3,5,2,1,2 As we encounter a number make the index of that number negative if it is positive. A[]= -3,-2,-5,2,-1,2 Since our index 4 and 6 are positive after the complete pass we conclude they are missing ones. Advantages: No extra space requirement time is O(n). On Tue, Oct 12, 2010 at 11:49 AM, Dave dave_and_da...@juno.com wrote: @Asquare: The two numbers that are not present at least once must be missing. Suppose that a and b are missing and c and d occur twice (with the possibility that c = d so that one number occurs three times). We are going to need four equations in the four unknowns a, b, c, and d. Here are four possible equations: 1. The sum of the numbers = n(n+1)/2 - a - b + c + d, 2. The sum of the squares of the numbers = n(n+1)(2n+1)/6 - a^2 - b^2 + c^2 + d^2, 3. The sum of the cubes of the numbers = n^2(n+1)^2/4 - a^3 - b^3 + c^3 + d^3, and 4. The sum of the fourth powers of the numbers = n(n+1)(2n+1) (3n^2+3n-1)30 - a^3 - b^3 + c^3 + d^3. This system of equations probably will take some fancy algebra to solve for a, b, c, and d. If it is permitted to rearrange the array, another way to do this is as follows using 1-based arrays (warning: untested pseudocode) for i = 1 to n j = i while a(j) not_equal j k = a(a(j)) a(j) = j j = k end_while end_for for i = 1 to n if a(i) not_equal i print i is missing end_if end_for This puts each number in its own spot in the array. Obviously missing numbers can't be in their own spots. Because each number is moved only once, the algorithm is O(n). @Bharath. Of course, n! will overflow quite quickly, and two equations isn't enough to determine the two missing numbers, since there are two more unknowns. Dave On Oct 11, 8:11 pm, bharath kannan bharathgo...@gmail.com wrote: sum of n elements from 1=n(n+1)/2 product from 1 to n=n! calculate dis.. sum=calculated sum-orig sum prod=calculated prod-orig prod with dis form quadratic eq and solve... hope this works... On Tue, Oct 12, 2010 at 12:29 AM, Asquare anshika.sp...@gmail.com wrote: Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers. I know of a solution using another array to store frequency of each number.. But this holds for than 2 nums also.. So Is there any other solution apart from this specific for 2 nums and of lesser complexity..?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: missing 2 nums in an array
On Tue, Oct 12, 2010 at 9:04 PM, vijay k kvija...@gmail.com wrote: @Nikhil, But your solution changes original array, which is not an acceptable method. Ya I know.But he didnt explicitly mention that.If we can't change the original array then this is not an acceptable algorithm. On Tue, Oct 12, 2010 at 6:18 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: @Asquare : Please check the following example: Given: an array of numbers ranging from 1-n A[]= 3,3,5,2,1,2 As we encounter a number make the index of that number negative if it is positive. A[]= -3,-2,-5,2,-1,2 Since our index 4 and 6 are positive after the complete pass we conclude they are missing ones. Advantages: No extra space requirement time is O(n). On Tue, Oct 12, 2010 at 11:49 AM, Dave dave_and_da...@juno.com wrote: @Asquare: The two numbers that are not present at least once must be missing. Suppose that a and b are missing and c and d occur twice (with the possibility that c = d so that one number occurs three times). We are going to need four equations in the four unknowns a, b, c, and d. Here are four possible equations: 1. The sum of the numbers = n(n+1)/2 - a - b + c + d, 2. The sum of the squares of the numbers = n(n+1)(2n+1)/6 - a^2 - b^2 + c^2 + d^2, 3. The sum of the cubes of the numbers = n^2(n+1)^2/4 - a^3 - b^3 + c^3 + d^3, and 4. The sum of the fourth powers of the numbers = n(n+1)(2n+1) (3n^2+3n-1)30 - a^3 - b^3 + c^3 + d^3. This system of equations probably will take some fancy algebra to solve for a, b, c, and d. If it is permitted to rearrange the array, another way to do this is as follows using 1-based arrays (warning: untested pseudocode) for i = 1 to n j = i while a(j) not_equal j k = a(a(j)) a(j) = j j = k end_while end_for for i = 1 to n if a(i) not_equal i print i is missing end_if end_for This puts each number in its own spot in the array. Obviously missing numbers can't be in their own spots. Because each number is moved only once, the algorithm is O(n). @Bharath. Of course, n! will overflow quite quickly, and two equations isn't enough to determine the two missing numbers, since there are two more unknowns. Dave On Oct 11, 8:11 pm, bharath kannan bharathgo...@gmail.com wrote: sum of n elements from 1=n(n+1)/2 product from 1 to n=n! calculate dis.. sum=calculated sum-orig sum prod=calculated prod-orig prod with dis form quadratic eq and solve... hope this works... On Tue, Oct 12, 2010 at 12:29 AM, Asquare anshika.sp...@gmail.com wrote: Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers. I know of a solution using another array to store frequency of each number.. But this holds for than 2 nums also.. So Is there any other solution apart from this specific for 2 nums and of lesser complexity..?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering
Re: [algogeeks] Help required
@ankur Please give me a proper link.I mean with hash after 4shared.com On Wed, Sep 22, 2010 at 11:26 AM, ankur aggarwal ankur.mast@gmail.comwrote: http://www.4shared.com/ check it.. On Wed, Sep 22, 2010 at 12:00 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Can anybody share his/her E-copy of An Introduction to algorithm by Udi manber.It's a great resource.If anybody has please share his E-copy.Thanks in advance. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal +91-7838289304 Software Engineer Slideshare Delhi INDIA. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Point lies inside or outside of triangle?
Method 1: Yes you can do by writing equation of 3 lines taking 2 points at a time and finding the sign with the third point. Suppose: ax+by+c=0 is your first line and (x,y) is the third point then find out the sign of the 3rd point satisfying it on the line. suppose this sign is S (for +ve) Similarly calculate for signs for other 2 lines. Now give a point(p,q) should give the same signs for all the 3 lines .If it gives the same sign for all the 3 lines that means it lies btwn all the 3 lines and all the 3 points.hence proved. Method 2: Area mentioned by praveen Method 3: http://en.wikipedia.org/wiki/Barycentric_coordinates_(mathematics)#Determining_if_a_point_is_inside_a_triangle You can choose the best method. On Mon, Sep 20, 2010 at 9:18 PM, Nicolae Titus nicolaetitu...@gmail.comwrote: there are some approximations involved there, it should be (area(big) - sum(area small)) error a better approach would be to find if the point is on the proper side of each edge take all the edges clockwise and calculate the sinus between each edge and the point, if they are all positive, the point is inside. Titus -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Help required
Can anybody share his/her E-copy of An Introduction to algorithm by Udi manber.It's a great resource.If anybody has please share his E-copy.Thanks in advance. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] LIS in nlogn
This has been discussed already.Please refer that post I have provided the actual code . On Sat, Sep 11, 2010 at 3:20 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: Can anybody tell me least increasing sub sequence in nlogn please try to provide code in 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Permutation of Array.
@chonku our desired result is 312313355 On Sat, Aug 21, 2010 at 7:30 PM, Chonku cho...@gmail.com wrote: Treat each number as string and make a trie out of it. For the first input [55,31,312,33], it would look like the following . /\ 3/ 5\ 1/ 3\5\ 31/ 2\ 33\ \55 312\ Once we have a trie, just print it out by based on the smallest number first. In this case, the print would go as follows. 313123355 On Sat, Aug 21, 2010 at 12:53 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Suppose the test is like: 21 71 217 after sorting and msb appending we get: 217 712 217 sort: 217 217 712 here we have 2 same elements 217 and 217 so we remove the 7 from the following logic: 1.if msb lsb we delete from the 2nd 217.else 2.we delete 7 from 1st one. so this gives 2121771 if it wud have been 41 200 412-412 200 412-200 412 412 here we will remove 2 from last one.giving 20041241 instead of 20041412 . On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: @Nikhil I am clear with your first 2 algos but not with the change u introduced ie., adding a check. please give a working example -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Permutation of Array.
I have corrected my msb algo please have a look. On Fri, Aug 20, 2010 at 10:59 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: On Fri, Aug 20, 2010 at 10:06 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: The solution for the above problem will be, 1.First convert all the smaller nos of by concatenating 9 at the end suppose 23,333 - (239,333) to the size of the maximum digit. 2.Sort the numbers; 3.remove the 9 from the nos where we had concatenated. 4.concatenate the string eg1. 55 31 312 33 - 559 319 312 339 sort- 312 319 339 559 remove 9s- 312 31 33 55 concatenate- 312313355 eg2 6 5 9 111- 699 599 999 111 sort- 111 599 699 999 remove 9s- 111 5 6 9 concatenate- 111569 any counter egs are welcome. Apologies ,this algorithm fails with 22 and 223 it gives 22322 instead of 3 which is wrong This is a working algo: Suppose set is : [22,223,24,247] 1.Sort the no.s 22 24 223 247 2.append the no. smaller in size with the msb of next no at the end : 222 242 223 247 3. sort 222 223 242 247 4.remove the appended bits: 22 223 24 247 Whenever we have two same nos in step 3 we have a check.(if msb of the no lsb then we shall remove from 2nd no. else we shall remove from 1st no. the appended digit.) On Fri, Aug 20, 2010 at 8:00 PM, Sakshi Handa sakshi.handa...@gmail.comwrote: @srinivas Following your method won't the answer be 31 312 33 55, which is not the smallest concatenated no. here? On Fri, Aug 20, 2010 at 3:05 AM, srinivas reddy srinivaseev...@gmail.com wrote: @Divya chandrasekhar your algorithm doesn't satisfy the condition like {130,11} we can give so many examples like this so the solution may come like this follow these rules: 1.imagine that all the numbers are equal length.(i.e;if the numbers are not equal lenth just add 0's at right hand side to the numbers which have less number of digits) 2.now arrange all these numbers in ascending order. 3.now remove the additionally added zero numbers from the numbers to get original numbers soon i wiil write the code On Fri, Aug 20, 2010 at 2:34 AM, Divya Chandrasekar divyac1...@gmail.com wrote: Never mind. This algo doesn't work properly. Apologies. On Thu, Aug 19, 2010 at 3:34 PM, Divya Chandrasekar divyac1...@gmail.com wrote: By the algo I gave : 1. Grouping - 3 digits - 111 1 digit - 6,5,9 2. Sorting within each bucket 3 digits - 111 1 digit - 5,6,9 3. Concatenation by descending order of number of digits, and increasing order within each digit bucket - Grouping would then be - 3 digit numbers in sorted order followed by 1 digit numbers in sorted order 111 5 6 9 Is there a number smaller than 111569 that can be formed with the set given? Also, I am not sure about the complexity of this algo. On Thu, Aug 19, 2010 at 1:56 PM, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: @Divya : Does the algo you gave work for the set { 6,5,9,111} ? I hope it doesnt... 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 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. -- Sakshi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http
Re: [algogeeks] Permutation of Array.
Suppose the test is like: 21 71 217 after sorting and msb appending we get: 217 712 217 sort: 217 217 712 here we have 2 same elements 217 and 217 so we remove the 7 from the following logic: 1.if msb lsb we delete from the 2nd 217.else 2.we delete 7 from 1st one. so this gives 2121771 if it wud have been 41 200 412-412 200 412-200 412 412 here we will remove 2 from last one.giving 20041241 instead of 20041412 . On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: @Nikhil I am clear with your first 2 algos but not with the change u introduced ie., adding a check. please give a working example -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
@marius Why are you xorring the indexes along with nos.?any special reason? On Sun, Aug 22, 2010 at 7:19 AM, UMarius mar...@aseara.ro wrote: @Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1} the output is correct. Maybe I didn't explain the steps correctly. This is the code: for(int i = 0 ; i arr1.Length ; i++) { arr1XOR ^= arr1[i]; arr1XOR ^= i; arr1SUM += arr1[i]; arr1MUL *= arr1[i]; } for (int i = 0; i arr2.Length; i++) { arr2XOR ^= arr2[i]; arr2XOR ^= i; arr2SUM += arr2[i]; arr2MUL *= arr2[i]; } if(arr1XOR == arr2XOR arr1SUM == arr2SUM arr1MUL == arr2MUL) { //SAME VALUES - IDENTICAL ARRAYS } else { //NOT IDENTICAL } Please correct me if I'm wrong. Marius. On Aug 22, 3:45 am, Dave dave_and_da...@juno.com wrote: @UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the original problem, you see that the question is not whether the arrays are identical (which is easily determined by simply comparing them element-by-element in O(n)), but whether they contain the same values, possibly in a different order. Dave On Aug 21, 11:01 am, UMarius mar...@aseara.ro wrote: What about this? 1. xor all elements of each array and their corresponding indexes sum all the elements of each array mul all elements of each array 2. if all results are the same then the arrays are identical Nice to meet you all, I just joined and this is my first post :) ... Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space?- 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Permutation of Array.
The solution for the above problem will be, 1.First convert all the smaller nos of by concatenating 9 at the end suppose 23,333 - (239,333) to the size of the maximum digit. 2.Sort the numbers; 3.remove the 9 from the nos where we had concatenated. 4.concatenate the string eg1. 55 31 312 33 - 559 319 312 339 sort- 312 319 339 559 remove 9s- 312 31 33 55 concatenate- 312313355 eg2 6 5 9 111- 699 599 999 111 sort- 111 599 699 999 remove 9s- 111 5 6 9 concatenate- 111569 any counter egs are welcome. On Fri, Aug 20, 2010 at 8:00 PM, Sakshi Handa sakshi.handa...@gmail.comwrote: @srinivas Following your method won't the answer be 31 312 33 55, which is not the smallest concatenated no. here? On Fri, Aug 20, 2010 at 3:05 AM, srinivas reddy srinivaseev...@gmail.comwrote: @Divya chandrasekhar your algorithm doesn't satisfy the condition like {130,11} we can give so many examples like this so the solution may come like this follow these rules: 1.imagine that all the numbers are equal length.(i.e;if the numbers are not equal lenth just add 0's at right hand side to the numbers which have less number of digits) 2.now arrange all these numbers in ascending order. 3.now remove the additionally added zero numbers from the numbers to get original numbers soon i wiil write the code On Fri, Aug 20, 2010 at 2:34 AM, Divya Chandrasekar divyac1...@gmail.com wrote: Never mind. This algo doesn't work properly. Apologies. On Thu, Aug 19, 2010 at 3:34 PM, Divya Chandrasekar divyac1...@gmail.com wrote: By the algo I gave : 1. Grouping - 3 digits - 111 1 digit - 6,5,9 2. Sorting within each bucket 3 digits - 111 1 digit - 5,6,9 3. Concatenation by descending order of number of digits, and increasing order within each digit bucket - Grouping would then be - 3 digit numbers in sorted order followed by 1 digit numbers in sorted order 111 5 6 9 Is there a number smaller than 111569 that can be formed with the set given? Also, I am not sure about the complexity of this algo. On Thu, Aug 19, 2010 at 1:56 PM, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: @Divya : Does the algo you gave work for the set { 6,5,9,111} ? I hope it doesnt... 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 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. -- Sakshi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Permutation of Array.
On Fri, Aug 20, 2010 at 10:06 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: The solution for the above problem will be, 1.First convert all the smaller nos of by concatenating 9 at the end suppose 23,333 - (239,333) to the size of the maximum digit. 2.Sort the numbers; 3.remove the 9 from the nos where we had concatenated. 4.concatenate the string eg1. 55 31 312 33 - 559 319 312 339 sort- 312 319 339 559 remove 9s- 312 31 33 55 concatenate- 312313355 eg2 6 5 9 111- 699 599 999 111 sort- 111 599 699 999 remove 9s- 111 5 6 9 concatenate- 111569 any counter egs are welcome. Apologies ,this algorithm fails with 22 and 223 it gives 22322 instead of 3 which is wrong This is a working algo: Suppose set is : [22,223,24,247] 1.Sort the no.s 22 24 223 247 2.append the no. smaller in size with the msb of next no at the end : 222 242 223 247 3. sort 222 223 242 247 4.remove the appended bits: 22 223 24 247 On Fri, Aug 20, 2010 at 8:00 PM, Sakshi Handa sakshi.handa...@gmail.comwrote: @srinivas Following your method won't the answer be 31 312 33 55, which is not the smallest concatenated no. here? On Fri, Aug 20, 2010 at 3:05 AM, srinivas reddy srinivaseev...@gmail.com wrote: @Divya chandrasekhar your algorithm doesn't satisfy the condition like {130,11} we can give so many examples like this so the solution may come like this follow these rules: 1.imagine that all the numbers are equal length.(i.e;if the numbers are not equal lenth just add 0's at right hand side to the numbers which have less number of digits) 2.now arrange all these numbers in ascending order. 3.now remove the additionally added zero numbers from the numbers to get original numbers soon i wiil write the code On Fri, Aug 20, 2010 at 2:34 AM, Divya Chandrasekar divyac1...@gmail.com wrote: Never mind. This algo doesn't work properly. Apologies. On Thu, Aug 19, 2010 at 3:34 PM, Divya Chandrasekar divyac1...@gmail.com wrote: By the algo I gave : 1. Grouping - 3 digits - 111 1 digit - 6,5,9 2. Sorting within each bucket 3 digits - 111 1 digit - 5,6,9 3. Concatenation by descending order of number of digits, and increasing order within each digit bucket - Grouping would then be - 3 digit numbers in sorted order followed by 1 digit numbers in sorted order 111 5 6 9 Is there a number smaller than 111569 that can be formed with the set given? Also, I am not sure about the complexity of this algo. On Thu, Aug 19, 2010 at 1:56 PM, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: @Divya : Does the algo you gave work for the set { 6,5,9,111} ? I hope it doesnt... 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 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. -- Sakshi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit
Re: [algogeeks] Array Problem
On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} There is an obvious check. N1==N2 at the beginning. On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
@saikat ur algo fails with the test case a1=-2,-2 and a2=2,2 On Thu, Aug 19, 2010 at 10:22 PM, Saikat Debnath saikat@gmail.comwrote: 1. Add sum of squares of all numbers in respective groups, if equal goto step 2. 2. XOR all elements of both groups, (if==0) elements are same. On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote: @Nikhil Jindal: What you say is true for 2 numbers, but not for more than 2. 1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36. Dave On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote: Nikhil's algo is correct if the following is always true: Given: x + y = S, x * y = M and x' + y' = S', x' * y' = M' If: S' = S and M' = M, then x = x' and y = y' i.e for given sum and product, the elements are unique. On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} . S1=0;S2=0; M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected) M1!=M2 there fore it is correct. Code: bool check_arrays(vectorint v1,vectorint v2){ if(v1.size()!=v2.size()) return 0; if(v1.size()==0v2.size()==0) return 1; int sum,product1,product2; sum=0;product1=1;product2=1; for(int i=0;iv1.size();i++){ sum+=v1[i]; sum-=v2[i]; if(v1[i]!=0) product1*=v1[i]; if(v2[i]!=0) product2*=v2[i]; } if(sum==0(product1==product2)) return 1; return 0; } On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote: @Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B = (0,2,-3). I was thinking ones-complement arithmetic instead of twos- complement. Dave On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote: @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2). Dave On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote: add one more thing to the solution suggested by nikhil i.e;count the number of elements in array 1 and number of elements in array2 if these two values are equal then after follow the algo proposed by nikhil agarwal.. On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Chonku: Your algo seems to fail with following input. Arr1[]= {1,6} Arr2[]={7} On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com algogeeks%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 algogeeks%2bunsubscr...@googlegroups .com algogeeks
Re: [algogeeks] Brent's algorithm
On Wed, Aug 18, 2010 at 5:12 AM, jayapriya surendran priya7...@gmail.comwrote: hi..i wanna know what is brent's algorithm n whether it can be used to detect loops in linked list.If yes..is it better than Floyd's cycle finding algo? Brent's algorithm is also called Tortoise and Rabbit algorithm.It has been proved by brent's that it is 36% faster than floyd's loop detection algorithm. bool cycle_check(LL list){ rabbit=list.top; tortoise=list.top; step_val=0; step_limit=2; while(1){ if(rabbit-next==NULL) return 0; rabbit=rabbit-next; step_val+=1; if(rabbit==tortoise) return 1; if(step_val==step_limit){ step_val=0; step_limit*=2; tortoise=rabbit; } }//while ends }//func ends. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Array Problem
Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Median of two arrays..
@maxim . my algo is for array of equal sizes.Sorry I didn't notice the unequal thing. On Tue, Aug 17, 2010 at 10:09 AM, Maxim Mercury maxim.merc...@gmail.comwrote: above algo isnt handling unequal length arrays, On Aug 13, 10:06 pm, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Check this code int med1,med2; void func(int a[], int x1, int x2, int b[], int y1, int y2){ int midx,midy; if((y2-y1+1)==2) { med1=max(a[x1],b[y1]); med2=min(a[x2],b[y2]); return;} midx=(x1+x2)/2; midy=(y1+y2)/2; if(a[midx]b[midy]){ x2=x2-(midy-y1); y1=midy; }else{y2=y2-(midx-x1); x1=midx;} func(a,x1,x2,b,y1,y2); } med1 and med2 are two medians. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Median of two arrays..
Check this code int med1,med2; void func(int a[], int x1, int x2, int b[], int y1, int y2){ int midx,midy; if((y2-y1+1)==2) { med1=max(a[x1],b[y1]); med2=min(a[x2],b[y2]); return; } midx=(x1+x2)/2; midy=(y1+y2)/2; if(a[midx]b[midy]){ x2=x2-(midy-y1); y1=midy; }else{y2=y2-(midx-x1); x1=midx; } func(a,x1,x2,b,y1,y2); } med1 and med2 are two medians. On Fri, Aug 13, 2010 at 6:32 PM, Raj N rajn...@gmail.com wrote: Can someone tell me what do you mean by median of 2 arrays ? Is it that the sorted arrays are merged and finding the median of resulting one? On Fri, Aug 13, 2010 at 1:32 AM, sachin sachin_mi...@yahoo.co.in wrote: If the ranges of the arrays are 1..n 1..m, then we can solve it this way if ((m+n)1){ we can go with the method same as rahul patil's and in the condition we can use count=(m+n)/2+1, the median will be stored in res. } else{ we can go with the method same as rahul patil's and in the condition we can use count=(m+n)/2+1 and the median in this case will be the average of elements at count (m+n)/2 at count (m+n)/2+1.So, we will have to store the last element in this case. } On Aug 11, 5:25 pm, rahul patil rahul.deshmukhpa...@gmail.com wrote: is there any time complexity? the also can be like this char *res; char *ptr1 =arr1; char *ptr2 =arr2; int count =0, n= len(arr1) ,m=len(arr2); while(1){ while(*ptr1 *ptr2){ ptr2++; count ++; if( count == (n+m)/2 ){ res=ptr1; break out of outer while loop; } } while(*ptr1 *ptr2){ ptr1++; count ++; if( count == (n+m)/2 ){ res=ptr2; break out of outer while loop; } } } On Aug 6, 7:20 pm, Manjunath Manohar manjunath.n...@gmail.com wrote: will this work in two sorted arrays of equal length.. -- 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 Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
There few errors in your code rest is fine.I have updated in line 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);//precedence of addition operator is greater then a terenery } 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; //updated.. while(ptr1-next) ptr1=ptr1-next ptr1-next=ptr2; 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Entryinto elite companies
@sharad, Well said.It can be summarized as kamyaab hone ke liye nahi..kabil hone ke liye padho.. . On Wed, Jul 21, 2010 at 11:45 AM, sharad kumar aryansmit3...@gmail.com wrote: @aparichit:c brother u need to live,breathe enjoy algorithms not studyU shldnt limit ur choice that just because you want to get placed in MS/Google you want to do coding.You need to pursue coding as a career .you need to do it for your self not for entering the company.even if you dont make into MS atleast feel that you are specialI've knw guys here in US who havent attended schools but have startedc their own firms which are listed in nasdaq which take on MS/Google.in short i would like to say gain knwledge and pursue excellence.. On Wed, Jul 21, 2010 at 10:49 AM, aparichith vineelyalamar...@gmail.com wrote: Guys, Can some one tell me how to enter into elite companies like Yahoo, Microsoft,Symantec ,Amazon etc.. I did my engineering in IT in India , but I 'm not that phodu in coding etc -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: microsoft.
@saurav The answer must be 2 because it is the first repeating element . We can find the 1st repeating element by creating a hash map of 1st k+1 elements because we can have at most k distinct elements and after that a digit should repeat. eg. N=10; k=5; so the array can be 1 2 3 4 5 1. therefore we can get the 1st repeating element with k+1 elements. T(n)=O(k+1)=O(k) On Thu, Jul 8, 2010 at 1:03 AM, souravsain souravs...@gmail.com wrote: @sharad When you say you want first repeating element, do u mean first in the sense in which numbers are layed out in the array (i mean moving from left to right in the array, the first element, =K, that is repeating) or the first smallest element that is repeating? for example in the given example 2,4,3,6,7,1,2,5,1,2 which has 10 elements, if your answer 2 or 1? Sourav On Jul 7, 4:52 pm, Satya satya...@gmail.com wrote: Use selection algorithm, a variation of quicksort algorithm which is in place.http://en.wikipedia.org/wiki/Selection_algorithm . Satya On Wed, Jul 7, 2010 at 1:45 PM, sharad kumar sharad20073...@gmail.comwrote: ya i want inplace soln -- 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.- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Integer from number in words
On Sun, Jun 20, 2010 at 6:34 PM, debajyotisarma sarma.debajy...@gmail.comwrote: How to device an algorithm for converting the number given in words to an int? Eg: i/p : ninety thousand two hundred fourth three o/p: 90243 even the number can be very big ... in million or billion ... Here i/p should be read from left to right word by word.Each keyword and its value must be stored prehand 1-1 mapping.eg. ninety=90 ,thousand =1000 and all these keyword values are multiplied and added(90*1000+2*100+43=90243) and number is generated. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
This question has already been discussed here.There are 4-5 methods to do this ,best is 'Moore voting algorithm' . refer: http://geeksforgeeks.org/?p=503 On Mon, May 31, 2010 at 10:01 PM, souravsain souravs...@gmail.com wrote: Hi All This is my first post to this community and so am exited. The problem is to find the no. that has maximum frequency in an array (size n) of integers. The approach to use a hash table, itereate through array (O(n)) and keep inserting into hash table (O(1)) and then scan the hash table (O(n)) to find entry with max frequency is known. Not to mention that one more iteration is needed to find the maximum value in array so as to decide the sixe of hash table (to keep insertion perfectly O(N). I am looking for a solution which is having O(1) space complexity. The best I can think of is to sort the array in O(nlogn) and then make a pass through the array O(n) to find one with max frequency. So here time complexity is O(nlogn + n). Can we have a better solution? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Can you solve this?
This problem is like 2 processor job scheduling problem ,We may get an optimal solution for different instances using different algorithm apart from brute force.Whereas Brute force covers all possible subsets but may take years to complete if N is large. above algo fails in the following example. Eg. 2 2 2 3 3 above algo gives: T1: 2 2 3 =7 T2: 2 3 =5 But closest distribution is T1=2 2 2=6 T2 3 3=6 On Mon, May 31, 2010 at 6:24 AM, sharad kumar aryansmit3...@gmail.comwrote: @abhishek:i meant after sorting split the array into 2 part each with equal sum On Sun, May 30, 2010 at 11:45 PM, Abhishek Sharma jkabhishe...@gmail.comwrote: @sharad: if you find the subarrays of equal sum then the number of players might differ in the team... also can you tell me how will you do that..according to me time cmoplexity will be higher.. According to me: sort the palyers based on skill points (O(nlogn) --mergesort) then assign the players one by one to each team (O(n)) Ex: Consider 10 players to be assigned to two teams. skill points: 12, 12, 7, 8, 15, 19, 11, 14, 5, 10. Ans: after sorting: 5, 7, 8, 10, 11, 12, 12, 14, 15, 19. Team1: 5, 8, 12, 14, 19 Team2: 7, 11,12,15. This is not exactly even but i think is the closest approach. correct me if I am wrong.. Regards, Abhishek On Sun, May 30, 2010 at 8:21 PM, sharad kumar aryansmit3...@gmail.comwrote: sort the players based on skill point and get the subarray of equal sum.. On Sun, May 30, 2010 at 6:58 PM, Veer Sharma thisisv...@rediffmail.comwrote: Hi Friends, This is my first post to this forum. A Hi to all of you and here is my first problem... Giiven int n, the total number of players and their skill-point. Distribute the players on 2 evenly balanced teams. Lets see who gives the best solution (least space complexity / least time complexity or both...) -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Longest Increasing Subsequence in O(nlogn)
Check: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence On Sat, May 29, 2010 at 4:15 AM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: A hint from Introduction to algorithms on this problem: Observe that the last element of a candidate subsequence of length *i* is at least as large as the last element of a candidate subsequence of length *i-1. *Maintain candidate subsequences by linking them through the input sequence The attached file is a tutorial from train.usaco.org which includes 3 approaches to the problem and explains them with some examples. I hope it would help! On Fri, May 28, 2010 at 7:44 PM, amit amitjaspal...@gmail.com wrote: Hi , Can anyone plz explain this algorithm taking some example. I read this on wiki but could'nt get how binary search was working. -- 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 Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. #include vector using namespace std; /* Finds longest strictly increasing subsequence. O(n log k) algorithm. */ void find_lis(vectorint a, vectorint b) { vectorint p(a.size()); int u, v; if (a.empty()) return; b.push_back(0); for (size_t i = 1; i a.size(); i++) { if (a[b.back()] a[i]) { p[i] = b.back(); b.push_back(i); continue; } for (u = 0, v = b.size()-1; u v;) { int c = (u + v) / 2; if (a[b[c]] a[i]) u=c+1; else v=c; } if (a[i] a[b[u]]) { if (u 0) p[i] = b[u-1]; b[u] = i; } } for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v; } /* Example of usage: */ #include cstdio int main() { int a[] = { 9,10,11,12,1,2,3,4,5,6,7 }; vectorint seq(a, a+sizeof(a)/sizeof(a[0])); vectorint lis; find_lis(seq, lis); for (size_t i = 0; i lis.size(); i++) printf(%d , seq[lis[i]]); printf(\n); return 0; }
Re: [algogeeks] Re: median of a bst
We can try rotation too. 1.We iterate rotating of the left/right sub-tree having greater number of nodes. 2. if number of keys are :- ODD- Equal number of nodes exist on both left and rt subtree of root .Key at root is the median of the BST.. EVEN-left subtree should have 1 less node than right.Both root node and a node just below on the rt. sub tree will be the median. On Sat, May 15, 2010 at 2:31 AM, W Karas wka...@yahoo.com wrote: On May 14, 3:32 am, divya sweetdivya@gmail.com wrote: please suggest an efficient algo to find the median of a bst A recursive solution: unsigned count(node_handle_t base) { return(base == null ? 0 : count(left(base)) + 1 + count(right(base))); } val_t max(node_handle_t base) { return(right(base) == null ? val(base) : max(right(base))); } val_t min(node_handle_t base) { return(left(base) == null ? val(base) : min(left(base))); } val_t median_help( node_handle_t base, unsigned low_count, unsigned high_count) { unsigned left_count, right_count; left_count = count(left(base)); right_count = count(right(base)); low_count += left_count; high_count += right_count; if (low_count == high_count) return(val(base)); if (low_count == (high_count + 1)) return((val(base) + max(left(base))) / 2); if (high_count == (low_count + 1)) return((val(base) + min(right(base))) / 2); if (low_count high_count) return(median_help(left(base), low_count - left_count, high_count + 1)); /* low_count high_count */ return(median_help(right(base), low_count + 1, high_count - right_count)); } val_t median(node_handle_t root) { return(median_help(root, 0, 0)); } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- 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] 400!
...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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. -- There are two kinds of people. Those who care for others and The others -- 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. -- Siddharth Srivastava Human Knowledge is for all -- 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. -- There are two kinds of people. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. 329.png
Re: [algogeeks] Build BST from binary tree without extra space
On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.comwrote: How to build BST from binary tree in place i.e without extra space ?? Are you looking for: http://discuss.joelonsoftware.com/default.asp?interview.11.781167.4 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Junior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] First k smallest elements
Hey rohit.You were referring to Binary tree.Search keyword was missing.Because rotation makes no sense in binary tree.Please note binary tree and BST are different. On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Read the slides i uploaded. They explain what rotation does in a BST. Also you might like to refer to Red Black Trees in CLRS that chapter explains rotations. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: but still the binary tree solution is of more practical use.i will explain the solution once i reach my comp On 4/11/10, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Time complexity is O(n log n). But the last solution I gave has O(n). What did u not understand abt thesolution @Rohit Please explain how that Binary tree solution works. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee dona.1...@gmail.com wrote: On 11 April 2010 10:46, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Construct a binary tree from the data (maintain the size of subtree under each node). Do rotations till the left subtree does not have size k. Rotation is a constant time operation. Please prove the correctness of your algorithm with the time complexity -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.com wrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above procedure for all n elements in an array At last you will get k smallest elements and root is kth smallest element in the array this is O(nlogk) CHERUVU JAANU REDDY M.Tech in CSIS On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.com wrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So any suggestions ? Thanks On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond patidarc...@gmail.com wrote: there are better solution of O(n) are posted in the thread... [?]. using order statices On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3) Return the smallest of temp[] Time Complexity: O((n-k)*k). try it ..for this problem[?] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr
Re: [algogeeks] First k smallest elements
On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: are yaar... i meant BST... i thought that was obvious ! sry if i confused you @rohit It's ok.Actually in this group people come up with very different and non-common solutions so its risky to take things 'obviously'. Rotation algo has a complexity of O(nlogn)[for constructing a BST] +O(n) [for rotating n times]=O(nlogn) . Till now best algo we have is using heaps which give rise to complexity = O(n+klogn) Please pass on algos having better runtime complexity. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Hey rohit.You were referring to Binary tree.Search keyword was missing.Because rotation makes no sense in binary tree.Please note binary tree and BST are different. On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Read the slides i uploaded. They explain what rotation does in a BST. Also you might like to refer to Red Black Trees in CLRS that chapter explains rotations. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: but still the binary tree solution is of more practical use.i will explain the solution once i reach my comp On 4/11/10, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Time complexity is O(n log n). But the last solution I gave has O(n). What did u not understand abt thesolution @Rohit Please explain how that Binary tree solution works. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee dona.1...@gmail.com wrote: On 11 April 2010 10:46, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Construct a binary tree from the data (maintain the size of subtree under each node). Do rotations till the left subtree does not have size k. Rotation is a constant time operation. Please prove the correctness of your algorithm with the time complexity -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.com wrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above procedure for all n elements in an array At last you will get k smallest elements and root is kth smallest element in the array this is O(nlogk) CHERUVU JAANU REDDY M.Tech in CSIS On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.com wrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So any suggestions ? Thanks On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond patidarc...@gmail.com wrote: there are better solution of O(n) are posted in the thread...[?]. using order statices On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3) Return the smallest of temp[] Time Complexity: O((n-k)*k). try it ..for this problem[?] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr
Re: [algogeeks] First k smallest elements
Oh yes.Median of medians selection algo is with the best complexity O(n). anythin else? On Mon, Apr 12, 2010 at 7:51 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Find the kth element using order statistics - O(n)As far as i know , u will have to use median of medians selection algorithm for this... Rest is fine.. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Apr 12, 2010 at 3:20 PM, souri datta souri.isthe...@gmail.comwrote: Steps: 1. Find the kth element using order statistics - O(n) 2. In one pass over the array, get all the elems less than the kth element. Let me know if this is not correct. On Mon, Apr 12, 2010 at 1:57 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: I have already given an O(n) solution. See above ! The BST solution is O(nlogn) but is practically more nice. :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Mon, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: are yaar... i meant BST... i thought that was obvious ! sry if i confused you @rohit It's ok.Actually in this group people come up with very different and non-common solutions so its risky to take things 'obviously'. Rotation algo has a complexity of O(nlogn)[for constructing a BST] +O(n) [for rotating n times]=O(nlogn) . Till now best algo we have is using heaps which give rise to complexity = O(n+klogn) Please pass on algos having better runtime complexity. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Hey rohit.You were referring to Binary tree.Search keyword was missing.Because rotation makes no sense in binary tree.Please note binary tree and BST are different. On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Read the slides i uploaded. They explain what rotation does in a BST. Also you might like to refer to Red Black Trees in CLRS that chapter explains rotations. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: but still the binary tree solution is of more practical use.i will explain the solution once i reach my comp On 4/11/10, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Time complexity is O(n log n). But the last solution I gave has O(n). What did u not understand abt thesolution @Rohit Please explain how that Binary tree solution works. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee dona.1...@gmail.com wrote: On 11 April 2010 10:46, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Construct a binary tree from the data (maintain the size of subtree under each node). Do rotations till the left subtree does not have size k. Rotation is a constant time operation. Please prove the correctness of your algorithm with the time complexity -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.com wrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above
Re: [algogeeks] First k smallest elements
are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.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 Nikhil Agarwal Junior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. 338.gif361.gif
Re: [algogeeks] Divide and Conquer problem
Following are the recurrences: T(n)=2T(n/2)+1 T(2)=1 T(n)=n-1 =O(n) 1 is added because winner of both the sides will compete at most 1 once. for Time table u can form a tree x1 x2 x3 x4 x5 \ / \ / / x1 x3 / \ \ / \ x5 \ / x1 Here are four matches and team nos =5 On Wed, Apr 7, 2010 at 12:20 PM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Can any one help me with this problem Its a divide and conquer problem where, there are n teams and each team plays each opponent only once. And each team plays exactly once every day. If n is the power of 2, I need to construct a timetable allowing the tournament to finish in n-1 days... Any help would be appreciated.. 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. -- Thanks Regards Nikhil Agarwal Junior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] First k smallest elements
There are about 5-6 solutions mentioned at http://geeksforgeeks.org/forum/topic/kth-largest-element anyone having a different and more efficient algorithm please come up. On Sun, Mar 28, 2010 at 11:44 AM, sharad kumar aryansmit3...@gmail.comwrote: i feel heapify the array to get a min heap and keep extracting root k times.any further optimisations??? On Sun, Mar 28, 2010 at 11:33 AM, Priyanka Chatterjee dona.1...@gmail.com wrote: Design the most efficient algorithm to find the first k smallest elements in an array ? -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Junior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Interview question.Provide the solution as per the constraints.
@all: you cannot traverse through the tree recursively because it has been mentioned that no extra memory (in recursive calls or stack ) is allowed. On Mon, Mar 8, 2010 at 8:42 AM, gaurav gupta 1989.gau...@googlemail.comwrote: Median of BST means : median of Sorted array of elements? is it? Convert BST into Hight Balance Search Tree then root node will be your median. On Sun, Mar 7, 2010 at 2:42 AM, Nik_nitdgp nikhil.bhoja...@gmail.comwrote: Given a BST (Binary search Tree) how will you find median in that? Constraints: -No extra memory. Algorithm should be efficient in terms of complexity. Write a solid secure code for it. No extra memory--u cannot use stacks to avoid recursion. No static,global--u cannot use recursion and keep track of the elements visited so far in inorder. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Junior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Interview question.Provide the solution as per the constraints.
On Mon, Mar 8, 2010 at 5:04 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: can we assume that we have the sizes of subtree rooted at all nodes in our datastructure.? Yeah,that can be lead to 1 solution.well done. -Rohit On Mon, Mar 8, 2010 at 5:02 PM, sharad kumar aryansmit3...@gmail.comwrote: @gaurav :ur sol u mean like tk the mem loc for each node and make it as array ? On Mon, Mar 8, 2010 at 8:42 AM, gaurav gupta 1989.gau...@googlemail.comwrote: Median of BST means : median of Sorted array of elements? is it? Convert BST into Hight Balance Search Tree then root node will be your median. On Sun, Mar 7, 2010 at 2:42 AM, Nik_nitdgp nikhil.bhoja...@gmail.comwrote: Given a BST (Binary search Tree) how will you find median in that? Constraints: -No extra memory. Algorithm should be efficient in terms of complexity. Write a solid secure code for it. No extra memory--u cannot use stacks to avoid recursion. No static,global--u cannot use recursion and keep track of the elements visited so far in inorder. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Junior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.