一亩三分地论坛

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

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

刚刚结束的Bloomberg 电面

[复制链接] |试试Instant~ |关注本帖
xuqicx23 发表于 2016-9-28 06:48:10 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 硕士 全职@Bloomberg - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
新人第一次发帖子,希望大家关照。之前看了地里的帖子感觉还是得到了很大的帮助,感谢各位地里的同志。所以我面完了也赶紧来回馈大家。美国小哥打来的电话上来做了自我介绍给我,之后让我做自我介绍。再就是问了下简历上的实习经历,遇到了哪些难点。可能我的背景小哥有点经验,问了挺深的在这个项目上。第一个问了bst和hashtable,介绍定义,各自的优劣。不过我提到了hashtable 是array based。小哥问我除了array还能用什么实现,没回答出来。。。
第一道coding,leetcode上的count and say变型,不同的是输入从他输入的string开始,递归运行n次。函数定义为. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
public void helper(String s, int n) 做完之后小哥让我写了test cases,又用手帮他跑了几个输入数据证明代码的正确性。。。。
第二道题目是一堆数组,
[1,1,1,1]
[2].鏈枃鍘熷垱鑷1point3acres璁哄潧
[3,3]. 鍥磋鎴戜滑@1point 3 acres
[4,4,4,4,4]
. 1point3acres.com/bbs要求输出的数是[1,2,3,4,1,3,4,1,4,1,4,4]就是纵着输出,我有点蒙蔽。用了queue来存然后pointer每次都扫过所有的数组,如果小于该数组长度就把值放入q里面去。走完一圈输出一次。
走的圈数是我先找了所有数组里最长的那个,当我index小于它的长度的时候我就一直运行循环。小哥提了疑问就是说如果像第二个数组这种已经走到头了按照我的算法以后还会比较index跟它的长度,. more info on 1point3acres.com
但我们已经可以省略掉这个数组了。怎么优化?这个地方又没答出来。。。本来这道题目小哥说不用写code,讲思路。但听完我的想法小哥还是让我写一下,于是我写完了。但是好像不是他想要的答案。。。
这道题结束大概50min了,问了他两个问题他说过几天有消息就结束了。感觉心里面没底。。。
新人没有大米,求打赏。。。

评分

1

查看全部评分

xiaozhuxiaozhu 发表于 2016-9-29 07:57:59 | 显示全部楼层
public class bloomberg {
        . 鍥磋鎴戜滑@1point 3 acres
        public static void main(String[] args)
        {
                Integer[][] nums = {
                        {1,1,1,1},
                        {2,3,4},
                        {3,3},
                        {4,4,4,4}. visit 1point3acres.com for more.
                };
                Queue<Iterator<Integer>> queue = new ArrayDeque<Iterator<Integer>>();
                for(int i =0 ; i < nums.length;i++)
                {-google 1point3acres
                        queue.add(Arrays.asList(nums[i]).iterator());. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                }
                while(!queue.isEmpty())
                {
                        Iterator<Integer> temp = queue.poll();
                        if(temp.hasNext())
                        {
                                System.out.println(temp.next());
                                queue.add(temp);
                        }
                }
        }. 鍥磋鎴戜滑@1point 3 acres
}

评分

2

查看全部评分

回复 支持 3 反对 0

使用道具 举报

湾区留下来 发表于 2016-9-28 06:56:37 | 显示全部楼层
感谢分享啊

不过按楼主的算法,即使比较index和长度,也是O(1)啊,不理解这里为什么需要优化。. Waral 鍗氬鏈夋洿澶氭枃绔,

或者说可以放k个指针到一个queue里,每次取每个指针指向的元素,然后让指针加一,如果已经到头,那么就删除掉指针。这样可以吗?.鐣欏璁哄潧-涓浜-涓夊垎鍦

然而如果是Java,又该怎么办呢?. visit 1point3acres.com for more.

回复 支持 反对

使用道具 举报

 楼主| xuqicx23 发表于 2016-9-28 06:59:19 | 显示全部楼层
湾区留下来 发表于 2016-9-28 06:56. 鍥磋鎴戜滑@1point 3 acres
感谢分享啊

不过按楼主的算法,即使比较index和长度,也是O(1)啊,不理解这里为什么需要优化。

其实我也不懂为什么一个if语句要优化,但是小哥是说你这个数组已经走到头了就没意义再用index跟这个数组长度比较了。所以这个地方我一直没给出他想要的结果
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-9-28 07:17:07 | 显示全部楼层
感谢楼主分享~ 请问hashtable底层除了array base 还能什么呢?。。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-9-28 07:22:46 | 显示全部楼层
何打发123 发表于 2016-9-28 07:17
感谢楼主分享~ 请问hashtable底层除了array base 还能什么呢?。。

linked list也可以吧?
回复 支持 反对

使用道具 举报

