Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

1> Setup two pointers Left and Right to the start/end of the string.
2> If Left is white space or punctuation char, move Left to another non whitespace and non punctuation char Left to it unless end of string. If Right is white space or punctuation char, move Right to the another non white space and non punctuation char Right to it unless start of string. If Left>=Right, return TRUE. (Either all are whitespace or punctuation key or only one non whitespace and punctuation key).
3> Other compare LOWERCASE(*Left) and LOWERCASE(*Right), if they are the same, go to 2>. Otherwise return FALSE.

- chenlc626 March 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Function Call :
isPalandrome(str.toLowerCase()

boolean isPalandrome(String s) {
		int strLength = s.length();
		
		if(strLength == 0 || s == null)
			return false;
		int start	= 0;
		int end		= strLength - 1;
		
		while(start < end) {
			
			while(!isAlphabet(s.charAt(start)) && start <= end)
				start++;
			while(!isAlphabet(s.charAt(end)) && start <= end)
				end--;
			if(s.charAt(start) == s.charAt(end)) {
				start++;
				end--;
			} else {
				return false;
			}

		}
		
		return true;
	}

- Vijay March 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can make your code a little more concise by changing your inner "while" statements to be "if" statements and use "continue" when they evaluate to true (after either incrementing start or end, respectively). If you do this, you can avoid the "start <= end" checks.

This sounds like nitpicking, but the deeper benefit is that you could reason about the outer loop more easily. If every time through the loop the code only ever adjusts the pointers by one (or returns), it's a little easier for a reader to reason their way through your code, not only in terms of correctness, but also in terms of O(N) time.

Having said that, it's a nice, solid, clear implementation.

- showell30@yahoo.com March 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The code throws exception when all characters are whitespace. like ",,,,,"
I think when strLength == 0 the code should return true. Also you can change start <= end to start < end
Thanks!

- Pooyo April 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You should also check for lower/upper case discrepancies in the last if statement.

e.g. if inputString[start].lower() == inputString[end].lower():

- gillian.p.tee April 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;

public class Palin {

  public static void main(String args[]) {
	String original = "A man, a plan, a canal: Panama.";
	String c1 = "", c2 = "";

	Set<Character> set = new HashSet<Character>(Arrays.asList('.', ';', ' ', ',', ':'));

	for (char c : original.toLowerCase().toCharArray()) {
	   if (set.contains(c)) continue;
	   c1 = c1 + c;
	   c2 = c + c2;
        }

	System.out.println(c1);
	System.out.println(c2);

	System.out.println(c1.equals(c2));
  }

}

- Eddie March 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Your code runs in O(N squared) time and uses O(N) storage. It can be solved almost as easily in O(N) time and O(1) space. Maintain two string indexes, one moving forward from the front and one moving backward from the end, and keep comparing them until you have a mismatch, at which point you can immediately return false. Terminate and return true if and when the pointers meet.

(It runs in O-squared time, because inside your O(N) loop each call to "c1 = c1 + c" has to copy O(N) characters, due to Java using immutable strings.)

- showell30@yahoo.com March 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@showell30 Absolutely right. I had the same solution as you except I accidentally placed the punctuation check outside the main loop.

- Barry Fruitman March 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is better to check if a character is NOT a letter than to check if it IS whitespace or punctuation.

- Barry Fruitman March 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Barry, I almost made the exact same comment that you did, but the question does state "ignore any whitespace or punctuation." So, if you take the formulation at face value, you can't simply whitelist alphas, since there are plenty of non-alpha characters that pass the criteria (namely, digits). Good thing to clarify with the interviewer, of course.

- showell30@yahoo.com March 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;

class Palindrome {
	public static void main(String args[]) {

		String string = "A man, a plan, a canal: Panama.";
		String str = string.toLowerCase();

		int start = 0;
		int end  = str.length() - 1;

		Set<Character> set = new HashSet<Character>(Arrays.asList('.', ';', ' ', ',', ':'));

		while (start < end) {	
			char cStart = str.charAt(start);
			char cEnd = str.charAt(end);
			if (set.contains(cStart)) { 
				start++;
				continue;
			}
			if (set.contains(cEnd))  {
				end--;
				continue;
			} 
			if (cStart != cEnd) 
				break;
			start++;
			end--;
		}
	
		if (start < end) 
			System.out.println("String is not palindrom");
		else 
			System.out.println("String is palindrom");
	}
}

- PCB March 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>

int strlen(char *p)
{
	int len=0;
  while(*p++!='\0')
    len++;
  return(len);
}
   
int main()
{
 int strlen(char* p);
  	
 int i,len;
 char str[50];
 // two ptrs to point for beg & end of string str
 char *f,*s;
 
 //read string -- a line of text
 puts("enter a line : ");
 gets(str);
 
 //display given line
 puts("\ngiven line is : ");
 puts(str);
 
 len=strlen(str);
 printf("\nline length is : %d \n",len);
 
 f=str;
 s=&str[len-1];
 
 //checking for palindrome
 for(i=0;i<(len/2);i++)
 {  
	 // check for 1st ptr value is a char or not
	if(((((int)*f>=65)&&(int)*f<=90)||((int)*f>=90&&(int)*f<=122)))
	{
		// check for 2nd ptr value is a char or not
	  if((((int)*s>=65&&(int)*s<=90)||((int)*s>=90&&(int)*s<=122)))
		{
		  // compare both char values
	     if(!(*f=*s||*f==*s+32||*f==*s-32||*f+32==*s||*f-32==*s))
		  {
			 printf("false--not palindrome\n");
			 exit(1);
		  }
		 else
		  {
			 // both chars are same , so increment 1st ptr & decrement 2nd ptr
			 f++;
			 s--;
		  }	 
     	}
      else
       { 
			//	1st val is char but 2nd val is not a char
			// so decrement one addresss of 2nd ptr
			s--;
	   }		  
   	}
   	else 	
   	{
		// 1st ptr is not a char so check for 2nd val is char or not
		if(((int)*s>=65&&(int)*s<=90)||((int)*s>=90&&(int)*s<=122))
		{
			// 1st val is not a char  & 2nd val is a char
               f++;
        }
       else
       {
		   // 1st val & 2nd val both r not chars
		    f++;
		    s--;
	   }
	}        
  
 } // end of for 
 printf("true--given string is a palindrome\n");
			
 return(0);
}

- venky March 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean palindrome?(String s)
{

if (s==Null)
	return False;
int strLen = s.length();

// Return true if given string is one charachter long
if (strLen==1)
	return True;


// delete all char beyond ascii of a-z
s.sanitize();
//convert all char to lower case
s.tolowercase();

int leftPtr =0;
int rghtPtr =0;

if(strLen%2==0)
{
	leftPtr=strLen/2 - 1;
	rghtPtr= leftPtr + 1;
}
else 
{
	leftPtr=strLen/2 - 1;
	rghtPtr= leftPtr + 2;
}

while(leftPtr <= 0 && rghtPtr > strLen)
{
	if(s[leftPtr].equals(s[rghtPtr]))
  	{
		leftPtr--;
		rghtPtr++;
	}
	else 
	return False;
}
return True;
}

- akhil March 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

boolean palindrome?(String s)
{
// delete all char beyond ascii of a-z
s.sanitize();
//convert all char to lower case
s.tolowercase();

if (s==Null)
	return False;
int strLen = s.length();

// Return true if given string is one charachter long
if (strLen==1)
	return True;

int leftPtr =0;
int rghtPtr =0;

if(strLen%2==0)
{
	leftPtr=strLen/2 - 1;
	rghtPtr= leftPtr + 1;
}
else 
{
	leftPtr=strLen/2 - 1;
	rghtPtr= leftPtr + 2;
}

while(leftPtr <= 0 && rghtPtr > strLen)
{
	if(s[leftPtr].equals(s[rghtPtr]))
  	{
		leftPtr--;
		rghtPtr++;
	}
	else 
	return False;
}
return True;
}

- Anonymous March 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

// delete all char beyond ascii of a-z
s.sanitize();
//convert all char to lower case
s.tolowercase();

should be before strLen is initialized.

- Anonymous March 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def is_palindrome(string):
     if not string:
         return false
     black_list = [",", ".", ":", " ", ";"]
     for c in black_list:
         string = "".join(string.split(c))
     string = string.lower()
     return string==string[::-1]

- ericgmconrado March 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Python, really nice and simple for ya =)

