Google新加坡OA 2020题目汇总

OA两个题，Leetcode medium难度 ，但是用Hackerearth做题真的挺不方便的，甚至有的test cases在Hackerearth UI现在未通过，但是Summit之后显示全对。
第一题：Find the smallest substring that contains K character C in a string S
第二题：
给一个matrix A，如下，U/D/L/R分别代表向上

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

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

through the original string and put the index of C into an array "arr"
Then find the smallest difference between adjacent elements in "arr"

稍微难一点的第二题 30分

再来两个题

1.     def minCost(grid):
   
2.         m, n = len(grid), len(grid[0])
   
3.         heap = [(0, (0, 0))]
   
4.         visited = set()
   
5.         while heap:
   
6.             cost, (x, y) = heapq.heappop(heap)
   
7.             if x == m - 1 and y == n - 1:
   
8.                 return cost
   
9.             if (x, y) in visited:
   
10.                 continue
    
11.             visited.add((x, y))
    
12.             for idx, i, j in [('R', x, y + 1), ('L', x, y - 1), ('U', x + 1, y), ('D', x - 1, y)]:
    
13.                 if 0 <= i < m and 0 <= j < n and (i, j) not in visited:
    
14.                     heapq.heappush(heap, (cost + (grid[x][y] != idx), (i, j)))

复制代码

min cost的代码

好棒！非常感谢你的分享！

啊啊啊啊啊啊太谢谢了！

持续更新中！求加米呀！

最后两个题！其他几乎都是重复的了！

Yostas 发表于 2020-10-22 16:34
啊啊啊啊啊啊太谢谢了！

不客气！欢迎加米哈哈哈哈。

yixxxfan 发表于 2020-10-22 16:28
好棒！非常感谢你的分享！

不客气哦，谢谢你给我加米

第一题解题思路：
Method 1: Sliding window
Keep track of the smallest length "min_len" and the index where the substring ends "index"
Move the right boundary "r" 1 index to the right if there's fewer than K character C in the current substring

Method 2:
Loop through the original string and put the index of C into an array "arr"
Then find the smallest difference between adjacent elements in "arr"