Re: [algogeeks] Gate complaxity question
see A(n)ie the average case will always be smaller or equal to the worst case... ie something like... A(n)= c. w(n) for some c as constt ... which the definition of big O... correct me if i'm wrong.. On Sat, Aug 25, 2012 at 7:11 PM, rahul sharma rahul23111...@gmail.comwrote: *Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?* (A) [image: A(n) = \Omega(W(n))] (B) [image: A(n) = \Theta(W(n))] (C) [image: A(n) = O(W(n))] (D) [image: A(n) = o(W(n))] answer is c plz explain y??? -- 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] Re: MS interview
@all .. i suggested him the hashing method... but was not convinced... he might be expecting something else.. something like tries.. etc.. @ Karthikeyan Muthu... can u explain it in detail with some ex ... On Thu, Aug 23, 2012 at 11:28 PM, Karthikeyan Muthu keyankarthi1...@gmail.com wrote: i would suggest using tires data structure, basically a n-nary tree to store the dictionary. Entire algo is as follows: 1) Create a trie http://en.wikipedia.org/wiki/Trie representing the dictionary. 2) create a aux array for the search key. as count [ key[i] ] ++; 3) Start a recursion from the root of the trie and pick a path if (count [ path ] 0 ) 3rd step ensures that we traverse only those valid paths (ie valid words, this would reduce n! checking of all combinations). On Thu, Aug 23, 2012 at 8:23 PM, Ashish Goel ashg...@gmail.com wrote: yes, that is correct. O(mn) to form multimap and then O(m) to tell all anagram groups Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Aug 23, 2012 at 5:11 PM, kings dns.bhar...@gmail.com wrote: Dear GC, The efficient data structure in my opinion is Hash Table. 1. For a given word in the dictionary we need to form an anagram dictionary i.e. take a given word sort it which forms the key for the hashtable , then start forming the different anagrams for that word and insert it into the hash table with the corresponding key. 2. Once the hash table is ready for the given word sort it find the key and print all the anagarams i.e. values associated to that key. we will get all the anagrams for a given word. Coming to time complexity... sorting of a word can be done in a O(nlogn). building of anagram will take O(n). hash complexity O(n) worst case. so total time complexity is O(nlogn) for whole execrcise. Thanks Bhargava On Wednesday, 22 August 2012 23:39:02 UTC+5:30, GC wrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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/-/ySPUSvS0Sh0J. 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. -- 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.
[algogeeks] MS interview
Ques Given a large text... in the text.. there are gt; , lt; etc representing and .(there can be others like eq; etc) the task is to replace such (gt;) with the '' symbol... and (lt;) with '' given the table which have corresponding matches... and table is finite . suggest an efficient algo... -- Regards, G C -- 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] MS interview
Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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: Partition the array with equal average
@ prem... can U submit the code...for all Subsets of the particular array with O(n^2). thanks.. On Sun, May 20, 2012 at 1:11 AM, abhijeet srivastva nwaab.abhij...@gmail.com wrote: This is a subset sum problem. You have to find a subset of elements of array whose sum is x/2, where x is sum of all the elements of the array. On Sat, May 19, 2012 at 2:07 PM, payal gupta gpt.pa...@gmail.com wrote: this wont work out as we need to partition the elements to get the average of the two parts to be equal and not the sum of the two parts.. On Fri, May 18, 2012 at 11:57 PM, Ramindar Singh ramin...@gmail.comwrote: Not sure if i am correct but still be very close. 1. Intial Array is A with n elements 2. Sort the Array's in descending order 3. take 2 more arrays B and C in which u keep the partition 4. pull the one element from A to B and keep keep track of the sum's in both the arrays B C 5. Try to reach the sum in B by pulling the elements from A 6. Continue till all the n elements are partitioned. 7. If in the end still some difference is there b/w B and C, it can be settled by exchanging the elements among them as they both would be sorted. hope this helps... -- 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/-/BRRM2sjulSEJ. 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. -- 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] Re: finding anagrams in a list of words
@payal instead corresponding ascaii, corresponding primes can be taken (preDefined) as explaind in my previous post. On Tue, May 15, 2012 at 12:02 AM, payal gupta gpt.pa...@gmail.com wrote: hmm... thnx for the catch of my flaw... On Mon, May 14, 2012 at 11:56 PM, saurabh singh saurabh.n...@gmail.comwrote: u mean ad == bc ? On Mon, May 14, 2012 at 10:41 PM, payal gupta gpt.pa...@gmail.comwrote: @atul instead of sorting the string individually which would require tc- O(nlogn) shouldnot it be a better idea to use the sum of the ascii values of the individual alphabets as the key which would require tc-O(n) ??? On Sun, May 13, 2012 at 7:07 PM, GAURAV CHAWLA togauravcha...@gmail.com wrote: @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. -- 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, Saurabh -- 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, 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] 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] finding anagrams in a list of words
what we can do is ,... lets have a array of 25 prime nos .. and corresponding to its index no. i.e a :0 ,b:1,c:3.. now we traverse each word and generate a count of each word .. and if count for any two or three are same will be anagrams.. hope this will work.. give comments plz... On Fri, May 11, 2012 at 6:11 PM, Aman Raj amanka...@gmail.com wrote: use trie trees, and for every word sort the word and store the sorted word in the trie tree and also keep the index of that word in leaf of trie tree..after traversing the whole list of words you'll have all the indices of a anagrams of a particular word in its leaf nodes. 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. -- 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.
