一亩三分地论坛

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

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

[找工就业] Shopkick面试

[复制链接] |试试Instant~ |关注本帖
adiggo 发表于 2014-12-6 09:07:59 | 显示全部楼层 |阅读模式

2014(4-6月)-[12]EE硕士+3个月-1年 - 网上海投| 码农类全职@shopkick

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

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

x
刚刚面了shopkick, 两道题, 第一道题比较简单, 就是给个string, 给个max width , 然后输出格式为每行的word 最多占有max width。
第二题, 是给个cost function,  是每行的输出长度减去max-width 的方。 找到最优解。并且打印出string。-google 1point3acres

ps: 输入string是由word和space组成。 .鏈枃鍘熷垱鑷1point3acres璁哄潧

第二题没做出来, 感觉用dp, 但也没construct出来。



评分

2

查看全部评分

北美农民 发表于 2014-12-6 09:37:20 | 显示全部楼层
f[i][j] 表示前i个单词组成j行最少得cost, 那么f[i][j] = min{f[k][j - 1] + (length(words[k + 1 .. i]) - max_width)^2}
回复 支持 反对

使用道具 举报

 楼主| adiggo 发表于 2014-12-6 09:49:19 | 显示全部楼层
北美农民 发表于 2014-12-6 09:37
f[j] 表示前i个单词组成j行最少得cost, 那么f[j] = min{f[k][j - 1] + (length(words[k + 1 .. i]) - max_ ...

那你的意思是从f[n]
  • 中找到最小的。 但是他要我输出最小的cost的word combination。这样的话, 怎么记录word combination呢, 你这样应该还是不知道具体的每行放什么单词把。
  • 回复 支持 反对

    使用道具 举报

    北美农民 发表于 2014-12-6 09:51:18 | 显示全部楼层
    adiggo 发表于 2014-12-5 20:49-google 1point3acres
    那你的意思是从f[n]
  • 中找到最小的。 但是他要我输出最小的cost的word combination。这样的话, 怎么记 ...

  • 你再复述遍题目?说清楚些
    回复 支持 反对

    使用道具 举报

     楼主| adiggo 发表于 2014-12-6 09:56:58 | 显示全部楼层
    北美农民 发表于 2014-12-6 09:51
    你再复述遍题目?说清楚些
    . From 1point 3acres bbs
    要求打印出cost最小的word combination。
    input:"apple is good for health"
    maxlength is 9
    output:
    apple is    (9-8)^2
    good for     (9-8)^2
    health        (9-6)^2
    假设这个是cost的最优解, 打印出:
    . 1point 3acres 璁哄潧apple is   
    good for   
    health        . 鍥磋鎴戜滑@1point 3 acres
    . 1point3acres.com/bbs
    只用你刚才建的dp, 应该只能输出最小值吧。. From 1point 3acres bbs


    补充内容 (2014-12-6 10:00):. 1point3acres.com/bbs
    cost= sum of ((each line length - max_width)^2). Each line maximum allow words whose length is smaller than max_length. So the combinatio also can be :
    apple
    is
    good
    for
    health

    but 不是cost最小的...
    回复 支持 反对

    使用道具 举报

    北美农民 发表于 2014-12-6 10:04:32 | 显示全部楼层
    adiggo 发表于 2014-12-5 20:56
    要求打印出cost最小的word combination。
    input:"apple is good for health"
    maxlength is 9

    用track[ i ][ j ]记录状态转移点就行了。 假设track[ i ][ j ] = k, 那么找track[ k ][ j - 1], 并且 k + 1 到 i是一行
    回复 支持 反对

    使用道具 举报

     楼主| adiggo 发表于 2014-12-6 10:07:02 | 显示全部楼层
    北美农民 发表于 2014-12-6 10:04
    用track[ i ][ j ]记录状态转移点就行了。 假设track[ i ][ j ] = k, 那么找track[ k ][ j - 1], 并且 k  ...

    没想到用行当作一维, 最后用dfs做的, 我也是跪了。。
    回复 支持 反对

    使用道具 举报

    rwei 发表于 2015-3-4 06:17:29 | 显示全部楼层
    我昨天去考了一模一樣的,不過第二題 interviewer 跟我說 assume 我有 unlimited memory 而且可以 take unlimited time。他主動叫我寫 brute force,generate all ways of splitting。(我估計他本來想讓我寫好 brute force 以後優化的,可惜沒時間了
    我還被考了“get nth smallest element from binary search tree”, “clone graph”(leetcode) 和 “implement quick sort”(忘記怎麼做了,跪)
    回复 支持 反对

    使用道具 举报

    hit_piggy 发表于 2015-3-19 03:45:06 | 显示全部楼层
    rwei 发表于 2015-3-4 06:17
    我昨天去考了一模一樣的,不過第二題 interviewer 跟我說 assume 我有 unlimited memory 而且可以 take unl ...
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    这是第几轮面试啊。。。第一轮recruiter面应该不是这些吧
    回复 支持 反对

    使用道具 举报

    哆啦嗦 发表于 2015-5-6 06:02:53 | 显示全部楼层
    不开心啊,被shopkick的电话面试放鸽子了!
    回复 支持 反对

    使用道具 举报

    本版积分规则

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

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

    关闭

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

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

    custom counter

    GMT+8, 2016-12-5 16:59

    Powered by Discuz! X3

    © 2001-2013 Comsenz Inc. Design By HUXTeam

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