2020年 微软 亚麻 脸书 Capital ONE DE类编程题

收集了一些DE技术面试的题目，很少涉及算法，基本都是概念类基础知识，倾向用PYTHON。
Greatest Common Divisor of Strings


Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

1. class Solution:   
   
2.     def gcdOfStrings(self, str1: str, str2: str) -> str:
   
3.         if len(str2) > len(str1):
   
4.             return self.gcdOfStrings(str2, str1)
   
5.         if str1 == str2:
   
6.             return str2
   
7.         elif str1[:len(str2)] == str2:
   
8.             return self.gcdOfStrings(str1[len(str2):], str2)
   
9.         else:
   
10.             return ""

复制代码

PYTHON

概念：列表，字符串，字典，简单的链表和二叉树（知道怎么操作head和node，怎么取val即可）
算法：Brute Force，Recursion 和 Iteration，bar raiser有一点点会试探Divide and Conquer，比如双指针。不需要会dynamic programming和greedy。

坦白说，4道PYTHON不难，难在30分钟之内全部正确解决，感觉公司已经默认所有人都是刷过3遍题的，所以不刷题或者刷题不够的，很难过的了DE面试。只有提前做过，并且非常熟练，才能在那么短的时间内把代码全部写正确。对于我而言，更喜欢90分钟做两道比较难的题，不喜欢30分钟做4道简单题。

上题的Iteration做法，我就没在8分钟内解决，写出了80%的样子，早知道就用Recursion了，早知道还是要多刷题。

1. def gcdOfStrings(self, str1, str2):
   
2.         for i in reversed(range(0, len(str2))):
   
3.             if len(str2) % (i + 1) or len(str1) % (i + 1):
   
4.                 continue
   
5.             if not str2.replace(str2[:i+1], "") and not str1.replace(str2[:i+1],""):
   
6.                 return str2[:i+1]
   
7.         return ""

复制代码

第一道题，开胃小菜，3分钟速战，不刷题也应该能做出来

把字符串的元音字母去掉

Input: "leetcodeisacommunityforcoders"
Output: "ltcdscmmntyfrcdrs"

1. def removeVowels(self, S: str) -> str:
   
2.         s = list(S)
   
3.         l = []
   
4.         for c in s:
   
5.             if c not in ['a','e','i','o','u']:
   
6.                 l.append(c)
   
7.         return ''.join(l)

复制代码

开胃小菜第二道，5分钟解决，不用刷题也应该会的

Return all strings in words which is substring of another word in any order.
Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]

1. def stringMatching(self, words: List[str]) -> List[str]:
   
2.         l = []
   
3.         for i in range(len(words)):
   
4.             for j in range(len(words)):
   
5.                 if words[i] in words[j] and i != j:
   
6.                     l.append(words[i])
   
7.         return set(l)

复制代码

[/i][/i]

高盛的题，被capital one用了

Given a string S that only contains "I" (increase) or "D" (decrease), let N = S.length.

Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:


Input: "IDID"
Output: [0,4,1,3,2]

1. def diStringMatch(self, S):
   
2.         low, high = 0, len(S)
   
3.         l = []
   
4.         for c in S:
   
5.             if c == 'I':
   
6.                 l.append(low)
   
7.                 low += 1
   
8.             else:
   
9.                 l.append(high)
   
10.                 high -= 1
    
11.         return l + [low]

复制代码

最后加上low，或者high都一样

1. def diStringMatch(self, S: str) -> List[int]:
   
2.         low, high = 0, len(S)
   
3.         l = []
   
4.         for c in S:
   
5.             if c == 'I':
   
6.                 l.append(low)
   
7.                 low += 1
   
8.             else:
   
9.                 l.append(high)
   
10.                 high -= 1
    
11.         return l + [high]  

复制代码

1. '''
   
2. 给一个有 None 值的list，把所有None 用前一个数代替
   
3. '''
   
4. 
   
5. 
   
6. d = [None,1,1,2, None,3,None]
   
7. output = [None,1,1,2,2,3,3]
   
8. 
   
9. s = []
   
10. c = d[0]
    
11. s.append(c)
    
12. for i in range(1,len(d)):
    
13.     if d[i] != c and d[i] is not None:
    
14.         c = d[i]
    
15.         s.append(c)
    
16.     else:
    
17.         s.append(c)
    
18. print(s)

复制代码

都是基础知识

1. '''
   
2. 返回两个字符串的差值，里面含空值，排序
   
3. '''
   
4. 
   
5. s1 = 'abccdeabhf'
   
6. s2 = 'ac dexbyf'
   
7. output = [' ', 'h', 'x', 'y']
   
8. 
   
9. print(sorted(list(list(set(s2).difference(set(s1))) + list(set(s1).difference(set(s2))))))

复制代码

补充内容 (2020-9-17 23:12):
return sorted(list(set(s1).difference(s2).union(set(s2).difference(s1))))

1. '''
   
2. 给一个字符串，计算某个子串重复次
   
3. '''
   
4. 
   
5.                   
   
6. s1 = 'abccdeabbf'
   
7. s2 = 'ab'
   
8. output = 2
   
9. 
   
10. m = s1.count(s2)
    
11. print(m)

复制代码

1. '''
   
2. 合并overlap数值区间
   
3. '''
   
4. 
   
5. a = [[2, 3], [1, 4], [2, 10], [20, 30]]
   
6. output = [[1, 10], [20, 30]]
   . check 1point3acres for more.
7. 
   
8. a.sort()
   
9. start = a[0][0]
   
10. end = a[0][1]
    
11. output = []
    
12. for i in range(1,len(a)):
    
13.     if end >= a[i][0] and end <= a[i][1]:
    
14.         end = a[i][1]
    
15.     elif end < a[i][0]:
    
16.         output.append([start,end])
    
17.         start = a[i][0]
    
18.         end = a[i][1]
    
19. output.append([start,end])
    
20. print(output)

复制代码