Re: [algogeeks] Re: Adobe - Coding
@bittu , I think RLE , would be of no use ; as inp:AAABBRRGH out :3A2B2R1G1H so to reach the top 5 counts , there will be of no use . as stated earlier by others , HASH TABLE will be the one of best solution for this . maintain hash table in O(n) and then sort it .for top 5 counts. Please mend me if I am wrong somewhere as I am also in a learning phase. On Sat, Jan 8, 2011 at 7:08 AM, bittu wrote: > RLE run length encoding is another solution because counting sort > eats space whilw with RLE we can do it in > > time complexity O(n) > Space Complexity O(1) > > Correct me if i am wrong ...i m talking about possibility not > exactness. > > 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.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Lalit Kishore Sharma IIIT Allahabad (Amethi Capmus) 5th Sem -- 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] Re: Adobe - Coding
RLE run length encoding is another solution because counting sort eats space whilw with RLE we can do it in time complexity O(n) Space Complexity O(1) Correct me if i am wrong ...i m talking about possibility not exactness. 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe - Coding
Here's a different language from the usual to enjoy! This algorithm is O(n) where n is the length of the input. with Ada.Text_IO, Ada.Strings.Unbounded.Text_IO, Ada.Strings.Unbounded; use Ada.Text_IO, Ada.Strings.Unbounded.Text_IO, Ada.Strings.Unbounded; procedure Top5 is type Pair_Type is record Key : Unbounded_String; Count : Natural := 0; end record; N_Top : constant := 5; N_Top_With_Sentinel : constant := N_Top + 1; Top : array(1 .. N_Top_With_Sentinel) of Pair_Type; I : Natural; Input : Unbounded_String; Tmp : Pair_Type; begin while not End_Of_File loop Get_Line(Input); I := Top'First; while I <= N_Top loop exit when Top(I).Key = Input; I := I + 1; end loop; Tmp.Count := Top(I).Count + 1; Tmp.Key := Input; while I > Top'First and then Tmp.Count > Top(I - 1).Count loop Top(I) := Top(I - 1); I := I - 1; end loop; Top(I) := Tmp; Top(N_Top_With_Sentinel) := (others => <>); end loop; for I in Top'Range loop exit when Top(I).Count = 0; Put_Line(Top(I).Key & Natural'Image(Top(I).Count)); end loop; end Top5; === C:\>top5 a b c f a d e f b f f ^Z f 4 a 2 b 2 c 1 d 1 -- 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: Adobe - Coding
>From the questions example it seems they are looking for five most common character seen in the list. Please clarify on this. On Fri, Jan 7, 2011 at 2:02 PM, Avi Dullu wrote: > @Decipher > > As far as I understand the problem it says "returns the 5 most common > occuring strings in a list", and the example u give is of a character > array, when u go to a list of strings with len_of_each_string > 1, u wil > have to *hash* them, which is when u will run into problems with count sort. > So count sort wil not work. > > As juver++ said sorting is one option. > Going for hashing of each string and using a hashtable is another possible > solution. > Also building a compressed Trie out of the list and a traversal of it, will > give the top 5 counts (but this will be too much work for this task :) ) > > > Programmers should realize their critical importance and responsibility in > a world gone digital. They are in many ways similar to the priests and monks > of Europe's Dark Ages; they are the only ones with the training and insight > to read and interpret the "scripture" of this age. > > > > On Sat, Jan 8, 2011 at 1:59 AM, Decipher wrote: > >> We can apply count sort here also and take the range of numbers as >> 256 . Example take an array c[256] , where c[i] gives the number of >> times i_th ASCII value is repeated . Then after you have obtained >> c[256] . Check for maximum 5 nos. in this array (which can be done in >> O(n) time and 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.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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: Adobe - Coding
@Decipher As far as I understand the problem it says "returns the 5 most common occuring strings in a list", and the example u give is of a character array, when u go to a list of strings with len_of_each_string > 1, u wil have to *hash* them, which is when u will run into problems with count sort. So count sort wil not work. As juver++ said sorting is one option. Going for hashing of each string and using a hashtable is another possible solution. Also building a compressed Trie out of the list and a traversal of it, will give the top 5 counts (but this will be too much work for this task :) ) Programmers should realize their critical importance and responsibility in a world gone digital. They are in many ways similar to the priests and monks of Europe's Dark Ages; they are the only ones with the training and insight to read and interpret the "scripture" of this age. On Sat, Jan 8, 2011 at 1:59 AM, Decipher wrote: > We can apply count sort here also and take the range of numbers as > 256 . Example take an array c[256] , where c[i] gives the number of > times i_th ASCII value is repeated . Then after you have obtained > c[256] . Check for maximum 5 nos. in this array (which can be done in > O(n) time and 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.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe - Coding
We can apply count sort here also and take the range of numbers as 256 . Example take an array c[256] , where c[i] gives the number of times i_th ASCII value is repeated . Then after you have obtained c[256] . Check for maximum 5 nos. in this array (which can be done in O(n) time and 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe - Coding
As you work with strings, you cannot apply count sort here. Basic approach is to sort array, iterate over it and mantain ordered set of 5 items. -- 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.
