📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2433| 回复: 6
跳转到指定楼层
上一主题 下一主题
收起左侧

[找工就业] Tusimple2轮挂经

全局:

2019(1-3月)-EE硕士+3个月-1年 | 内推| 码农类General全职@tusimple

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
之前有两轮电面,然后第二轮的时候挂了,分享一波面经一轮
在一个升序的序列中,有k个数字是被替换了,现在希望重新把它排序,不能使用排序算法因为时间复杂度太高
我一开始用的是当遇到一个数字小于它后面的数字,就将这个数字的前段拿出来,然后用merge k sort list 的方法,时间复杂度O(nlogk)
提示下想到另一个是当遇到异常数字,因为无法判断是前面一个被替换还是后面一个被替换,那么就同时把这两个数字取出来,总共2k个排序,然后再merge,时间复杂度O(n + klogk)
. 1point3acres.com
二轮
类似华容道变种,给定一个n*n的matrix,它是打乱的,然后希望恢复成有序,例如
4 6 2    =》 1 2 3
1 5 3           4 5 6
每次只能行或者列的移位  如左移  4 6 2 变成 6 2 4,求恢复有序的最快步骤
思路是bfs,记录每个步骤的state,同时unordered_map记录到每个state的步骤是什么,最后看是否能到获胜的state
感觉都做出来了不知道为什么挂了. ----

评分

参与人数 2大米 +4 收起 理由
qiaoqiao_sweet + 1 很有用的信息!
PhiloVance + 3 给你点个赞!

查看全部评分


上一篇:啊马总 VO 结束一直没消息,是被遗忘了吗
下一篇:转专业C++选手,能投哪些大厂的哪些岗位?加米求建议!
推荐
麻倉枼 2019-4-2 05:13:28 | 只看该作者
全局:
qiaoqiao_sweet 发表于 2019-3-30 19:27
想请问楼主第一题的思路。
如果本来是1234567, 变成了1237654, k =4 。这个时候是应该把123和7654都排序然 ...

根据你的例子,.
1237654,
你最终结果是把它分割成
123, 7, 6, 5, 4, 这四个list。
然后就是merge k sorted list, 不过刷题网是用Linked list,这里是array,但思路是一样的。
你可以弄一个pair<int, pair<int,int>>来记录每个pair (或者说Node,如果你想象成刷题网的那道题),. Waral dи,
pair<first number in the current list, pair<first number index, current array index>>

每一次从queue pop一个node出来后把这个number存进result array里面,然后查当前这个数字是不是当前这个array的最后一个数字(check if this array still has numbers to be checked)。如果有,更新一下这个pair的数据(pair<arrayLis[arrayIndex][numIndex +1], pair<numIndex +1, arrayIndex>>),然后再存进queue里面。直到queue.empty().

Time: O(klogn), k 个sub array,每次sort 时间为 (logn), 总共n个数字。
Space: O(n)
回复

使用道具 举报

推荐
麻倉枼 2019-3-25 00:28:29 | 只看该作者
全局:
华容道那题,用3x3以下可以用BFS做,但4X4之后必须用A*.
最简单就是用个queue记录每一个string state,每次都通过找0的位置来找到当前0的row and col,然后就正常BFS了,最后更新一下state,没看过的就存进queue,看过的就skip。

. 1point3acresA*的话要查g和h 和f = g +h的数值,这个网上查一下就有教程,稍微改一下data structure就能写出来,可是很烦。

评分

参与人数 1大米 +1 收起 理由
opedashila + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
inhow 2019-3-20 12:33:51 | 只看该作者
全局:
求问timeline 二面多久出结果
回复

使用道具 举报

🔗
 楼主| deandx 2019-3-28 05:09:10 | 只看该作者
全局:
inhow 发表于 2019-3-20 12:33. check 1point3acres for more.
求问timeline 二面多久出结果

二面大概过了一个星期之后出的结果
回复

使用道具 举报

全局:
想请问楼主第一题的思路。
如果本来是1234567, 变成了1237654, k =4 。这个时候是应该把123和7654都排序然后再merge吗?
. 1point3acres.com
我努力理解了半天还是没懂...

另外想请教楼主,有k个数字的顺序被打乱了,这里k个数字是连续的吗?

麻烦楼主了,谢谢!
回复

使用道具 举报

全局:
麻倉枼 发表于 2019-4-2 05:13
根据你的例子,
1237654,
你最终结果是把它分割成

谢谢层主的详细解答!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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