新鲜的amazon Intern VO面经

新鲜的面经：
tight deadline, responsibility 我说了我当peer tutor, 然后不满意说要technical project responsibility，45分钟浪费了25分钟在这个上面
coding：给你个2d grid 起始点和终点，有些grid是blocked的，问从起点到终点走最少需要转几个弯
coding的应该是这题
https://www.1point3acres.com/bbs/thread-516663-1-1.html
这题太难了，从来没见过
没答上来，哭了，就一个bfs的思路，不允许用backtracking
求加米

补充内容 (2022-08-22 01:37 +8:00):
题目是
一个迷宫，给起点终点，有api可以检测当前四个方向是否有墙。问如何minimize转弯的次数到达终点（只要经过终点就算到达）
不一定要走到头

补充内容 (2022-08-23 08:02 +8:00):
今天进了

coding：给你个2d grid 起始点和终点，有些grid是blocked的，问从起点到终点走最少需要转几个弯

请问这题具体思路是什么啊。
一个2d grid 去记录当前的cell 有没有访问过。
起始点是给的起点（x,y）.
每次向上向下或者向左向右，
每次push 位置进queue的时候，有两种可能呀。向上向下转弯次数不变，向左向右，转弯次数+1。那这个怎么记录呢。创建一个新的class？自带转弯count？

而且传统bfs每次都可以向上向左右向右同时push进queue的时候，思想是先到了destination的(x,y)了那就一定是最点路径。

这道题，要怎么保证同时push进去的时候，转弯次数一定是最少的呢？ 把queue换成priorityqueue？用新建class里自带的转弯count计数？

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

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

起点不确定是 (0, 0) 的话dp不太好做把好像，如果确定是 (0, 0) 的话dp好像可以，每一步判断一下上面和左边的格子是不是转弯的，如果是就加一。
我的思路是bfs从起点四个方向走到end，然后路径上所有点加进queue，转弯加一，重复直到碰到终点？

楼主你发的链接打不开了，可以再发一下吗，谢谢

sweeter0306 发表于 2022-8-20 21:56
楼主你发的链接打不开了，可以再发一下吗，谢谢

我感觉和利口63很相似，但是需要dp做（不能backtrack），然后增加一个维度存方向

patpat～ 是 bq的故事必须是 简历上的 project么？

最近的vo都好难，不是ood就是sd T_T
感觉bar升了好多

匿名用户 发表于 2022-08-20 22:09:11
我感觉和利口63很相似，但是需要dp做（不能backtrack），然后增加一个维度存方向

可以用bfs吗

zzpYRWO 发表于 2022-8-21 12:13
起点不确定是 (0, 0) 的话dp不太好做把好像，如果确定是 (0, 0) 的话dp好像可以，每一步判断一下上面和左边 ...

一个方向上面的点的左右两边是新的breadth，直接先加到queue里面做bfs

sweeter0306 发表于 2022-8-21 00:56
楼主你发的链接打不开了，可以再发一下吗，谢谢

补充内容写了

AnnaNotHanna 发表于 2022-8-21 12:04
可以用bfs吗

+1, 看上去是一个典型的 medium难度bfs