Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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;
}
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.
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!
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));
}
}
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 Absolutely right. I had the same solution as you except I accidentally placed the punctuation check outside the main loop.
It is better to check if a character is NOT a letter than to check if it IS whitespace or punctuation.
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.
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");
}
}
#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);
}
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;
}
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;
}
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]
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();
}
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();
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);
}
}
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");
}
}
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;
}
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.
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;
}
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;
}
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;
}
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;
}
#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!
1> Setup two pointers Left and Right to the start/end of the string.
- chenlc626 March 21, 20132> 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.