近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2560|回复: 10
收起左侧

Google电面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
谷歌第一轮电面,已过。
1. Longest substring without repeating letters. 原题,不说了. 1point 3acres 璁哄潧
2. Longest consecutive numbers in a binary tree.
. 鍥磋鎴戜滑@1point 3 acres
关于第二题,大致意思是这样,让在binary tree里挑出最长的连续(必须后面数=前面数+1)递增数列,数列顺序只能从parent到child,不可以反着来。比如:

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴                 1
                    \-google 1point3acres
                      3. more info on 1point3acres.com
                    /    \
                  2      4
                           \
                             5
则返回[3, 4, 5]


再比如:
                 2
                    \
                      3
                    /    \
                  1      4
                 /          \
               2             5
              /
             3
            /
           4
. Waral 鍗氬鏈夋洿澶氭枃绔,
则返回[1, 2, 3, 4]
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷-google 1point3acres
我一开始想着一个recursive就好了,后来发现还得用dfs更新每一个节点,大致程序这样:

public List<Integer> longestConsecutiveSequence(TreeNode root) {. 鍥磋鎴戜滑@1point 3 acres
        List<Integer> max = new ArrayList<Integer>();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        longestListHelper(max, new ArrayList<Integer>(), root);  
        return max;
    }
    . 1point 3acres 璁哄潧
    -google 1point3acres
private void longestListHelper(List<Integer> max, List<Integer> list, TreeNode node) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
        if (node == null) {. from: 1point3acres.com/bbs
            return;
        }
        . Waral 鍗氬鏈夋洿澶氭枃绔,
        if (list.size() == 0) {
            list.add(node.val);
        } else if (list.size() > 0 && list.get(list.size() - 1) == node.val -1) {
            list.add(node.val);.鏈枃鍘熷垱鑷1point3acres璁哄潧
        } else {
            list = new ArrayList<Integer>();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            list.add(node.val);
        }
        
        if (list.size() > max.size()) {.1point3acres缃
            max.clear();. more info on 1point3acres.com
            max.addAll(list);
        }
        longestListHelper(max, list, node.left);
        longestListHelper(max, list, node.right);
        
    }




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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

Wizmann 发表于 2015-10-2 22:00:45 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
  1. int ans = 0;
  2. void dfs(TreeNode* cur, int pre, int len) {
  3.     if (cur == nullptr) {
  4.         return;
  5.     }. more info on 1point3acres.com
  6.     int value = cur->value;
  7.     if (value == pre + 1) {
  8.         len++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.     } else {
  10.         len = 1;
  11.     }
  12.     ans = max(ans, len);
  13.     dfs(cur->left, value, len);
  14.     dfs(cur->right, value, len);
  15. }
  16. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  17. dfs(root, -INF, 0);
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| 我是小马甲 发表于 2015-10-2 16:16:34 | 显示全部楼层
关注一亩三分地微博:
Warald
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) {-google 1point3acres
  6.         path.push_back(make_pair(root->val, 1));
  7.     } else {. From 1point 3acres bbs
  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;
  11.             tail = path.back().first;
  12.         }. from: 1point3acres.com/bbs
  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最大长度

补充内容 (2015-10-2 21:07):
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:. 1point 3acres 璁哄潧
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.left = None. Waral 鍗氬鏈夋洿澶氭枃绔,
  5.         self.right = None

  6. class Solution:
  7.     def longestConsecutiveNumsinBT(self, root):
  8.         if not root: return []
  9.         stack = [(root, [root.val])]. 鍥磋鎴戜滑@1point 3 acres
  10.         res = [].1point3acres缃
  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])). Waral 鍗氬鏈夋洿澶氭枃绔,
  19.                 else:. more info on 1point3acres.com
  20.                     stack.append((node.left, [node.left.val]))
  21.             if node.right:. more info on 1point3acres.com
  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. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  27.         longest = res[0]
  28.         for i in range(1, len(res)):
  29.             if len(res[i]) > len(longest):
  30.                 longest = res[i]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  31.         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);. from: 1point3acres.com/bbs

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.          *    \. From 1point 3acres bbs
  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):. from: 1point3acres.com/bbs
  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;
    }
    int value = root->val;
    len = value==pre+1? len+1 : 1;
    . 鍥磋鎴戜滑@1point 3 acres
    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;
    helper(root, INT_MIN, 0, ans, val);
    vector<int> v;
    for(int i = ans-1;i>=0; --i){. more info on 1point3acres.com
      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!
. visit 1point3acres.com for more.
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;
  4.   TreeNode left; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.   TreeNode right;
  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,"");
  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.         }
    . visit 1point3acres.com for more.
  19.         public void helper(TreeNode root,String str){
    -google 1point3acres
  20.                 String result = str+String.valueOf(root.val);
  21.                 if(result.length()>max){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.                         max=result.length();
  23.                         longest=result;
  24.                 }
  25.                 if(root.left==null && root.right==null) return;
  26.                 if(root.right!=null){. more info on 1point3acres.com
  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[]) {. From 1point 3acres bbs
  36.                 FindSequenceTree cmt = new FindSequenceTree();
  37.                 TreeNode root=new TreeNode(4);
  38.                 TreeNode t1=new TreeNode(1);
  39.                 TreeNode t2=new TreeNode(2);. 1point 3acres 璁哄潧
  40.                 TreeNode t3=new TreeNode(3);
  41.                 TreeNode t5=new TreeNode(5);
  42.                 TreeNode t6=new TreeNode(6);
  43.                 TreeNode t7=new TreeNode(7);
  44.                 TreeNode t8=new TreeNode(8);
  45.                 root.left=t1;
  46.                 t1.left=t2;
  47.                 t1.right=t3;
  48.                 root.right=t6;.1point3acres缃
  49.                 t6.right=t7;
  50.                 t7.left=t8;
  51.                 System.out.println(cmt.findSeq(root));
  52.         }
  53. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-26 08:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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