Facebook Interview Question
SDE1sCountry: United States
<?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";
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);
}
}
/**
* 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);
}
}
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.
#!/bin/bash
read entered
#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
#!/bin/bash
read entered
#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
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
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')
}
}
Reverse the original string(lets call it revrs_str).
- weak_pointer January 07, 2018Find 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.