《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2653|回复: 9
收起左侧

[找工就业] Shopkick面试

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

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

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

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

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

ps: 输入string是由word和space组成。
. 鍥磋鎴戜滑@1point 3 acres
第二题没做出来, 感觉用dp, 但也没construct出来。. 1point 3acres 璁哄潧


.1point3acres缃

评分

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
    那你的意思是从f[n]
  • 中找到最小的。 但是他要我输出最小的cost的word combination。这样的话, 怎么记 ...

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

    使用道具 举报

     楼主| adiggo 发表于 2014-12-6 09:56:58 | 显示全部楼层
    北美农民 发表于 2014-12-6 09:51-google 1point3acres
    你再复述遍题目?说清楚些

    要求打印出cost最小的word combination。. from: 1point3acres.com/bbs
    input:"apple is good for health"
    maxlength is 9. more info on 1point3acres.com
    output:. From 1point 3acres bbs
    apple is    (9-8)^2
    good for     (9-8)^2
    health        (9-6)^2
    假设这个是cost的最优解, 打印出:. visit 1point3acres.com for more.
    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 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    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. 1point3acres.com/bbs
    我昨天去考了一模一樣的,不過第二題 interviewer 跟我說 assume 我有 unlimited memory 而且可以 take unl ...
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    这是第几轮面试啊。。。第一轮recruiter面应该不是这些吧
    回复 支持 反对

    使用道具 举报

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

    使用道具 举报

    本版积分规则

    关闭

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

    手机版|小黑屋|一亩三分地论坛声明

    custom counter

    GMT+8, 2017-11-20 16:07

    Powered by Discuz! X3

    © 2001-2013 Comsenz Inc. Design By HUXTeam

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