微软苏州4面挂经

第一轮
二叉树左视图
bfs   要求递归 （没想出来）   
两个有序数组求第k大的数（没写出最优解 刷题王狄思提）
. 1point3acres.com 第二轮
问了项目
问了用什么语言：java
方法重载和重写的区别  局部变量和全局变量的区别
算法
给一个字符串 里面只有数字和字母  找出字母和数字长度最长的连续子串（前缀和）
第三轮
算法：中文大写数字转换为阿拉伯数字（没写出来，应该是用stack解决）
第四轮
上来就问你解决的最大难题
数据库的acid 和事务解释下，怎么sql调优的
算法题: 给定一个包含整数的无序数组和一个目标值，求和为这个目标值得数组组合有多少（数组不用连续），求数量，数字可能为负和重复
先排序 然后 dfs
问了处了dfs还有什么更好的解法（没想出来，最后问了面试官  怎么解决更好（问了两遍）， 他说你去网上搜下就行，这题很经典的，我有点蒙了，然后我就不想问了）
. From 1point 3acres bbs

第一题二叉树左视图用递归的话需要一个全局变量，维护目前为止探测过的最深深度，然后正常的前序遍历就行了，dfs过程中传递当前深度和指针，发现当前深度大于全局变量就代表发现了新的左视点

那么多人把 subset sum 的变种当成背包说明题刷的还是不够啊

1. int solve(const vector<int>a, int k) {
   
2.     int lo = 0;
   
3.     int hi = 0;
   
4.     for (int t : a) {
   
5.         if (t < 0) lo += t; else hi += t;
   
6.     }
   
7.     auto dp = make_unique<int[]>(hi-lo+1);
   
8.     dp [-lo] = 1;
   
9.     for (int t : a) {
   
10.         if (t > 0)      for (int x=hi-lo; x>=t;       x--) dp[x]+=dp[x-t];
    
11.         else if (t < 0) for (int x=0;     x<=hi-lo+t; x++) dp[x]+=dp[x-t];
    
12.     }
    
13.     return dp[k-lo];
    . check 1point3acres for more.
14. }
    
15. 
    
16. // [1,2,1,2],3 ==> 4
    
17. // [4,-3,2], 3 ==> 1
    
18. // [-2,2],   0 ==> 2
    

复制代码

baihou 发表于 2020/06/03 00:29:15
请问面的哪个组，有英文面试吗

有自我介绍，和简单问答

四面好像lc上面combination或者target sum的题目

子轩不语 发表于 2020/06/01 18:08:31
四面好像lc上面combination或者target sum的题目

不一样，好像只能dfs

mazrim-- 发表于 2020-6-1 18:53
不一样，好像只能dfs

combination sum ii? (答案里也有用dfs的）

求所有方案才是 dfs，如果只问多少种就是背包，可以重复就是完全背包，想到这里就是很经典模板题了

我只想说以我的经验，面试官可能并没有一个清晰完整的解决方案，最后只好让你自己下来搜

最后一题如果是子数组的个数那是刷题网物流领，不知道那个数组不用连续指的是什么？是从数组里挑若干个数，看和是否等于target？如果那样应该是记忆化递归或者dp来做

中文转阿拉伯那个需要考虑各种异常输入么？如果都是正常输入，可以用递归

byroncheng 发表于 2020/06/01 20:40:54
求所有方案才是 dfs，如果只问多少种就是背包，可以重复就是完全背包，想到这里就是很经典模板题了

关键是有负数，怎么背包？