一亩三分地论坛

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

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

Google OA新题型

[复制链接] |试试Instant~ |关注本帖
allenxn24 发表于 2016-10-21 14:10:43 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Google - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
Google OA 变题了,说好的路径呢. Waral 鍗氬鏈夋洿澶氭枃绔,
第一题 输入一个String S(只包含- 和字母) 和 int K, 重新组织String,从末尾开始 每k个字符加一个”-“。O(n)时间
第二题 求一个二叉查找数中,最大的subtree的size。subtree所有元素都必须在范围[A,B]之间。O(n)。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
宝宝心累- -

评分

2

查看全部评分

本帖被以下淘专辑推荐:

zjuzqh 发表于 2016-10-21 22:36:59 | 显示全部楼层
第二题可以递归来做。

class solution {
public:
   int getSubTreeSize(node* root,int left,int right) {   //主函数
       Result=INT_MIN;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
       helper(root,left,right);
       return Result;. 鍥磋鎴戜滑@1point 3 acres
   }

   int helper(node* root,int left,int right) {   //返回以root为根节点的子树满足[left,right]条件的节点数。根节点必须选。
       if(root==NULL) return 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
       int left_num=helper(root->left,left,right);
       int right_num=helper(root->right,left,right);
       int res=0;
       if(left<=root->val&&right>=root->val) {
           res=1+left_num+right_num;
       }
       if(res>Result) {
          Result=res;
       }
       return res;
   }
private:
   int Result;
};
回复 支持 2 反对 0

使用道具 举报

zzgzzm 发表于 2016-11-1 23:43:00 | 显示全部楼层
zjuzqh 发表于 2016-10-21 22:36
第二题可以递归来做。

class solution {

这个题是找最大的满足条件的subtree,一个subtree是必须某个node和其所有子孙nodes. 在判断 “if(left<=root->val&&right>=root->val) {  res=1+left_num+right_num;  }”时,应该先判断left/right subtree是否满足条件再更新res吧。这个help function应该加一个invalid default return value (any negative value is OK),表示该subtree不是在[left, right]范围内的。否则例如对于一个简单的3 nodes的tree:root=1, left node = 100, right node = 100, 范围[0, 2],本来是没有这样的subtree,但原code返回1.
稍改动加个default value就可以了。
  1. int Result; // global variable to store node count of max valid subtree

  2. // main function
  3. int getSubTreeSize(Node* root, int left, int right) {
  4.   Result = -1; // default node count if subtree invalid
  5.   helper(root, left, right);
  6.   return Result;
  7. }

  8. // get node count of subtree rooted at "root" if valid; otherwise, return -1
  9. int helper(Node* root, int left, int right) {
  10.   if (root == NULL) return 0;
  11.   int left_num = helper(root->left, left, right);
  12.   int right_num = helper(root->right, left, right);
  13.   int res = -1; // default node count if subtree invalid
  14.   if (left_num >= 0 && right_num >= 0 && left <= root->val && right >= root->val) {
  15.     res = left_num + right_num + 1; // update node count only if valid
  16.     Result = max(Result, res); // update global result. visit 1point3acres.com for more.
  17.   }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  18.   return res;
  19. }
复制代码

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

qiweiren 发表于 2016-10-25 14:30:09 | 显示全部楼层
zjuzqh 发表于 2016-10-21 22:36
第二题可以递归来做。-google 1point3acres
.鏈枃鍘熷垱鑷1point3acres璁哄潧
class solution {

代码是不是有点问题?left_sum 和 right_sum应该check是不是-1?是的话说明subtree已经不合法了,然后直接返回-1?最后检测root.val 的时候也应该是如果它不在范围里面直接返回-1?
回复 支持 1 反对 0

使用道具 举报

syjohnson 发表于 2016-10-26 07:41:36 | 显示全部楼层
分享一个第二题代码,求大米.1point3acres缃
  1. //maxsubsize
  2.     public static class TreeNode{
  3.     TreeNode left;
  4.     TreeNode right;
  5.     int val;
  6.     public TreeNode(int val){
  7.       this.val = val;
  8.     } . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9.   }
  10. static int max = -1;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  11. public static int maxSubsize(int A, int B, TreeNode root){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.   if(root == null) return 0;
  13.   if(root.val < A || root.val > B) return -1;
  14.   int left = maxSubsize(A, B, root.left);
  15.   int right = maxSubsize(A, B, root.right);
  16.   if(left == -1 || right == -1){
  17.     return -1;
  18.   }. from: 1point3acres.com/bbs
  19.   if(left != -1 && right != -1){
  20.     max = Math.max(1 + left + right, max);
  21.     return 1 + left + right;
  22.   }
  23.   return -1;

  24. }
复制代码

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

zzgzzm 发表于 2016-10-26 09:36:23 | 显示全部楼层
syjohnson 发表于 2016-10-26 07:41
分享一个第二题代码,求大米

Line 14: if(root.val < A || root.val > B) return -1;
这一行不应该立即返回吧。这样如果root node value一旦不在区间[A,B]范围内就不再检查子树范围了。例如给定范围[3,4]和一个3结点的tree: root = 1, left child = 2, right child = 3. 最大subtree size应该是1,不应该返回-1.
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-10-21 14:12:09 | 显示全部楼层
实习也有OA ?
回复 支持 反对

使用道具 举报

zws1818918 发表于 2016-10-21 16:10:32 | 显示全部楼层
我也是准备了路径那套题。。然后也是这个 楼主第二题做的咋样
回复 支持 反对

使用道具 举报

笑眯眯的白云 发表于 2016-10-21 16:28:38 来自手机 | 显示全部楼层
谢谢分享! 请问能否描述更清楚一点? 谢谢啦!
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-10-21 23:02:48 | 显示全部楼层
请问第一题从末尾开始取 K个字符只能是K个字母是吗?
回复 支持 反对

使用道具 举报

rubyj 发表于 2016-10-22 13:21:09 | 显示全部楼层
第一题有memory的要求吗?还是只要时间是O(n)就行了?
回复 支持 反对

使用道具 举报

