我是靠谱客的博主 温暖皮卡丘,最近开发中收集的这篇文章主要介绍面经------Google Onsite(3),觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

Onsite (4 rounds):

  1. n-straight, see if a list is a valid n-straight list,
    e.g. 3-straight: [1, 2, 3] return True, [1,2,4] return false, [1,2,3,4] return false, [1,2,3,4,5,6] return true, cause it can be seen as [1,2,3] + [4,5,6]
    if n-straight is valid for at least n continous number.
    答案:Leetcode 659

  2. given a integer list ,[a, b, …] and coresponding char[‘x’,‘u’,…] means the number of different char, return every possible combination (unique)
    follow up: just return the number of different combination. and optimize.

  3. given a integer array, contain unique number, represent the velocity of the car in the road (the position in the array represent the possition in the road, and there is only one road), the fast car will be block by the slow car, return a array, each number represent the number of car in that group.
    e.g. [4,2,3,1] return [1,2,1] because 4 the is faster and no one can block it, but 3 will be block by 2, and previous cars are faster than 1, so 1 will not be in the same group with them.
    follow up, add a new car with a new speed into this array , return every possible answer.
    答案:Leetcode: Car Fleet

  4. given two string. one has exactly one more letter than the other, find this letter, the input must be valid.
    e.g. s1:‘abbc’, s2:‘bcbad’ return d
    Method1: traverse first and second string from starting with xor operation at the end you get the character which is extra.
    Time Complexity:- O(n+n+1)
    Space Complexity:- O(1).

 static char findExtraCharcter(String strA, String strB)
{
// result store the result 
int res = 0, i;
// traverse string A till

// end and xor with res 
for (i = 0; i < strA.length(); i++)
{
// xor with res 
res ^= strA.charAt(i);
}
// traverse string B till end and

// xor with res 
for (i = 0; i < strB.length(); i++)
{
// xor with res 
res ^= strB.charAt(i);
}
// print result at the end 
return ((char)(res));
}

Method2: Create an empty hash table and insert all character of second string. Now remove all characters of first string. Remaining character is the extra character.
Time Complexity:- O(n)
Auxiliary Space:- O(n).

// CPP program to find extra character in one

// string 
#include <bits/stdc++.h> 
using namespace std;
char findExtraCharcter(string strA, string strB)
{
// store string values in map 
unordered_map<char, int> m1;
// store second string in map with frequency 
for (int i = 0; i < strB.length(); i++)
m1[strB[i]]--;
// store first string in map with frequency 
for (int i = 0; i < strA.length(); i++)
m1[strA[i]]--;
for (auto h1 = m1.begin(); h1 != m1.end(); h1++) {
// if the frequency is 1 then this 
// character is which is added extra 
if (h1->second == -1)
return h1->first;
}
}
int main()
{
// given string 
string strA = "abcd";
string strB = "cbdae";
// find Extra Character 
cout << findExtraCharcter(strA, strB);
}

最后

以上就是温暖皮卡丘为你收集整理的面经------Google Onsite(3)的全部内容,希望文章能够帮你解决面经------Google Onsite(3)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(37)

评论列表共有 0 条评论

立即
投稿
返回
顶部