Interview Question
<pre lang="c++" line="1" title="CodeMonkey3691" class="run-this">// RemoveAdjacentDuplicates.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <string>
#include <cassert>
typedef std::basic_string<char> string;
/*
RemoveAdjacentDuplicates: string, string -> string
Given two strings s1 & s2, this function returns a composite of s1 & s2;
If there is a trailing sub-string of s1 and a leading sub-string of s2 which are common,
Returns a concatenation of the prefix of s1, followed by the common substring, followed by the suffix of s2;
i.e if s1 = s1' + s' and if s2 = s' + s2' then the result is s1' + s' + s2'
If there is nothing in common, then s' becomes the empty string and the result will be a concatenation of the two strings.
*/
string
RemoveAdjacentDuplicates(string const& s1, string const& s2)
{
// Handle edge cases of one or both inputs being empty;
if (s1.empty()) return s2;
if (s2.empty()) return s1;
//Both strings must be non-empty if we got here;
assert(!s1.empty() && !s2.empty());
//find the last character of s1 anywhere in s2;
size_t m = s1.size();
//index into the current character of interest in s1;
string::size_type i = m - 1;
//index into the current character of interest in s2;
string::size_type pos = s2.find_last_of(s1[i]);
string s(s1); //return value initialized must atleast have s1;
string::size_type k = pos; //Offset just before the suffix that must be concatenated with s1;
if (pos != string::npos) {
assert(s1[i] == s2[pos]);
while (s1[i] == s2[pos] && i > 0 && pos > 0) { //make sure we don't run off s1 or s2;
--i; --pos;
}
assert(i >= 0 && pos >= 0);
if (pos > 0) { //Ran out of s1 but not s2, therefore no common sub-sequence;
k = string::npos;
}
}
s.append(s2.substr(k + 1));
return s;
}
int _tmain(int argc, _TCHAR* argv[])
{
struct {
const char* const s1;
const char* const s2;
} testBed[] = {
{ "", "" }, { "a", ""}, { "", "b"}, { "aa", ""}, { "", "bb"}, {"aaa", ""}, {"", "bbb"}, {"aa", "a"},
{"ab", "ba"}, {"ab", "ab"}, {"abc", "bcd"}, {"abcd", "bcde"},
{"Hello how is everyone", "everyone is good?"}, {"Hello how is everyone", "is everyone good?"},
{"Hello how is everyone", "Hi, is everyone"}, {"Totally", "Unrelated"},
};
for (int i = 0; i != sizeof(testBed)/sizeof(testBed[0]); ++i) {
string s(RemoveAdjacentDuplicates(testBed[i].s1, testBed[i].s2));
printf("s1 '%s' s2 '%s' result '%s'\n", testBed[i].s1, testBed[i].s2, s.c_str());
}
return 0;
}
</pre><pre title="CodeMonkey3691" input="yes">
// RemoveAdjacentDuplicates.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <string>
#include <cassert>
typedef std::basic_string<char> string;
/*
RemoveAdjacentDuplicates: string, string -> string
Given two strings s1 & s2, this function returns a composite of s1 & s2;
If there is a trailing sub-string of s1 and a leading sub-string of s2 which are common,
Returns a concatenation of the prefix of s1, followed by the common substring, followed by the suffix of s2;
i.e if s1 = s1' + s' and if s2 = s' + s2' then the result is s1' + s' + s2'
If there is nothing in common, then s' becomes the empty string and the result will be a concatenation of the two strings.
*/
string
RemoveAdjacentDuplicates(string const& s1, string const& s2)
{
// Handle edge cases of one or both inputs being empty;
if (s1.empty()) return s2;
if (s2.empty()) return s1;
//Both strings must be non-empty if we got here;
assert(!s1.empty() && !s2.empty());
//find the last character of s1 anywhere in s2;
size_t m = s1.size();
//index into the current character of interest in s1;
string::size_type i = m - 1;
//index into the current character of interest in s2;
string::size_type pos = s2.find_last_of(s1[i]);
string s(s1); //return value initialized must atleast have s1;
string::size_type k = pos; //Offset just before the suffix that must be concatenated with s1;
if (pos != string::npos) {
assert(s1[i] == s2[pos]);
while (s1[i] == s2[pos] && i > 0 && pos > 0) { //make sure we don't run off s1 or s2;
--i; --pos;
}
assert(i >= 0 && pos >= 0);
if (pos > 0) { //Ran out of s1 but not s2, therefore no common sub-sequence;
k = string::npos;
}
}
s.append(s2.substr(k + 1));
return s;
}
</pre>
If it is tail overlap removal, there are two possibilities
case 1: sentence1+tail || tail+sentence2
or
case 2: sentence2+tail || tail+sentence1
If last(sentence1) equals first(sentence2)
then case 1:
iterate back in sentence1 && iterate forward in sentence2 until neither is empty
if word not equal,
then
output sentence1 from begining to mismatched word + complete sentence2
done
if sentence1 word is empty
output sentence2
done
if sentence2 word is empty
output sentence1
done
else case 2
logic similar to above
O(n + m), n and m are word lengths of sentences
If we know that last word in first sentence and first word in second sentence overlap then :
1. we can simply scan the second sentence until we find a ' '.
2. If we find first ' '(space) in second sentence that means "everyone" in second sentence is scanned.
3. so we ll append rest of the second string to first.
4. we ll get the desired result.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class RemoveDuplicate {
public static String str1 = "hello everyone";
public static String str2 = "everyone is good";
/**
* @param args
*/
public static void main(String[] args) {
String tmp = str1+" "+str2;
String[]listString = tmp.split(" ");
Set<String> nodup = new HashSet<String>();
List<String> returnString = new ArrayList<String>();
for(int i= 0; i<listString.length ;i++){
if(nodup.add(listString[i])){
returnString.add(listString[i]);
}
}
StringBuffer sb = new StringBuffer();
for (String s:returnString){
sb.append(s);
sb.append(" ");
}
System.out.println(sb.toString());
}
}
merge sort of list of words?
- Anonymous November 19, 2010