## Facebook Interview Question for SDE1s

Country: United States

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

Reverse the original string(lets call it revrs_str).
Find the LCS between original string and the revrs_str.
That LCS is the largest palindrome one can create from original string by removing few chars.
Now we can check if the length of LCS is greater than (length of original string - k.)
If so, the final answer is YES otherwise NO.

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

``````<?php

// check if a string is a polyndrome
function isPoly(\$str) {
\$str = preg_replace('/[^A-Za-z0-9]+/i', '', \$str);
\$result = (strcasecmp(\$str, implode('', array_reverse(str_split(\$str)))) == 0);
return \$result;
}

// check if a string (without up to K chars) is a polyndrome
function checkPoly(\$str, \$k) {
if (!\$str) return false;
\$len = strlen(\$str);

// check 0000 to 1111 (str length bits), when it's 1, replace that char in a space
\$maxNum = pow(2, \$len) - 1;
for (\$i = 0; \$i < \$maxNum; ++\$i) {
\$binStr = sprintf("%0{\$len}b", \$i);
// check that the number of "1"s in the number doesn't exceed K
if (substr_count(\$binStr, '1') > \$k) continue;

// replace chars to space in the same indexes as "1"s in the binary number
\$tmpStr = \$str;
foreach (str_split(\$binStr) as \$j => \$bit) {
if (\$bit == '1') \$tmpStr = substr_replace(\$tmpStr, ' ', \$j, 1);
}

// check if the newly created char is a polyndrome
if (isPoly(\$tmpStr)) return true;
}

return false;
}

\$str = 'abcXYZbca';
\$k = 3;
\$res = checkPoly(\$str, \$k);
echo "checking '{\$str}', k = {\$k}, result = ", (\$res?'true':'false'), "\n";``````

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

def checkispalindrome(string):
b = string[::-1]
if b == string:
return True
else:
return False

def removeintegers(string,k):
for i in range(0,len(string)+1):
t = string[:i] + string[i+k :]
if(checkispalindrome(t)):
print(string[i:i + k])

string = "abcxyzcba"
k = 3
removeintegers(string,k)

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

``````def checkispalindrome(string):
b = string[::-1]
if b == string:
return True
else:
return False``````

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

``````public static boolean canMakePalindrome(String s, int n) {
return canMakePalindrome(s.toCharArray(), 0, s.length() - 1, n);
}

private static boolean canMakePalindrome(char[] chars, int left, int right, int n) {
if (left >= right) {
return true;
} else if (chars[left] == chars[right]) {
return canMakePalindrome(chars, left + 1, right - 1, n);
} else if (n == 0) {
return false;
} else {
return canMakePalindrome(chars, left + 1, right, n -1 ) ||
canMakePalindrome(chars, left, right - 1, n - 1);
}
}``````

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

``````/**
* Reverse the string
*/
private static String reverseSTR(String word)
{	StringBuilder sb = new StringBuilder();
String[] contents = word.split(" ");
int hi = contents.length - 1;
int low = 0;
while(low <= hi) {
String loVal = contents[low];
String hiVal = contents[hi];
contents[low] = hiVal;
contents[hi] = loVal;
low+=1;
hi-=1;
}
for(String s : contents) {
sb.append(s);
}
return sb.toString();
}
/* Deletes from the string 'n' amount of characters. */
public static String removeChar(String word, int n) {
char[] contents = word.toCharArray();
for(int i = 0; i < n; i++) {
contents[i] = '\0';
}
return new String(contents);
}
/**
* Checks if a string can be a palindrome after deleting k chars.
*/
public static boolean isPalindrome(String word, int n) {
String reversed = reverseSTR(word);
if(n <= 0) {
return reversed.length() == word.length() && word.equals(word);
}
else {
String deletedK = removeChar(reversed, n);
return deletedK.length() == word.length() && deletedK.equals(word);
}
}``````

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

This problem is the same as Longest Palindromic Subsequence. Solved in O(N^2) and O(N^2) space.

The Longest Palindromic Subsequence key idea is, let's suppose that we want to know the longest subpalindrome of substring [1, n].

If the characters in position 1 and n are equals, then the answer is the longest subpalindrome of substring [2, n-1] + 2.
Else, the answer is the largest subpalindrome between substrings [1, n-1] and [2, n].

Note that, if there is more than one subpalindrome as answer we can pick any, because we will always build the largest subpalindrome. Therefore, substrings of size <= 2 are always palindrome.

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

It is an Edit distance problem.
The only one edit distance operation we are looking for is the remove operation.

