Facebook Interview Question Android Engineers
Country: United States
Interview Type: In-Person
Maintain two pointers, start and end and sequentially go through the string comparing characters. If you notice a special character, then increment start pointer or decrement end pointer. Posting my solution in Python below.
Solution:
from string import punctuation
def isPalindrome(inputStr):
inputStr = inputStr.lower()
start, end = 0, len(inputStr) - 1
while start <= end:
if inputStr[start] in punctuation:
start += 1
continue
if inputStr[end] in punctuation:
end -= 1
continue
if inputStr[start] != inputStr[end]:
return False
start += 1
end -= 1
return True
print(isPalindrome('L*&EVe)))l')) # True
public static void main (String[] args) throws java.lang.Exception{
String cleanInput = cleanStr("L*&EVe)))l");
boolean isPal = isPalM(cleanInput);
System.out.println("the input string without special chars is "+ cleanInput + " & ispallindrome:" + isPal);
}
public static boolean isPalM(String input){
if(input.length() <=1)
return true;
else
return isPalRec(input, 0, (input.length()-1));
}
public static boolean isPalRec(String str, int s, int e){
if(s==e)
return true;
if(str.charAt(s) != str.charAt(e))
return false;
if(s < e-1)
isPalRec(str, s+1, e-1);
return true;
}
public static String cleanStr(String input){
Pattern escaper = Pattern.compile("([^a-zA-z0-9])");
String newStr = escaper.matcher(input).replaceAll("");
//System.out.println(input + " " + newStr);
return newStr.toLowerCase();
}
public static void main(String[] args) {
System.out.println(isPalindrome("L*&EVHe)))l"));
}
private static boolean isPalindrome(String s) {
int start = 0, end = s.length() - 1;
while (start < end) {
while (start <= end && !Character.isLetter(s.charAt(start))) start++;
if (start > end) break;
while (start <= end && !Character.isLetter(s.charAt(end))) end--;
if (start > end) break;
if (Character.toLowerCase(s.charAt(start)) != Character.toLowerCase(s.charAt(end))) return false;
start++;
end--;
}
return true;
}
Scala
object Palindrome extends App {
println(isPalindrome("L*&EVe)))l"))
def isPalindrome(str: String): Boolean = {
var (left, right) = (0, str.length - 1)
while (left < right) {
val (lc, rc) = (str(left), str(right))
if (!lc.isLetterOrDigit) {
left += 1
} else if (!rc.isLetterOrDigit) {
right -= 1
} else {
if (rc.toLower != lc.toLower) return false
left += 1
right -= 1
}
}
true
}
}
public class Palindrome {
public static void main(String[] args) {
// TODO Auto-generated method stub
String input = "L*&EVe)))l";
System.out.println(Palindrome.comparePalindrome(input));
}
public static boolean comparePalindrome(String input){
input = Palindrome.cleanText(input);
String newInput = Palindrome.invertString(input);
boolean areEqual = false;
if(input.equals(newInput)){
areEqual = true;
}
return areEqual;
}
public static String cleanText(String input){
input = input.toLowerCase();
String validCharacters = "abcdefghijklmnopqrstuvwxyz";
StringBuffer sb = new StringBuffer(input);
int x = 0;
while(x < input.length()){
if(validCharacters.indexOf(input.charAt(x)) == -1){
sb.deleteCharAt(x);
input = sb.toString();
}else{
x++;
}
}
return input;
}
public static String invertString(String input){
String newInvertedInput = "";
for(int x = input.length() -1; x >= 0; x--){
newInvertedInput+= input.charAt(x);
}
return newInvertedInput;
}
}
public class MainActivity extends AppCompatActivity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
boolean result = isPalindrome("L*&EVe)))l");
System.out.println(result);
}
private boolean isPalindrome(@Nullable String input) {
if (input == null){
return false;
}
int inputLength = input.length();
if (inputLength == 0){
return true;
}
int leftIndex = 0;
int rightIndex = inputLength -1;
char leftChar;
char rightChar;
while (leftIndex < rightIndex){
leftChar = input.charAt(leftIndex);
rightChar = input.charAt(rightIndex);
if (Character.isLetter(leftChar) && Character.isLetter(rightChar)){
if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)){
return false;
}
leftIndex++;
rightIndex--;
}
else if (Character.isLetter(leftChar)){
rightIndex--;
}
else {
leftIndex++;
}
}
return true;
}
}
def extractText_Palindrome(string):
alpha ='abcdefghijklmnopqrstuvwxyz'
text = []
for i in range(len(string)):
if(string[i].lower() in alpha):
text.append(string[i].lower())
ret = "".join(c for c in text)
if((ret[::-1])==ret):
return True
else:
return False
var = '%6^^&(L)eVeL#@!&*&*&*&'
print(extractText_Palindrome(var))
In Python
def extractText_Palindrome(string):
alpha ='abcdefghijklmnopqrstuvwxyz'
text = []
for i in range(len(string)):
if(string[i].lower() in alpha):
text.append(string[i].lower())
ret = "".join(c for c in text)
if((ret[::-1])==ret):
return True
else:
return False
var = '%6^^&(L)eVeL#@!&*&*&*&'
print(extractText_Palindrome(var))
public class checkPalindrome {
public static void main(String[] args) {
String input = "L*&EVe)))l";
if (isPalindrome(input))
System.out.println("Palindrome");
else
System.out.println("NO Palindrome");
}
static public boolean isPalindrome(String input) {
String out = "";
// 1) remove special character
int len = input.length();
for (int i = 0; i < len; i++) {
char c = input.charAt(i);
if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'))
out += c;
}
// 2) make it lowercase
out = out.toLowerCase();
// 3) check if palindrom.
// compare [i] vs [len-i-1], we dont need check the center element if it exists (in case of odd length)
len = out.length();
for (int i = 0; i < len/2; i++) {
if ((out.charAt(i) != out.charAt(len-i-1))) {
return false;
}
}
return true;
}
}
public class MyPalindrome {
public static void main(String args[]) {
System.out.println(isPalindrome(sanitize("level")));
}
private static String sanitize(String aString){
return aString.replaceAll("[^a-zA-Z]", "").toLowerCase();
}
private static boolean isPalindrome(String aString){
int aHalfLength = Math.round(aString.length()/2);
String aSubstring;
if(aString.length()%2 != 0){
aSubstring = aString.substring(0, aHalfLength+1);
}
else{
aSubstring = aString.substring(0, aHalfLength);
}
StringBuilder aStringBuilder = new StringBuilder(aSubstring);
//reverse the half of the string
aSubstring = aStringBuilder.reverse().toString();
return aString.substring(aHalfLength).equals(aSubstring);
}
}
Use two pointers.
Convert string to lowercase.
ignore punctuations, while incrementing/decrementing the start/end pointers.
compare pointers in each iteration, if there is a mismatch then return false.
In the end, if there is no mismatch then return true.
class Palindrome{ public static void main(String[] args){ isPalindrome("L*&EVe)))l"); } private static void isPalindrome(String p){ int start = 0; int end = p.length()-1; String s = p.toLowerCase(); char[] arr = s.toCharArray(); while(start <= end){ if(!Character.isLetterOrDigit(arr[start])){ start++; continue; } if(!Character.isLetterOrDigit(arr[end])){ end++; continue; } if(arr[start]!=arr[end]){ System.out.println("False"); } start++; end--; } System.out.println("True"); } }You can also use a stack. Put all the characters in the stack, and then pop all those to a separate string. At the ends compare the two string. If there are equal return true, otherwise return false.
- infoginx March 14, 2018