一亩三分地论坛

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

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

Google电面

[复制链接] |试试Instant~ |关注本帖
我是小马甲 发表于 2015-10-2 16:13:49 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Passfresh grad应届毕业生

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

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

x
谷歌第一轮电面,已过。. visit 1point3acres.com for more.
1. Longest substring without repeating letters. 原题,不说了
2. Longest consecutive numbers in a binary tree.

关于第二题,大致意思是这样,让在binary tree里挑出最长的连续(必须后面数=前面数+1)递增数列,数列顺序只能从parent到child,不可以反着来。比如:

                 1
                    \ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                      3
                    /    \
                  2      4-google 1point3acres
                           \
                             5
则返回[3, 4, 5]
. 鍥磋鎴戜滑@1point 3 acres

再比如:
                 2
                    \
                      3
                    /    \
                  1      4
                 /          \
               2             5. 1point3acres.com/bbs
              /
             3
            /
           4
. From 1point 3acres bbs
则返回[1, 2, 3, 4]

我一开始想着一个recursive就好了,后来发现还得用dfs更新每一个节点,大致程序这样:

public List<Integer> longestConsecutiveSequence(TreeNode root) {.1point3acres缃
        List<Integer> max = new ArrayList<Integer>();. 1point3acres.com/bbs
        longestListHelper(max, new ArrayList<Integer>(), root);  . 1point3acres.com/bbs
        return max;
    }
   
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴   
private void longestListHelper(List<Integer> max, List<Integer> list, TreeNode node) {
        if (node == null) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
            return;
        }. From 1point 3acres bbs
        
        if (list.size() == 0) {
            list.add(node.val);
        } else if (list.size() > 0 && list.get(list.size() - 1) == node.val -1) {.1point3acres缃
            list.add(node.val);
        } else {
            list = new ArrayList<Integer>();
            list.add(node.val);
        }
        
        if (list.size() > max.size()) {
            max.clear();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            max.addAll(list);
        }
        longestListHelper(max, list, node.left);
        longestListHelper(max, list, node.right);
        
    }




补充内容 (2015-10-2 16:16):
of course, second test case would pass if you return [2,3,4,5]

评分

1

查看全部评分

本帖被以下淘专辑推荐:

Wizmann 发表于 2015-10-2 22:00:45 | 显示全部楼层
  1. int ans = 0;
  2. void dfs(TreeNode* cur, int pre, int len) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  3.     if (cur == nullptr) {
  4.         return;
  5.     }
  6.     int value = cur->value;
  7.     if (value == pre + 1) {
  8.         len++;
  9.     } else {
  10.         len = 1;
  11.     }
  12.     ans = max(ans, len);
  13.     dfs(cur->left, value, len);. 1point 3acres 璁哄潧
  14.     dfs(cur->right, value, len);
  15. }

  16. dfs(root, -INF, 0);
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| 我是小马甲 发表于 2015-10-2 16:16:34 | 显示全部楼层
of course, second test case would pass if you return [2,3,4,5]
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-2 21:06:08 | 显示全部楼层
  1. void findLongest(TreeNode *root, vector<pair<int, int> > &path, int &max_len, int &tail) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  2.     if (root == NULL) {
  3.         return ;
  4.     }
  5.     if (path.empty() || root->val != path.back().first + 1) {
  6.         path.push_back(make_pair(root->val, 1));
  7.     } else {
  8.         path.push_back(make_pair(root->val, path.back().second + 1));
  9.         if (max_len < path.back().second) {
  10.             max_len = path.back().second;.1point3acres缃
  11.             tail = path.back().first;
  12.         }
  13.     }
  14.     findLongest(root->left, path, max_len, tail);
  15.     findLongest(root->right, path, max_len, tail);
  16.     path.pop_back();
  17. }
复制代码
有点像dp吧,pair first是结尾k,second为结尾为k最大长度. 鍥磋鎴戜滑@1point 3 acres

补充内容 (2015-10-2 21:07):. Waral 鍗氬鏈夋洿澶氭枃绔,
max_len是存的最大长度,tail是最大长度的结尾。输出直接输出tail-max_len + 1 ~ tail即可。

补充内容 (2015-10-2 21:18):
啊,也可以不用pair,只用int,记录当前节点的长度,前驱节点用一个参数传进去就行了。。
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-2 23:02:18 | 显示全部楼层
写了个iterative的
  1. class TreeNode:
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.left = None
  5.         self.right = None

  6. class Solution:
  7.     def longestConsecutiveNumsinBT(self, root):
  8.         if not root: return []
  9.         stack = [(root, [root.val])]
  10.         res = []
  11.         while stack:
  12.             node, path = stack.pop()
  13.             if not node.left and not node.right:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  14.                 res.append(path)
  15.                 continue
  16.             if node.left:
  17.                 if node.left.val == node.val + 1:
  18.                     stack.append((node.left, path + [node.left.val]))
  19.                 else:
  20.                     stack.append((node.left, [node.left.val]))
  21.             if node.right:
  22.                 if node.right.val == node.val + 1:
  23.                     stack.append((node.right, path + [node.right.val]))
  24.                 else:
  25.                     stack.append((node.right, [node.right.val]))

  26.         longest = res[0]
  27.         for i in range(1, len(res)):. 1point 3acres 璁哄潧
  28.             if len(res[i]) > len(longest):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  29.                 longest = res[i]
  30.         return longest
复制代码
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-10-4 05:16:59 | 显示全部楼层
Actually your code may not work for this case. you should reset list to the origin state when it's passed in before you call longestListHelper(max, list, node.left); and  longestListHelper(max, list, node.right);

