baidu 电面 & onsite

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


电面1：Minimum Window Substring。hashtable记录window内字母出现次数，加一个count

电面2：题1。题目不太好描述，在一个只包含1，2，3这三种整数的数组input[]中，求所有(i,j,k)下标组合的数量，使得 i < k < j 并且 input[i] < 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

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

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

果list of pair中的char可以有重复。我的做法是遇到重复的情况就把每个情况都试一遍然后不行就backtracking。

4. behavior

所有coding的题都要在在线编辑里面写。包括电面和onsite。我当时除了第一个电面还有onsite第3题的follow up没时间跑test之外，都是一遍就过了test case。结果还是挂了，看来自己水平还是需要提高。

欢迎交流算法。也祝大家好运！

John.Tan 发表于 2017-7-10 01:28
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消掉。

John.Tan 发表于 2017-7-11 09:20
按lz的思路我写了下onsite 3 的follow up

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <stack>
using namespace std;

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()) {
        for(char p : mp[s[pos]-'a']) {
            if(char2count[p-'a'] > 0) {
                char2count[p-'a']--;
                if(helper(mp, char2count, s, pos+1)) return true;
                char2count[p-'a']++;
            }
        }
    }
    // s[pos] act as "left" parentheses
    char2count[s[pos]-'a']++;
    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);
    for(auto p : pairs) {
        mp[p.second-'a'].push_back(p.first);
    }
    vector<int> char2count(26, 0);
    return helper(mp, char2count, s, 0);
}

int main(int argc, const char * argv[]) {
    // insert code here...
    vector<pair<char, char>> strs1 = {{'a', 'c'}, {'c', 'd'}, {'a','a'}};
    string s1 = "acddaa";
    cout << validPairs(strs1, s1) << endl;
   
    vector<pair<char, char>> strs2 = {{'a', 'd'}, {'c', 'd'}, {'a','a'}};
    string s2 = "acddaa";
    cout << validPairs(strs2, s2) << endl;
   
    vector<pair<char, char>> strs3 = {{'a','b'}, {'a','c'}, {'b','d'}};
    string s3 = "abdc";
    cout << validPairs(strs3, s3) << endl;
    return 0;
}

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

更正，电面2的input < input[j] < input[k]应该是input[i] < input[j] < input[k]

太社会了。

system design答了都没过，而且我们还是native speaker！！

LZ 电面2第一题是leetcode  456 132 Pattern   

LZ onsite 第3题follow up 你的解"把每个情况都试一遍然后不行就backtracking"，请问这里为啥还需要backtracking, 有啥test case能写一下吗，谢谢！

电面2每个比一次复杂度O(k*n). 类似merge k sorted array， 用一个heap来keep k 个元素，同时记录heap中的min,max，只要min==max， 元素就是valid的。 这样复杂度只有O(logk*n)

感觉都是原题啊....

没有leetcode 原题啊