Facebook Interview Question
Software DevelopersCountry: UK
Interview Type: Phone Interview
Looks much cleaner than mine, thanks for comment on improving my code! feel like getting more professional now :)
Thanks for the comment on improving my code! :) Feel like getting more professional now~
do you need head < tail check for while loop also. With it, the method wud return false for A!#A ?
To Naomi: I'm glad I was able to help you! :) I failed interview at Yandex only because of a dirty coding. So, don't repeat my mistakes :) I think there is no appropriate books describing how to write well-readable code, though I would highly recommend you to take a look at trending github projects.
To Michael: You caught me! :) Edited
To Rams: If I correctly understood your question - we always need to check if head is less than tail, because we need to guarantee that charAt operation works with correct indices (they are positive and less that str.length()) F.e. for input "#!!#" if we won't check for "h < t", soon the head index will reach the end of the string and will get an Exception.
Because of it, both while loops contains this condition. It works correctly for input "A!#A".
bool isChar(char a) {
if ( a <= 'Z' && a >= 'A') {
return true;
}
if ( a <= 'z' && a >= 'a') {
return true;
}
return false;
}
bool isPalin(string input) {
int start = 0;
int end = input.length() - 1;
bool ok;
while (start < end) {
ok = false;
if ( isChar(input[start]) && isChar(input[end])) {
if (tolower(input[start]) == tolower(input[end]))
ok = true;
else
ok = false;
start ++;
end --;
} else if (isChar(input[start]) == false) {
ok = true;
start ++;
} else if ( isChar(input[end]) == false) {
ok = true;
end --;
}
if (ok == false)
return false;
}
return ok;
}
int main() {
string data_1= "ABA"; // is palindrome
string data_2 = "A!#A"; // is palindrome
string data_3 = "A man, a plan, a canal, Panama!"; // is palindrome
if (isPalin(data_3)) {
cout << "YES it is" << endl;
} else {
cout << "No its not" << endl;
}
}
def is_alpha_palindrome(str):
if not str:
return True
chars = str[:]
start, end = 0, len(chars) - 1
# The idea is to use 2 indexes and move index 1 from start to end and
# index 2 from end to start.
# Every time both indexes find a alpha char, those must be compared.
while True:
while start < len(chars) and not chars[start].isalnum():
start += 1
while end >= 0 and not chars[end].isalnum():
end -= 1
# If pointers crossed, no news chars to look at
if start > end:
return True
if chars[start].lower() != chars[end].lower():
return False
# Move both pointers ahead otherwise we will be in a infinite loop
start, end = start + 1, end - 1
public class CheckPalindrome {
private static boolean isLetterOrDigit(char ch){
return Character.isAlphabetic(ch) || Character.isDigit(ch);
}
public static boolean isPalindrome(String str){
if(str == null){
throw new IllegalArgumentException("String must be not null");
} else if(str.length() == 0 || str.length() == 1 ){
return true;
} else {
int left = 0, right = str.length() - 1;
while(left < right){
if(!isLetterOrDigit(str.charAt(left))){
left++;
} else if(!isLetterOrDigit(str.charAt(right))){
right--;
} else {
if(Character.toLowerCase(str.charAt(left)) == Character.toLowerCase(str.charAt(right))){
left++;
right--;
} else {
return false;
}
}
}
}
return true;
}
public static void main(String[] args) {
System.out.println(isPalindrome("ABA"));
System.out.println(isPalindrome("A!#A"));
System.out.println(isPalindrome("A!AB#A"));
System.out.println(isPalindrome("A man, a plan, a canal, Panama!"));
}
}
Trivial is to clean up the string before checking whether the cleaned string is palindrome
python:
#check palindrome skip non-alpha-numerical
def special_palindrome(s):
ret = True
cleaned = ''
for i in range(len(s)):
if s[i].isalpha() or s[i].isdigit():
cleaned += s[i]
return palindrome(cleaned)
def palindrome(s):
for i in range(len(s)/2):
if s[i] != s[len(s)-i-1]:
return False
return True
So sorry, didn't read the question correctly. Without copying the string, here's my solution using iterative pointers in python.
#check palindrome skip non-alpha-numerical
def special_palindrome(s):
idx1 = 0
idx2 = len(s)-1
while idx1 < idx2:
if not (s[idx1].isalpha() or s[idx1].isdigit()):
idx1 += 1
continue
if not (s[idx2].isalpha() or s[idx2].isdigit()):
idx2 -= 1
continue
if not s[idx1]==s[idx2]:
return False
else:
idx1 += 1
idx2 -= 1
return True
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(isPalindrome("ABA"));
System.out.println(isPalindrome("A#!A"));
System.out.println(isPalindrome("A man, a plan, a canal, Panama!"));
}
public static boolean isLetterDigit(char ch)
{
if(Character.isLetter(ch)||Character.isDigit(ch))
return true;
else
return false;
}
public static boolean isPalindrome(String s)
{
boolean valid = true;
for(int i = 0, j = s.length()-1; i<j; i++,j--)
{
while(!isLetterDigit(s.charAt(i)) && i<j)
i++;
while(!isLetterDigit(s.charAt(j)) && i<j)
j--;
if(Character.toLowerCase(s.charAt(i))!=Character.toLowerCase(s.charAt(j)))
{
valid = false;
break;
}
}
if(valid)
return true;
else
return false;
}
}
Your implementation is correct, but quality of the code can be better :) :
1) You may use Character.isLetterOrDigit(char c)
2) In the end of the functions you shouldn't check whether the boolean variable/result is true or false.
if(valid)
return true;
else
return false;
should be replaced with
return valid;
Same story with isLetterDigit implementation - should be replaced with
public static boolean isLetterDigit(char ch)
{
return (Character.isLetter(ch)||Character.isDigit(ch));
}
Just being lazy, I did not convert upper case to lower case. so something like 'AAa' will not work in my case, but just to present idea.
bool isletter(char a)
{
if (a >= 'a' && a <= 'z')
return true;
else if (a >= 'A' && a <= 'Z')
return true;
else if (a >= '0' && a <= '9')
return true;
else
return false;
}
bool ispalindrome(char* input, int size)
{
int begin = 0;
int end = size - 1;
while(begin < end){
while( ! isletter(input[begin]) ){
begin++;
}
while( ! isletter(input[end]) ){
end--;
}
if (input[begin] != input[end])
return false;
}
return true;
}
sorry, bug in my code. the following lines
if (input[begin] != input[end])
return false;
should be
if (input[begin++] != input[end++])
return false;
#include <string>
#include <iostream>
bool IsNumberOrDigit(char c)
{
return ((c >= '0' && c <= '9')
|| (c >= 'a' && c <= 'z')
|| (c >= 'A' && c <= 'Z'));
}
bool SameCharacters(char c1, char c2)
{
return (c1 == c2
|| (c1 >= 'a' && c1 <= 'z' && c2 >= 'A' && c2 <= 'Z' && c1 == c2 + 32)
|| (c1 >= 'A' && c1 <= 'Z' && c2 >= 'a' && c2 <= 'z' && c2 == c1 + 32));
}
bool IsPalindrome(const std::string &haystack)
{
bool isPalindrome = true;
int i, j;
if (haystack.length() != 0)
{
i = 0;
j = haystack.size() - 1;
while (i < j)
{
while (i < j && !IsNumberOrDigit(haystack[i]))
i++;
while (i < j && !IsNumberOrDigit(haystack[j]))
j--;
if (IsNumberOrDigit(haystack[i]) && IsNumberOrDigit(haystack[j]) && !SameCharacters(haystack[i], haystack[j]))
{
isPalindrome = false;
break;
}
else
{
i++;
j--;
}
}
}
return isPalindrome;
}
int main(int argc, const char * argv[]) {
/* IsPalindrome */
std::string haystack = "A man, a plan, a canal, panama!";
std::cout << IsPalindrome(haystack) << std::endl;
return 0;
}
This can be done with a single loop no need to do multiple ones.
bool IsPalindrome(string S)
{
int start = 0;
int end = S.Length - 1;
while(start <= end)
{
if(!IsValid(start))
{
start++
}
else if(!IsValid(end))
{
end--;
}
else if(S[start] == S[end]
{
start++;
end--;
}
else
{
return false;
}
}
return true;
}
public boolean isPalindrome(String s) {
int i = 0 , j = s.length() - 1 ;
while (i <= j) {
while (i <= j && !Character.isLetterOrDigit(s.charAt(i))){
i++;
}
while (i <= j && !Character.isLetterOrDigit(s.charAt(j))){
j--;
}
if (i <= j && Character.toLowerCase(s.charAt(i)) !=
Character.toLowerCase(s.charAt(j))) {
return false ;
}
i++;
j--;
}
return true ;
}
assert = require('assert')
function isLetter(c) {
return (/\w/).test(c)
}
function isPal(string) {
var s = 0, e = string.length - 1;
while((e - s) > 0) {
if (!isLetter(string[s])) {
s++
}
if (!isLetter(string[e])) {
e--
}
test = (string[s].toLowerCase() == string[e].toLowerCase())
s++;
e--;
return test;
}
console.log('done')
}
assert.ok(isPal("ABA"), 'Pass')
assert.ok(isPal("A!#A"), 'Pass')
assert.ok(isPal("A man, a plan, a canal, Panama!"), 'Pass!')
assert.ok(isPal("A man, a plan, a canal, Panamas!"), 'NO PASS!')
void palindrome(String str) {
String res = str.replaceAll(“[^A-Za-z0-9]”,””);
checkIfPalin(res);
}
void checkIfPalin(String res) {
int start = 0;
int end = len -1;
while (start <= len/2) {
if(Character.toLowerCase(res.chatAt(start) != Character.toLowerCase(res.chatAt(end))
return false;
start++;
}
return true;
}
void palindrome(String str) {
String res = str.replaceAll(“[^A-Za-z0-9]”,””);
checkIfPalin(res);
}
void checkIfPalin(String res) {
int start = 0;
int end = len -1;
while (start <= len/2) {
if(Character.toLowerCase(res.chatAt(start) != Character.toLowerCase(res.chatAt(end))
return false;
start++;
}
return true;
}
void palindrome(String str) {
String res = str.replaceAll(“[^A-Za-z0-9]”,””);
checkIfPalin(res);
}
void checkIfPalin(String res) {
int start = 0;
int end = len -1;
while (start <= len/2) {
if(Character.toLowerCase(res.chatAt(start) != Character.toLowerCase(res.chatAt(end))
return false;
start++;
}
return true;
}
void palindrome(String str) {
String res = str.replaceAll(“[^A-Za-z0-9]”,””);
checkIfPalin(res);
}
void checkIfPalin(String res) {
int start = 0;
int end = len -1;
while (start <= len/2) {
if(Character.toLowerCase(res.chatAt(start) != Character.toLowerCase(res.chatAt(end))
return false;
start++;
}
return true;
}
public boolean isPalindrome(String input){
int i, j;
i = 0;
if(input == null)
return true;
j = input.length()-1;
while(i < j){
if(Character.isLetterOrDigit(input.charAt(i)) && Character.isLetterOrDigit(input.charAt(j))){
if(Character.toLowerCase(input.charAt(i)) != Character.toLowerCase(input.charAt(j)))
return false;
i++; j--;
}else{
if(!Character.isLetterOrDigit(input.charAt(i))){
i++;
}
if(!Character.isLetterOrDigit(input.charAt(j))){
j--;
}
}
}
return true;
}
Python
def pal(s):
s = s.lower()
print s
l=0
r=len(s)-1
while l <= r:
# Case 1: two ends are identical
if s[l] == s[r] and (s[l].isalpha() or s[l].isdigit()):
l+=1
r-=1
# Case 2: left end is non alpha or digit, skip over it to right
elif not ( s[l].isalpha() or s[l].isdigit() ):
l+=1
# Case 3: right end is non alpha or digit, skip over it to left
elif not ( s[r].isalpha() or s[r].isdigit() ):
r-=1
# Case 4: two ends are not equal. i.e. s[l] != s[r]
#elif s[l] != s[r]:
# return False
else:
return False
return True
def pal(s):
s = s.lower()
print s
l=0
r=len(s)-1
while l <= r:
# Case 1: two ends are identical
if s[l] == s[r] and (s[l].isalpha() or s[l].isdigit()):
l+=1
r-=1
# Case 2: left end is non alpha or digit, skip over it to right
elif not ( s[l].isalpha() or s[l].isdigit() ):
l+=1
# Case 3: right end is non alpha or digit, skip over it to left
elif not ( s[r].isalpha() or s[r].isdigit() ):
r-=1
# Case 4: two ends are not equal. i.e. s[l] != s[r]
#elif s[l] != s[r]:
# return False
else:
return False
return True
static boolean checkPalinForLetters(String src) {
// Queue<Character> tokens = new LinkedList<Character>();
//
// for (int i = 0; i < src.length(); i++) {
//
// tokens.offer(src.charAt(i));
// }
// int ind = 0;
//
// while (!tokens.isEmpty()) {
//
// char token = tokens.poll();
//
// if (!Character.isAlphabetic(src.charAt(ind))) {
// ind ++;
// continue;
// }
// else {
//
// if (!(token == src.charAt(ind))) return false;
// ind++;
// }
//
// }
// return true;
int count = 0;
src = src.toLowerCase();
for (int i = src.length() - 1; i >= 0; i--) {
if (i == count) return src.charAt(i) == src.charAt(count);
if (!Character.isAlphabetic(src.charAt(i))) {
continue;
}
else if (!Character.isAlphabetic(src.charAt(count))) {
count++;
i = i + 1;
}
else {
if (src.charAt(i) != src.charAt(count)) return false;
count++;
}
}
return true;
}
{{ #include <iostream>
#include <ctype.h>
using namespace std;
bool isPalin(string str) {
int n = str.size();
if (n==0) return false;
int s = 0;
int e = n-1;
bool palin = false;
// note the = sign , to handle case like A$ which is a palin
while(s <= e) {
if (!isalpha(str[s]) && !isdigit(str[s])) {
s++;
continue;
}
if (!isalpha(str[e]) && !isdigit(str[e])) {
e--;
continue;
}
palin = true; // handles the case where we have just one alpha num
if (str[e] != str[s]) {
palin = false;
break;
}
s++;
e--;
}
return palin;
}
int main() {
cout << "is palin : " << isPalin("ABA") << "\n";
cout << "is palin : " << isPalin("A$A") << "\n";
cout << "is palin : " << isPalin("A$#A") << "\n";
cout << "is palin : " << isPalin("A11$#12A") << "\n";
cout << "is palin : " << isPalin("A21$#12A") << "\n";
cout << "is palin : " << isPalin("A21$") << "\n";
cout << "is palin : " << isPalin("A$") << "\n";
cout << "is palin : " << isPalin("$*") << "\n";
} }}
import java.util.*;
class LetterPalindrome
{
static boolean isPalindrome(String str)
{
int noChars=0;
for(int i=0;i<str.length();++i)
{
if(isOurChar(str.charAt(i)))
noChars++;
}
int lo=0,hi=str.length()-1;
for(int i=0;i<noChars/2;++i,++lo,--hi)
{
while(!isOurChar(str.charAt(lo)))
++lo;
while(!isOurChar(str.charAt(hi)))
--hi;
if(str.charAt(lo)!=str.charAt(hi))
return false;
//System.out.println("lo: "+str.charAt(lo)+" hi: "+str.charAt(hi));
}
return true;
}
static boolean isOurChar(char ch)
{
if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9'))
return true;
return false;
}
public static void main(String[] st)
{
String str="A man, a plan, a canal, Panama!";
//System.out.println("is A our:"+isOurChar(' '));
System.out.println("str: "+str+" result: "+isPalindrome(str.toLowerCase()));
}
}
import java.io.*;
import java.util.*;
class custompalin
{
public static void main(String[] args)
{
String str="AB*^#(*@^#$)VV@#*$@#)(*$&$BA";
int l=0;
int r=str.length()-1;
boolean retVal=true;
while(l<r)
{
l=move(l,str,true);
r=move(r,str,false);
if(str.charAt(l)!=str.charAt(r))
{
retVal=false;
break;
}
l++;
r--;
}
System.out.println(retVal);
}
private static int move(int i, String str,boolean increment)
{
while(!( (str.charAt(i) >='0' && str.charAt(i) <='9' )
|| (str.charAt(i)>='a' && str.charAt(i) <='z')
|| (str.charAt(i) >= 'A' && str.charAt(i)<='Z') ) )
{
if(increment)
i++;
else
i--;
}
return i;
}
}
import java.io.*;
import java.util.*;
class custompalin
{
public static void main(String[] args)
{
String str="AB*^#(*@^#$)VV@#*$@#)(*$&$BA";
int l=0;
int r=str.length()-1;
boolean retVal=true;
while(l<r)
{
l=move(l,str,true);
r=move(r,str,false);
if(str.charAt(l)!=str.charAt(r))
{
retVal=false;
break;
}
l++;
r--;
}
System.out.println(retVal);
}
private static int move(int i, String str,boolean increment)
{
while(!( (str.charAt(i) >='0' && str.charAt(i) <='9' )
|| (str.charAt(i)>='a' && str.charAt(i) <='z')
|| (str.charAt(i) >= 'A' && str.charAt(i)<='Z') ) )
{
if(increment)
i++;
else
i--;
}
return i;
}
}
Here is my solution in PHP:
function IsPalindrome ($phrase)
{
$start_index = 0;
$end_index = strlen($phrase) - 1;
while ($start_index < $end_index) {
while (!(preg_match ('/[a-z0-9]/i', $phrase[$start_index])) && $start_index < $end_index)
++$start_index;
while (!(preg_match ('/[a-z0-9]/i', $phrase[$end_index])) && $start_index < $end_index)
--$end_index;
if (($start_index < $end_index) && (strtolower($phrase[$start_index]) != strtolower($phrase[$end_index])))
return false;
++$start_index;
--$end_index;
}
return true;
}
To test it use the following code:
$inputs = array (
"ABA",
"A!#A",
"A man, a plan, a canal, Panama!",
"This is not a palindrome!"
);
foreach ($inputs as $input)
echo "The phrase \"$input\" is " . (IsPalindrome ($input) ? '' : 'NOT ') . "a palindrome\n";
Output:
The phrase "ABA" is a palindrome
The phrase "A!#A" is a palindrome
The phrase "A man, a plan, a canal, Panama!" is a palindrome
The phrase "This is not a palindrome!" is NOT a palindrome
Here is my solution in PHP:
function IsPalindrome ($phrase)
{
$start_index = 0;
$end_index = strlen($phrase) - 1;
while ($start_index < $end_index) {
while (!(preg_match ('/[a-z0-9]/i', $phrase[$start_index])) && $start_index < $end_index)
++$start_index;
while (!(preg_match ('/[a-z0-9]/i', $phrase[$end_index])) && $start_index < $end_index)
--$end_index;
if (($start_index < $end_index) && (strtolower($phrase[$start_index]) != strtolower($phrase[$end_index])))
return false;
++$start_index;
--$end_index;
}
return true;
}
To test it use the following code:
$inputs = array (
"ABA",
"A!#A",
"A man, a plan, a canal, Panama!",
"This is not a palindrome!"
);
foreach ($inputs as $input)
echo "The phrase \"$input\" is " . (IsPalindrome ($input) ? '' : 'NOT ') . "a palindrome\n";
Output:
The phrase "ABA" is a palindrome
The phrase "A!#A" is a palindrome
The phrase "A man, a plan, a canal, Panama!" is a palindrome
The phrase "This is not a palindrome!" is NOT a palindrome
Here is C++ version of solution:
#include <string>
#include<iostream>
using namespace std;
bool Isdigitletter(char c)
{
return ((c>= '0' && c <= '9')||(c>='a' && c<='z')||(c>='A' && c <='Z'));
}
bool IsSame(char s, char d)
{
char lower_s = s -'a';
char upper_s = s -'A';
char lower_d = d - 'a';
char upper_d = d - 'A';
return ((s == d)||(lower_s == upper_d)||(upper_s == lower_d));
}
bool check_palindrome(string input)
{
int s = 0;
int e = input.length()-1;
while (s <e)
{
if (!Isdigitletter(input[s]))
{
s++;
continue;
}
if (!Isdigitletter(input[e]))
{
e--;
continue;
}
if (!IsSame(input[s], input[e]))
return false;
s++;
e--;
}
return true;
}
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
solution.execute("ABA");
solution.execute("A!#A");
solution.execute("A man, a plan, a canal, Panama!");
solution.execute("123454321");
solution.execute("12345a321");
solution.execute("12344321");
}
public void execute(String text) {
// Calculate string's HALF size. If even, it should downgrade (e.g. half of 7 is 3.5 the result should be 3)
int halfSize = text.length() / 2;
boolean isPalindrome = true;
int lastEndPos = text.length() - 1; // Will be used to fetch from char array
// Iterate up to half fetching next start/end valid characters and comparing them
for (int i = 0; i < halfSize; i++) {
char curCharStart = text.charAt(i);
// Check if cur char is an eligible char
if (!isEligible(curCharStart)) {
continue;
}
// Fetch next eligible char from the end
lastEndPos = getNextEligibleCharFromEndPosition(text, lastEndPos, halfSize);
if (lastEndPos == -1) {
break;
}
char curCharEnd = text.charAt(lastEndPos);
// Check chars for equality, if not, break failing
if (Character.toUpperCase(curCharStart) != Character.toUpperCase(curCharEnd)) {
System.out.println(i + "-" + lastEndPos);
isPalindrome = false;
break;
}
// Decrease next end pos
lastEndPos--;
}
if (lastEndPos == text.length() - 1) {
// No eligible char was found
System.out.println("No eligible char was found");
} else if (isPalindrome) {
System.out.println("Text: " + text + " is a palindrome");
} else {
System.out.println("Text: " + text + " is NOT a palindrome");
}
}
// Fetch next eligible char from the end
private int getNextEligibleCharFromEndPosition(String text, int startPos, int halfSize) {
int result = -1;
for (int i = startPos; i > halfSize; i--) { // TODO: Check inner edge
//System.out.println(text + "-" + i);
char curCharEnd = text.charAt(i);
if (!isEligible(curCharEnd)) {
//System.out.println("Not eligible: '" + curCharEnd + "'");
continue;
}
result = i;
break;
}
return result;
}
// Determine if a char is eligible
private boolean isEligible(char curChar) {
// Check if letter or digit
boolean result = false;
if (Character.isLetter(curChar) || Character.isDigit(curChar)) {
result = true;
}
return result;
}
}
Here's JS solution:
assert = require('assert')
function isLetter(c) {
return (/\w/).test(c)
}
function isPal(string) {
var s = 0, e = string.length - 1;
while((e - s) > 0) {
if (!isLetter(string[s])) {
s++
}
if (!isLetter(string[e])) {
e--
}
test = (string[s].toLowerCase() == string[e].toLowerCase())
s++;
e--;
return test;
}
console.log('done')
}
assert.ok(isPal("ABA"), 'Pass')
assert.ok(isPal("A!#A"), 'Pass')
assert.ok(isPal("A man, a plan, a canal, Panama!"), 'Pass!')
assert.ok(isPal("A man, a plan, a canal, Panamas!"), 'NO PASS!')
- GK February 25, 2015