- ericgmconrado March 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

def is_palindrome(string):
     string = ''.join(filter(lambda c: c.islower(), string.lower()))
     return string==string[::-1]

- Anonymous April 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static boolean isPalindrom(String originalString, Set<Character> ignoreCharacters){
		String manipulatedString = removeSpecialCharacters(originalString.toString().toLowerCase(), ignoreCharacters);
		int length = manipulatedString.length();
		int traverseIndex = length/2 ;
		
		for ( int startIndex = 0; startIndex < traverseIndex ; startIndex ++){
			char char1 = manipulatedString.charAt(startIndex);
			char char2 = manipulatedString.charAt( (length -1) - startIndex );
			if ( char1 != char2 ){
				return false;
			}
		}
		
		return true;
		
	}
	
	private static String removeSpecialCharacters(String orginalString, Set<Character> ignoreCharacters){
		int length = orginalString.length();		
		StringBuilder tagettedString = new StringBuilder();
		for ( int startIndex = 0; startIndex < length ; startIndex ++){
			char ch = orginalString.charAt(startIndex); 
			if (!ignoreCharacters.contains(ch)){
				tagettedString.append(ch);
			}
		}		
		return tagettedString.toString();
		
	}

- Madhav April 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about this one? For Javascript.

String.prototype.isPalindrome = function(){
    var o = this.sanitize();
    var s = this.simple_reverse().sanitize();
    alert(o + " = " + s + "\n" + (o == s));     
};

