Facebook Interview Question Software Engineer Interns
Country: United States
i1 represents index of str1 and i2 represents the index of str2
bool hasCheated(str1,str2, i1, i2, N)
{
if ( N==0)
return true;
if (str1 == NULL) || ( str2 == NULL)
return false;
if (( i1 >= strlen(str1) )|| ( i2 >= strlen( str2)))
return false;
bool b1 =false;
//if string match at current index
if ( str1[i1] == str2[i2])
b1 = hasCheated(str1, str2,i1+1, i2+1,N-1)
return (hasCheated(str1, str2,i1, i2+1,N) || //str2 increased
hasCheated(str1, str2,i1+1, i2,N) || //str1 index increased
b1)
}
As some one suggested, the answer for this problem is to use a suffix trie!
<i'm assuming that the strings given doesnt contain spaces (albeit it doesnt really matter, let me downcomplicate this problem)>
So basically, collect all the suffixes of string 1, and put them in a trie.
Trie *TR;
Add all suffixes of the first string into the trie
mainfunction()
{
for(i=0; i<strlen(s1) i++)
{
// adding every suffix into the trie, we dont care what is return is.
insertIntoTrie(&TR, getstring(s1, i, strlen(s1)-1));
}
// do the same for second string
For every suffix of the second string, check if that suffix is present in the trie until the required length
for(i=0; i<strlen(s2) i++)
{
if (CheckTrie(TR, getstring(s2, i, strlen(s2)-1), N))
{
// adding every suffix into the trie, while doing this keep checking
// if the current substring is present in the trie
return true;
}
}
return False;
}
bool CheckTrie(Trie * TR, char *suffix, int RequiredLength)
{
// Contains() simply walks through the branches of the tree for Required length depth
// and checks if there is a match until the required length
if (strlen(suffix) >= RequiredLength &&
Contains(TR, suffix, RequiredLength))
{
return true;
}
}
insertIntoTrie(Trie **TR, char* suffix)
{
if(TR == null)
{
newnode = makenode[suffix[0]];
if (suffix[0] == '\0')
{
newNode->endOfWord = 1;
} else {
insertIntoTrie(&newNode->child[word[0] - 'a'], suffix+1);
}
*TR = newNode;
} else {
insertIntoTrie(&TR->child[word[0] - 'a'], suffix+1);
}
}
// something along these lines!, I have not executed this code so there can be a lot of syntactical errors!, but I've written the code to explain the approach.
I would use (LCS) longest common subsequence which is a dynamic programming approach. Its running time is s1.size*s2.size.
The idea is like this:
X = x_1 x_2 ... x_m
Y = y_1 y_2 ... y_n
if( x_m == y_n) then find LCS of x_(m-1) & y_(n-1) and concat x_m to it.
if( x_m != y_n) then find max LCS of { (x_m & y_(n-1)) , (x_(m-1) &y_n)
why cant you use any of the std libraries if its referred to substring?
how about this approach?
string longest_common_contig_substr(const string &str1, const string &str2) {
int index_start = 0;
int index_end = 0;
int count = 0;
int count_max = 0;
for(int i = 0; i < str1.size(); i++) {
int k = i;
for(int j = 0; j < str2.size(); j++) {
if(k >= str1.size()) {
break;
}
if(str1[k] == str2[j]) {
if(count > count_max) {
count_max = count;
index_start = i;
index_end = k;
}
count++;
k++;
}
else {
count = 0;
}
}
}
return str1.substr(index_start, index_end - index_start + 1);
}
public class Professor2 {
public static void main(String[] args) {
String s1="asdf";
String s2="basdasds";
int n=4;
Professor p=new Professor();
if(p.hasCheated(s1, s2, n))
{
System.out.println("copy");
return;
}
System.out.println("not copied");
}
public boolean hasCheated(String s1,String s2, int N)
{
ArrayList<String> al=new ArrayList<String>();
ArrayList<String> bl=new ArrayList<String>();
al.addAll(getData(s1,N));
bl.addAll(getData(s2,N));
return al.retainAll(bl);
}
public List<String> getData(String s,int n)
{
ArrayList<String> temp=new ArrayList<String>();
temp.clear();
String myStr=Arrays.toString(s.split("(?<=\\G.{4})"));
//System.out.println(myStr);
Scanner sc=new Scanner(myStr).useDelimiter(",");
while(sc.hasNext())
{
String my=sc.next();
// my.replaceAll("\\w", "");
//System.out.println(my);
temp.add(my);
}
return temp;
}
}
Out Put:
Student Cheated
public class Prof {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s1="asdf";
String s2="basdasdsasdf";
int n=4;
Prof p=new Prof();
if(p.hasCheated(s1, s2, n))
{
System.out.println("Student Cheated ");
return;
}
System.out.println("Not Cheated");
}
public boolean hasCheated(String s1,String s2, int N)
{
boolean b=true;
ArrayList<String> al=new ArrayList<String>();
ArrayList<String> bl=new ArrayList<String>();
al.addAll(getData(s1,N));
bl.addAll(getData(s2,N));
al.retainAll(bl);
if(al.size()==0)
{
b=false;
}
//System.out.println(b);
return b;
}
public List<String> getData(String s,int n)
{
ArrayList<String> temp=new ArrayList<String>();
temp.clear();
String myStr=Arrays.toString(s.split("(?<=\\G.{4})"));
//System.out.println(myStr);
Scanner sc=new Scanner(myStr).useDelimiter(",");
while(sc.hasNext())
{
String my=sc.next().replaceAll("\\W", "");
//System.out.println(my);
temp.add(my);
}
return temp;
}
}
Out Put:
Student Cheated
import java.io.InputStreamReader;
import java.util.Scanner;
public class Cheaters {
String s1,s2;
int n;
Scanner x;
public static void main(String[] args) throws Exception {
Cheaters c=new Cheaters();
System.out.println("Student"+" "+c.find()+" "+"in exam");
}
String find() throws Exception
{
String result="";
x=new Scanner(new InputStreamReader(System.in));
System.out.println("enter first string");
s1=x.nextLine();
System.out.println("Enter size of n");
n=Integer.parseInt(x.nextLine());
System.out.println("enter second string");
s2=x.nextLine();
int count=0,t=0;
for(int i=0;i<s1.length()&&i<s2.length();i++)
{
if(s1.charAt(i)==s2.charAt(i))
{
count++;
if(count==n)
{
t=1;
break;
}
}
else
{
count=0;
}
}
if(t==1)
{
result="cheated";
}
else
{
result="did not cheat";
}
return result;
}
}
ublic class unique {
public static boolean hadCheated(String str1,String str2, int num){
char[] ch1= str1.toCharArray();
char[] ch2= str2.toCharArray();
for(int i=0; i< str1.length();i++){
int temp =i;
for(int j=0; j<num; ){
if(ch1[i]==ch2[j]){
j++;
i++;
}else {
i = temp;
break;
}
if(j==(num))
return true;
}
}
return false;
}
public static void main(String[] args) {
String s1 = "amitkumar";
String s2 = "mitk";
System.out.println(hadCheated(s1, s2, s2.length()));
}
}
a DP solution where it coputes results in O(nm) and BigOmega(nm). Using Java
package com.dinesh.cup.stringcheated;
//TODO ::
public class StringCheated {
public static void main(String[] args) {
String a = "asdsasad ds sada sd asd sad hello world im a cat";
String b = "gfh hfgh h gfh gfhgh Yello world im not a cat gfhgfhgf ghgf gh";
System.out.println(hasCopied(a,b, 10));
System.out.println(hasCopied(a,b, 13));
System.out.println(hasCopied(a,b, 17));
}
private static boolean hasCopied(String a, String b, int len) {
int[][] copyMatrix = new int[a.length()][b.length()];
for (int i=0; i<a.length(); i++) {
for (int j=0; j<b.length(); j++) {
if (a.charAt(i) == b.charAt(j)) {
int prevValue = 0;
if (i>0 && j>0) {
prevValue = copyMatrix[i-1][j-1];
}
int newValue = prevValue + 1;
copyMatrix[i][j] = newValue;
if (newValue > len) {
System.out.print(a.substring(i-len, i) + " : ");
return true;
}
}
}
}
return false;
}
}
import java.util.HashSet;
import java.util.Set;
public class FindSUbStringOfSomeInputLength {
public static void main(String[] args) {
// TODO Auto-generated method stub
FindSUbStringOfSomeInputLength find=new FindSUbStringOfSomeInputLength();
String s1="adsfgdsfjhgdsahjagjhds4234gjagsadsasdasdhj";
String s2="sdfsadfasqadcxzxdfa4234sdas";
int N=4;
find.hasCheated(s1,s2,N);
}
private boolean hasCheated(String s1, String s2, int n) {
Set<String> set=new HashSet<String>();
char stringFirst[]=s1.toCharArray();
char stringSecond[]=s2.toCharArray();
int arrayLength=stringFirst.length;
boolean flag=false;
for(int i=0;i<=arrayLength-n;i++)
{
set.add(new String(stringFirst,i,n));
}
arrayLength=stringSecond.length;
for(int i=0;i<=arrayLength-n;i++)
{
String s=new String(stringSecond,i,n);
if(set.contains(s))
{
System.out.println("Cheated : "+s);
flag=true;
}
}
return flag;
}
}
It is important to distinguish between substring or subsequence. If it is substring and we can't use any of the std libraries then we can use any of the substring search algorithms: KMP, Rabin-Karp etc...
- Anonymous February 25, 2014If it is subsequence search then we use the classic LCS algorithm as posted above.