谷歌实习电面

职位：Software Engineer Intern (PhD)

第一轮：华人小哥，先问了什么是priority queue，如何implement。然后正式做题

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

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

第二轮：还是华人小哥，两道题。第一题给一个正整数n,找到从1开始的前n个non confusing number。Confusing number 是指倒过来会变成另一个数，比如81，倒过来会变成18，就是个confusing number （18也是）。69倒过来还是69，就不是confusing number。

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

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

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

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

兄弟，我从2011年开始研究navier stokes equations，到今天也要转行了

第一轮：

1. class Solution():
   
2.     def fun(self, nums):
   
3.         # have two points, p0 points to 'a' with step 2,  p1 points to 'b' with step 1
   
4.         p0 = 0
   
5.         p1 = len(nums) // 2
   
6. 
   
7.         while p1 < len(nums) - 1:
   
8.             # remember p1, and move every element from p0 + 1 to p1 - 1 one step further
   
9.             temp = nums[p1]
   
10.             for i in range(p1-1, p0, -1):
    
11.                 nums[i + 1] = nums[i]
    
12. 
    
13.             # p0 + 1 = remember
    
14.             nums[p0+1] = temp
    
15. 
    
16.             # p0 += 2, p1 += 1
    
17.             p0 += 2
    
18.             p1 += 1
    
19.         return nums
    
20. 
    
21. a = Solution()
    
22. print(a.fun([1,3,5,2,4,6]))

复制代码

第二轮第一题： LeetCode有
第二轮第二题： 不重叠， 麻烦的做法

1. class Solution():
   
2.     def max_repeating(self, s):
   
3.         p = 0
   
4.         length = len(s)
   
5.         max_s = ''
   
6.         while p < length:
   
7. 
   
8.             # check i in range [p, (length-p)//2   ]
   
9.             # i means that our maximum length of our basic repeating element
   
10.             # ('baba', basic repeating element is 'ba')
    
11.             # , which is our left element // 2
    
12.             for i in range(0, (length-p)//2 ):
    
13.                 # check if s[p:i+1] == s[i+1: i-p+1]
    
14.                 # continuous check if it will appear 3 times
    
15.                 count = 1
    
16.                 diff = i + 1
    
17.                 start = p
    
18.                 while s[start:start+diff] == s[start+diff:start+diff*2]:
    
19.                     count += 1
    
20.                     start += diff
    
21.                 if count > 1:
    
22.                     if count * diff > len(max_s):
    
23.                         # record max_s
    
24.                         max_s = s[p:p+count*diff]
    
25.             p += 1
    
26. 
    
27.         return max_s
    
28. 
    
29. a = Solution()
    
30. print(a.max_repeating("aaaaaaaxxxxbcbcbc"))
    
31. 
    
32. print(a.max_repeating("abc"))
    

复制代码

第二轮第一题还有个follow up, 如果数字有上限，比如600. 即使倒过来是不同的数，只要大于这个上限就认为是non confusing.比如108，倒过来是801，但是801大于600了，所以108是 non confusing.

第一题怎么做呢

wtcupup 发表于 2019-10-17 00:29
第一题怎么做呢

我自己试了一下，不过复杂度是O（MN）

1. def test1(nums):
   
2.     n = len(nums)//2
   
3.     p1 = 1
   
4.     p2 = n
   
5.     while p1 < len(nums)-1:
   
6.         flag = True
   
7.         if nums[p1] == nums[p1-1]+1:
   
8.             p1 += 1
   
9.             p2 += 1
   
10.             continue
    
11.         #print(nums, p1, p2)
    
12.         while nums[p1] != nums[p1-1]+1:
    
13.             #print('s', nums, p1, p2)
    
14.             nums[p1], nums[p2] = nums[p2], nums[p1]
    
15.             if nums[p1] == nums[p1-1]+1:
    
16.                 p1 += 1
    
17.                 p2 += 1
    
18.                 break
    
19.             else:
    
20.                 if flag:
    
21.                     p2 -= 1
    
22.                     if p2 <= p1:
    
23.                         flag = False
    
24.                         p2 += 1
    
25.                 else:
    
26.                     p2 += 1
    
27.     return nums

复制代码

第二轮第一题1088

第二轮第二题像不像1044？

第一轮: 比较a0 b0第一个元素, 如果a0小 done, 比较a1, 如果b0小， 遍历bi直到bi大于a0， 这之间的所有对应的a0 - b1, a1 - b2全部交换， 然后同第一步操作 应该是O(N)
第二轮第一题 估计confusing number个数然后DFS找减一下？但是直接从1到n跑一边也是nlogn啊...
第二轮第二题 这个？ https://www.geeksforgeeks.org/lo ... rlapping-substring/ 或者后缀数组 可重叠吗?

真的是实习吗。。。这也太难了吧（还是我太菜了）

感谢分享！