## Facebook Interview Question for SDE1s

• 0

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

I think that the "catch" here is to implement the match function, so solutions that uses built-in match functions like - grep,contains etc misses the point (in my opinion).

And the objective, as I see it is to find an efficient solution for the matching function.

We can go char by char as stated in a few solutions above and simply compare, that will have us compare all the characters in the input strings with all the characters in the pattern.

I would go at it in a bit different approach and compare in bulks, by using a hashing function on the pattern.

The idea is to calculate the hash (for example sum(2^ASCII(char))) value of the searched pattern and then calculate the same hash value for each "bulk" in the input string. We then can use the notion that the hash value of the N chars we calculated can be composed of hash(N-1) + hash(N), so by calculating this first, to calculate the next hash we only need to subtract N-len(pattern) and add N+1 hash to get the new hash for the comparison.
And only if the hash matches we can verify by matching with comparison of the string.

Complexity of the above is O(n) , since we go over the entire input once and do 2 calculations - O(1) , for each comparison.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use shell script (If working environment is Linux). This is very simple & efficient. You can easily parse through numerous strings.

str_list=( "crane" "grain" "Insane" )
for i in "\${str_list[@]}"
do
echo "\$i" | grep '.*an.*'
done

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray<NSString *> *strings = @[@"crane", @"drain", @"refrain"];
NSPredicate *predicate = [NSPredicate predicateWithFormat:@"SELF CONTAINS[cd] 'an'"];

NSArray *result = [strings filteredArrayUsingPredicate:predicate];
NSLog(@"%@", [result firstObject]);
}
return 0;
}``````

This is how I would do this, I don't know if it's "Efficient"

Comment hidden because of low score. Click to expand.
0
of 0 vote

str_list=( "crane" "grain" "Insane" )
for i in "\${str_list[@]}"
do
echo "\$i" | grep '.*an.*'
done

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static boolean isMatch(String pattern, String word) {
boolean match = false;
if(!pattern.contains("*")){
return word.contains(pattern);
}
else{
char[] chArr = pattern.toCharArray();
boolean isprevW  = false;
boolean isnextW = false;
int patternindex = 0;
int wordindex = 0;
char[] wArr = word.toCharArray();
boolean matchchar = false;

while(patternindex < chArr.length && wordindex < wArr.length){
if(chArr[patternindex] == '*'){
isprevW = true;
patternindex++;
continue;
}
if(isprevW || isnextW){
if(chArr[patternindex] == wArr[wordindex]){
patternindex++;
if(isprevW)isprevW = false;
if(isnextW)isnextW = false;
wordindex++;
match = true;
matchchar = true;
}
else{
wordindex++;
match = false;
}
}
else{
if(chArr[patternindex] == wArr[wordindex]){
patternindex++;
wordindex++;
match = true;
matchchar = true;
}
else{
if(matchchar){
return false;
}
if(patternindex+1 < chArr.length){
if(chArr[patternindex+1] == '*'){
isnextW = true;
wordindex++;
}
else{
return false;
}
}
}
}
}
}
return match;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static boolean isMatch(String pattern, String word) {
boolean match = false;
if(!pattern.contains("*")){
return word.contains(pattern);
}
else{
char[] chArr = pattern.toCharArray();
boolean isprevW  = false;
boolean isnextW = false;
int patternindex = 0;
int wordindex = 0;
char[] wArr = word.toCharArray();
boolean matchchar = false;

while(patternindex < chArr.length && wordindex < wArr.length){
if(chArr[patternindex] == '*'){
isprevW = true;
patternindex++;
continue;
}
if(isprevW || isnextW){
if(chArr[patternindex] == wArr[wordindex]){
patternindex++;
if(isprevW)isprevW = false;
if(isnextW)isnextW = false;
wordindex++;
match = true;
matchchar = true;
}
else{
wordindex++;
match = false;
}
}
else{
if(chArr[patternindex] == wArr[wordindex]){
patternindex++;
wordindex++;
match = true;
matchchar = true;
}
else{
if(matchchar){
return false;
}
if(patternindex+1 < chArr.length){
if(chArr[patternindex+1] == '*'){
isnextW = true;
wordindex++;
}
else{
return false;
}
}
}
}
}
}
return match;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void findWordsByPattern (String[] inputStrings, String pattern)
{
String regex = pattern.replace("*", ".*");
for (String s: inputStrings)
{
if (Pattern.matches(regex, s))
{
System.out.println(s);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Scala

``````object PatternMatch extends App {

println(pmatch("*an*", List("crane", "drain", "refrain")))

def pmatch(p: String, strings: List[String]): List[String] = {
strings.filter { str =>
var si = 0
var pi = 0
var hit = false // set to true if we hit a last * in the pattern
while (si < str.length && pi < p.length && !hit) {
if (p(pi) == '*') {
if (pi < p.length - 1 && p(pi + 1) == str(si)) {
pi += 1
} else if (pi == p.length - 1) {
pi += 1
hit = true
} else {
si += 1
}
} else if (p(pi) == str(si)) {
pi += 1
si += 1
} else {
pi = 0
si += 1
}
}
// the full pattern was matched
pi == p.length ||
// allows * to match empty character as the final character in the pattern
(pi == p.length - 1 && p.last == '*')
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static String getMatchingWordFromList (List<String> inputList,String pattern) {

String output = "";
char[] patternArray = pattern.toCharArray();
char[] realCharsArray = new char[patternArray.length -2];

for(int i=1;i<patternArray.length-1;i++) {
realCharsArray[i-1] = patternArray[i];
}

for(String input: inputList) {
int k=0;
char[] inputArray = input.toCharArray();
for(int i=0;i<inputArray.length;i++){
if(i!=inputArray.length-1 && inputArray[i]==realCharsArray[k] && inputArray[i+1]==realCharsArray[k+1]) {
//return input; but since not a good practice
output = input;
break;
}
}
if(output!=""){
break;
}
}

return output;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static String getMatchingWord(List<String> inputList,String pattern) {
final String newPattern = pattern.replace("*",".*");
return inputList.stream().filter(input-> input.matches(newPattern)).findAny().get();``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String args[])
{

String pattern="*an*";
String enPattern=encodeString(pattern);
String word="xyanxvsdanf";
String enWord=encodeString(word);

System.out.println(enPattern+" "+enWord);

int v1=Integer.parseInt(enPattern);
int v2=Integer.parseInt(enWord);
System.out.println(" % :"+ v2%v1);
if(v2%v1 !=0){
System.out.println("not matched");
}  else {
System.out.println(" matched");
}

}

static String encodeString(String x){

String output="";
for(int i=0;i<x.length();i++){

// *an* == 0110
char c=x.charAt(i);
if(c=='n'|| c=='a'){
output +="1";
} else {
output +="0";
}
}
return output;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.