发个谷歌onsite面经攒攒人品

Oct 20 2016 Google面经新鲜出炉1. 日本大叔：合并两个字符串

1.1合并两个字符串s1 s2，保证字符原本顺序不变

1.2 Follow up: s1 长度为 m,s2 长度为 n,有多少种合并方法？ 给出公式 F(m, n)=?

Solution:

#include <iostream>

#include <string>

#include <vector>

using namespace std;

long factorial(long n){

    long fact = 1;

    for (long i = 1; i<= n; ++i)

        fact *= i;

    return fact;

}

void DFS(const string &s1, int m, int i,

         const string&s2, int n, int j,

         string path,vector<string> &ret)

{

    if(i==m &&j==n)  {

       ret.push_back(path);

        return;

    }

    if(i < m)  DFS(s1, m, i+1, s2, n, j, path+s1, ret);

    if(j < n)  DFS(s1, m, i, s2, n, j+1, path+s2[j], ret);

}

vector<string> combineTowStrings(const string &s1,const string &s2) {

    int m =s1.length(), n = s2.length();

    long count =factorial(m+n)/factorial(n)/factorial(m);

    cout <<"count:" << count << endl;

   vector<string> ret;

    DFS(s1, m, 0, s2,n, 0, "", ret);

    return ret;

}

int main() {

   vector<string> ret = combineTowStrings("AB","CDF");

    cout <<ret.size() << endl;

    for(string &s: ret)  cout << s << endl;

    return 0;

}

1.2 Follow up proof

Supposethat you have[i] k ordered lists ofelements--where the file://localhost/private/var/folders/gm/xyhdwlxn6r73x50zbqj0d3y40000gp/T/TemporaryItems/msoclip/0clip_image001.png list has file://localhost/private/var/folders/gm/xyhdwlxn6r73x50zbqj0d3y40000gp/T/TemporaryItems/msoclip/0clip_image002.png elements for 1≤j≤k,and that you wish to interleave them.[/i]

Now,there will be file://localhost/private/var/folders/gm/xyhdwlxn6r73x50zbqj0d3y40000gp/T/TemporaryItems/msoclip/0clip_image003.pngplaces that we must fill. So,first, we assi

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

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

3">99

4. 白人小哥

平面坐标系中：

给定一个API

//return a uniformly random number in range [x, y)

double randomBetween(double x, double y);

输入一系列长方体的右上角坐标，写出函数，uniformly randomly 返回阴影中的一个点。

pair<double, double> randoPoint(constvector<pair<double, double>> &rectangle);

5. Nice 孟加拉长毛哥

5.1 开放问题：当你在浏览器里输入一个url然后会车，都发生了什么？

5.2 给一组 int， 输出那些比左边所有数都大且比右边所有数都小的数。

#include <iostream>

#include <vector>

using namespace std;

void printLargerSmaller(const vector<int> &v) {

    int n = v.size();

    vector<int>leftMax(n, INT_MIN);

    for(int i=1;i<n; ++i)     leftMax[i]  = max(leftMax[i-1], v[i-1]);

    int rightMin =INT_MAX;

    for(int i=n-1;i>=0; i--)  {

        if(i<n-1)rightMin = min(rightMin, v[i+1]);

        if(v[i] >leftMax[i] && v[i] < rightMin) cout << v[i] << " ";[/i][/i][/i][/i]

[i][i]    }[/i][/i]

[/i]

[i][i][i]}[/i][/i]

[/i]

[i][i][i]int main() {[/i][/i]

[i][i]    vector<int>v = {3,4,7,1,8,12};[/i][/i]

[i][i]   printLargerSmaller(v);[/i][/i]

[i][i]    return 0;[/i][/i]

[i][i]}[/i][/i]

[/i][/i][/i][/i]

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

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

第一题，应该考虑两个string里面有相同字母的情况吧？比如s1 = “a”。 s2=“a”。结果应该是1 不是2。在楼主的基础上，加个set就行了。
公式应该是楼上说的，F(m, n)=F(m-1, n) + F(m, n-1)。但这个也没考虑有相同字母的情况，

code 写的很不错，拿到offer了吗？

给出公式 F(m, n)=?

F(m, n)=F(m-1, n) + F(m, n-1)；

Is good enough?

吃啥才算成熟 发表于 2017-2-21 06:17
研究了好大一圈儿。。。DP应该这么写：

请问这dp公式怎么解释呢

吃啥才算成熟 发表于 2017-2-21 06:17
研究了好大一圈儿。。。DP应该这么写：

这个dp, 当i == 1的时候 dp[i - 2]就不存在了

ccc5ccc 发表于 2017-2-17 10:18
给出公式 F(m, n)=?

F(m, n)=F(m-1, n) + F(m, n-1)；

没看懂为什么是这个公式，能讲讲不

请问lz
第四题 怎么解的？
就是用 double randomBetween(double x, double y);
分别得出一个 范围内的 x 和范围内的y?
这好像太简单了 应该不对。。。
坑在哪呢？

吃啥才算成熟 发表于 2017-2-21 06:17
研究了好大一圈儿。。。DP应该这么写：

The code has bug. 试一下“ab”, "bc"? j - 2 和i - 2可能会溢出