一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 5702|回复: 31
收起左侧

[找工就业] google电面,直接把我和面试官面时候的google doc复制下来给大家看

[复制链接] |试试Instant~ |关注本帖
mengyadaizi 发表于 2016-5-10 07:33:01 | 显示全部楼层 |阅读模式

2016(4-6月)-[12]Math/AppliedMath本科+fresh grad 无实习/全职 - 猎头| 码农类全职@Googlefresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
中国小哥,他直接要和我讲中文,虽然他一听就是说粤语的,中文也没比英文好懂多少,不过心理上还是觉得很放松
出的题好良心,真心不难,比起地里的其他面经
最后问了问我第二题我写的方法的复杂度,我没说对,太愚蠢了




Q1:

Write a function that takes in a string and returns the length of the longest string prefix in which all characters are arranged in alphabetical order.  Use the language with which you are the most familiar.

Examples:
        alphaprefix("ransom")   = 1
        alphaprefix("google") = 3
        alphaprefix("knotty")   = 6
. from: 1point3acres.com/bbs
“ab”
int alphaprefix(string s) {
        if (s.length() == 0) {
                return 0;
        }
        if (s.length() == 1) {
                return 1;
        }
        int len = 1;
       
        for (int i = 0; i < s.length() - 1; i++) {
               
                if (s[i+1] < s) {
                        break;
                }
                else {
                        len ++ ;
                }
        }
        return len;
}

“sweet”
“balance”
“I”

. 鍥磋鎴戜滑@1point 3 acres

-google 1point3acres
Q2:

You are given a int[N] array num, count how many triplets (x, y, z) that
num[x] + num[y] + num[z] < K


assuming x < y < z

num[] = {
, 3, 6, 1, 8, 10}  K = 13

5 + 3 + 1 = 9 < 13
5 + 6 + 1 = 12 < 13
3 + 6 + 1 = 10 < 13
3 + 1 + 8 = 12 < 13

ans = 4

int Count(int num[], int N, int K) {
}
void helper( int sum, int cur, vector<int>& res, const int K, const int n, vector<int> candidate, vector<vector<int>> ans) {
        if (sum < K ) {
                ans.push_back(res);
        }
        if (candidate.size() > 3) {
                return;
        }
        for (int i=cur; i < n; i++){
                if (sum + candidate < K) {
                        res.push_back(candidate);
                        helper(sum + candidates, i, res, K, n, candidate, ans);
                        res.pop_back();
                }
        }
}




评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · google|主题: 58, 订阅: 6
sherrylin1989 发表于 2016-11-6 05:29:33 | 显示全部楼层
这样把题目复制粘贴过来不太好吧,会不会影响到那个善良的小哥
回复 支持 0 反对 1

使用道具 举报

dukangs 发表于 2016-8-25 15:01:16 | 显示全部楼层
fanfeng 发表于 2016-5-17 21:50
第二题如果是3sum的话(找三个数的和正好等于k),time complexity可以减少到n^2,用hash table。
但是这 ...

可以n^2logN做
回复 支持 1 反对 0

使用道具 举报

blackrose 发表于 2016-5-11 09:13:09 | 显示全部楼层
hidden_track 发表于 2016-5-11 08:12
没太懂,比如说楼主给的这个例子 {5,3,6,1,8,10} 排序后变成了{1,3,5,6,8,10}。。这样你选1 , ...

1, 3, 5 里面总是存在 i < j < k 的,不用考虑 num, num[j], num[k] 表示哪个数,
回复 支持 1 反对 0

使用道具 举报

dgswh 发表于 2016-5-10 23:06:38 | 显示全部楼层
handsomecool 发表于 2016-5-9 22:27. From 1point 3acres bbs
x < y < z
x y z 是index

是返回个数哦,出现顺序可以不考虑
回复 支持 1 反对 0

使用道具 举报

