一亩三分地论坛

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

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

Bloomberg四轮挂经

[复制链接] |试试Instant~ |关注本帖
zzz1322 发表于 2016-5-20 06:36:37 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Bloomberg - 网上海投 - 技术电面 Onsite |Failfresh grad应届毕业生

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

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

x
Phone,一轮。
第一题,给一个数字n,按字典序输出1-n的所有数字,要求尽可能优化时空复杂度。
例如,n=11. 1point3acres.com/bbs
Output:1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9
第二题,BST上面的Two Sum:一颗二叉搜索树,给一个target,求树里面和为target的任意一个pair。.鐣欏璁哄潧-涓浜-涓夊垎鍦

Onsite
第一轮:
设计国际象棋,设计一个函数使得query(int row, int col) 可以表示在(row, col)的棋子可以吃掉那些棋子。

第二轮:
1. 一个String,求里面第一个出现的Unique Char. 1point 3acres 璁哄潧
2. 约瑟夫问题.鏈枃鍘熷垱鑷1point3acres璁哄潧
3. Invert Binary Tree LC226

第三轮:
HR扯淡

第四轮:
Manager就我的Project提出的一些Design方面的问题。

Onsite第一轮表现的不好,没玩过国际象棋,现问的规则。。。
发帖攒RP,祝大家都能拿到满意的Offer!

评分

2

查看全部评分

jiaozhu200601 发表于 2016-8-27 00:32:45 | 显示全部楼层
第一题是lc 386. Lexicographical Numbers

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

dfnjy 发表于 2016-7-15 10:04:35 | 显示全部楼层
陈润鹏 发表于 2016-7-15 08:23. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
请问电面第一题怎么做呀?想了一个往前推的方法 发现做不了

我也胡写了一个:
return aaa(a,1,n):
  1. void aaa(vector<int> &a, int num, int cap){
  2.         if (num>cap) return;
  3.         int i,j;
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.         j=num%10?9:10;
  5.         for (i=0;i<j;i++){
  6.                 if (i+num>cap) return;. more info on 1point3acres.com
  7.                 a.push_back(i+num);
  8.                 aaa(a,(i+num)*10,cap);
  9.         }
  10. }
复制代码
回复 支持 1 反对 0

使用道具 举报

陈润鹏 发表于 2016-7-15 08:23:49 | 显示全部楼层
请问电面第一题怎么做呀?想了一个往前推的方法 发现做不了
回复 支持 反对

使用道具 举报

xiongm 发表于 2016-7-15 09:40:26 | 显示全部楼层
陈润鹏 发表于 2016-7-15 08:23
请问电面第一题怎么做呀?想了一个往前推的方法 发现做不了

想了半天写了一个,不知道对不对,真不太好做

int base,left,right;
for (auto i = 1; i <= 9; i++). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
{. From 1point 3acres bbs
   base = 1;
   while(1)
   {
      left = base * i;
      right = left + base;
      if (n < left ) break;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
      else if (n >= left && n < right) output left->n including n
      {
         for(j = left;j <= n; j++) cout << j << " ";   . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
      }. 鍥磋鎴戜滑@1point 3 acres
      else // output whole range excluding right
      {
          for (j = left; j < right; j++) cout << j << " ";
      }
       base *= 10;      
   } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}
回复 支持 反对

使用道具 举报

dfnjy 发表于 2016-7-15 10:02:19 | 显示全部楼层
店面第二题有logn的解法吗
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-7-15 11:06:43 | 显示全部楼层
dfnjy 发表于 2016-7-15 10:04
我也胡写了一个:
return aaa(a,1,n):
  1. public class NumDict {
  2.         public ArrayList<Integer> getNums(int n) {
  3.                 ArrayList<Integer> res = new ArrayList();. 1point 3acres 璁哄潧
  4.                 for (int i =1; i<=9;i++) {
  5.                         generate(res, i,n);
  6.                 }
  7.                 return res;
  8.         }

  9.         private void generate(ArrayList<Integer> res, int cur, int n) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.                 if (cur>n) return;
  11.                 res.add(cur);
  12.                 for (int i=0;i<10;i++) {
  13.                         if ((long) cur*10+i <=n) {
  14.                                 generate(res,cur*10+i,n);
  15.                         }
  16.                 }
  17.         }

  18.         public static void main(String[] args) {
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19.                 NumDict q = new NumDict();
  20.                 System.out.println(q.getNums(11));
  21.         }
  22. }
