在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2777|回复: 9
收起左侧

[找工就业] Shopkick面试

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

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

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

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

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

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

第二题没做出来, 感觉用dp, 但也没construct出来。. 牛人云集,一亩三分地

来源一亩.三分地论坛.
.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. visit 1point3acres for more.
    那你的意思是从f[n]
  • 中找到最小的。 但是他要我输出最小的cost的word combination。这样的话, 怎么记 ...

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

    使用道具 举报

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

    要求打印出cost最小的word combination。
    input:"apple is good for health"
    maxlength is 9
    output:.1point3acres网
    apple is    (9-8)^2
    good for     (9-8)^2
    health        (9-6)^2
    假设这个是cost的最优解, 打印出:
    apple is   
    good for    . Waral 博客有更多文章,
    health        
    . more info on 1point3acres
    只用你刚才建的dp, 应该只能输出最小值吧。

    . from: 1point3acres
    补充内容 (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. From 1point 3acres bbs
    good
    for
    health

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

    使用道具 举报

    北美农民 发表于 2014-12-6 10:04:32 | 显示全部楼层
    adiggo 发表于 2014-12-5 20:56. 围观我们@1point 3 acres
    要求打印出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”(忘記怎麼做了,跪)
    Mobile Apps Category (English)728x90
    回复 支持 反对

    使用道具 举报

    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的电话面试放鸽子了!
    回复 支持 反对

    使用道具 举报

    本版积分规则

    提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

    ■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
    ■意思是:用户积分低于200则看不到被隐藏的内容
    ■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
    ■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
    ■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
    ■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

    关闭

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

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

    custom counter

    GMT+8, 2018-5-23 06:07

    Powered by Discuz! X3

    © 2001-2013 Comsenz Inc. Design By HUXTeam

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