Re: [algogeeks] finding anagrams in a list of words
@ashish: your key creation method would need additional space for converting it into form a2b2c1 in O(n) time . as we all know that a word length is not very large .say on avg 15 letters . so we can use counting sort which is also O(n). On Sun, May 13, 2012 at 6:05 AM, Ashish Goel ashg...@gmail.com wrote: while making a multimap is a great idea, instead of sorting the word, the key could be formed by using a hash seprately as char and its count as pair and then making the string like a2b4c1 as the key, the key would form in O(n) too. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, May 12, 2012 at 1:57 PM, atul anand atul.87fri...@gmail.comwrote: given the list of words... what you can do is the following :- now take first word from the list.. sort this word in alphabetical order...for eg str=bcda --- sort , we get str=abcd now considering this sorted word as a key(abcd) , insert original word (bcda as value) into the hash table ( hash table with chaining ) similarly do it for other words. now given a word , you just need to sort this given word and use it as a key to fetch all anagram. On Fri, May 11, 2012 at 5:24 PM, mayur mayursa...@gmail.com wrote: Hi all, I am stuck with a question for a long time...can someone provide the best algorithm for this.. Question).. find all the anagrams in a list of words. The algorithm should be efficient as the list can be very large. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/c4cSIMcBYLEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] finding anagrams in a list of words
Yup i agree with Atul's solution. Just explaining the same thing a little better. Have a HashMap with the following structure:- HashMapString, ArrayListString; now scan through the List of words Sort the word and check whether it is already there on the hashmap if it is just add this word to the list for this corresponding word else just add this sorted form of this word to the HashMap . So if you give me any word i will sort it check it in hashmap and get the list of all its corresponding anagrams. On Sat, May 12, 2012 at 1:57 PM, atul anand atul.87fri...@gmail.com wrote: given the list of words... what you can do is the following :- now take first word from the list.. sort this word in alphabetical order...for eg str=bcda --- sort , we get str=abcd now considering this sorted word as a key(abcd) , insert original word (bcda as value) into the hash table ( hash table with chaining ) similarly do it for other words. now given a word , you just need to sort this given word and use it as a key to fetch all anagram. On Fri, May 11, 2012 at 5:24 PM, mayur mayursa...@gmail.com wrote: Hi all, I am stuck with a question for a long time...can someone provide the best algorithm for this.. Question).. find all the anagrams in a list of words. The algorithm should be efficient as the list can be very large. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/c4cSIMcBYLEJ. 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, Jeevitesh Shekhar Singh.* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding anagrams in a list of words
@deepikaanand: 1 is not a prime no. and also ignore 2 as chosen prime no,. On Sun, May 13, 2012 at 6:31 PM, deepikaanand swinyanand...@gmail.comwrote: @gaurav the approach suggested as : to have an array of 25 prime nos..How is it supposed to work ; cz(this is wat i have understood) if a :0 ,b:1,c:3,d:5,e:7 then be = b + e = 1+7 =8 and dc = d + c =5 +3 = 8.. -- 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, GAURAV CHAWLA +919992635751 +919654127192 -- 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] new social network (be the owner of the website)
spam On 5/13/12, abhi mehrotra abhishekmehrotra.i...@gmail.com wrote: Guys, As u all know, Facebook CEO and Founder Mark Zuckerburg stole the idea of Facebook from twin brothers - Tyler Winklevoss Cameron Winklevoss from harvard university in 2001.. later on they filed a complaint Mark and got 65 million dollar in 2007.. In 2009, the twins started a new project and launched the beta version in dec 2011.. You can join it now and become a share holder of this website.. Currently there are thousands of member joining this web site in UK alone per day, totally free , new features than Facebook and G+ (Yet to arrive I guess). Facebook is worth 50 billion today but its users are getting 0% of the shares.. So this new idea is invoked by the twins is definitely amazing.. Welcome To Zurker - A Chance In A Lifetime! Zurker - How You Can Be An Owner. Zurker is a new and unique type of social media. It seems to be a mixture between Facebook and Google + but with a unique selling point: it's owned by its members! You earn shares in Zurker by referring members. You get 2 shares for each referral in the first 24 hours of your membership and one share per referral thereafter. Click Here to Join Zurker! Since it is beta, you definitely need a n invitation.. http://www.zurker.in/i-152526-xkykcgxtqw Abhhishek Mehrotra -- 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. -- -- http://about.me/raikrahul -- 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] new social network (be the owner of the website)
spam On 5/13/12, abhi mehrotra abhishekmehrotra.i...@gmail.com wrote: Guys, As u all know, Facebook CEO and Founder Mark Zuckerburg stole the idea of Facebook from twin brothers - Tyler Winklevoss Cameron Winklevoss from harvard university in 2001.. later on they filed a complaint Mark and got 65 million dollar in 2007.. In 2009, the twins started a new project and launched the beta version in dec 2011.. You can join it now and become a share holder of this website.. Currently there are thousands of member joining this web site in UK alone per day, totally free , new features than Facebook and G+ (Yet to arrive I guess). Facebook is worth 50 billion today but its users are getting 0% of the shares.. So this new idea is invoked by the twins is definitely amazing.. Welcome To Zurker - A Chance In A Lifetime! Zurker - How You Can Be An Owner. Zurker is a new and unique type of social media. It seems to be a mixture between Facebook and Google + but with a unique selling point: it's owned by its members! You earn shares in Zurker by referring members. You get 2 shares for each referral in the first 24 hours of your membership and one share per referral thereafter. Click Here to Join Zurker! Since it is beta, you definitely need a n invitation.. http://www.zurker.in/i-152526-xkykcgxtqw Abhhishek Mehrotra -- 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. -- -- http://about.me/raikrahul -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] How can we rank the players in a relative game Ranking Players
This is a live problem from interviewstreet.com: In the game challenges that we host, one practial problem that we face is to rank the contestants. Contestants need to submit code for a game problem and we pair up them against each other to see their relative performance. The aim of this tournament is to rank the players on the quality of code they submit. The task for you is to come up with an approach to rank the players using as few matches as possible. Submission Notes: You have to complete the function game given for this task. You can also create your own data structures and functions as needed. The function game is passed as parameter the number of players nPlayers and players have ids from 0 to nPlayers-1( 0 and nPlayers-1 included ). This function should return a vector of player ids. In this vector better players have lower indices. You can make calls to a hidden function gameResult which takes as argument the id of two players and conduct a match, this function returns the id of winner among the two players. Scoring: The list of player that you produce is compared against the hidden expected list, and for each player the difference in their position from both lists is added. If this sum is less than 3*nPlayers you get a score based on the number of calls you made to function gameResult. Less number of calls fetches higher score. Further Notes: This is approx-type problem so compile and test option might not work, so directly submit your code ans see the score in submissions tab. Since there is no deterministic minimal number of comparison, you may see you submission as wrong bu the score you get will give you an idea of your code's performance. The language shown for submission is C++, but it should not be a problem to the programmers of other language since the i/o and other details has been taken care of and you just need to write the appropriate functions. You can refer to http://www.cplusplus.com/doc/tutorial/ for more details if necessary. Standard header files/STL have already been included so you need not include/import additional header files. Note: nPlayers is not greater than 100. Different calls to gameResult between same pair of players may not necessarily return same winner always. We have tried to tweak a real game data by incorporate the elo rating system to determine the winner of matches. So in a call to gameResult, the winner is determined by that probability. Note: Don't give the the exact solution...jut m looking for an approach. Some of the approach I have followed are as: First Approach Have n/2 matches among n players then n/4 matches among previous looser and n/4 among previous winner Continue recursively. Second Approach Each player play against each other. The players having the maximum winning appear above in the returning queue Both the above approach doesn't seem working...can u please suggest what's going wrong here...and how to proceed further... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] spoj problem
@ashish pant We must compute all the queries in O(n)+O(k). We must have array like counting array. It is not my logic but my friend told about this logic -- 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.