fantasy_001 发表于 2016-9-28 07:29:39 | 显示全部楼层
楼主那道纵向输出的题给的input是不是有规律,每个数组的数字都是相同的?如果是那样可以用个hashtable来做,不过那个时间复杂度也是O(n). hashtable是不是另一种实现是tree base呢?我知道C++里面有unordered_map,这个就是arraybase的,还有一个map,这个是红黑树实现的,查找和删除都是O(logN),但是因为是树形结构,所以随需随取,不用像array那样先分配一大片空间。不知道这个算不算hashtable。。
回复 支持 反对

使用道具 举报

fantasy_001 发表于 2016-9-28 07:31:23 | 显示全部楼层
leixiang5 发表于 2016-9-28 07:22
linked list也可以吧?

你说的是用linked list处理collision吧?不是也得一个array,key是hash function返回值,然后value是个list指针?
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-9-28 07:38:35 | 显示全部楼层
fantasy_001 发表于 2016-9-28 07:31
你说的是用linked list处理collision吧?不是也得一个array,key是hash function返回值,然后value是个li ...
. more info on 1point3acres.com
面试官应该是问...还有什么能implement dictionary吧..hashtable是其中一个。。linkedlist..bst都可以吧..只是速度慢了点..
回复 支持 反对

使用道具 举报

buqun 发表于 2016-9-28 07:38:44 | 显示全部楼层
请问下楼主是怎么申的Bloomberg?
回复 支持 反对

使用道具 举报

 楼主| xuqicx23 发表于 2016-9-28 07:46:32 | 显示全部楼层
fantasy_001 发表于 2016-9-28 07:29. 鍥磋鎴戜滑@1point 3 acres
楼主那道纵向输出的题给的input是不是有规律,每个数组的数字都是相同的?如果是那样可以用个hashtable来做 ...

没有规律的,我问了是不是sorted的。小哥明确说任意数组
回复 支持 反对

使用道具 举报

 楼主| xuqicx23 发表于 2016-9-28 07:46:55 | 显示全部楼层
buqun 发表于 2016-9-28 07:38
请问下楼主是怎么申的Bloomberg?

师兄内推的哈
回复 支持 反对

使用道具 举报

 楼主| xuqicx23 发表于 2016-9-28 07:47:39 | 显示全部楼层
leixiang5 发表于 2016-9-28 07:22
linked list也可以吧?

我也同意linkedlist应该也是一个答案。唉,可惜面试的时候没想到
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-9-28 08:10:38 | 显示全部楼层
xuqicx23 发表于 2016-9-28 07:47
我也同意linkedlist应该也是一个答案。唉,可惜面试的时候没想到
. Waral 鍗氬鏈夋洿澶氭枃绔,
没事..表现的很不错了~.会有next round的..
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-28 08:45:54 | 显示全部楼层
从他输入的string开始,递归运行n次 是什么意思?比如 string=111221

补充内容 (2016-9-28 08:53):
ignore my post
回复 支持 反对

使用道具 举报

hulahu 发表于 2016-9-28 09:28:13 | 显示全部楼层
把扫完的index变成负数。。
回复 支持 反对

使用道具 举报

119018682 发表于 2016-9-28 09:40:27 | 显示全部楼层
谢楼主分享
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-9-28 10:22:43 | 显示全部楼层
leixiang5 发表于 2016-9-28 07:38
面试官应该是问...还有什么能implement dictionary吧..hashtable是其中一个。。linkedlist..bst都可以吧. ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
但是面试官已经问了BST和map的区别=。=0.0.。。。。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-28 12:39:01 | 显示全部楼层
请问楼主BB是用HackerRank来做电面吗?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-28 13:16:19 | 显示全部楼层
第二道题数组纵向输出的优化:假设给定vector<vector<int>>arr, 实际上就是问用什么数据结构来做对于第一指标arr循环时可以省区不必要的比较。个人认为用list<int>,因为list的iterator是persist的,也就是说当元素删除时, iterator会自动指向下一个元素,而不会invalid。

void VerticalPrint(vector<vector<int>>& arr) {
. 1point3acres.com/bbs  int n = arr.size(), maxLen = 0;
  list<int> idx; // store index of arr which still has values to output
  int i = 0; while (i < n) idx.push_back(i++);
  for (auto& x:arr) maxLen = max(maxLen, x.size());
  for (int j = 0; j < maxLen; ++j) {
    auto it = idx.begin();
    while (it != idx.end()) {
      cout << arr[*it][j] << " ";. more info on 1point3acres.com
      if (j+1 == a[*it].size()) idx.erase(it);
. more info on 1point3acres.com      else it++;
    }
  }
  
}. 鍥磋鎴戜滑@1point 3 acres
. from: 1point3acres.com/bbs
补充内容 (2016-9-29 05:41):
typo " idx.erase(it);" should be corrected to " it = idx.erase(it);"
回复 支持 反对

使用道具 举报

cicean 发表于 2016-9-28 14:31:47 | 显示全部楼层
我以为,我面的挺容易的,发现也有不太难的。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 09:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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