String.prototype.sanitize = function(){
    return this.replace(/[^a-zA-Z]+/g, '').toLowerCase();   
};

String.prototype.simple_reverse = function(){
    return this.split('').reverse().join('');
};

"Doc Note: I dissent. A fast never prevents a fatness. I diet on cod".isPalindrome();

- Stephen May 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a recursive solution to the problem:

/**
 * Write a function that takes a string and returns true if the entire string is a palindrome, 
 * otherwise return false. The function should be case-insensitive and ignore any whitespace or punctuation. 
 * 
 * For example, return true for: 
 * "A man, a plan, a canal: Panama."
 * @author patrick
 *
 */
public class PalindromeAdv {
	
	private static final char START = 'A';
	private static final char END = 'Z';
	
	public static void main(String[] args) {
		String text = "A man, a plan, a canal: Panama.";
		
		System.out.println(text + " -> " + isPalindromeRecursive(text.toUpperCase().toCharArray(), 0, text.length()-1));
	}
	
	public static boolean isPalindromeRecursive(char[] text, int start, int end) {
		if(start>=end)
			return true;
		
		char b = text[start];
		if(!isValidChar(b)) {
			return isPalindromeRecursive(text, start+1, end);
		}
		char e = text[end];
		if(!isValidChar(e)) {
			return isPalindromeRecursive(text, start, end-1);
		}
		return b!=e ? false : isPalindromeRecursive(text, start+1, end-1);
	}

	private static boolean isValidChar(char c) {
		return (c>=START && c<=END);
	}
}

This is an iterative solution for the problem

/**
 * Write a function that takes a string and returns true if the entire string is a palindrome, 
 * otherwise return false. The function should be case-insensitive and ignore any whitespace or punctuation. 
 * 
 * For example, return true for: 
 * "A man, a plan, a canal: Panama."
 * @author patrick
 *
 */
public class PalindromeAdv {
	
	private static final char START = 'A';
	private static final char END = 'Z';
	
	public static void main(String[] args) {
		String text = "A man, a plan, a canal: Panama.";
		
		System.out.println(text + " -> " + isPalindrome(text));
	}

	public static boolean isPalindrome(String text) {
		if(text == null)
			return false;
		if(text.length()<=1)
			return true;
		
		char[] letters = text.toUpperCase().toCharArray();
		
		int k = text.length()-1;
		
		for(int i=0; i<text.length(); i++) {
			char beginning = letters[i];
			if(isValidChar(beginning)) {
				char ending = letters[k];
				while(!isValidChar(ending)) {
					k--;
					ending = letters[k];
				}
				if(k<=i)
					return true;
				
				if(beginning != ending)
					return false;
				k--;
			}
		}
		
		return false;
	}
	
	private static boolean isValidChar(char c) {
		return (c>=START && c<=END);
	}
}

- diloreto.p June 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Palindrome {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		String str = "A man, a plan, a canal: Panama.";

		StringBuilder sb = new StringBuilder();
		char c;

		for (int i = 0; i < str.length(); i++) {
			c = str.charAt(i);
			if (c == ':' | c == ',' | c == ' ' | c == '.')
				continue;
			sb.append(c);
		}
		str = sb.toString().toLowerCase();

		int length = str.length();
		for (int i = 0; i < length; i++) {

			if (str.charAt(i) == str.charAt(length - i - 1))
				continue;
			else {
				System.out.println("Not a Palindrome");
				length = -1;
				break;
			}
		}

		if (length != -1)
			System.out.println("Hope this is a palindrome");
	}

}

- vins July 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Somebody tell me what is the complexity of this piece of code. And let me know if any suggestions for improvements in perfomance.

