Cisco Systems Interview Question
Software EngineersCountry: India
Interview Type: Written Test
- O(n^2)
- Given s1 and s2
- For each substring(i, s2.length) check if substring is in s1
- if so print substring
- O(n) #on average
- Given s1 and s2
- Create suffix hash of s1
- Ex: s1 = 'abc'
- suffix hash = { 'a': 'a', 'abc' : 'abc': 'b': 'b', 'bc': 'bc': 'c': 'c' }
- For each suffix in s2, check hash if exist print
std::string findCommonSuffix(std::string s1, std::string s2)
{
int i, j;
for(i = s1.size()-1, j = s2.size()-1 ; i >= 0 && j >= 0; --i, --j)
{
if(s1[i] != s2[j]) break;
if(i == 0 || j == 0) break;
}
std::string result;
if(i == 0)
result = s1;
else if(j == 0)
result = s2;
else
result = s1.substr(i+1, s1.size() - i);
return result;
}
String s1 = "cornfiled";
String s2 = "Exfiled";
String suffix;
if ( s1.length() > s2.length()){
suffix = searchSuffix(s1, s2);
}else{
suffix = searchSuffix(s2, s1);
}
System.out.println("Matching suffix is :" + suffix);
}
static String searchSuffix(String searchString, String searchInString){
String sbSearch = null;
for (int i=0; i<searchString.length(); i++){
sbSearch = searchString.substring(i);
System.out.println("sbSearch :" + sbSearch);
if(searchInString.contains(sbSearch)){
return sbSearch;
}
}
return null;
}
public static void main(String[] args){
String s1 = "cornfiled";
String s2 = "Exfiled";
String suffix;
if ( s1.length() > s2.length()){
suffix = searchSuffix(s1, s2);
}else{
suffix = searchSuffix(s2, s1);
}
System.out.println("Matching suffix is :" + suffix);
}
static String searchSuffix(String searchString, String searchInString){
String sbSearch = null;
for (int i=0; i<searchString.length(); i++){
sbSearch = searchString.substring(i);
System.out.println("sbSearch :" + sbSearch);
if(searchInString.contains(sbSearch)){
return sbSearch;
}
}
return null;
}
String[] words = {"cornfiled", "Exfiled", "eled"};
Stream.of(words)
.sorted(Comparator.reverseOrder())
.reduce((r, l) ->
{
String suff = "";
for (int i = r.length() - 2; i >= 0; i--) {
String temp = r.substring(i);
if (!l.endsWith(temp)) {
break;
}
suff = temp;
}
return suff;
}).ifPresent(System.out::println);
String[] words = {"cornfiled", "Exfiled", "eled"};
Stream.of(words)
.sorted(Comparator.reverseOrder())
.reduce((r, l) ->
{
String suff = "";
for (int i = r.length() - 2; i >= 0; i--) {
String temp = r.substring(i);
if (!l.endsWith(temp)) {
break;
}
suff = temp;
}
return suff;
}).ifPresent(System.out::println);
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int temp;
try{
System.out.println("enter string 1:");
String str1=sc.nextLine();
System.out.println("enter string 2:");
String str2=sc.nextLine();
if(str1.length()>str2.length())
{
if(str1.contains(str2)){
temp=str1.indexOf(str2);
System.out.print(str1.substring(temp));
}
}
else
{
if(str2.contains(str1)){
temp=str2.indexOf(str1);
System.out.print(str2.substring(temp));
}
}
}
catch(Exception e){
System.err.print(e);
}
}
- Sunny September 15, 2017