7/27 布鲁伯格 电面跪筋

刚接起电话的时候听着像个美国小哥，到后面开始做题的时候小哥的烙印口音就憋不住了。。。。
一开始是介绍自己，然后就自己挑一个自己做过的最有意思的项目说说，然后讲讲这个项目最有挑战性的地方。 说完之后就直接上codepair做题。之前还以为用codepair是要自己写test case跑，结果是自己用嘴跑一遍test case就可以了。楼主碰到的都是新题，

第一题是给了一串0,1,0,1,1,1,1,1,0,0,0,1.......的数组， 然后给了一个K， 表示最多可以翻转K个

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

之后和朋友讨论才知道还可以用dp做。
第二天早上就收到拒信了，不知道是被烙印黑了还是楼主的问题，让楼主哭会

jy_121 发表于 2016-8-1 01:52
哪位同学能详细说下dp的解法啊。谢谢了

写了一个 感觉像背包问题~

1. class Solution {
   
2.         public int getMaxProfit(int[] arr){
   
3.                 if(arr == null || arr.length == 0) return 0;
   
4.                 int[] dp = new int[arr.length + 1];
   
5.                
   
6.                
   
7.                 for(int i = 1; i <= arr.length; i++){
   
8.                         dp[i] = arr[i - 1];
   
9.                         for(int j = 0; j <= i; j++){
   
10.                                 dp[i] = Math.max(dp[i], dp[i - j] + dp[j]);
    
11.                         }
    
12.                 }
    
13.                 return dp[arr.length];
    
14.         }
    
15.        
    
16.         public static void main(String[] args) {
    
17.                 Solution r = new Solution();
    
18.                 int[] arr = {1, 4, 7, 9,12, 3,15,20};
    
19.                 int max = r.getMaxProfit(arr);
    
20.                 System.out.println(max);
    
21.         }
    
22. }

复制代码

第一题可以这样写？

public int kBinary(int[] arr, int k) {

        int maxLen = 0;
        Queue<Integer> zeroes = new LinkedList<Integer>();
        int left = -1, right = 0;

        while (right < arr.length) {

                if (arr[right] == 0) {

                        if (zeroes.size() == k) {
                                left = zeroes.poll();
                        }

                        zeroes.offer(right);
                        maxLen = Math.max(maxLen, right - left);

                }

                right++;
        }

        maxLen = Math.max(maxLen, arr.length - 1 - left);
        return maxLen;
}

第二题类似knapsack？

LZ别哭，继续加油噜
我bb有轮电面做了三题 最后一题还要跑几十个test cases
都完成了然后一样悲剧。。。

这个和那个刺破气球的题有一拼吧，高级dp

Fustang 发表于 2016-7-29 04:48
第二题类似knapsack？

LZ别哭，继续加油噜

做了三题还悲剧。。。是烙印面的你吗？

感觉第二题可以用DFS做哦，优化用DP？第一题小哥给的hint是什么呀？

感觉是被黑了。。。bb电面应该难不到这个程度，一个月前都还是两道easy就能过的。。

hnyjy 发表于 2016-7-30 01:10
感觉第二题可以用DFS做哦，优化用DP？第一题小哥给的hint是什么呀？

他说你从第一个1开始，然后该怎么做，我说继续往下找1，他问那你现在看到0该怎么办，我说翻转然后从K里减一。基本上没什么有效的提示。。。。。。

糖果栅儿 发表于 2016-7-31 20:50
他说你从第一个1开始，然后该怎么做，我说继续往下找1，他问那你现在看到0该怎么办，我说翻转然后从K里减 ...

我说的是第二题。。。

糖果栅儿 发表于 2016-7-31 20:50
他说你从第一个1开始，然后该怎么做，我说继续往下找1，他问那你现在看到0该怎么办，我说翻转然后从K里减 ...

不好意思，我打错了。。。

第一题应该是O(n)就能做。 大致意思是这样：从第一个1（head）开始往后面延伸，碰到0就翻直到用完k次（记录尾巴tail, 长度为tail-head），在这个过程中同时用queue记录遇到的所有的0的区间；然后pop第一个0区间，区间右端点＋1为新的head, 假使这个区间有m个0，那从tail开始继续翻m个0, 更新长度；重复这个流程。有一些特殊情况比如tail到序列的底部的就从head往左翻0，如果这样也就能提早结束iteration了。

第二题是dp，只用记录8个。