一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1404|回复: 19
收起左侧

7/27 布鲁伯格 电面跪筋

[复制链接] |试试Instant~ |关注本帖
糖果栅儿 发表于 2016-7-29 01:08:20 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Bloomberg - 网上海投 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

第一题是给了一串0,1,0,1,1,1,1,1,0,0,0,1.......的数组, 然后给了一个K, 表示最多可以翻转K个0,从0翻转到1。问题是最长的连续的1序列有多长。楼主一开始说了暴力解法,但是觉得肯定有更优,就想了一会,实在没想出来就跟小哥要了下hint,他说到一半我就想到解法了(好像跟他的hint没啥关系的解法?)。楼主用的sliding window的做的, 大概和这道题类似:https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/,小哥说相信这个能work,就继续下一题了。

第二题是给了一个数组,
1, 2, 3, 4, 5, 6,  7,  8
1, 4, 7, 9,12,14,15,20. From 1point 3acres bbs
第一排是index,也是一笔交易中卖出的股票数量,第二排是对应的收益,比如说我第一笔交易卖了三只股票,那么收益就是7。可以选择任意的卖法,比如一只一只的卖,或者也可以一次性卖8只。题目要求求得最大收益。楼主用的recursive的解法,如果一共有8只股票,这一次卖了两只之后,下一层的问题就是一共有6只,求最大收益。用一个global variable存最大收益,碰到大的就更新。小哥好像不是很明白我的解法(为什么不明白啊?!),和他解释了一通之后还是没有完全确信, 之后他就问了一下时间复杂度。面完之后和朋友讨论才知道还可以用dp做。
第二天早上就收到拒信了,不知道是被烙印黑了还是楼主的问题,让楼主哭会. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

5

查看全部评分

何打发123 发表于 2016-8-1 03:06:17 | 显示全部楼层
jy_121 发表于 2016-8-1 01:52
哪位同学能详细说下dp的解法啊。谢谢了
-google 1point3acres
写了一个 感觉像背包问题~
  1. class Solution {
  2.         public int getMaxProfit(int[] arr){
  3.                 if(arr == null || arr.length == 0) return 0;. 1point3acres.com/bbs
  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]);. more info on 1point3acres.com
  11.                         }
  12.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.         }. visit 1point3acres.com for more.
  22. }
复制代码
回复 支持 1 反对 0

使用道具 举报

Fustang 发表于 2016-7-29 04:48:19 | 显示全部楼层
第二题类似knapsack?
. 1point 3acres 璁哄潧
LZ别哭,继续加油噜
我bb有轮电面做了三题 最后一题还要跑几十个test cases. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
都完成了然后一样悲剧。。。
回复 支持 反对

使用道具 举报

llatjob 发表于 2016-7-29 06:55:38 | 显示全部楼层
这个和那个刺破气球的题有一拼吧,高级dp
回复 支持 反对

使用道具 举报

 楼主| 糖果栅儿 发表于 2016-7-29 10:41:39 | 显示全部楼层
Fustang 发表于 2016-7-29 04:48
. 1point3acres.com/bbs第二题类似knapsack?

LZ别哭,继续加油噜

做了三题还悲剧。。。是烙印面的你吗?
回复 支持 反对

使用道具 举报

hnyjy 发表于 2016-7-30 01:10:37 | 显示全部楼层
感觉第二题可以用DFS做哦,优化用DP?第一题小哥给的hint是什么呀?
回复 支持 反对

使用道具 举报

stevez 发表于 2016-7-30 01:13:25 | 显示全部楼层
感觉是被黑了。。。bb电面应该难不到这个程度,一个月前都还是两道easy就能过的。。
回复 支持 反对

使用道具 举报

 楼主| 糖果栅儿 发表于 2016-7-31 20:50:21 | 显示全部楼层
hnyjy 发表于 2016-7-30 01:10
感觉第二题可以用DFS做哦,优化用DP?第一题小哥给的hint是什么呀?

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

使用道具 举报

hnyjy 发表于 2016-7-31 22:26:37 | 显示全部楼层
糖果栅儿 发表于 2016-7-31 20:50
他说你从第一个1开始,然后该怎么做,我说继续往下找1,他问那你现在看到0该怎么办,我说翻转然后从K里减 ...

我说的是第二题。。。
回复 支持 反对

使用道具 举报

hnyjy 发表于 2016-7-31 22:27:56 | 显示全部楼层
糖果栅儿 发表于 2016-7-31 20:50. more info on 1point3acres.com
他说你从第一个1开始,然后该怎么做,我说继续往下找1,他问那你现在看到0该怎么办,我说翻转然后从K里减 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不好意思,我打错了。。。
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-7-31 22:41:31 | 显示全部楼层
第一题应该是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个。
回复 支持 反对

使用道具 举报

hnyjy 发表于 2016-7-31 22:54:09 | 显示全部楼层
xihaokai1 发表于 2016-7-31 22:41
第一题应该是O(n)就能做。 大致意思是这样:从第一个1(head)开始往后面延伸,碰到0就翻直到用完k次(记录 ...

8个应该只是个例子吧,是吗?
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-7-31 22:56:17 | 显示全部楼层
hnyjy 发表于 2016-7-31 22:54
8个应该只是个例子吧,是吗?

嗯,8个, n个,道理时一样的嘛
回复 支持 反对

使用道具 举报

hnyjy 发表于 2016-7-31 23:18:14 | 显示全部楼层
xihaokai1 发表于 2016-7-31 22:56
嗯,8个, n个,道理时一样的嘛

嘻嘻,我的意思是dp要记录的是股票的数量,而不是数组的size哦,对吧~
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-1 01:08:23 | 显示全部楼层
感谢楼主分享 不过感觉被黑了 希望碰见国人亲大哥啊
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-8-1 01:52:36 | 显示全部楼层
哪位同学能详细说下dp的解法啊。谢谢了
回复 支持 反对

使用道具 举报

cicean 发表于 2016-9-13 07:05:03 | 显示全部楼层
http://www.geeksforgeeks.org/find-index-0-replaced-1-get-longest-continuous-sequence-1s-binary-array/
http://www.geeksforgeeks.org/find-zeroes-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized/

感觉可以参考下这个 东西
回复 支持 反对

使用道具 举报

fay19 发表于 2016-9-18 22:55:29 | 显示全部楼层
感觉第二题有点像combination sum的变体...
回复 支持 反对

使用道具 举报

Neil_Acton 发表于 2016-9-19 04:19:43 | 显示全部楼层
Fustang 发表于 2016-7-29 04:48 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第二题类似knapsack?
. 1point 3acres 璁哄潧
LZ别哭,继续加油噜

有轮电面?。。所以你有几轮电面呀
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-19 07:03:17 | 显示全部楼层
第一题可以这样写?

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

        int maxLen = 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        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;-google 1point3acres
}
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 08:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表