谷歌实习电面

gxy200992243 发表于 2019-10-17 01:40
兄弟，我从2011年开始研究navier stokes equations，到今天也要转行了

可以的，我三年就坚持不下去了

第一题写了一下，one pass O(n)

1. void wigglesort(vector<int>& nums){
   
2.         if(nums.empty())
   
3.             return;
   
4. 
   
5.         vector<bool> sorted(nums.size());
   
6.         sorted[0] = true;
   
7.         int pre = 0;
   
8. 
   
9.         for(int i=0; i<nums.size(); ++i){
   
10.             if(sorted[i])
    
11.                 continue;
    
12.             pre = i;
    
13. 
    
14.             while(pre < nums.size() && !sorted[pre]){
    
15.                 if(pre < nums.size()/2) {
    
16.                     swap(nums, i, 2 * pre);
    
17.                     pre = 2 * pre;
    
18.                 }
    
19.                 else {
    
20.                     swap(nums, i, 1 + 2 * (pre - nums.size() / 2 ));
    
21.                     pre = 1 + 2 * (pre - nums.size() / 2 );
    
22.                 }
    
23. 
    
24.                 sorted[pre] = true;
    
25. 
    
26. 
    
27.             }
    
28. 
    
29.         }
    
30. 
    
31.     }
    
32. 
    
33.     void swap(vector<int>& nums, int i, int j){
    
34.         int tmp = nums[i];
    
35.         nums[i] = nums[j];
    
36.         nums[j] = tmp;
    
37.     }

复制代码

NavierStoke 发表于 2019-10-17 09:22
可以的，我三年就坚持不下去了

NS方程这个鸟东西我觉得再给人类200年也搞不出来

gxy200992243 发表于 2019-10-18 03:32
NS方程这个鸟东西我觉得再给人类200年也搞不出来

我倒不这么看，因为我觉得人类已经没有200年了哈哈哈

第一轮：

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"))
    

复制代码

ncy 发表于 2019-10-18 02:27
第一题写了一下，one pass O(n)

[mw_shl_code=cpp,true]void wigglesort(vector& nums){

大佬可以讲一下思路吗..?= =看不太懂...谢谢谢谢！！

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

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

ncy 发表于 2019-10-18 12:37
就是前半部分index为i的数应该交换到2*i， 后半部分i应该交换到1+2*(i-size/2)
举例子：
number:   a1  ...

哦哦哦讲得好清楚！！谢谢您！！

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

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

记忆中的微光 发表于 2019/10/19 01:30:01

这题要求in-place做出来诶，这个解法额外花了空间吧~

这个解法是in-place呀，你说的额外空间是指swap？ 一般in-place都是会允许额外O（1）空间的