your code will give [1, 2, 3, 4, 5, 6] given the following test case. while [1,2,3,4] is the right answer..鐣欏璁哄潧-涓浜-涓夊垎鍦
Anyway. Congs!
  1.         /*
  2.          *   1
  3.          *    \. more info on 1point3acres.com
  4.          *     2
  5.          *    / \
  6.          *   3   5
  7.          *  /     \
  8.          * 4       6
  9.          *      
  10.          */
复制代码
回复 支持 反对

使用道具 举报

tangvictor 发表于 2015-10-19 09:01:16 | 显示全部楼层
我用的是dfs做的,贴下我的代码以供大家参考。
  1. class TreeNode:
  2.         def __init__(self, val):. Waral 鍗氬鏈夋洿澶氭枃绔,
  3.                 self.val = val
  4.                 self.left = None
  5.                 self.right = None

  6. def longestConsecutiveNumbers(root):
  7.         res = [[]]
  8.         helper(root, [], res, True)
  9.         helper(root, [], res, False)
  10.         return res[0]

  11. def helper(root, line, res, isIncreased):
  12.         if root == None:
  13.                 return

  14.         if len(line) == 0 or (isIncreased and root.val == line[-1] + 1) or (not isIncreased and root.val == line[-1] - 1):
  15.                 if len(list(line) + [root.val]) > len(res[0]):
  16.                         res[0] = list(line) + [root.val]
  17.                 helper(root.left, line + [root.val], res, isIncreased). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.                 helper(root.right, line + [root.val], res, isIncreased)
  19.         else:
  20.                 helper(root.left, [root.val], res, True)
  21.                 helper(root.left, [root.val], res, False)
  22.                 helper(root.right, [root.val], res, True)
  23.                 helper(root.right, [root.val], res, False)
复制代码
回复 支持 反对

使用道具 举报

becky12 发表于 2015-10-19 10:08:58 | 显示全部楼层
我的代码:
void helper(TreeNode* root, int pre, int len, int& ans, int& val) {
    if (!root) {
        return;
    }. more info on 1point3acres.com
    int value = root->val;
    len = value==pre+1? len+1 : 1;
   
-google 1point3acres    if(len>ans){
        ans = len;
        val = value;
    }

    helper(root->left, value, len, ans, val);
    helper(root->right, value, len, ans, val);
}
vector<int> longest(TreeNode *root) {
    int ans =0, val = 0;. visit 1point3acres.com for more.
    helper(root, INT_MIN, 0, ans, val);
    vector<int> v;
    for(int i = ans-1;i>=0; --i){
      v.push_back(val-i);
    }
    return v;
}
回复 支持 反对

使用道具 举报

孤笑客 发表于 2015-10-20 02:15:10 | 显示全部楼层
这个应该邀请onsite了吧?MTV吗?
回复 支持 反对

使用道具 举报

肖邦的眼泪 发表于 2015-10-20 05:00:20 | 显示全部楼层
LifeGoesOn 发表于 2015-10-4 05:16
Actually your code may not work for this case. you should reset list to the origin state when it's p ...

Very correct points!

instead of longestListHelper(max, list, node.right), it should be longestListHelper(max, new ArrayList<Integer>(list), node.right)
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-10-20 12:45:13 | 显示全部楼层
用string保存,dfs
  1. import java.util.*;
  2. class TreeNode {
  3.   int val;
    .1point3acres缃
  4.   TreeNode left;
  5.   TreeNode right;. 1point3acres.com/bbs
  6.   TreeNode(int x) { val = x; }
  7. }
  8. public class FindSequenceTree {
  9.         int max =0;
  10.         String longest = "";. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  11.         public List<Integer> findSeq(TreeNode root){
  12.                 helper(root,"");.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.                 List<Integer> ret= new ArrayList<Integer>();
  14.                 for(int i =0 ; i < longest.length();i++){
  15.                         ret.add(longest.charAt(i)-'0');
  16.                 }               
  17.                 return ret;
  18.         }
  19.         public void helper(TreeNode root,String str){
  20.                 String result = str+String.valueOf(root.val);
  21.                 if(result.length()>max){
  22.                         max=result.length();
  23.                         longest=result;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.                 }
  25.                 if(root.left==null && root.right==null) return;
  26.                 if(root.right!=null){
  27.                         if(root.right.val==root.val+1) helper(root.right,result);
  28.                         helper(root.right,"");
  29.                 }
  30.                 if(root.left!=null){
  31.                         if(root.left.val==root.val+1) helper(root.left,result);
  32.                         helper(root.left,"");
  33.                 }
  34.         }
  35.         public static void main(String args[]) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  36.                 FindSequenceTree cmt = new FindSequenceTree();
  37.                 TreeNode root=new TreeNode(4);
  38.                 TreeNode t1=new TreeNode(1);
  39.                 TreeNode t2=new TreeNode(2);
  40.                 TreeNode t3=new TreeNode(3);
  41.                 TreeNode t5=new TreeNode(5);
  42.                 TreeNode t6=new TreeNode(6);. Waral 鍗氬鏈夋洿澶氭枃绔,
  43.                 TreeNode t7=new TreeNode(7);
  44.                 TreeNode t8=new TreeNode(8);. 鍥磋鎴戜滑@1point 3 acres
  45.                 root.left=t1;
  46.                 t1.left=t2;
  47.                 t1.right=t3;
  48.                 root.right=t6;
  49.                 t6.right=t7;
  50.                 t7.left=t8;
  51.                 System.out.println(cmt.findSeq(root));
  52.         }
  53. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 06:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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