Shopkick面试

刚刚面了shopkick， 两道题， 第一道题比较简单， 就是给个string， 给个max width , 然后输出格式为

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

做出来， 感觉用dp， 但也没construct出来。

f[i][j] 表示前i个单词组成j行最少得cost， 那么f[i][j] = min{f[k][j - 1] + (length(words[k + 1 .. i]) - max_width)^2}

北美农民 发表于 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-5 20:49
那你的意思是从f[n]

中找到最小的。 但是他要我输出最小的cost的word combination。这样的话， 怎么记 ...

你再复述遍题目？说清楚些

北美农民 发表于 2014-12-6 09:51
你再复述遍题目？说清楚些

要求打印出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
is
good
for
health

but 不是cost最小的...

论坛匿名用户 发表于 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是一行

北美农民 发表于 2014-12-6 10:04
用track[ i ][ j ]记录状态转移点就行了。 假设track[ i ][ j ] = k, 那么找track[ k ][ j - 1], 并且 k  ...

没想到用行当作一维， 最后用dfs做的， 我也是跪了。。

我昨天去考了一模一樣的，不過第二題 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”(忘記怎麼做了，跪)

rwei 发表于 2015-3-4 06:17
我昨天去考了一模一樣的，不過第二題 interviewer 跟我說 assume 我有 unlimited memory 而且可以 take unl ...

这是第几轮面试啊。。。第一轮recruiter面应该不是这些吧

不开心啊，被shopkick的电话面试放鸽子了！