[algogeeks] Re: Programming Problem
i think we cannot change the order of the characters On Thursday, 19 July 2012 11:00:20 UTC+5:30, gobind hemb wrote: String s is called *unique* if all the characters of s are different. String s2 is *producible* from string s1, if we can remove some characters of s1 to obtain s2. String s1 is *more beautiful* than string s2 if length of s1 is more than length of s2 or they have equal length and s1 is lexicographically greater than s2. Given a string s you have to find the *most beautiful unique* string that is producible from s. *Input:* First line of input comes a string s having no more than 1,000,000(10^6) characters. all the characters of s are lowercase english letters. *Output:* Print the most beautiful unique string that is producable from s *Sample Input:* babab *Sample Output:* ba *Explanation* In the above test case all unique strings that are producible from s are ab and ba and ba is more beautiful than ab. -- 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/-/xq8pHByKW9kJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: programming problem
You could do this too... 1. Sort the words based on length. Max Time: O(nlogn) 2. Now, Create a tree similar to a state transition diagram. For each word in the tree, store their start and end pointers. 3. If a word comprises of another word, then the main word would only store start and end pointers for the enclosed word. For example in the tree , the word catsdogcats, will stored as original cats+pointer to start and end of dog+pointer to start and end of cats Even if all the words are different, this construction will not take you more then O(n*w) time where w is the maximum length of any word. 4. Finding the longest word which can be constructed using other words can either be done online i.e. while constructing the tree or after constructing the tree, we do it for each unique branch of the tree. Max Time: O(n*I) Hence. total time: O(n log n) On Tue, May 20, 2008 at 1:56 PM, anshu [EMAIL PROTECTED] wrote: This question aint clear So, for example in above list hippopotamuses is also in the list of word in the file. So this word includes itself and is 14 characters. where is a condition that concatenation is a must? On May 20, 3:39 am, greg [EMAIL PROTECTED] wrote: Write a program that reads a file containing a sorted list of words (one word per line, no spaces, all lower case), then identifies the longest word in the file that can be constructed by concatenating copies of shorter words also found in the file. For example, if the file contained: cat cats catsdogcats catxdogcatsrat dog dogcatsdog hippopotamuses rat ratcatdogcat The answer would be 'ratcatdogcat' - at 12 letters, it is the longest word made up of other words in the list. I'm having trouble coming up with anything other than starting with the longest word in the list and checking for each of the other words in the list, which seems incredibly inefficient, any ideas or suggestions of things to look at? --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: programming problem
The very fact that the complexity is O(nlogn) doesn't hold good since the comparison operation takes O(length of string). Can you give us more details on the algorithm? On Wed, May 21, 2008 at 11:32 AM, Chonku [EMAIL PROTECTED] wrote: You could do this too... 1. Sort the words based on length. Max Time: O(nlogn) 2. Now, Create a tree similar to a state transition diagram. For each word in the tree, store their start and end pointers. 3. If a word comprises of another word, then the main word would only store start and end pointers for the enclosed word. For example in the tree , the word catsdogcats, will stored as original cats+pointer to start and end of dog+pointer to start and end of cats Even if all the words are different, this construction will not take you more then O(n*w) time where w is the maximum length of any word. 4. Finding the longest word which can be constructed using other words can either be done online i.e. while constructing the tree or after constructing the tree, we do it for each unique branch of the tree. Max Time: O(n*I) Hence. total time: O(n log n) On Tue, May 20, 2008 at 1:56 PM, anshu [EMAIL PROTECTED] wrote: This question aint clear So, for example in above list hippopotamuses is also in the list of word in the file. So this word includes itself and is 14 characters. where is a condition that concatenation is a must? On May 20, 3:39 am, greg [EMAIL PROTECTED] wrote: Write a program that reads a file containing a sorted list of words (one word per line, no spaces, all lower case), then identifies the longest word in the file that can be constructed by concatenating copies of shorter words also found in the file. For example, if the file contained: cat cats catsdogcats catxdogcatsrat dog dogcatsdog hippopotamuses rat ratcatdogcat The answer would be 'ratcatdogcat' - at 12 letters, it is the longest word made up of other words in the list. I'm having trouble coming up with anything other than starting with the longest word in the list and checking for each of the other words in the list, which seems incredibly inefficient, any ideas or suggestions of things to look at? --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: programming problem
Well, he does say other words. hippopotamuses is not made up of other words in the list. It looks like a recursive procedure would do the trick. It might help to sort the word list into order by length. Then beginning with the longest word, find other words that match the beginning of the word. For each of them, recurse on the rest of the word. If you get to end the word, you've found your answer. Dave On May 20, 3:26 am, anshu [EMAIL PROTECTED] wrote: This question aint clear So, for example in above list hippopotamuses is also in the list of word in the file. So this word includes itself and is 14 characters. where is a condition that concatenation is a must? On May 20, 3:39 am, greg [EMAIL PROTECTED] wrote: Write a program that reads a file containing a sorted list of words (one word per line, no spaces, all lower case), then identifies the longest word in the file that can be constructed by concatenating copies of shorter words also found in the file. For example, if the file contained: cat cats catsdogcats catxdogcatsrat dog dogcatsdog hippopotamuses rat ratcatdogcat The answer would be 'ratcatdogcat' - at 12 letters, it is the longest word made up of other words in the list. I'm having trouble coming up with anything other than starting with the longest word in the list and checking for each of the other words in the list, which seems incredibly inefficient, any ideas or suggestions of things to look at?- 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: programming problem
Regular expressions ? --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: programming problem
You can solve this problem by the following technique:
Proc 1: Take any word W in the file
Find all strings S(k) which are formed by concatenating k words in the file
and is a prefix of W. [A word can repeat multiple times in different places]
As you can see, number of words in S(k) will certainly be greater than or
equal to S(k+1). Further, S(k+1) can be formed using S(k).
Algo1: You run the Proc 1 finding S(k)s for each k = 2 until you either
1. find some count(S(k)) = 0 where you are not able to find other words
which can be used to form the current word
2. if some word in S(k) is equivalent to W, then you have a candidate word W
which can be formed using other words.
Here goes the pseudo code for the program :
*vs arr; *// a vector of strings containing the word that I am searching
for.
// The function takes as input an integer pos. This pos is the index of
the string in arr for which we are finding whether the string arr[pos] can
be formed using other words.
*bool canForm(int pos) {*
bool *tmp, *tmp1;
int l = arr[pos].size();
tmp = new bool[l+1];
tmp1 = new bool[l+1];
for(i,0,l+1) tmp1[i] = tmp[i] = false;
tmp[0] = true;
while (true) {
bool atleastOne = false;
for(i,0,l+1) tmp1[i] = false;
for(i,0,l) {
if (tmp[i] == true) {
for(j,0,arr.size()) {
if (pos != j) {
if (l - i = arr[j].size()) {
bool match = true;
for(k,0,arr[j].size()) {
if (arr[j][k] != arr[pos][i+k]) {
match = false;
break;
}
}
if (match) {
tmp1[i + arr[j].size()] = true;
atleastOne = true;
if (i + arr[j].size() == l) return true;
}
}
}
}
}
}
bool *t = tmp;
tmp = tmp1;
tmp1 = t;
if (!atleastOne) return false;
}
// never comes
return false;
}
worst case time complexity : If there are n words and the maximum length
string is of length l, then O(n^2 * l ^ 2)
--deepak
On Tue, May 20, 2008 at 11:26 PM, [EMAIL PROTECTED]
[EMAIL PROTECTED] wrote:
Regular expressions ?
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: programming problem
Does anyone has any ideas on how 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: programming problem
The following is a statement of a programming problem i encountered I don't know how to solve it. Any ideas?? The owner of shop Jell Bells has order a large consignment of jell balls which is about to arrive. He has hired you as an assistant to help him sort the balls and put them in their respective containers at the shop (pretty simple ? HuH!!). Now the Job Profile Is : The balls are of different colors (say n), though many of the colors are repeated. Whenever the balls are removed from the consignment, they have to be kept in some temporary sack (say a stack) with each ball on top of other in no particular order. Each sack is of infinite capacity and you can use as many sacks as u like. When all the balls are removed from the consignment, they are then to be put in their respective colored containers at the store. Here comes the tricky thing, any colored container can be given to you by the owner to be filled. All the balls of that particular color have to be put in container at once. It may be possible that that particular colored ball is at the bottom of the sack, then you have to first move all the balls above it in some other sack. The owner wants that the number of temporary sacks multiplied by the number of moves is minimum. (How moves are counted when a ird move) and so on, then finally to the container (last move) for that particular ball). Once the things are sorted, you get your pay (and some jell balls too. Yummy!!) INPUT The first line of input contains an integer X, specifying the number of test cases. Second line contains number of containers N, and the number of balls M. the third line is the sequence in which the balls are removed from the consignment. Fourth is the order in which the owner of shop gives you the containers to be filled. OUTPUT The first line of output will be the number of moves P, and the number of sacks used Q. From second line onwards you have to specify each and every move as described in the example below. EXAMPLE Say the N colors are represented by numbers 1 to n, the temporary sacks as temp1, Sample input 1 3 6 3 3 2 2 1 1 1 2 3 Sample output 12 1 Move 1 :: put ball 3 in temp1 Move 2 :: put ball 3 in temp1 Move 3 :: put ball 2 in temp1 Move 4 :: put ball 2 in temp1 Move 5 :: put ball 1 in temp1 Move 6 :: put ball 1 in temp1 Move 7 :: put ball 1 in cont1 Move 8 :: put ball 1 in cont1 Move 9 :: put ball 2 in cont2 Move 10 :: put ball 2 in cont2 Move 11 :: put ball 3 in cont3 Move 12 :: put ball 3 in cont3 -------- --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
