Google Phone + Onsite 以及其他多家公司面经

1111光棍节onsite的。。拖延症晚期所以拖到今天才发出来。。（其实是一朋友想要。。）

Google Phone:
1.  boolean hasDuplicateCharacter(String word);
给定一个string 判断是否有重复的char
2. Lowest Common Parent of two nodes in a binary tree
这里有点tricky的是LCP和LCA的区别，假如p,q 是BT中的两个node，p是q的ancestor，那么LCA是p， LCP是p的parent。

Onsite：
第一轮：
Bomb Game，给一个m*n的二维数组，其中有： -1 墙， 1 怪兽， 0 空白。 你有一个炸弹，可以扔在除墙之外的任意位置，最多可以炸死几个怪兽。
一开始给出了Brute Force的方法O(m*n*(m+n)), 后来优化给出了O(mn)的方法。 聊了一下可能出现的问题，如何test。

第二轮：
Longest [continuous increasing] subarray, 返回长度
e.g. 1,2,3,5,8,9,12,13
LCIS: 1,2,3   return 3


Longest continuous increasing path in a tree (不一定是binar

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

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

ont style="font-size:12pt">

5. Advanced Security Team
[1] SQL injection
[2] 谈谈当下你关心的安全问题。。XCodeGhost
[3] PKI Infra
[4] Kerberos..完全忘了。。
[5] LinkedList找环 I(判断是否有环)， II（找环起点）
[6] 一道概率分布的题。。

6. Real Application Cluster
isPalindrome。。国人大哥放水了。。

----------------------------------------
以上，祝大家新年里找工顺利！

                               
                       
               

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

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

写了下phone interview的题

1. public class LowestCommonParent {
   
2. 
   
3.         static class TreeNode {
   
4.                 TreeNode left, right;
   
5.                 int val;
   
6. 
   
7.                 public TreeNode(int val) {
   
8.                         this.val = val;
   
9.                 }
   
10.         }
    
11. 
    
12.        
    
13.         public static TreeNode getLowestCommonParent(TreeNode root, TreeNode p, TreeNode q) {
    
14.                 if (root == null) {
    
15.                         return null;
    
16.                 }
    
17.                
    
18.                 if (root.left == p || root.right == p || root.left == q || root.right == q) {
    
19.                         return root;
    
20.                 }
    
21.                 TreeNode left = getLowestCommonParent(root.left, p, q);
    
22.                 TreeNode right = getLowestCommonParent(root.right, p, q);
    
23.                 if (left != null && right != null) {
    
24.                         return root;
    
25.                 }
    
26.                 if (left != null) {
    
27.                         return left;
    
28.                 } else {
    
29.                         return right;
    
30.                 }
    
31.         }
    
32.        
    
33.        
    
34.         public static void main(String[] args) {
    
35.                 TreeNode root = new TreeNode(50);
    
36.                 root.left = new TreeNode(10);
    
37.                 root.right = new TreeNode(60);
    
38.                 root.left.left = new TreeNode(5);
    
39.                 root.left.right = new TreeNode(20);
    
40.                 root.right.left = new TreeNode(55);
    
41.                 root.right.left.left = new TreeNode(45);
    
42.                 root.right.right = new TreeNode(70);
    
43.                 root.right.right.left = new TreeNode(65);
    
44.                 root.right.right.right = new TreeNode(80);
    
45.                
    
46.                 System.out.println(getLowestCommonParent(root, root.left.left, root.left.right).val);
    
47.                 System.out.println(getLowestCommonParent(root, root.right.left, root.right.left.left).val);
    
48.                 System.out.println(getLowestCommonParent(root, root.right.right, root.right.right.left).val);
    
49.         }
    
50. }

复制代码

第一轮：
Bomb Game，给一个m*n的二维数组，其中有： -1 墙， 1 怪兽， 0 空白。 你有一个炸弹，可以扔在除墙之外的任意位置，最多可以炸死几个怪兽。
一开始给出了Brute Force的方法O(m*n*(m+n)), 后来优化给出了O(mn)的方法。 聊了一下可能出现的问题，如何test。

请问这个炸弹爆炸的范围是怎么说的？

rb131108 发表于 2016-1-28 06:58
第一轮：
Bomb Game，给一个m*n的二维数组，其中有： -1 墙， 1 怪兽， 0 空白。 你有一个炸弹，可以扔在 ...

对。。忘记说了 炸弹爆炸可以清除这个炸弹所在的一行和一列的怪兽，但是不能穿过墙

第一题可以dp 吧？

kinggarden2001 发表于 2016-1-28 07:53
第一题可以dp 吧？

对 就是dp

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

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

论坛匿名用户 发表于 2016-1-29 00:05
对 就是dp

怎么感觉fulltime的题好难啊。。。

letsdoit666 发表于 2016-2-1 21:27
怎么感觉fulltime的题好难啊。。。

我感觉我遇到的题算中等偏简单的。。我看有phd的面试有数学+概率的题(也有可能和他的方向有关系)。。

论坛匿名用户 发表于 2016-1-29 00:18
嗯 大致看了下应该是对的 实现的时候面试官要求2 pass 最后取max的那次遍历实际上可以和更新纵向怪兽数量 ...

这个题应该是和flower and garden是一个题吧