Google 昂赛

11.15 昂赛

听说G家内部题库一千多道，就没怎么刷题准备。吃吃喝喝倒是挺爽的，强烈推荐san jose的韶山印象，不错的湘菜哈哈哈。

G家昂赛感觉没有FB那么形式化，比较casual。地点在tech corners

十点半刚到building，一个俄罗斯小哥招呼我面试。

喝了杯咖啡，小哥看看表，问我想不想提前开始，我说好～

1. dp题。给一个grid的宽和长，求得从左下的点到右下的点所有可能的路径之和。

起点当然是左下，要求每次只能走三个方向， ➡

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

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

ue.

这题楼主没做过，后来发现就是ugly number ii。我花了45分钟勉强写一个O(nlogn)，面试官心里的答案是O(n)

挂的妥妥的。

总体来看题并不难，怪自己刷题不够。恶补基础了

renou 发表于 2018-1-15 03:08
写了个扫地机器人代码，大家看看行不行？

def clean_room(robot, i, j, d, visited):

这应该是不行的  我没有理解错的话 这道题的难点就是你不知道机器人一开始的坐标 也不知道房间的地图

大概思路应该是假设机器人一开始在中间，然后你自己假设一个足够大的未探索‘’迷宫‘’ 然后用数据结构经典例题  栈走迷宫的办法(iterative) 或者是dfs(recursive) 然后使用api探索的， 边探索边更新迷宫的值

比如你假设这个房间最多50*50， 你就一开始初始化一个100*100 的char[][] 就假设机器人从 （50,50）开始  除了（50， 50）其余的都是‘*’ 表示未探索 然后你走到一个地方如果撞墙了就把‘*’ 改成1 else 改成0 应该大概就是这样子

楼主可以再讲下第一题吗？是可以走哪三个方向？？从左下到右下感觉挺奇怪的

写了个扫地机器人代码，大家看看行不行？

def clean_room(robot, i, j, d, visited):
    delta = [(-1, 0), (0, 1), (1, 0), (-1, 0)]
    for k in range(4):
        new_d = (d + k) % 4
        di, dj = delta[new_d]
        if (i + di, j + dj) not in visited:
            visited.add((i + di, j + dj))
            moved = robot.move()
            if moved:
                clean_room(robot, i + di, j + dj, new_d, visited)
                # point to op dir
                robot.move()
                robot.turn_right(2)
            robot.turn_right(1)
    robot.turn_right(2)

谢谢楼主分享～ 请问第一题没有给grid里面的值吗？ 只给宽和高的话求路径和的意思是？

别的题都是leetcode medium/easy题没啥好说的   那个机器人题具体展开讲讲？

楼主能不能再说说第二轮那个封装extra 参数的题？

这个“{4, 0, x}, {3, 3, x}, {2, 2, x}, {1, 5, x} 答：binary search”是啥意思啊？

edyyy 发表于 2017-11-21 12:04
这个“{4, 0, x}, {3, 3, x}, {2, 2, x}, {1, 5, x} 答：binary search”是啥意思啊？

做个累积和就好了，之后就可以binary search

大懒懒一休哥 发表于 2017-11-21 11:34
谢谢楼主分享～ 请问第一题没有给grid里面的值吗？ 只给宽和高的话求路径和的意思是？

没有的，举个例子：

|---|----|-----|
|---|----|-----|
|---|----|-----|

这是一个宽为3，高为2，那么只考虑这上面的所有点也就是12个点。
就是说其实要建立的矩阵是4*3的

hychin 发表于 2017-11-21 11:46
别的题都是leetcode medium/easy题没啥好说的   那个机器人题具体展开讲讲？

那道题，api 是这样的

bool move();
void turnRight(int n);
void turnLeft(int n);
void clean();

要求探索一个未知的房间。
实现就要用dfs然后clean到底之后要move back回原来的点
四个方向要用api实现，要对应好，然后move back回来的时候需要调整方向

edyyy 发表于 2017-11-21 12:04
这个“{4, 0, x}, {3, 3, x}, {2, 2, x}, {1, 5, x} 答：binary search”是啥意思啊？

x就是多封装出来的参数，我选的是total number of elements at that point.
这样就能用idx进行二分查找。

lidongze91 发表于 2017-11-21 13:34
那道题，api 是这样的

bool move();

如果是未知空间，你怎么记录哪些房间是已经访问过的了避免重复访问？