jingchi 电面+onsite

电面：给一列字符串，判断是否能接龙。接龙相邻的两个字符串要求满足 前一个的最后一个字符等于后一个的第一个字符。follow up：construct接龙顺序

onsite:
1. 一维直线上有若干村庄，能够建若干个仓库，每个村庄的cost为距离其最近的仓库到它距离的平方，求最小cost总和
2. 给一个矩阵，0表示无障碍物，1表示有障碍物，从上往下走，问有多少条路径可以到

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

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

”， “123” -> “122312” > "12123"

xbbjames1 发表于 2018-2-6 14:39
兄弟， 你看了下你这个状态转移方程 我有一个问题啊？ 当你选了S(k, u) = S(k-i, u-1) + Cost(k-i+1, k)  ...

这是个好问题，考虑动态规划算法给出的最优划分，实质上是如下问题的最优解：

将V1, ..., Vn划分成m个区间，使Wi取值为第i个区间的所有村庄位置的平均值，求cost最小的划分方案

而你的意思是说，动态规划算法给出的“最优划分”，是否会出现这样的情况：

存在两个区间S、T，其中S中的某个村庄（比起S自身的中值点）反而更靠近T的中值点。

答案是不可能有这样的情况，用反证法不妨设某些村庄离其他区间的中值点更近，那么我们做如下操作：

(1) 将这些村庄移入对应的距离最近的区间
(2) 调整受影响区间的中值重新计算cost

那么，(1)+(2)本质上是K-means算法的1D特例的一个iteration，可以证明cost一定是减小的（分别考虑(1)和(2)，都是减小cost的；或者可以看下这个ppt的Proof of monoticity那一页：http://web.engr.oregonstate.edu/ ... /clustering2-16.pdf）

这与动态规划给出的cost的最优性矛盾。▢



补充内容 (2018-2-7 14:58):
还搜到一篇文章就是讲的一模一样的状态转移方程（居然有100多引用..）：
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5148156/#!po=95.5882

不过文章里面也没有对最优性进行证明

这破公司，面试题目还不简单呀

kate8528577 发表于 2018-1-27 04:50
onsite的第一题楼主怎么解答的呢我一直没有思路

设村庄数目为n，表示为V1, ..., Vn，且不妨设V1 <= ... <= Vn
设仓库数目为m，表示为W1, ..., Wm

首先考虑m = 1的情况，也就是只有一个仓库。那么问题就是求W1的值，使得

1. (V1 - W1)^2 + ... + (Vn - W1)^2

复制代码

的值最小。

使用微积分的知识我们可以知道当

1. W1 = (V1 + ... + Vn) / n

复制代码

时 —— 也就是W1是所有村庄中点时 —— 上面的表达式有最小值。

现在考虑有多个仓库的情况，这等价于将V1, ..., Vn划分成m个区间，使Wi取值为第i个区间的中点，求cost最小的划分方案

那么就是动态规划了，定义：

1. 
   
2. S(k, u) = 前k个村庄放置u个仓库的最小cost
   
3. 
   
4. C(i, j) = 将仓库建在Vi, ..., Vj中点处的cost，这个值可以O(j-i+1)时间内计算出来
   

复制代码

那么状态转移方程：

1. 
   
2. S(k, 1) = C(1, k)
   
3. 
   
4. S(k, u) = min( S(k-1, u-1) + C(k, k),
   
5.                S(k-2, u-1) + C(k-1, k),
   
6.                ...
   
7.              )
   

复制代码

时间复杂度O(m * n * n) —— 不确定还有没有进一步优化
空间复杂度O(n) —— 使用滚动数组的话

恭喜~

jingchi的package咋样呢？LZ能否透露下

楼主要做OA嘛

onsite的第一题楼主怎么解答的呢我一直没有思路

多谢多谢多谢多谢多谢多谢多谢

siyangdream 发表于 2018-1-26 10:40
楼主要做OA嘛

没做，直接电面的

ReMind 发表于 2018-1-27 10:00
没做，直接电面的

好的，谢谢楼主

请问楼主，电面那道题，construct接龙就是调换数组元素的位置让他组成接龙对吗？