google电面 9/2 顺便求助一下onsite的时间安排问题

分享一下面经。 1. 把数组奇偶数字排序 基数在左边 偶数在右边。
2. 两个字符串 找到里面所有不同的单词。
3. 略有难度，不过地里出现过几次了。 滑雪问题变种。 dp＋ dfs 搞定。

下周讨论onsite时间问题。我想定在下个月底。 但了解到最近google缩招，怕到时候没坑了。请问如果没坑的话是不是就相当于直接挂了，即使去onsite？

又见紫风铃 发表于 2015-9-8 06:13
稍微python写了下，这个意思吧

我觉得这样不对啊，你可以写个测试的例子跑一下。首先你没有判断num[right]是不是奇数，再者最后的数组也不是有序的。

哦 大概面了一个多小时 因为代码写的慢 不过那边面试的人还不错。一直没催我。

请问lz 第一题对空间复杂度或者时间复杂度有要求么？我能想到的就是brute force。。。。

amyzen 发表于 2015-9-5 04:15
请问lz 第一题对空间复杂度或者时间复杂度有要求么？我能想到的就是brute force。。。。

直接双指针就解决了

楼主，第二题可以举个具体的例子么～

muancy 发表于 2015-9-5 04:20
楼主，第二题可以举个具体的例子么～

哦 比如 ：
“This is apple”
“This is pig”

输出apple和pig 。。。

hello2pig 发表于 2015-9-5 04:24
哦 比如 ：
“This is apple”
“This is pig”

所以每个单词是以空格区分的是吧～～
那做法是不是用个HashTable存一下就好啊～
THX

muancy 发表于 2015-9-5 04:34
所以每个单词是以空格区分的是吧～～
那做法是不是用个HashTable存一下就好啊～
THX

必须是，不然还能怎样。。。

jiebour 发表于 2015-9-5 04:40
必须是，不然还能怎样。。。

是啊 只能这样了。。 确切的说应该是用hash set

hello2pig 发表于 2015-9-4 14:19
直接双指针就解决了

请问lz怎么用双指针解决？也就是O(N)时间解决？没看明白，能解释一下吗？谢谢

luzhuzeng 发表于 2015-9-8 15:11
请问lz怎么用双指针解决？也就是O(N)时间解决？没看明白，能解释一下吗？谢谢

1. class Solution:
   
2.     def sepOddEven(self, nums):
   
3.         if not nums or len(nums) == 0: return None
   
4.         left = 0
   
5.         right = len(nums) - 1
   
6.         while left < right:
   
7.             if nums[left] % 2 == 0:
   
8.                 nums[left], nums[right] = nums[right], nums[left]
   
9.                 right -= 1
   
10.             else:
    
11.                 left += 1
    
12.         return nums

复制代码

稍微python写了下，这个意思吧

供参考
void sepOddEven(vector<int>& num) {
        int i = 0, j = num.size() - 1;
        while (i < j) {
            while (num[i]%2 == 1 && (i < j)) {
                i++;
            }
            while (num[j]%2 == 0 && (i < j)) {
                j--;
            }
            swap(num[i++], num[j--]);
        }
        for (auto i : num) {
            cout <<i<<" ";
        }
        cout<<endl;
    }

供参考

1. void sepOddEven(vector<int>& num) {
   
2.         int i = 0, j = num.size() - 1;
   
3.         while (i < j) {
   
4.             while (num[i]%2 == 1 && (i < j)) {
   
5.                 i++;
   
6.             }
   
7.             while (num[j]%2 == 0 && (i < j)) {
   
8.                 j--;
   
9.             }
   
10.             swap(num[i++], num[j--]);
    
11.         }
    
12.         for (auto i : num) {
    
13.             cout <<i<<" ";
    
14.         }
    
15.         cout<<endl;
    
16.     }

复制代码

hello2pig 发表于 2015-9-8 13:24
供参考

这样数组最后不是有序的，比如11234478,  按照你的算法最后是: 11734428, 不是sorted的

luzhuzeng 发表于 2015-9-9 05:01
这样数组最后不是有序的，比如11234478,  按照你的算法最后是: 11734428, 不是sorted的

题目没这些要求啊 就是分割奇偶数而已

hello2pig 发表于 2015-9-9 07:00
题目没这些要求啊 就是分割奇偶数而已

本身输入也不是有序的

补充内容 (2015-9-9 07:06):
而且即使输入有序 很多case切分以后也注定无序嘛

hello2pig 发表于 2015-9-8 17:00
题目没这些要求啊 就是分割奇偶数而已

哦，以为是分开后奇数部分和偶数部分分别是拍好序的呢，那这个two pointer就够了，谢谢!

滑雪问题是怎么做的呢？

lz约到下个月都嫌晚啊，我还想约到明年2月份。。。。因为感觉onsite难好多，想准备得久一点
好纠结。。。。