Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
vector<int> prefixtable(string p){
vector<int> temp;
int i=1,j=0;
while(i<p.length()){
if(p[i] == p[j]){
temp.push_back(j+1);
i++;
j++;
}
else if(j>0){
j = temp[j-1];
}
else{
temp.push_back(0);
i++;
}
}
return temp;
}
int kmp(vector<int> temp,string s,string p){
int i=0,j=0;
while(i<s.length()){
if(s[i] == p[j]){
if( j == p.length()-1)
return (i-j);
else{
i++;
j++;
}
}
else if(j > 0){
j = temp[j-1];
}
else{
i++;
}
}
return -1;
}
int main(){
string s,p;
cin>>s>>p;
vector<int> prefix = prefixtable(p);
// for(int i=0;i<prefix.size();i++)
// cout<<prefix[i]<<" ";
// cout<<endl;
cout<<kmp(prefix,s,p)<<endl;
return 0;
}
public class NeedleInHaystack {
private static String substractString (String source,int pos1, int pos2)
{
String ret="";
for (int i=pos1;i<pos2+1;i++)
{
ret=ret + source.charAt(i);
}
return ret;
}
private static int findNeedleInHaystack(String haystack,String needle)
{
int ret=-1;
boolean found=false;
for (int i=0;i<haystack.length() && !found;i++)
{
if (haystack.charAt(i)==needle.charAt(0))
{
String hayStackSubstract=substractString(haystack,i,i+needle.length()-1);
if (hayStackSubstract.equalsIgnoreCase(needle))
{
ret=i;
found=true;
}
}
}
return ret;
}
public static void main(String[] args)
{
if (args.length==2)
{
String hayStack=args[0];
String needle=args[1];
System.out.println("hayStack=" + hayStack );
System.out.println("needle=" + needle );
int needlePosition=findNeedleInHaystack(hayStack,needle);
System.out.println(" The needle position is "+needlePosition);
}
else{
System.out.println("Please provie both haystack and needle value");
}
}
}
KMP
void Next(char * p, std::vector<int> & next) {
int n = strlen(p);
if (p == 0) return;
next.resize(n, 0);
int i = 0;
next[i] = -1;
int k = next[i];
while (i < n) {
while (k >= 0 && p[i] != p[k]) k = next[k];
i++;
k++;
if (i == n) break;
if (p[i] == p[k]) next[i] = next[k];
else next[i] = k;
}
}
char * KMP(char *s, char * p) {
int s_len = strlen(s);
int p_len = strlen(p);
if (p_len == 0) return s;
std::vector<int> next;
Next(p, next);
int i = 0;
int j = 0;
while (i < s_len) {
if (s[i] == p[j]) {
i++;
j++;
} else j = next[j];
if (j == p_len) return s + i - p_len;
if (j == -1) {
i++;
j++;
}
}
return NULL;
}
/*
Implement indexOf function to find a substring from a given string
So, implement indexOf(String str) from index 0
Can use KMP as well for O(n) time complexity...
Salesforce interview question
Facebook question "find needle in haystack"
*/
public static int indexOf(String str, String substring)
{
char[] strArray = str.toCharArray();
char[] subArray = substring.toCharArray();
char first = subArray[0];
int max = (strArray.length - subArray.length);
for (int i = 0; i <= max; i++) {
/* Look for first character of the substring in the original. */
if (strArray[i] != first) {
while (++i <= max && strArray[i] != first);
}
/* Found first character (i is now at the start of substring in original string), now look at the rest of v2
* to make sure the whole substring is in the string */
if (i <= max) {
int j = i + 1;
int end = j + subArray.length - 1; //the end index of the substring in the original string
for (int k = 1; j < end && strArray[j] == subArray[k]; j++, k++);
if (j == end) {
/* Found whole string. */
return i;
}
}
}
return -1;
}
public static int findNeedleInHaystack(String haystack, String needle){
int ret = -1;
int itr = 0;
int needleLen = needle.length();
int max = haystack.length() - needle.length();
while (itr <= max){
String inspectString = haystack.substring(itr, itr + needleLen);
if (inspectString.equals(needle)){
ret = itr;
break;
}
itr++;
}
return ret;
}
Fairly certain this is O(n) time. Can definitely be optimized by KMP.
KMP is optimal worst case complexity, hashing is very practical and easy to code, I would start with that.
m = needle.length();
hash function f would be for the form
f(c1c2...cm) = (c1x^(m-1) + c2x^(m-2) + ... + cm) % D where x and D are primes
// precompute x^j for j < m
f(i+1:m+i) = (f(i:m+i-1) - cix^(m-1))*x + c(m+i)
I can pass a moving window on haystack and compute hash(i:i+m-1) efficiently,
use that to filter out mismatches and fallback on character by character comparison when hash values match
Look at entropy of needle and decide on number of hash functions to use, more hash functions if needle has low entropy
int findSubstring(String haystack, String needle)
{
if(haystack.contains(needle))
return haystack.indexOf(needle);
else
return -1;
}
Are you guys serious?
Do you really think that this is the answer the interviewer is looking for?
Java and C#'s string class has "IndexOf" and the interviewer isn't asking you this question to test your knowledge of Java/C#'s String class.
Instead, you're supposed to implement the "IndexOf" method. You need to actually search the string and find the index of the "needle".
Look up the KMP algorithm
Did they want some optimized solution (KMP/Rabin-Karp/FA)? Or you could just use a naive approach?
- dskut March 21, 2013