微软笔试算法（一）

发表于 | 分类于

最近求职中接到的好多外包公司的电话，一般我都是拒绝的，其中告知外包到微软的就有三家，有一家说是微软小冰项目，给了我八道算法题，都不是太难，有的在LeetCode上还做过，在这里记录一下，正好也整理下LeetCode上刷过的题。

这里记录的算法是只用python实现，也是我目前能想到的最优解，一共八个问题。

  1. 完成一个函数：def Add(num1, num2):其中，两个输入都是数字，都是字符串（如：“12345678986543210123456789”），要求计算两个数字的和，返回一个字符串，不能使用内置函数，如int，long等。例如，输入两个数字是：“1000000000000000”和“-1”，返回“999999999999999”。

这个问题比较简单了，主要就是三个小问题：

  1. 字符串和数字的互转
  2. 加法的进位
  3. 减法的借位

字符串和数字的互转不让用int函数，这个简单，python只要写个字典就解决了，C的话就要写switch case来一个一个比较了。这里就解决了字符转数字的问题了。

到的数字开始计算，因为要设计借位和进位，答案会有四种情况

  1. 正数 + 正数 = 正数 2 + 3 = 5
  2. 负数 + 负数 = 负数 -2 + -3 = -5
  3. 大正数 + 负数 = 正数 -2 + 3 = 1
  4. 正数 + 大负数 = 负数 2 + -3 = -1

貌似就是这样，但是观察结果除了负号就是两种，所以程序一开始应该先分析负号，进位的情况有1,2，借位情况是3,4，正好这两个结果除了负号答案一样，所以分两类就OK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
# 问题 1
def question1_add(num1, num2):
    # 创建个字典用来把字符转为int便于计算
    def strtoint(str):
        numdict = {"0": 0, "1": 1, "2": 2, "3": 3, "4": 4, "5": 5, "6": 6, "7": 7, "8": 8, "9": 9}
        return numdict.get(str)
    
    # 把列表中的数字转会字符串 
    def inttostr(lt):
        ls2 = [str(i) for i in lt]
        return ''.join(ls2)

    lt, x, y = [], [], []
    
    # 两个数是否为负数的标记
    minusflag1, minusflag2 = 0, 0
    
    # 首先先提取出负号，记录负号的情况 
    if num1[0] is "-":
        x = list(map(strtoint, num1[1:]))
        minusflag1 = 1
    else:
        x = list(map(strtoint, num1))

    if num2[0] is "-":
        y = list(map(strtoint, num2[1:]))
        minusflag2 = 1
    else:
        y = list(map(strtoint, num2))

    # 把 x作为最长的那列，y是短的那列
    if len(x) < len(y):
        x, y = y, x

    maxlen, minlen = len(x), len(y)
    
    # 在短的那列前面插上0让两列一样齐以便于计算
    for i in range(maxlen-minlen):
        y.insert(0, 0)

    # 计算通常是从最低位开始，所以i从最低位开始
    # carry记录借位和进位情况
    i, carry = 0, 0

    # 两个数都是正数或负数
    if (minusflag1 == 0 and minusflag2 == 0) or (minusflag1 == 1 and minusflag2 == 1):
        # +1是为了防止最高位有进位的情况，给最高位加一个0
        for j in range(maxlen+1):
            i -= 1
            if j < maxlen:
                sum = x[i] + y[i] + carry
            else:
                sum = carry
            # 两个数相加大于十代表有进位， 把结果和10的商给新列表，余给进位标志   
            if sum >= 10:
                lt.insert(0, sum%10)
                carry = sum//10
            else:
                lt.insert(0, sum)
                carry = 0
        # 如果最高位没有进位 把0删除       
        if lt[0] == 0:
            lt.pop(0)

        # 如果都为负数 加 -
        if minusflag1 == 1 and minusflag2 == 1:
            lt.insert(0, "-")
            return inttostr(lt)
        else:
            return inttostr(lt)

    # 一正一负
    if (minusflag1 == 1 and minusflag2 == 0) or (minusflag1 == 0 and minusflag2 == 1):
        for j in range(maxlen):
            i -= 1
            sum = x[i] - y[i] + carry
            if sum < 0:
                lt.insert(0, sum%10)
                carry = sum//10
            else:
                lt.insert(0, sum)
                carry = 0

        while lt[0] == 0:
            lt.pop(0)
            if len(lt) == 1:
                break

        # 判断是否应该加 - 号
        if (num1[0] is "-" and len(num1[1:]) > len(num2)) or num2[0] is "-" and len(num2[1:]) > len(num1) :
            lt.insert(0, "-")
            return inttostr(lt)
        return inttostr(lt)
  1. 给定一个数组nums，然后对其排序，使得排序结果满足nums[0] < nums[1] > nums[2] < nums[3]…。 例如给定数组nums=[1,2,3,4,5,6,7,8,9],其中一个满足条件的结果是1<6>2<7>3<8>4<9>5.给出一个结果即可（可能无解）。最优解法是O(n)时间复杂度和O(1)空间复杂度。

原题位置：https://leetcode.com/problems/wiggle-sort-ii/

