脸书面试代码整理

gistfile1.py

"""
array anagramBuckets(array strings)

Write a function to group an array of strings by anagrams.

Input: An array of strings (possibly with duplicates)
Output: An array of arrays.  Each array contains a set of strings from the input array that are anagrams of each other.  The output should not contain any duplicates.

Example:
Input: ('abc', 'bac', 'xyz', 'xyz')
Output: (('abc', 'bac'), ('xyz'))

length of array: m
average length of strings: n
O(m*n*log(n))
"""

def anagramBuckets(strings):
    result = {}
    for string in strings:
        sig = get_sig(string)
        if not result.get(sig):
            result[sig] = set()
        result[sig].add(string)
       
    return list(result.values())
        
def get_sig(string):
    # return sorted string
    counts = {}
    for c in string:
        if not counts.get(c):
            counts[c] = 0
        counts[c]+=1
        
    return hash(frozenset(counts.items()))
    
"""
bool isPalindrome(string s);

A palindrome is a string that is the same when read backwards or forwards.  For example, "aba", "abba", and "racecar" are all palindromes.
You will implement a method to determine whether a string is a palindrome.

- Palindromes are case insensitive, so "Aba" is a palindrome.
- Palindromes ignore non a-z characters, so "a0ba" and "a- #&#b*b-a" are palindromes
- The empty string "" and strings with no letters, e.g. "123" are not palindromes.

1a2
"""

def isPalindrome(s):
    left = 0
    right = len(s) - 1
    hasCompared = False
    while left <= right:
        if not s[left].isalpha():
            left += 1
        elif not s[right].isalpha():
            right -= 1
        else:
            hasCompared = True
            if s[left].lower() != s[right].lower():
                return False
            else:
                left += 1
                right -= 1
    if hasCompared:           
        return True
    else:
        return False
        
import unittest
class Test(unittest.TestCase):
    def testIsPalindrome(self):
        self.assertEqual(True, isPalindrome('1a2'))
        self.assertEqual(False, isPalindrome(''))
        self.assertEqual(False, isPalindrome('123'))
        self.assertEqual(True, isPalindrome('a0ba'))
        self.assertEqual(True, isPalindrome('a- #&#b*b-a'))
        self.assertEqual(True, isPalindrome('Aba'))
        
        
if __name__ == '__main__':
    unittest.main()