概述
Onsite (4 rounds):
-
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 -
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. -
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 -
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)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复