May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2447|回复: 9
收起左侧

[找工就业] Shopkick面试

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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

ps: 输入string是由word和space组成。

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



评分

2

查看全部评分

北美农民 发表于 2014-12-6 09:37:20 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
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 | 显示全部楼层
关注一亩三分地微博:
Warald
北美农民 发表于 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. more info on 1point3acres.com
    那你的意思是从f[n]
  • 中找到最小的。 但是他要我输出最小的cost的word combination。这样的话, 怎么记 ...

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

    使用道具 举报

     楼主| adiggo 发表于 2014-12-6 09:56:58 | 显示全部楼层
    北美农民 发表于 2014-12-6 09:51
    .1point3acres缃你再复述遍题目?说清楚些
    . 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的最优解, 打印出:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    apple is   
    good for   
    health        

    只用你刚才建的dp, 应该只能输出最小值吧。


    补充内容 (2014-12-6 10:00):
    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 . more info on 1point3acres.com
    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
    . 鍥磋鎴戜滑@1point 3 acres
    用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. From 1point 3acres bbs
    用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 以後優化的,可惜沒時間了. from: 1point3acres.com/bbs
    我還被考了“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的电话面试放鸽子了!
    回复 支持 反对

    使用道具 举报

    本版积分规则

    关闭

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

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

    custom counter

    GMT+8, 2017-5-24 09:15

    Powered by Discuz! X3

    © 2001-2013 Comsenz Inc. Design By HUXTeam

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