 楼主| allenxn24 发表于 2016-10-25 15:39:10 | 显示全部楼层
rubyj 发表于 2016-10-22 13:21
第一题有memory的要求吗?还是只要时间是O(n)就行了?

空间也是O(n)
回复 支持 反对

使用道具 举报

 楼主| allenxn24 发表于 2016-10-25 15:42:19 | 显示全部楼层
zjuzqh 发表于 2016-10-21 22:36. from: 1point3acres.com/bbs
第二题可以递归来做。

class solution {
. 1point 3acres 璁哄潧
我用divide and conquer做的. 遍历树,然后用全局变量存答案。
回复 支持 反对

使用道具 举报

 楼主| allenxn24 发表于 2016-10-25 15:42:53 | 显示全部楼层
笑眯眯的白云 发表于 2016-10-21 16:28. from: 1point3acres.com/bbs
谢谢分享! 请问能否描述更清楚一点? 谢谢啦!

忘记截屏了T T 你那里不明白,我可以回答你
回复 支持 反对

使用道具 举报

 楼主| allenxn24 发表于 2016-10-25 15:43:19 | 显示全部楼层
syjohnson 发表于 2016-10-21 23:02.1point3acres缃
请问第一题从末尾开始取 K个字符只能是K个字母是吗?

没错!只能k个不多不少
回复 支持 反对

使用道具 举报

 楼主| allenxn24 发表于 2016-10-25 15:44:23 | 显示全部楼层

他叫coding sample...现在大公司越来越难了,日子太难过了。
回复 支持 反对

使用道具 举报

 楼主| allenxn24 发表于 2016-10-25 15:45:07 | 显示全部楼层
zws1818918 发表于 2016-10-21 16:10
我也是准备了路径那套题。。然后也是这个 楼主第二题做的咋样

分治做的,凑活的过了test case。不知道会不会有漏洞。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-25 23:36:06 | 显示全部楼层
第二题 求一个二叉查找数中,最大的subtree的size in range [A, B]。
因为一个tree的node范围是否在区间[A,B]可以很容易由他的左右子树的范围以及根的value来决定,所以可以用post-order traversal O(N)时间遍历整个tree, 同时注意不断更新最大满足区间范围子树的node count. 注意:在遍历过程中,若判定一个子树满足区间范围时一定要及时记录其node count以备parent trees使用。
  1. // global variables
  2. int low, high; // range low and high bounds
  3. int maxSubTreeSize = 0; // max subtree size in [low,high]

  4. struct Node {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  5.   int val; Node* left, *right;
  6.   Node(int v) :val(v), left(NULL), right(NULL) {}.鏈枃鍘熷垱鑷1point3acres璁哄潧
  7. };