复制代码
我写了一个dfs
回复 支持 反对

使用道具 举报

myangelasuka 发表于 2016-7-15 11:27:48 | 显示全部楼层
dfnjy 发表于 2016-7-15 10:04
我也胡写了一个:.鐣欏璁哄潧-涓浜-涓夊垎鍦
return aaa(a,1,n):

为什么要判断num%10 啊 我觉得 j 直接等于10就行。。。
回复 支持 反对

使用道具 举报

lb5160482 发表于 2016-8-10 06:29:43 | 显示全部楼层
DFS, 试了几组数字,应该没问题,有问题欢迎指出。。
  1. class Solution {
  2. public:. 1point 3acres 璁哄潧
  3.         vector<int> pringDict(int n) {
  4.                 vector<int> res;. 鍥磋鎴戜滑@1point 3 acres
  5.                 helper(res, 0, n);

  6.                 return res;
  7.         }

  8.         void helper(vector<int>& res, int n, int maxNum) {
  9.                 if (n > maxNum) {
  10.                         return;
  11.                 }
  12.                 for (int i = 0; i < 10; ++i) {
  13.                         if (n + i > maxNum) {
  14.                                 break;
  15.                         }
  16.                         if (n + i == 0) {
  17.                                 continue;
  18.                         }.1point3acres缃
  19.                         res.push_back(n + i);
  20.                         helper(res, (n + i) * 10, maxNum);
  21.                 }
  22.         }. From 1point 3acres bbs
  23. };
复制代码
回复 支持 反对

使用道具 举报

hanover 发表于 2016-8-12 03:40:07 | 显示全部楼层
void printNumLexOrder(int limit)
{
    int val = 1;-google 1point3acres
    bool cont = true;
   
    while (cont) {
        print(val)
        int out;
        cont = generateLexNext(val, limit, out);
        val = out;
    }
}


bool generateLexNext(const int val, const int limit, int& out)
{
    if (val * 10 <= limit) . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    {
        out = val * 10;
        return true;
    }
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    bool found = false;
    int currVal = val;
    while (!found && currVal > 0) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
        int modNUm = currVal % 10;        
        if (modNum < 9) {
            out = currVal + 1;
            found = true;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        } else {
            currVal /= 10;
        }
    }        
   
    return found;
.鏈枃鍘熷垱鑷1point3acres璁哄潧
}
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-14 03:57:49 | 显示全部楼层
第一题写了一个dfs 测了几个大概是对的~ 求指正~~


  1.         public void print(int n){
  2.                 if(n <= 0) return;
  3.                 dfs(0, n);
  4.         }
  5.        
  6.         private void dfs(int cur, int max){
  7.                 if(cur > max) return;
  8.                 //System.out.println(cur);
  9.                
  10.                 int i = 0;
  11.                 if(cur == 0){
  12.                         i = 1;
  13.                 }
  14.                 . From 1point 3acres bbs
  15.                 for(; i <= 9; i++){
  16.                         int origin = cur;
  17.                         cur = cur*10 + i;
  18.                         . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  19.                         if(cur > max) break;
  20.                         System.out.println(cur);
  21.                        
  22.                         dfs(cur, max);
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  23.                         //backtracking
  24.                         cur = origin;
  25.                 }
  26.         }. more info on 1point3acres.com
  27.         .鐣欏璁哄潧-涓浜-涓夊垎鍦
  28.         public static void main(String[] args){
  29.                 PrintNum r = new PrintNum();
  30.                 r.print(100);
  31.         }
