一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1101|回复: 16
收起左侧

baidu 电面 & onsite

[复制链接] |试试Instant~ |关注本帖
guaibao135 发表于 2017-7-9 07:18:07 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 硕士 全职@baidu USA - 网上海投 - 技术电面 Onsite |Failfresh grad应届毕业生

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

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

x
面了baidu USA自我感觉不错然而还是挂了,发面经攒人品。顺便问问现在还有哪些公司可以投么。。。后面写的都是我自己的做法,不保证最好


电面1:Minimum Window Substring。hashtable记录window内字母出现次数,加一个count. more info on 1point3acres.com

.鏈枃鍘熷垱鑷1point3acres璁哄潧电面2:题1。题目不太好描述,在一个只包含1,2,3这三种整数的数组input[]中,求所有(i,j,k)下标组合的数量,使得 i < k < j 并且 input < input[j] < input[k]。例如一个数组是[1,2,3],那么答案是1因为只有(0,1,2)这样的下标组合满足要求,如果输入是[3,1,1,2,3],那么答案是2,因为有(1,3,4)和(2,3,4)这两种组合满足要求。用DP,从左往右扫,遇见1就记录出现过的1,遇见2计算出现过的(1,2),遇见3计算出现过的(1,2,3)。
题2。find common elements in k sorted array. 先找出1和2的common element,然后跟第三个比,以此类推。参考以下链接不过把3变成k。 http://www.geeksforgeeks.org/fin ... hree-sorted-arrays/
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

onsite:
1. 在一个长度为n+1的数组中,所有数字都在1~n之间。所以至少有1个数字是重复的,可能有多个,返回任意一个重复的数字。多种解法,先是一个一个比暴力解,然后是用hashset,然后每看见一个数把对应的index那个数改成负数,记录这个数是否出现过。还有sort原始数列找duplicate。最后写的一种方法是不断缩小range找答案。最开始solution的range在[1, n+1],然后扫一遍全部数列,记录下所有[1,n/2]范围内数字的个数,如果这个个数大于n/2,说明solution在[1, n/2]之间,反之solution在[n/2 + 1, n+1]之间。以此类推二分直至找到答案。

2. system design,设计一个online spreadsheet,支持多个用户同时编辑,同时可以求多个cell的sum。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
3. 输入一个list of pair以及string。检查这个string是否合法。合法的标准是将string中的字符按照pair中的左右关系两两消除之后能够完全清零。例图list of pair是{(a,b), (c, d)},那么"abcd", "acdb", "cabd"都是合法的,而"ba", "dc", "adcb"都是不合法的。已知list of pair中的所有字符没有重复。做法就是跟validate parentheses一样,用一个stack,从左往右扫,看到match就消掉。follow up是如果list of pair中的char可以有重复。我的做法是遇到重复的情况就把每个情况都试一遍然后不行就backtracking。

4. behavior

所有coding的题都要在在线编辑里面写。包括电面和onsite。我当时除了第一个电面还有onsite第3题的follow up没时间跑test之外,都是一遍就过了test case。结果还是挂了,看来自己水平还是需要提高。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
欢迎交流算法。也祝大家好运!.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

1

查看全部评分

 楼主| guaibao135 发表于 2017-7-10 10:31:01 | 显示全部楼层
John.Tan 发表于 2017-7-10 01:28. Waral 鍗氬鏈夋洿澶氭枃绔,
LZ 电面2第一题是leetcode  456 132 Pattern

你说的对,不过跟leetcode 456不一样的是要return个数而不是有没有。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
至于onsite的follow up,举个例子就是{(a,b), (a,c), (b,d)},input是"abdc",往后扫的时候先把ab给match了,然后发现dc消不掉,然后backtrack,b先不和a match,走到d的时候bd消掉,再走到最后ac消掉。
回复 支持 1 反对 0

使用道具 举报

 楼主| guaibao135 发表于 2017-7-9 07:19:11 | 显示全部楼层
更正,电面2的input < input[j] < input[k]应该是input[i] < input[j] < input[k]
回复 支持 反对

使用道具 举报

david.fang 发表于 2017-7-9 08:58:50 | 显示全部楼层
system design答了都没过,而且我们还是native speaker!!
回复 支持 反对

使用道具 举报

John.Tan 发表于 2017-7-10 01:28:56 | 显示全部楼层
LZ 电面2第一题是leetcode  456 132 Pattern   
回复 支持 反对

使用道具 举报

John.Tan 发表于 2017-7-10 01:56:38 | 显示全部楼层
LZ onsite 第3题follow up 你的解"把每个情况都试一遍然后不行就backtracking",请问这里为啥还需要backtracking, 有啥test case能写一下吗,谢谢!
回复 支持 反对

使用道具 举报

Darkduke68 发表于 2017-7-10 03:29:38 | 显示全部楼层
电面2每个比一次复杂度O(k*n). 类似merge k sorted array, 用一个heap来keep k 个元素,同时记录heap中的min,max,只要min==max, 元素就是valid的。 这样复杂度只有O(logk*n)
回复 支持 反对

使用道具 举报

LeetCodeOJ 发表于 2017-7-10 03:46:01 | 显示全部楼层
感觉都是原题啊....
回复 支持 反对

