LeetCode Microsoft Python Algorithm 面试真题 (Arrays and Strings)

先小小吐槽一下Microsoft的HR，1月初通过了Data Scientist第一轮的Python Technical Screen，HR还让我book了一天off，参加1月22号温哥华的interview day，上周五居然群发邮件把我拒了，理由是人数多出来了，真是太坑了，害我认认真真准备了快两个星期了。

现在分享一下LeetCode上Microsoft Python Algorithm的真题吧，先分享arrays and strings这部分。希望能够多多涨大米，可以让我体验一把飞一样的感觉。

1. Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Solution：class Solution:   
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        for i in range(len(nums)):
            if target - nums in nums[i+1:]:
        return [i, nums[i+1:].index(target - nums)+i+1]

2. Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Solution：
class Solution:
    def isPalindrome(self, s: str) -> bool:

        l, r = 0, len(s)-1

        while l < r:

            if s[l].isalnum() and s[r].isalnum():
                if s[l].lower() != s[r].lower():
                    return False
                l += 1
                r -= 1
            else:
                if not s[l].isalnum():
                    l += 1
                if not s[r].isalnum():
                    r -= 1

        return True

3. Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

Read in and ignore any leading whitespace.
Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
Read in next the characters until the next non-digit charcter or the end of the input is reached. The rest of the string is ignored.
Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
Return the integer as the final result.
Note:

Only the space character ' ' is considered a whitespace character.
Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.
.
Solution：
class Solution:
    def myAtoi(self, s: str) -> int:

        s = s.lstrip()

        if not s:
            return 0

        res = ''

        if s[0] in ['+', '-']:
            res += s[0]
            s = s[1:]

        for i in range(len(s)):
            if s.isdigit():
                res += s
.--            else:
                break

        if res == '' or res == '+' or res == '-':
            return 0
        elif int(res) > 2**31 - 1:
            return 2**31 - 1
        elif int(res) < -2**31:
            return -2**31
        else:
            return int(res)

4. Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Solution：
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """

        l, r = 0, len(s)-1

        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1

5. Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Solution：
class Solution:
    def reverseWords(self, s: str) -> str:

        s = s.split()


        l, r = 0, len(s) - 1

        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1
.--
        return ' '.join(s)

6. Given an input string , reverse the string word by word.

Example:

Input:  ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
Note:

A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces.
The words are always separated by a single space.
Follow up: Could you do it in-place without allocating extra space?

Solution：
class Solution:
    def reverseWords(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """

        def reverse(s, l, r):
            while l < r:
                s[l], s[r] = s[r], s[l]
                l += 1
                r -= 1
.--
        def reverse_each_word(s):
            n = len(s)
            start = end = 0
            while start < n:
                while end < n and s[end] != ' ':
                    end += 1
                reverse(s, start, end-1)
                start = end+1
                end += 1

        reverse(s, 0, len(s)-1)
        reverse_each_word(s)

7. Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Solution：
class Solution:
    def isValid(self, s: str) -> bool:

        stack = []

        maps = {'(':')', '[':']', '{':'}'}

        for i in range(len(s)):
            if s in maps:
                stack.append(s)
            else:
                if not stack or maps[stack[-1]] != s:
                    return False
                else:
. .и                    stack.pop()

        return not stack

8. Given a string s, return the longest palindromic substring in s.

Solution:
class Solution:
    def longestPalindrome(self, s: str) -> str:

        def longestPalindromeCenteredAt(i, j):
            while i >= 0 and j < len(s) and s == s[j]:
                i -= 1
                j += 1
            return s[i+1:j]

        res = ''

        for i in range(len(s)):
            newResult = longestPalindromeCenteredAt(i, i)
            if len(newResult) > len(res):
                res = newResult
            if i+1 < len(s):
                newResult = longestPalindromeCenteredAt(i, i+1)
                if len(newResult) > len(res):
                    res = newResult

        return res

9. Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Solution：
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        res = {}

        for i in range(len(strs)):
            temp = tuple(sorted(strs))
            if temp in res:
                res[temp].append(strs)
            else:
                res[temp] = [strs]

        return res.values()

10. Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Solution：
class Solution:
    def trap(self, height: List[int]) -> int:

        leftmost = rightmost = 0
        left, right = 0, len(height)-1

        res = 0

        while left < right:
            leftmost = max(leftmost, height[left])
            rightmost = max(rightmost, height[right])
            if leftmost < rightmost:
                res += leftmost - height[left]
                left += 1
            else:
                res += rightmost - height[right]
                right -= 1

        return res

11. Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

Follow up:

A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Solution:
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """

        m, n = len(matrix), len(matrix[0])

        r, c = set(), set()

        for i in range(m):
            for j in range(n):
                if matrix[j] == 0:
                    r.add(i)
                    c.add(j)

        for i in range(m):
            for j in range(n):
                if i in r or j in c:
                    matrix[j] = 0

12. You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Solution:
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """

        n = len(matrix)

        for i in range(n):
            for j in range(i, n):
                matrix[j], matrix[j] = matrix[j], matrix[j]

        for k in range(n):
            matrix[k].reverse()

13. Given an m x n matrix, return all elements of the matrix in spiral order.

Solution:
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:

        R, C = len(matrix), len(matrix[0])
        seen = [[False]*C for _ in range(R)]
        dr = [0, 1, 0, -1]
        dc = [1, 0, -1, 0]
        r=c=di=0
        res=[]

        for _ in range(R*C):
            res.append(matrix[r][c])
            seen[r][c] = True

            rr, cc = r + dr[di], c + dc[di]

            if 0<= rr < R and 0 <= cc < C and not seen[rr][cc]:
                r, c = rr, cc
            else:
                di = (di+1) % 4
                r, c = r + dr[di], c + dc[di]

        return res

大温巨硬这么坑的吗。。。安慰下LZ

这个岗位HR在领英上找我，我申请之后就没消息了，害hhh

HR的名字是不是J开头的？也是在Linkedin上找我的，让我大年夜填了申请表，第二天又做了online test，后来告诉我过了，他们还在排时间，让我先请好假。

Sarahxy07 发表于 2021-1-21 02:23
HR的名字是不是J开头的？也是在Linkedin上找我的，让我大年夜填了申请表，第二天又做了online test，后来告 ...

不是的哈，是A开头的