blackrose 发表于 2016-5-10 12:29:16 | 显示全部楼层
int countTriplets(vector<int>& nums, int K) {
  if(nums.size() < 3) return 0;
  int count = 0;
  for(int i = 0; i < nums.size() - 2; ++i) {. 鍥磋鎴戜滑@1point 3 acres
    int target = nums[i]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    for(int j = i + 1; j < nums.size() - 1; ++j) {
      target += nums[j];
      for(int k = j + 1; k < nums.size(); ++k) {
        target += nums[k];
        if(target < K) {
          count++;
        }
        target -= nums[k];
      }
      target -= nums[j];
    }
  }
  return count;
}
.鏈枃鍘熷垱鑷1point3acres璁哄潧
int main(void) {
  vector<int> nums{5, 3, 6, 1, 8, 10};
  cout << countTriplets(nums, 13) << endl;
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 1 反对 0

使用道具 举报

blackrose 发表于 2016-5-10 12:11:45 | 显示全部楼层
zjw5224 发表于 2016-5-10 12:02
确实不难,第二题就是3sum和3sum closest的变形,楼主用backtracking应该是O(N3), 先sort下然后scan一遍会 ...

第二题不能sort。。。。。看清楚。。。
回复 支持 1 反对 0

使用道具 举报

zjw5224 发表于 2016-5-10 12:02:12 | 显示全部楼层
确实不难,第二题就是3sum和3sum closest的变形,楼主用backtracking应该是O(N3), 先sort下然后scan一遍会是O(N2)吧,祝楼主onsite也好运,加油!
回复 支持 0 反对 1

使用道具 举报

yueliu2366 发表于 2016-5-10 08:00:22 | 显示全部楼层
感谢分享,题目的确不难啊,祝楼主onsite好运!
回复 支持 反对

使用道具 举报

dgswh 发表于 2016-5-10 12:23:06 | 显示全部楼层
blackrose 发表于 2016-5-9 22:11
第二题不能sort。。。。。看清楚。。。

为啥不能sort?
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-5-10 12:27:21 | 显示全部楼层
-google 1point3acres
x < y < z
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴x y z 是index
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-10 12:28:44 | 显示全部楼层
Perhaps, a stupid ways?

补充内容 (2016-5-10 12:28):
int countTriplets(vector<int>& nums, int K) {
  if(nums.size() < 3) return 0;
  int count = 0;
  for(int i = 0; i < nums.size() - 2; ++i) {
    int target = nums;
    for(int j = i + 1; j < nums...

补充内容 (2016-5-10 12:29):
int countTriplets(vector<int>& nums, int K) {. From 1point 3acres bbs
  if(nums.size() < 3) return 0;
  int count = 0;
  for(int i = 0; i < nums.size() - 2; ++i) {
    int target = nums;
    for(int j = i + 1; j < nums...
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-5-10 19:44:54 | 显示全部楼层
请问楼主,这道题是否可以排序? 感觉题意问的是有多少不同的三元组,应该是可以排序的吧?
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-5-11 00:44:41 | 显示全部楼层
1. 如果这道题要求是返回 “所有结果” 就不能排序了,但是只是需要数量的话,任意选三个index不同的数,他们的index肯定是x < y < z 的,只需要换一下数字的顺序。
2. 这道题如果没有明说不能有duplicate的话,题意只需要index满足条件,again 任意三个数index都满足条件的,所以duplicate应该也包含在内的。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-11 00:55:35 | 显示全部楼层
sheepmiemies 发表于 2016-5-11 00:44
1. 如果这道题要求是返回 “所有结果” 就不能排序了,但是只是需要数量的话,任意选三个index不同的数,他 ...
. 鍥磋鎴戜滑@1point 3 acres
恩,也对。那就能简单了。
回复 支持 反对

使用道具 举报

zhengyino1 发表于 2016-5-11 05:54:54 | 显示全部楼层
我看lz第二题是有dfs/backtracking的思路对吧?
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-5-11 08:12:02 | 显示全部楼层
sheepmiemies 发表于 2016-5-11 00:44
1. 如果这道题要求是返回 “所有结果” 就不能排序了,但是只是需要数量的话,任意选三个index不同的数,他 ...

没太懂,比如说楼主给的这个例子 {5,3,6,1,8,10} 排序后变成了{1,3,5,6,8,10}。。这样你选1 ,3, 5的话index不符合 i < j < k。。。还是我理解错了 -google 1point3acres
回复 支持 反对

使用道具 举报

 楼主| mengyadaizi 发表于 2016-5-12 00:53:18 | 显示全部楼层
楼主没过啊 不用onsite好运了 可能是如果题这么简单的话,应该写的更好吧
回复 支持 反对

使用道具 举报

zhengyino1 发表于 2016-5-12 01:13:52 | 显示全部楼层
mengyadaizi 发表于 2016-5-12 00:53
楼主没过啊 不用onsite好运了 可能是如果题这么简单的话,应该写的更好吧

加油加油再接再厉!!
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-12 04:38:19 | 显示全部楼层
mengyadaizi 发表于 2016-5-12 00:53
楼主没过啊 不用onsite好运了 可能是如果题这么简单的话,应该写的更好吧

第二题的复杂度有点高。可以降低到O(N2) worst case。。。。pat pat,move on 了
回复 支持 反对

使用道具 举报

 楼主| mengyadaizi 发表于 2016-5-12 09:45:13 | 显示全部楼层
blackrose 发表于 2016-5-12 04:38
第二题的复杂度有点高。可以降低到O(N2) worst case。。。。pat pat,move on 了

没关系啦,这是我第一次面software engineer, 以前找的都是数学方面的从来没刷过题
回复 支持 反对

使用道具 举报

alex8937 发表于 2016-5-12 21:34:57 | 显示全部楼层
关键是lz的backtracking code 也有问题啊

首先判断sum<k 就push_back了, 那任何比k小的数都被找来了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 19:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表