Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
public boolean isPalindrome(String str) {
if (str.length() <= 1)
return true;
return (str.charAt(0) == str.charAt(str.length() - 1))
&& isPalindrome(str.substring(1, str.length() - 1));
}
u should put Str.length()<=2 , otherwise it will fail. Please check with Str value as "malyalam"
My solution in place and O(n) running time
/**
* Created by sky on 16/04/15.
*/
public class InPlacePalindromeCheck {
public static void main(String[] args) {
String word = "A man, a plan, a canal, Panama";
System.out.println(isPalindrome(word));
}
private static boolean isPalindrome(String word) {
boolean ret = true;
int i = 0;
int j = word.length() -1;
while (j > i) {
if (!Character.isDigit(word.charAt(j))) {
j--;
continue;
}
if (!Character.isDigit(word.charAt(i))) {
i++;
continue;
}
if (word.charAt(i) != word.charAt(j)) {
ret = false;
break;
}
j--;
i++;
}
return ret;
}
}
public static boolean isPalindrome(String s) {
if (s == null || s.length() == 0) {
return false;
}
if (s.length() == 1) {
return true;
}
char[] c1 = s.toCharArray();
int mid = c1.length/2;
int i = mid - 1;
int j = c1.length % 2 == 0 ? mid : mid + 1;
while(i > 0 && j < c1.length && c1[i] == c1[j]) {
i--;
j++;
}
return (i == 0);
}
This is done with a 2 pointer method, assuming you want the ENTIRE string to be a palindrome. That makes it quick and easy.
Just iterate forward from the start of the string, and backwards from the end of the string at the same rate, comparing the two pointers values at each iteration. This also automatically solves the odd-length edge case that can occur (which many people often write an extra conditional statement for)
In python:
def is_palindrome(word):
for i in range(0, len(word)/2):
if word[i] != word[len(word) - 1 - i]:
return False
return True
Runs O(n) time (actually n/2 but you get the idea) and uses no external data structures.
This also returns True for an empty string or 1 char string, as an empty or 1 char will always be symmetrical.
Here is my solution insensitive to char case with test cases:
public class PalindromInplaceCheck {
private static boolean isPalindrome(String text){
int length = text.length();
for(int i = 0; i < length; i++)
if(Character.toLowerCase(text.charAt(i)) != Character.toLowerCase(text.charAt(length - i - 1)))
return false;
return true;
}
public static void main(String [] args){
String testString1 = new String("common");
System.out.println(testString1 + " is a palindrom: " + isPalindrome(testString1));
String testString2 = new String("palIndromoRdniLap");
System.out.println(testString2 + " is a palindrom: " + isPalindrome(testString2));
String testString3 = new String("a");
System.out.println(testString3 + " is a palindrom: " + isPalindrome(testString3));
String testString4 = new String("");
System.out.println(testString4 + " is a palindrom: " + isPalindrome(testString4));
String testString5 = new String("abBa");
System.out.println(testString5 + " is a palindrom: " + isPalindrome(testString5));
String testString6 = new String("cdc");
System.out.println(testString6 + " is a palindrom: " + isPalindrome(testString6));
}
}
The fastest check if it is palindrome from stdin in the west:
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
#define PALINDROME_SIZE 100
int main(int argc, char *argv[])
{
» char p[PALINDROME_SIZE], c;
» size_t i = 0, j, half;
» bool palindrome = true;
» while ((c = getchar()) != EOF && c != '\n' && i < PALINDROME_SIZE)
» » if (isalpha(c))
» » » p[i++] = tolower(c);
» half = i / 2;
» for (j = 0; j < half; j++) {
» » if (p[j] != p[i - 1 - j]) {
» » » palindrome = false;
» » » break;
» » }
» }
» printf("\t%s\n", palindrome ? "Palindrome" : "Not Palindrome");
» return 0;
}
- Anonymous April 16, 2015