``````boolean canMakePalindrome(String s, int k)
return k==editDist(s,reversedS);``````

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

#!/bin/bash
#new_entered=\$(echo "\$entered" | sed 's/ //g')
new_entered=\$entered
no_of_chars=\$(echo \${#new_entered})
max_chars=\$no_of_chars
reverse_entered=""

for ((i=1;i <= \$no_of_chars;i++))
do
nth_char=\$(echo "\$new_entered" | head -c \$max_chars | tail -c 1)
max_chars=\$((max_chars-1))
reverse_entered="\${reverse_entered}\${nth_char}"
done

if [[ \$entered == "\$reverse_entered" ]]; then
echo "This word is a palindrome"
else
echo "This word is not a palindrome"
fi

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

``and``

#!/bin/bash
#new_entered=\$(echo "\$entered" | sed 's/ //g')
new_entered=\$entered
no_of_chars=\$(echo \${#new_entered})
max_chars=\$no_of_chars
reverse_entered=""

for ((i=1;i <= \$no_of_chars;i++))
do
nth_char=\$(echo "\$new_entered" | head -c \$max_chars | tail -c 1)
max_chars=\$((max_chars-1))
reverse_entered="\${reverse_entered}\${nth_char}"
done

if [[ \$entered == "\$reverse_entered" ]]; then
echo "This word is a palindrome"
else
echo "This word is not a palindrome"
fi

``and``

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

``````def delete_palindrome(s, k):

def helper(left, right):
if left >= right:
return 0

if s[left] == s[right]:
return helper(left+1, right-1)

delete_left = 1 + helper(left+1, right)
delete_right = 1 + helper(left, right-1)

return min(delete_left, delete_right)

return helper(0, len(s)-1) <= k``````

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

Ruby

``````def palindrome?(s)
n = s.length
i = 0
j = n-1
while i < j
if s[i] != s[j]
return false
end
i += 1
j -= 1
end
return true
end
def solution(s, k)
return true if s.length <= 1
return true if s.length == 2 && s[0] == s[1]
return palindrome?(s) if k == 0

first = s[0]
last = s[-1]

if first == last
solution(s[1..-2],k)
else
solution(s[0..-2], k-1) || solution(s[1..-1], k-1)
end

end``````

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

Time complexity: O(n)
Space complexity: O(1)

JS

``````const canMakePalindrome = (word, charRemoveCount) => {
const length = word.length
const halfLength = Math.floor(length / 2)

for (let i = 0; i < halfLength; i++) {
const firstCharIndex = i
const lastCharIndex = length - i - 1
const firstCharacter = word[firstCharIndex]
const lastCharacter = word[lastCharIndex]

if (firstCharacter !== lastCharacter) {
const firstCharDistance = findDistance(word, firstCharIndex, 'RIGHT')
const lastCharDistance = findDistance(word, lastCharIndex, 'LEFT')

const shouldRemoveLastChar = (firstCharDistance === null && lastCharDistance === null) || (lastCharDistance === null) || (firstCharDistance !== null && lastCharDistance >= firstCharIndex)
const shouldRemoveFirstChar = (firstCharDistance === null) || (lastCharDistance !== null && firstCharDistance > lastCharDistance)

if (charRemoveCount === 0) {
return false
} else if (shouldRemoveLastChar) {
return canMakePalindrome(word.slice(0, -1), charRemoveCount - 1)
} else if (shouldRemoveFirstChar) {
return canMakePalindrome(word.slice(1), charRemoveCount - 1)
}
}
}

return true
}

const findDistance = (word, charIndex, searchDirection) => {
const character = word[charIndex]

const searchRight = () => {
for (let i = charIndex + 1; i < word.length; i++) {
const nextCharacter = word[i]
if (character === nextCharacter) {
return i
}
}
return null
}

const searchLeft = () => {
for (let i = charIndex - 1; i >= 0; i--) {
const previousCharacter = word[i]
if (character === previousCharacter) {
return i + 1
}
}
return null
}

if (searchDirection === 'RIGHT') {
return searchRight()
} else if (searchDirection === 'LEFT') {
return searchLeft()
} else {
throw new Error('invalid direction, expected LEFT or RIGHT')
}
}``````

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

``````let isPalindrom = (str, k = 0) => {
if(k === 0) return str.split('').every((char, i) => char === str[str.length - i - 1])

if(isPalindrom(str, 0)) return true
return Array(str.length).fill().some((char, i) => isPalindrom(str.split('').filter((c, j) => i !== j).join(''), k - 1))``````

}

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.

### 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.