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.

- weak_pointer January 07, 2018 | Flag Reply
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";

- sgchris January 05, 2018 | Flag Reply
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)

- Anonymous January 05, 2018 | Flag Reply
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

- Anonymous January 05, 2018 | Flag Reply
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);
        }
    }

- naten January 07, 2018 | Flag Reply
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);
		}
	}

- user1994 January 08, 2018 | Flag Reply
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.

- paulofelipefeitosa January 09, 2018 | Flag Reply
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);

- Melad.Raouf January 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/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

- nezih January 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- nezih January 17, 2018 | Flag Reply
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

- cm January 18, 2018 | Flag Reply
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

- Anonymous January 27, 2018 | Flag Reply
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')
  }
}

- Cristian January 28, 2018 | Flag Reply
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))

}

- anders@snowflaketrading.com July 25, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More