谷歌近期面经整理

Job Hunting Interview
, , , , , ,
1

  1. 一个很温柔的小姐姐打来的，一共45分钟，做了一道题
    题目是 LC Meeting Room I 的变形，本质和 LC 是一样的
    不过要自己定义Input， 比如说 LC 上定义 Input 是 ，我定义为一个 Pair <int, int>

    写完后要求分析时间复杂度，然后给出一系列Corner Cases

  2. 面试官上来就问我准备好做题了吗？总共两道题
    第一题：问了很多关于各种不同Removing Repeated Char in a String 的问题， 例如：Given Sorted Str & Unsorted Str 如何保证一个字符只出现一次？
    ​ 最后让写一个程序只保留未排序好的String里相同字符的最后一，返回新的String

    第二题：给了两个Arbitrary Size String让做加法
    ​ 其实就是Add Two Strings

  3. 面试官问了前一个面试官给了我什么问题 （他说不想重复
    第一题：给你一个Input Array，检测是否这个Array是一个有效的日期
    ​ 【2000， 30，7】 - 输出True

  4. 考了一道前缀树。输入是一个电话本。
    name -> number。
    要求创建object，实现插入name->number的方法。并且实现按照前缀查找的方法。
    比如输入为
    abc -> 1
    abcd -> 2
    abce -> 3
    bcs -> 4
    ade -> 5
    输入 ab 要求返回 【1，2，3】。所有符合前缀的结果。
    使用trie解决。不过对于system deisgn的话，可以 key-value来应对频繁的读操作。
    之后问了复杂度和test的case。

  5. LC 679

  6. 一面：
    给你一个random(int n)，这个n等概率返回1~n的任意一个整数，写一个函数，调用random()，等概率返回0~9中两个数的排列，如返回12或者39，等概率。
    follow up: 在你的函数中，限制只能用一次random，如何返回

  7. 二面：
    第一题：用一个for loop遍历一个二维数组
    第二题：双链表中删除一个节点

  8. 字符串转换
    给定一个字符串s，问能不能转化成另一个字符串p，条件是每次转换要把所有相同的字母一起变动，例子如: abca(两个a一起变) -> dbcd(变c) -> dbed(变b) -> dced。所以abca能转化成dced，return true。

  9. 说一堆director和directee关系， 每个关系有positive 时间，问从ceo到每个员工传话最短要多久

  10. 说一堆有边界的int 找median，有负数 要linear 就是bucket sort

  11. 蠡口 尔妖尔（沃德 蛇去）

    给我一个词表有n个词，要我判断一个String是否和词表中的某个词有且仅有一个不同的char

  12. 15

  13. 708

  14. 一个思路变态的题目，参考 谷歌 residency 面经题

  15. lc489

  16. 给你一个二维字符矩阵 matrix 表示围棋棋盘，问你当前棋盘上有没有棋子是可以清除出去的, 即围棋中的包围，return false or true。matrix用0(empty), W (white), B (Black) 表示。下图的第一个B是会被包围的，第二个B不会。所以就看是否可以碰到0. dfs 可以解，需要用另一个matrix来做memorization。

    00W  
    0WB
    0BW

  1. lc769 Max Chunks To Make Sorted 需要用最优解 O(n)

  2. Interface logger 需要 implement两个方法，start和stop，并提供 helper 函数 log 方法。输入是一堆请求。先是对同一个request，当stop被调用，就log这个request的开始时间和结束时间。按格式输出：请求的开始时间和结束时间和请求id。followup是要求按请求开始时间升序。某个请求未结束时不能输出，不考虑多线程。followup需要用heap或priorityqueue来做。

  3. lc 774 Minimize Max Distance to Gas Station

🔎详情点击展开

On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1] , where N = stations.length .

Now, we add K more gas stations so that D , the maximum distance between adjacent gas stations, is minimized.

Return the smallest possible value of D .

Example:

Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9 Output: 0.500000

Note:

  1. stations.length will be an integer in range [10, 2000] .
  2. stations[i] will be an integer in range [0, 10^8] .
  3. K will be an integer in range [1, 10^6] .
  4. Answers within 10^-6 of the true value will be accepted as correct.
  1. lc800 Similar RGB Color
🔎详情点击展开

In the following, every capital letter represents some hexadecimal digit from 0 to f .

The red-green-blue color "#AABBCC" can be written as "#ABC" in shorthand. For example, "#15c" is shorthand for the color "#1155cc" .

Now, say the similarity between two colors "#ABCDEF" and "#UVWXYZ" is -(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2 .

Given the color "#ABCDEF" , return a 7 character color that is most similar to #ABCDEF , and has a shorthand (that is, it can be represented as some "#XYZ"

Example 1:
Input: color = "#09f166"
Output: "#11ee66"
Explanation:  
The similarity is -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73.
This is the highest among any shorthand color.

Note:

  • color is a string of length 7 .
  • color is a valid RGB color: for i > 0 , color[i] is a hexadecimal digit from 0 to f
  • Any answer which has the same (highest) similarity as the best answer will be accepted.
  • All inputs and outputs should use lowercase letters, and the output is 7 characters.
1 Like
4

感谢分享