I am preparing for a interview question.One of the question is to revert a sentence. Such as "its a awesome day" to "day awesome a its. After this,they asked if there is duplication, can you remove the duplication such as "I am good, Is he good" to "good he is, am I".
for reversal of the sentence i have written following method
public static string reversesentence(string one)
{
StringBuilder builder = new StringBuilder();
string[] split = one.Split(' ');
for (int i = split.Length-1; i >= 0; i--)
{
builder.Append(split[i]);
builder.Append(" ");
}
return builder.ToString();
}
But i am not getting ideas on removing of duplication.Can i get some help here.
This works:
public static string reversesentence(string one)
{
Regex reg = new Regex("\\w+");
bool isFirst = true;
var usedWords = new HashSet<String>(StringComparer.InvariantCultureIgnoreCase);
return String.Join("", one.Split(' ').Reverse().Select((w => {
var trimmedWord = reg.Match(w).Value;
if (trimmedWord != null) {
var wasFirst = isFirst;
isFirst = false;
if (usedWords.Contains(trimmedWord)) //Is it duplicate?
return w.Replace(trimmedWord, ""); //Remove the duplicate phrase but keep punctuation
usedWords.Add(trimmedWord);
if (!wasFirst) //If it's the first word, don't add a leading space
return " " + w;
return w;
}
return null;
})));
}
Basically, we decide if it's distinct based on the word without punctuation. If it already exists, just return the punctuation. If it doesn't exist, print out the whole word including punctuation.
Punctuation also removes the space in your example, which is why we can't just do String.Join(" ", ...) (otherwise the result would be good he Is , am I instead of good he Is, am I
Test:
reversesentence("I am good, Is he good").Dump();
Result:
good he Is, am I
For plain reversal:
String.Join(" ", text.Split(' ').Reverse())
For reversal with duplicate removal:
String.Join(" ", text.Split(' ').Reverse().Distinct())
Both work fine for strings containing just spaces as the separator. When you introduce the , then problem becomes more difficult. So much so that you need to specify how it should be handled. For example, should "I am good, Is he good" become "good he Is am I" or "good he Is , am I"? Your example in the question changes the case of "Is" and groups the "," with it too. That seems wrong to me.
The other answer points to using abstractions but interviewers usually want to see implementation.
For the reversal, the usual trick is to reverse the sentence first and then reverse each word as you travel from left to right. A space will you tell you that you have reached the end of a word. (See Programming Interviews Exposed for a solution to this or just google it. This used to be a VERY popular interview question). Your approach works but is frowned upon because you are using extra space (O(n)).
For removing duplicates, if you're only working with ASCII, you can do the following:
bool[] seenChars = new bool[128];
var sb = new StringBuilder();
foreach(char c in stringOne)
{
if(!seenChars[c]){
seenChars[c] = true;
sb.Append(c);
}
}
return sb.ToString();
The idea is to use the value of the char as an index in the array to tell you whether you've seen this character before or not. With this approach, you will be using O(1) space!
Edit: If you want to de-duplicate words, you probably want to use a HashSet and skip adding it if it already exists.