  8. // true if tree rooted at x is in range [low,high]
  9. // count: node count if tree in range
  10. bool checkRange(Node* x, int& count) {
  11.   if (!x) { count = 0; return true; }
  12.   int leftCount, rightCount;
  13.   // do post-order traversal to update maxSubTreeSize
  14.   bool leftInRange = checkRange(x->left, leftCount);
  15.   if (leftInRange) maxSubTreeSize = max(maxSubTreeSize, leftCount);
  16.   bool rightInRange = checkRange(x->right, rightCount);
  17.   if (rightInRange) maxSubTreeSize = max(maxSubTreeSize, rightCount);.1point3acres缃
  18.   if (leftInRange && rightInRange && x->val >= low && x->val <= high) {
  19.     count = leftCount + rightCount + 1;.1point3acres缃
  20.     maxSubTreeSize = max(maxSubTreeSize, count);
  21.     return true;
  22.   }
  23.   else return false;
  24. }

  25. int getMaxSubTreeSize(Node* r, int a, int b) {
  26.   low = a; high = b; int count = 0;
  27.   checkRange(r, count);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  28.   return maxSubTreeSize;
  29. }. 1point 3acres 璁哄潧
复制代码

补充内容 (2016-11-1 23:46):
Line 17 and Line 19 多余的,请忽略。因为post-order traversal时已经检查过左右child nodes了。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-26 03:53:45 | 显示全部楼层
第一题 输入一个String S(只包含- 和字母) 和 int K, 重新组织String,从末尾开始 每k个字符加一个”-“。O(n)时间
我不确定这个输入的string可不可以pass by reference. 如果可以的话就可以O(1)空间(in place swap).
我的想法:对于string& s用一个slow index从右向左扫描(slow = n-1; slow >= 0; slow--),再用一个fast index寻找可以和当前的s[slow]交换的前面的char的位置:
1. 当slow的位置不是(k+1)的整数倍时:若s[slow]是字母,忽略;否则和slow前的最后一个'-'交换;
2. 当slow的位置是(k+1)的整数倍时:若s[slow]是‘-’,忽略;否则和slow前的最后一个字母交换。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
注意有可能给的input string根本就无法完成要求,那么我的默认就是当找不到可以交换的char时就直接返回了,这样尽量把右边可以交换的string部分整理好就行了。例如 "qwd--rgf---r" k = 3, 返回 "---g-wdr-gfr"
该算法还保持了字母char的相对顺序在调用后是不变的。O(N)时间(应为slow, fast都至多扫描string各一遍),O(1)空间 (若string pass by value or const,重新创造string空间O(N))
  1. void rearrangeString(string& s, unsigned int k) {
  2.   int n = s.length(); //if (k == 0 || n < 2) return;
  3.   int slow = n;     // current index of char to check
  4.   int fast = n - 2; // last index of char before current to swap with
  5.   
  6.   while (--slow >= 0) { // scan s from right to left
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  7.     // not at multiple of (k+1)th position, but encounter '-'
  8.     if ((n - slow) % (k+1) && s[slow] == '-') {. 1point3acres.com/bbs
  9.       // find last index of letter char before current to swap with
  10.       while (fast >= 0 && s[fast] == '-') fast--;
  11.       if (fast < 0) return; // if no desired char, we have to quit
  12.       swap(s[slow], s[fast]); fast--;
  13.     }
  14.     // at multiple of (k+1)th position, but encounter a letter char. 鍥磋鎴戜滑@1point 3 acres
  15.     else if ((n - slow) % (k + 1) == 0 && s[slow] != '-') {
  16.       // find last index of '-' before current to swap with
  17.       while (fast >= 0 && s[fast] != '-') fast--;
  18.       if (fast < 0) return; // if no desired char, we have to quit
  19.       swap(s[slow], s[fast]); fast--;
  20.     }
  21.   }
  22. }
复制代码
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-10-26 07:41:06 | 显示全部楼层
贴上这两题的代码,顺便告知下全职的oa并没有变,变的应该只是实习,祝好运!
  1. //convert string.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2.   public static String convert(String s, int K){
  3.     StringBuilder sb = new StringBuilder();
  4.     for(char c : s.toCharArray()){
  5.       if(c != '-'){
  6.         sb.append(c);
  7.       }. 1point 3acres 璁哄潧
  8.     }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  9.     int len = sb.length();
  10.     while(len - K >0){
  11.       len = len - K;
  12.       sb.insert(len, '-');
  13.     }-google 1point3acres
  14.     return sb.toString().toUpperCase();
  15.   }
复制代码
回复 支持 反对

使用道具 举报

dlys3000 发表于 2016-10-26 09:45:14 | 显示全部楼层
我擦 现在的实习面试都这么难了。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 09:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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