使用道具 举报

lensbo 发表于 2017-7-10 05:53:45 | 显示全部楼层
没有leetcode 原题啊
回复 支持 反对

使用道具 举报

 楼主| guaibao135 发表于 2017-7-10 10:32:47 | 显示全部楼层
啊那个说native speaker的,面试全部是英文,并且从HR到面试官都是印度人,除了有一个长得像华裔的妹子,感觉是ABC
回复 支持 反对

使用道具 举报

 楼主| guaibao135 发表于 2017-7-10 10:38:12 | 显示全部楼层
Darkduke68 发表于 2017-7-10 03:29
电面2每个比一次复杂度O(k*n). 类似merge k sorted array, 用一个heap来keep k 个元素,同时记录heap中的m ...

你说的我感觉有点问题,如果你定义n是每个array的平均长度的话,我的解法是O(k*n),而你的解法是O(logk * k * n).
回复 支持 反对

使用道具 举报

Darkduke68 发表于 2017-7-10 10:49:52 | 显示全部楼层
guaibao135 发表于 2017-7-10 10:38
你说的我感觉有点问题,如果你定义n是每个array的平均长度的话,我的解法是O(k*n),而你的解法是O(logk * ...

哦,对,我想错了。你是两个两个比的。
回复 支持 反对

使用道具 举报

John.Tan 发表于 2017-7-11 07:45:53 | 显示全部楼层
guaibao135 发表于 2017-7-10 10:31
.鐣欏璁哄潧-涓浜-涓夊垎鍦你说的对,不过跟leetcode 456不一样的是要return个数而不是有没有。
至于onsite的follow up,举个例子 ...

噢噢,我理解错了抱歉,LZ电面2第一题这样看来应该是:
Counting length-k increasing subsequences in an array k = 3
https://www.quora.com/Given-an-a ... h-K-K-N-efficiently
https://apps.topcoder.com/forums ... amp;threadID=617827
回复 支持 反对

使用道具 举报

lulu_0386 发表于 2017-7-11 09:19:40 | 显示全部楼层
guaibao135 发表于 2017-7-10 10:32
啊那个说native speaker的,面试全部是英文,并且从HR到面试官都是印度人,除了有一个长得像华裔的妹子,感 ...
. more info on 1point3acres.com
怎么如此。。。。baidu都被印度人占了么。。。
回复 支持 反对

使用道具 举报

John.Tan 发表于 2017-7-11 09:20:51 | 显示全部楼层
guaibao135 发表于 2017-7-10 10:31-google 1point3acres
你说的对,不过跟leetcode 456不一样的是要return个数而不是有没有。
至于onsite的follow up,举个例子 ...

按lz的思路我写了下onsite 3 的follow up

回复 支持 反对

使用道具 举报

John.Tan 发表于 2017-7-11 09:21:31 | 显示全部楼层
John.Tan 发表于 2017-7-11 09:20
按lz的思路我写了下onsite 3 的follow up
-google 1point3acres
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <stack>
using namespace std;
. 1point 3acres 璁哄潧
bool helper(vector<vector<char>>& mp, vector<int>& char2count, string s, int pos) {
    if(pos == s.length()) {
        return count(char2count.begin(), char2count.end(), 0) == 26;
    }
    // if s[pos] can act as "righjt" parentheses
    if(!mp[s[pos]-'a'].empty()) {. visit 1point3acres.com for more.
        for(char p : mp[s[pos]-'a']) {
            if(char2count[p-'a'] > 0) {
                char2count[p-'a']--;
                if(helper(mp, char2count, s, pos+1)) return true;. more info on 1point3acres.com
                char2count[p-'a']++;
            }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }
    }
    // s[pos] act as "left" parentheses. 1point3acres.com/bbs
    char2count[s[pos]-'a']++;. visit 1point3acres.com for more.
    if(helper(mp, char2count, s, pos+1)) return true;
    char2count[s[pos]-'a']--;
    return false;
}

bool validPairs(vector<pair<char, char>>& pairs, string s) {
    vector<vector<char>> mp(26);.1point3acres缃
    for(auto p : pairs) {
        mp[p.second-'a'].push_back(p.first);
    }
    vector<int> char2count(26, 0);
    return helper(mp, char2count, s, 0);
}
-google 1point3acres
int main(int argc, const char * argv[]) {
    // insert code here...
    vector<pair<char, char>> strs1 = {{'a', 'c'}, {'c', 'd'}, {'a','a'}};. 鍥磋鎴戜滑@1point 3 acres
    string s1 = "acddaa";. visit 1point3acres.com for more.
    cout << validPairs(strs1, s1) << endl;
   
    vector<pair<char, char>> strs2 = {{'a', 'd'}, {'c', 'd'}, {'a','a'}};
    string s2 = "acddaa";. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    cout << validPairs(strs2, s2) << endl;. 1point3acres.com/bbs
   
    vector<pair<char, char>> strs3 = {{'a','b'}, {'a','c'}, {'b','d'}};
    string s3 = "abdc";
    cout << validPairs(strs3, s3) << endl;
    return 0;
}
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-12-11 10:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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