- vins July 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isPalindrome(String stext){
		 char [] chs=stext.toCharArray();
		 int i=0;
		 int j=chs.length-1;
		 boolean found=false;
		 for (;i<j;++i,--j){
			while (!isChar(chs[i])){
				i++;
			}
			
			
			while (!isChar(chs[j])){
				j--;
			}
			
			if (Math.abs(chs[i]-chs[j])==32||Math.abs(chs[i]-chs[j])==0){
				found=true;
			}else{
				found=false;
			}
		 }
		return found;
	}
	
	
	public static boolean isChar(char ch){
		if ((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){
			return true;
		}
		
		return false;

}

- Anonymous July 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A one liner ruby code:

string = "A man, a plan, a canal: Panama."

if string.downcase.gsub(/\W/, '') == string.downcase.gsub(/\W/, '').reverse
  puts "Palindrome!"
end

- Juan Brein July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Split the string in half, or into even parts ignoring the middle character if the length is odd. Then push the first half onto a stack, ignoring whitespace/punctuation. Then pop the stack and test against every character in the second half, again ignoring whitespace/punctuation. If there is mismatch return false.

- Ben October 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isValid(char c) {
    return c >= 'a' && c <= 'z' && c >= 'A' && c <= 'Z';
}
bool isPal(string s) {
    int len = s.length();
    int l = 0, r = len - 1;
    while (l <= r) {
        while (l + 1 <= r && !isValid(s[l])) {
            l++;
        }
        while (r - 1 >= l && !isValid(s[r])) {
            r--;
        }
        if (!isValid(s[l]) ^ !isValid(s[r])) {
            return false;
        }
        if (isValid(s[l]) && isValid(s[r])) {
            if (s[l] != s[r]) return false;
        }
        l++;
        r--;
    }
    return true;
}

- MatRush November 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh... I'm stupid...

bool isValid(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}
bool isPal(string s) {
    int len = s.length();
    int l = 0, r = len - 1;
    while (l <= r) {
        while (l + 1 <= r && !isValid(s[l])) {
            l++;
        }
        while (r - 1 >= l && !isValid(s[r])) {
            r--;
        }
        if (!isValid(s[l]) ^ !isValid(s[r])) {
            return false;
        }
        if (isValid(s[l]) && isValid(s[r])) {
            if (tolower(s[l]) != tolower(s[r])) return false;
        }
        l++;
        r--;
    }
    return true;
}

- MatRush November 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

2 lines

String palindrome = "A man, a plan, a canal: Panama."
boolean isPalindrome = palindrome.replaceAll("[^A-Za-z]", "").toLowerCase().equals(new StringBuilder(palindrome.replaceAll("[^A-Za-z]", "").toLowerCase()).reverse().toString());

- xd November 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The following is written in Objective-C

- (BOOL)isPalindromeIgnoreALot:(NSString *)string {
    BOOL isPalindrome = YES;
    NSString *lowercaseString = [string lowercaseString];
    NSString *purewordString = [[lowercaseString componentsSeparatedByCharactersInSet:[NSCharacterSet punctuationCharacterSet]] componentsJoinedByString:@""]; // remove punctuation
    purewordString = [[purewordString componentsSeparatedByCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]] componentsJoinedByString:@""]; // remove white space and new line
    if (purewordString) {
        NSInteger length = [purewordString length];
        NSInteger halfLength = (length / 2);
        for (int i = 0; i < halfLength; i++) {
            if ([purewordString characterAtIndex:i] != [purewordString characterAtIndex:length - i - 1]) {
                isPalindrome = NO;
                break;
            }
        }
    }
    
    return isPalindrome;
}

- Senry December 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This code will be ok.

bool Skip(char ch) {
  if (ch >= 'A' && ch <= 'Z' ||
      ch >= 'a' && ch <= 'z' ||
      ch >= '0' && ch <= '9') return false;
  return true;
}

char Lower(char ch) {
  if (ch >= 'A' && ch <= 'Z') return 'a' + ch - 'A';
  return ch;
}

bool IsPalindrome(std::string s) {
  int b = 0;
  int e = s.size() - 1;
  while (b < e) {
    if (Skip(s[b])) b++;
    else if (Skip(s[e])) e--;
    else if (Lower(s[b]) != Lower(s[e])) return false;
    else {
      b++;
      e--;
    }
  }
  return true;
}

- guoliqiang2006 December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
bool IsPalindrome(char str[])
{

    
    long len = strlen(str);
    char* start;
    char* end;
    start = str;
    end = &str[len-1];
    
    for(int i = 0; i < len/2; i++)
    {

        if(((int)*start>=65 && (int)*start <= 90) || ((int)*start >= 97 && (int)*start <= 122))
        {
            if(((int)*end>=65 && (int)*end <= 90) || ((int)*end >= 97 && (int)*end <= 122))
            {
                
                if(*start == *end || *start+32 == *end || *start-32 == *end || *start == *end+32 || *start == *end-32)
                {
                    start++;
                    end--;
                }
                else
                    
                {
                    return false;
                }
            }
            else
            {
                end--;
            }
            
        }
        else
        {
            start++;
        }
        
    }
    
   
    return true;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    char str[] = "A Man, A Plan, A Canal – Panama!";
    if(IsPalindrome(str))
        puts("Yes It is");
    else
        puts("No It is not");
    return 0;
}

//Other Test Strings
//A dog, a panic in a pagoda!
//A car, a man, a maraca!

- hm January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i found this in github.
rmariuzzo / palindrome.js
pretty amazing code written in JS. Takes care of all the scenario mentioned in the requirements.

- Venkit January 19, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More