一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4345|回复: 50
收起左侧

G家ONSITE失败

[复制链接] |试试Instant~ |关注本帖
souhomeca 发表于 2015-2-7 09:22:07 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 本科 全职@Google - Other - Onsite |Fail

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
第一题, 找出一个二叉树的最深节点。
这个题目实际是送分给我的。结果我太紧张,用递归函数完成算法,但是把返回最深节点程序写成了返回最深深度。后来考官提醒我不对,我方寸有点乱,推翻全部递归算法,重新用DFS写了一个非递归算法。结果虽然正确,但是过于复杂。后来想了想,其实这个问题稍微修改一下原有递归算法就好了。面试官是个老白,人还算NICE。

第二题,一个LIST里面放了很多句子,找出每个句子共同的PREFIX。这个问题不是很难,我写了个比较函数,然后依次比较每个句子。考官问我算法效率,我说是LIST长度乘最长的LIST单词长度。 他问我有没有更好的算法,我说可以先扫描LIST,找出最短的句子,以它为初始比较,可以减少比较次数。面试官感觉是个东欧白人,比较NICE.

第三题,设计一个 KEY-VALUE机制,必须在O(1)做下列操作: 插入,删除,get(),random_get(),可以使用hashmap.
这个题目非常tricky. 貌似可以直接使用一个HASHMAP就能完成,但是实际上random_get必须把每个K-V对与一个0到N的整数关联,这个如果直接
把MAP放到一个LIST里面去,算法效率就变成了O(N). 我最终使用了两个HASHMAP来实现这个功能,一个HASH表记录0-N的整数下标与KEY的关系,
另外一个HASH表记录K-V,还有这个下标。这个算法其实在删除时也有问题,因为删除后会有下标GAP.我实际上是使用了一个机制,让删除操作,. From 1point 3acres bbs
每次只删除HASH表最后那个K-V值(之前让最后值与删除值换个位置)。面试官是个亚裔小年轻,非常NICE.

第四题,找出一个GRAPH里面全部的三角形
我的算法: 先做一个访问队列,从一个节点开始BFS遍历,每次把一个节点的所有未访问过的邻居点放入一个LIST,判断这个邻居LIST里面有多少. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
点互相连接。这个就是与这个节点有关的三角形,对它们计数并把结果记入累加器。之后把这个LIST加入队列,继续遍历。累加器最后返回三角形总数。
这个面试官是个三哥,态度很糟糕。似乎看不懂我写的算法,问了很多莫名其妙的问题。估计他给我的REVIEW很差。请各位大神看看,我的算法确实有问题,还是三哥有问题。

第五题 字符串PATTERN MATCH。 一个P字符串 ,一个S字符串。P中下划线 "_"字符通配S的单个字符,"%" 通配S中任意长度字符。
我的算法出现了一个问题,P字符串“ABC_AB%AB"与S字符串 "ABCXABXXXXABAB"这样的匹配,我报FALSE,他说正确的应该是TRUE.
修改过程没有完成时间到了。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
好了,情况就这些了,祝各位好运!. Waral 鍗氬鏈夋洿澶氭枃绔,



补充内容 (2015-2-8 15:46):
这次G家先前电面了我两轮,都比较顺利。后来G出机票让我来ONSITE,题目我没有我想象的难,没想到没过,略有些失望。我不是科班出身,编程和算法都是自学的,没有工作经验应该也是FAIL的原因之一

评分

3

查看全部评分

本帖被以下淘专辑推荐:

 楼主| souhomeca 发表于 2015-2-7 14:01:58 | 显示全部楼层
完整呈现如下:
   import java.util.*;
public class Test {
static class         Node {
鏉ユ簮涓浜.涓夊垎鍦拌鍧.                    public int val;
              public Node left;
              public Node  right;
              public Node (int x). 1point 3acres 璁哄潧
              {
                      val=x;. from: 1point3acres.com/bbs
              }
             . 鍥磋鎴戜滑@1point 3 acres
            }
        public static int max_level=0;
        public static int level=0;
        public static Node deep_node=null;
        public static void main (String [] args)   {
        Node n1 =new Node(1);
       
        Node n2=new Node(2);. visit 1point3acres.com for more.
        Node n3 =new Node(3);
        Node n4 =new Node(4);
. 1point3acres.com/bbs        n1.left=n2;
        n2.left=n3;
        n2.right=n4;
         deepest(n1);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
         System.out.println(deep_node.val); //print deepest node value 4;
        }

        public static void  deepest(Node root) {
                if (root==null) return;
           if (level>=max_level) {
            deep_node=root;
            max_level=level;
        }

        level++;
           deepest( root.left);
           deepest( root.right);
           level--;
        }
}

补充内容 (2015-2-8 15:12):
这是我对第一题的解法
回复 支持 0 反对 1

使用道具 举报