复制代码
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-14 03:59:18 | 显示全部楼层
第二题请问楼主是先把中序存起来再用两个指针找吗?~ 这样要n space但是n就可以完成 我写了一个nlogn的 每次都要从root往下找值   不知道各位还有没有更好的做法~

  1. class TreeNode{.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.         int val;
  3.         TreeNode left, right;
  4.         public TreeNode(int v){
  5.                 val = v;
  6.         }
  7. }

  8. class Pair{. visit 1point3acres.com for more.
  9.         TreeNode n1, n2;
    . 1point 3acres 璁哄潧
  10.         public Pair(TreeNode node1, TreeNode node2){
  11.                 n1 = node1;
  12.                 n2 = node2;
  13.         }
  14. }
  15. -google 1point3acres
  16. public class findTargetPairInBST {
  17.         public Pair find(TreeNode root, int target){. 1point 3acres 璁哄潧
  18.                 if(root == null) return null;
  19.                
  20.                 return search(root, root, target);
  21.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.         . 鍥磋鎴戜滑@1point 3 acres
  23.         private Pair search(TreeNode node, TreeNode root, int target){. more info on 1point3acres.com
  24.                 if(node == null) return null;
  25.                 .1point3acres缃
  26.                 //System.out.println(node.val);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  27.                
  28.                 int cur = target - node.val;-google 1point3acres
  29.                
  30.                 // 从root找val = cur的node. 鍥磋鎴戜滑@1point 3 acres
  31.                 TreeNode n = helper(root, node, cur);
  32.                 if(n != null){
  33.                         return new Pair(node, n);
  34.                 }. 鍥磋鎴戜滑@1point 3 acres
  35.                 . 1point 3acres 璁哄潧
  36.                 Pair res1 = search(node.left, root, target);
  37.                 if(res1 != null) return res1;
  38.                
  39.                 return search(node.right, root, target);. 鍥磋鎴戜滑@1point 3 acres
  40.                
  41.         }
  42.         private TreeNode helper(TreeNode node, TreeNode cur, int target){
  43.                 if(node == null) return null;
  44.                 if(node.val == target){
  45.                         //不能是重复的点
  46.                         if(node != cur){
  47.                                 return node;
  48.                         }
  49.                         return null;-google 1point3acres
  50.                 }
  51.                 else if(node.val > target) return helper(node.left, cur, target);
  52.                 else return helper(node.right, cur, target);
  53.         }
  54. }
复制代码
回复 支持 反对

使用道具 举报

Lilian1109 发表于 2016-8-27 02:52:13 | 显示全部楼层
jiaozhu200601 发表于 2016-8-27 00:32
第一题是lc 386. Lexicographical Numbers
  1. vector<int> LexiNumber(int n){
  2.     vector<int> res;. Waral 鍗氬鏈夋洿澶氭枃绔,
  3.     int curr = 1;. from: 1point3acres.com/bbs
  4.     for(int i = 0; i < n; i++){
  5.         res.push_back(curr);
  6.         if(curr * 10 <= n) curr *= 10;
  7.         else if(curr % 10 != 9 && curr + 1 <= n) curr++;
  8.         else{. From 1point 3acres bbs
  9.             while(curr/10 % 10 == 9)curr /= 10; // for example: curr = 299
  10.             curr = curr/10 + 1;
  11.         }
  12.     }
  13.     return res;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  14. }
复制代码
copy 个答案过来
回复 支持 反对

使用道具 举报

jiaozhu200601 发表于 2016-8-27 06:38:53 | 显示全部楼层
我看到网上比较好的做法还是用两个stack来做的,一个stack follow 的是正常的inorder traversal顺序,另一个follow的是reverse inorder traversal的顺序, 然后其平均时间复杂度就能保证是O(logn), 而且space也是O(logn), 类似于这个: http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/

补充内容 (2016-8-27 06:39):
这是关于电面第二题的解答
回复 支持 反对

使用道具 举报

cicean 发表于 2016-9-21 12:40:56 | 显示全部楼层
jiaozhu200601 发表于 2016-8-27 00:32
第一题是lc 386. Lexicographical Numbers

完全不记得有这题,大神就是大神
回复 支持 反对

使用道具 举报

cicean 发表于 2016-9-21 12:42:20 | 显示全部楼层
jiaozhu200601 发表于 2016-8-27 00:32
第一题是lc 386. Lexicographical Numbers
. 1point 3acres 璁哄潧
我就是直接写了个比较器,也不知道对不对
回复 支持 反对

使用道具 举报

BRYCEMENG 发表于 2016-10-29 01:54:56 | 显示全部楼层
请问lz多久得到的回信啊
回复 支持 反对

使用道具 举报

bcc 发表于 2016-10-29 23:22:30 | 显示全部楼层
lz约瑟夫问题你怎么写的啊?数学方法么?需要推导公式么?
回复 支持 反对

使用道具 举报

BRYCEMENG 发表于 2016-10-30 07:55:47 | 显示全部楼层
请问lz多久得到的回复的啊
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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