17年10月狗家昂赛intern conversion两轮面经

很简单，第一轮
第一题： 给一段代码问返回啥，大致意思是遍历0-9999， 如果这个数字含有13，那么count＋＋，问最后count是多少
follow up：如果 0-9999

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

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

etwork，问两个人能不能被连起来，我说bfs，follow up：如果图很大，怎么优化

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

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

庭有枇杷树 发表于 2017-10-6 10:25
请问第一轮第二题怎样DP呢？第二轮第二题用union find可不可以？

我是这么想的, dp[n]代表长度为n时13的数量.
dp[0]=dp[1] = 0; d[2] = 1;
dp[n] = dp[n-1]*10+dp[n-2].

庭有枇杷树 发表于 2017-10-6 10:25
请问第一轮第二题怎样DP呢？第二轮第二题用union find可不可以？

那题好像是leetcode 139. union find还真没想到，感觉好像可以

祝offer，求问楼主最后一个follow up，如果图特别大，怎么优化呢

第一轮第二题用字典树是O(n)的复杂度. 第一轮第一题其实也是dp.

请问第一轮第二题怎样DP呢？第二轮第二题用union find可不可以？

GardenAAA 发表于 2017-10-6 03:00
祝offer，求问楼主最后一个follow up，如果图特别大，怎么优化呢

不知道啊，我说用cache

follow up感觉就是在问union find

楼主请问第二轮第二题，如果我回答从两端同时开始bfs，这样找中间点，会不会缩短时间呢？