蓝田十三点 发表于 2015-2-7 10:50:48 | 显示全部楼层
第五题是lc wildcard match?
回复 支持 反对

使用道具 举报

qeroqero 发表于 2015-2-7 11:03:40 | 显示全部楼层
多久收到消息..
回复 支持 反对

使用道具 举报

qeroqero 发表于 2015-2-7 11:03:59 | 显示全部楼层
多久收到结果消息
回复 支持 反对

使用道具 举报

 楼主| souhomeca 发表于 2015-2-7 11:08:25 | 显示全部楼层
一周内就通知FAIL了
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-2-7 11:29:51 | 显示全部楼层
第三题可以用一个hash map加一个array
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-2-7 11:30:43 | 显示全部楼层
第二和第五都是leetcode原题?
回复 支持 反对

使用道具 举报

YY大帝 发表于 2015-2-7 12:52:58 | 显示全部楼层
第五题的确蛮变态,虽然是ltcd的,想问下LZ结果是电话通知还是邮件的
回复 支持 反对

使用道具 举报

tommy1122337 发表于 2015-2-7 13:16:17 | 显示全部楼层
可以分享一下 第一題如何用递归函数解嗎
回复 支持 反对

使用道具 举报

 楼主| souhomeca 发表于 2015-2-7 13:46:36 | 显示全部楼层
Class Solution {

public static int max_level=0;
public static int level=0;
public static Node deep_node=null;
public void static deepest(Node root) {
   if (level>=max_level) {
    deep_node=root;
    max_level=level;
}
level++;
   deepest(Node root.left);
deepest(Node root.right);.1point3acres缃
level--;
  }
public static void main()
{

}. 1point3acres.com/bbs
}

补充内容 (2015-2-7 14:05):
这个程序不完整,请看楼下
回复 支持 反对

使用道具 举报

charles901030 发表于 2015-2-7 13:48:42 | 显示全部楼层
tommy1122337 发表于 2015-2-7 13:16
可以分享一下 第一題如何用递归函数解嗎

public static int height(TreeNode root) {
                if (root == null) {
                        return 0;. 鍥磋鎴戜滑@1point 3 acres
                }
                return Math.max(height(root.left), height(root.right)) + 1;
        }

        public static TreeNode findNode(TreeNode root) {
                if (root == null) {
                        return null;
                }
                return findDeepestNode(root, 1, height(root));
        }. more info on 1point3acres.com

        public static TreeNode findDeepestNode(TreeNode root, int level, int height) {
                if (root == null) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        return null;
                }
                TreeNode left = null;
                TreeNode right = null;

                if ((root.left == null && root.right == null) && level >= height) {
                        return root;
                }
                if (height < level) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        height = level;. 1point3acres.com/bbs
                }
                left = findDeepestNode(root.left, level + 1, height);
                right = findDeepestNode(root.right, level + 1, height);
                return left != null ? left : right;. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-2-7 13:49):
if (height < level) {
                        height = level;
                }这段没有用
回复 支持 反对

使用道具 举报

charles901030 发表于 2015-2-7 13:51:40 | 显示全部楼层
我觉得第二题,应该是用trie比较好,
回复 支持 反对

使用道具 举报

kuyen 发表于 2015-2-7 13:52:22 | 显示全部楼层
第四题比较intuitive的解法可以是用两个循环,外层是对所有边遍历,里层是对剩下的点找是否和那条边构成三角形。
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2015-2-7 14:21:59 | 显示全部楼层
五道题,是五轮的意思吗
回复 支持 反对

使用道具 举报

 楼主| souhomeca 发表于 2015-2-7 14:37:34 | 显示全部楼层
G家ONSITE弄一天,5个面试官每人45分钟,平均一道到两道题
回复 支持 反对

使用道具 举报

zuying 发表于 2015-2-8 00:14:10 | 显示全部楼层
图里三角形那个dfs, 参数里带个counter++, 如果counter - 3在visited set里就是一个三角形???
回复 支持 反对

使用道具 举报

yapingchen1990 发表于 2015-2-8 03:04:46 | 显示全部楼层
为啥楼主要面五轮呀?是不是因为楼主有工作经验?
回复 支持 反对

使用道具 举报

 楼主| souhomeca 发表于 2015-2-8 09:51:55 | 显示全部楼层
G家ONSITE面试都是一天内由5个面试官分别面试,每个人面45分钟,所有申请人都是这样,和有没有经验无关。
回复 支持 反对

使用道具 举报

pulpfree009 发表于 2015-2-8 10:40:08 | 显示全部楼层
感觉楼主基础不错,可能就是准备上有点仓促了。
第四题,觉得你的思路没问题. 你也可以google这方面的论文。
第三题,能再说的详细些吗?
但是实际上random_get必须把每个K-V对与一个0到N的整数关联,这个如果直接把MAP放到一个LIST里面去,算法效率就变成了O(N).

这是题目要求吗?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 17:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表