一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 1158|回复: 9
收起左侧

tusimple SDE general电面一轮挂经

[复制链接] |试试Instant~ |tusimple, 面试经验, 美国面经, 码农类general
论坛匿名账号
论坛匿名账号  发表于 2020-2-27 17:26:37 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎

2019(10-12月) 码农类General 硕士 全职@tusimple - 内推 - 技术电面  | Fail/Rej | fresh grad应届毕业生

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

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

x
SDE new grad General 岗位
发一道图森的电面题,没有做出来,第一次遇到这样的题,没有什么思路。
输入一个足够大的二维矩阵,矩阵元素只有0 和 1, 我们把这个矩阵横向切m次,纵向切n次,分成(m+1) * (n+1) 块。
请问是否有这样一种分割方法,使每个小矩阵上的1的总个数全部相同。
example1:
m = 1, n =
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

---- |-----
1 1 | 1 1
0 0 | 0 0
return true

评分

参与人数 3大米 +11 收起 理由
AliceLin2019 + 2 很有用的信息!
Taylor_Bird + 1 给你点个赞!
清道神君 + 8

查看全部评分


上一篇:cisco OA (求大米)02/27
下一篇:OCI new grad 面经
我的人缘0
顶顶 2020-3-6 00:55:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
感觉是用dfs + backtracking试遍所有分割的可能
回复

使用道具 举报

我的人缘0
AlchemistTan 2020-3-6 09:04:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
我觉得可以根据定义来做,先把整个matrix扫一遍,算出每行每列的1的个数。然后纵向每一刀要左边必须有m + 1的整数倍个1才能在横向切割的时候有可能能使得每一刀形成的区域都有1.横向切割同样处理。但是这样切完不能保证你这么切就一定能得到切法。如果这个matrix是有可行切法,那么一定是这么切,如果没有可行切法,你也有可能找到符合上面条件的切法,例子:
1 0 |0 0
0 1 |0 0
---------
0 0 |1 0
0 0 |0 1
横竖割一刀,但是没有这么个切法,所以你切完后还得验证一下这么切能否使得每个submatrix都有1
回复

使用道具 举报

我的人缘0
顶顶 2020-3-8 06:51:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
AlchemistTan 发表于 2020-3-5 20:04
我觉得可以根据定义来做,先把整个matrix扫一遍,算出每行每列的1的个数。然后纵向每一刀要左边必须有m + 1 ...

请问有没有好的方法在已知怎么分割的情况下快速验证每个submatrix的和相等?
回复

使用道具 举报

我的人缘0
AlchemistTan 2020-3-8 07:25:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
顶顶 发表于 2020-3-8 06:51
请问有没有好的方法在已知怎么分割的情况下快速验证每个submatrix的和相等?

计算怎么切的时候把切割位置记录下来,然后用两层for循环把所有submatrix扫一边,因为本质还是遍历一遍matrix,时间复杂度不会增加,一开始我们是可以计算出每个submatrix里面应该有多少个1的(1的总数/((m +1)*(n + 1))),当遍历到某个submatrix的1的和不等于该数返回直接返回false。成功遍历完返回true就行了。再简单的方法没想到
回复

使用道具 举报

论坛匿名账号
论坛匿名账号  发表于 2020-3-8 07:34:25
本楼: 👍   0% (0)
 
 
0% (0)   👎
先计算1的总数,然后每小块有几个,每行,每列有几个都是定死的,然后线性扫一遍不就好了
回复

使用道具 举报

我的人缘0
顶顶 2020-3-8 08:11:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
AlchemistTan 发表于 2020-3-7 18:25
计算怎么切的时候把切割位置记录下来,然后用两层for循环把所有submatrix扫一边,因为本质还是遍历一遍ma ...

对,我也是这么想的,但是即使在知道分割线在哪里的情况下,判断原matrix每一个1到底属于哪一个submatrix的时间复杂度我觉得不是O(1),因为每一个(i, j)都得判断i夹在 row_cut_array的哪个位置,j 夹在 col_cut_array的哪个位置,最终才能定位这个1属于哪个submatrix,我能想到的判断方法只能是二分搜索,再加上之前两层for loop的复杂度,这个验证过程的负责度应该不是O(MN)
回复

使用道具 举报

我的人缘0
AlchemistTan 2020-3-8 10:10:07 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
或许你可以换一种思路,就拿我第一次回答的例子来看把,切割位置分别都在正中间,我们记录下切割位置为 2 和 2,那么你就可以知道各个submatrix的 i j的范围,比如第一个submatrix 就是 0 < i < 2,  0 < j < 2,后面的submatrix也是同样到理,这样的话就剩去了你说的二分查找位置,其实我一开始的想法就是这样做遍历,可能没说清楚。
回复

使用道具 举报

我的人缘0
gjia0214 2020-3-8 13:22:01 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎
能不能分别求 axis sum 然后尝试分割? 如果能同时做到 equal cut on axis 0 with p lines 和 equal cut on axis 1 with q lines 那么就有解?

思路大概是:
假设这个是可以被割开的,然后我们sum over axis 0 那么 axis 0 上的割线应该刚好能把 axis sum 分割,axis 1 也一样。
回复

使用道具 举报

我的人缘0
stranger66 2020-3-9 01:01:56 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (14)
 
 
0% (0)    👎
顶顶 发表于 2020-3-8 06:51
请问有没有好的方法在已知怎么分割的情况下快速验证每个submatrix的和相等?

可以参考刷题网304
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-4-1 22:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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