这道题就比较有趣了，LeetCode上大神给出的算法挺多，但是最优解不是O(n)，用python实现的话还能比O(n)小。

先说我看到题第一眼的想法和看了LeetCode上大神的方法吧，很简单就三行

1
2
3
nums.sort()
median = len(nums[::2]) - 1
nums[::2], nums[1::2] = nums[median::-1], nums[:median:-1]

首先排序，找到中位数，然后把中位数左右两边的交叉相排就OK了。

好吧，详细一点吧，S代表比中位数小的，L代表比中位数大的，M代表中位数

1
2
3
4
Small half:  M . S . S . S      Small half:  M . S . S . S .
Large half:  . L . L . M .      Large half:  . L . L . L . M
--------------------------      --------------------------
Together:    M L S L S M S      Together:    M L S L S L S M

根据这个原理还可以写成其他形式

1
2
3
nums.sort()
median = len(nums[::2])
nums[1::2], nums[::2] = nums[median:],nums[:median]

这个方式简单但是不满足O(n)时间复杂度的要求，这个方法是LeetCode上大神想出的叫virtual indexing，地址

1
2
3
4
5
6

解释一下site()函数的作用

为了防止median的元素挨在一起，也就是说奇数位置上的值是median，同时与他相邻的某个偶数位置上的值也是median导致排序失败

为了避免这个问题，可以采用一种方法，即另j 每次移动两步，也就是说先另j直线奇数位置，再另j指向偶数位置，所以对于大小为10的序列，j的变化可能像是这样

1 -> 3 -> 5 -> 7 -> 9 -> 0 -> 2 -> 4 -> 6 -> 8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
暂且先不考虑怎么实现这样的改变，先说一下这样做带来的好处

由上面j的变化可知，j的改变是每次移动两步，所以，根据算法描述。所有和median相等的元素一定是最后才固定位置，又因为当j指向的值等于median时，是不与i和k指向的任何一个元素交换的。所以，每次移动两步带来的结果是这些median永远不可能相邻。换句话说就是永远不会出现两个median挨着的情况

```python
def question2_sort2(nums):
    def site(n):
        return (1 + 2 * n) % (len(nums) | 1)

    nums.sort()
    if len(nums) % 2 == 0:
        median = (nums[len(nums) // 2] + nums[len(nums) // 2 - 1]) / 2
    else:
        median = nums[len(nums) // 2]
    i, j, k = 0, 0, len(nums) - 1
    while j <= k:
        if nums[site(j)] > median:
            nums[site(i)], nums[site(j)] = nums[site(j)], nums[site(i)]
            i += 1
            j += 1
        elif nums[site(j)] < median:
            nums[site(j)], nums[site(k)] = nums[site(k)], nums[site(j)]
            k -= 1
            j += 1 # 没错就是这里，我认为执行过交换后j就在正确的位置上了，所以我让j+1结果就是循环次数减少了，如果进行j+1则会循环N次，两种的结果不同但都复合条件
        else:
            j += 1
    return nums

  1. 写一个函数，输入是两个int数组A和B。要求从A和B中分别取出一个数，使他们的和为20。打印出所有的组合。要求数字在数组中的位置和数字本身。比如输入为 A = [18, 2, 7, 8, 3], B = [17, 1, 19]，输出为 3 (A4) + 17 (B0) = 20，表示A的第4个元素是3，B的第0个元素是17

这就是道送分题了，嵌套循环就OK了，没什么好说的。

1
2
3
4
5
6
7
def question3_take(a, b):
    for i in range(len(a)):
        for j in range(len(b)):
            if a[i] + b[j] == 20:
                print("%d (A%d) + %d (B%d) = 20" % (a[i], i, b[j], j))
                return
    print(" No solution!")

  1. 写一个函数，输入一个随机的01序列，打印出这个序列中最长的01交替出现的序列的起始位置和结束位置。例如：输入“000101010101101”，输出起始位置2, 结束位置10

这题让我纠结了下，因为需要记录的位置有点多

因为我们要遍历这个序列中所有的01所以要两个指针同时移动才能确保01的出现，当出现01我们计数器n +1，然后判断是否到结尾或者下一个不是01的情况，我们就结束这段，记录这段的长度和结束开始的位置，如果下一段出现的01长我们就替换掉上次的记录。

值得注意的是01可能出现在序列的奇数或偶数位上，所以要遍历两次，再比较奇偶上哪个长，返回长的那段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def func(i, j, num):
    start, end, n, count = 0, 0, 0, 0
    while j < len(num):
        if num[i] is '0' and num[j] is '1':
            n += 1
        if j+1 >= len(num) - 1 or num[i+2] is '1' or num[j+2] is '0':
            if n > count:
                count = n
                n = 0
                end = j + 1
                start = end - count*2
        i += 2
        j += 2
    return start, end


def question4(num):
    i, j = 0, 1
    start1, end1 = func(i, j, num)
    i, j = 1, 2
    start2, end2 = func(i, j, num)
    if end1 - start1 > end2- start2:
        return start1, end1
    else:
        return start2, end2
0%