一亩三分地论坛

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

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

Bloomberg水过店面

[复制链接] |试试Instant~ |关注本帖
tktrung 发表于 2016-2-18 03:29:58 | 显示全部楼层 |阅读模式

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

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

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

x
准备onsite,才想起没回报店面面筋。就贴一下题和经历。大家路过给点米啊,好多帖子都没法看

白人小哥,来就问下简历的,然后就上题。两道在collabedit实现,写完要跑testcase.1point3acres缃
1)give a string, find number of unique substring (given string could be extremely long, contained duplicate alphabet a-z)
我有点崩溃,题不难,就两个for循环就搞出来substring,不过这题是counting的,想了一会是在想不出来好办法,就说两个for,一个set控制重复,最后return len(set)
小哥没一件,让我写。果然10个testcase只过了7个,小哥笑着,你这space cost太高了。当是真无奈了,也想不到更好办法,就说还是用set但优化set中的成员,就encode下string。idea是类似leecode中DNA那题,这样就不用存整个substring二只要存对应的int。讲了半天好像他才明白了我的意思,就说算了不用谢,继续下一题-google 1point3acres

2)Given an array, find second maximum element
. 鍥磋鎴戜滑@1point 3 acres这题之前考虑过,一看就知道扫一遍就是,但还装逼下,说最笨方法是扫两边,然后开始优化,说用两个变量,一个是first max,一个second max。从左往右,边走边更新。想法很简单,然后他让我写。傻逼的collabedit,当时就选不了Python, 让我等会才能下手
此题说简单,但要考虑各种case,各位看下case就明白
[1,2,3] —》 2
[1] -》 1
[1,1] -》1
[1,2,3,3] -》2
就是若没有第二大就给最大,若有多个同等最大,还是都当最大,在给出第二大的. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

代码写好了,跑case还话很多时间跳bug。最后小哥还是说可以了。.鐣欏璁哄潧-涓浜-涓夊垎鍦
. from: 1point3acres.com/bbs
然后问他一些经典问题,就拜拜。一周后收到onsite。大家说中午那天是不是要自己准备下饭吃,他们家的饭盒那么

就这些了,码农们加油!路过的给点米,给点分,给点油哈

评分

5

查看全部评分

Jailf 发表于 2016-6-30 14:36:36 | 显示全部楼层
我感觉你就每次遍历时候数长度相同的substring有多少个不同的。
比如先遍历数完长度为1的,然后2的,这样就不用存所有的substring。
字符串长度为N, substring长度为M时,最多有N-M个不一样的,每次的空间就是M*(N-M),这样最大的时候是当M = 1/2*N,空间就是1/4*N^2。. 鍥磋鎴戜滑@1point 3 acres

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

elevenz 发表于 2016-2-19 13:42:58 | 显示全部楼层
https://en.wikipedia.org/wiki/Suffix_array
不知道能不能说清楚额。。。比如给的string是“asda”,先生成一个O(n)的数组(n是string的length,这里就是4),每个元素对应的是string的(0-n)的后缀。(所以数组元素就分别是"a","da","sda"和"asda")
然后sort这n个后缀元素(变成"a","asds","da","sda"),从第一个开始比较sort之后的数组相邻的两个元素有几个char是前缀匹配的,然后当前数组元素那个string的长度减去匹配的char的个数就可以得到unique的substring个数啦。。。就是 1 + (4-1) + (2-0) +(3-0) = 9个元素啦。

楼主的方法当然也很不错,用set就可以直接把所有满足的unique string都print出来,但是这题目说只要个数的话,感觉应该还是用后缀数组会好一些(少用空间了),而且时间上整体也会更优一些。。。。

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

elevenz 发表于 2016-2-19 11:57:57 | 显示全部楼层
第一题用后缀数组做比较好吧
回复 支持 反对

使用道具 举报

 楼主| tktrung 发表于 2016-2-19 12:23:31 | 显示全部楼层
elevenz 发表于 2016-2-19 11:57. 1point3acres.com/bbs
第一题用后缀数组做比较好吧

能详细点吗?
回复 支持 反对

使用道具 举报

neostar2008 发表于 2016-2-19 12:34:15 | 显示全部楼层
第一题不用Set存,用Trie存应该会节省点空间,不知道是不是面试官想要的. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
当然LZ的方法也很好
回复 支持 反对

使用道具 举报

 楼主| tktrung 发表于 2016-2-19 23:22:39 | 显示全部楼层
elevenz 发表于 2016-2-19 13:42. 鍥磋鎴戜滑@1point 3 acres
https://en.wikipedia.org/wiki/Suffix_array
不知道能不能说清楚额。。。比如给的string是“asda”,先生 ...

受教了,多谢大神
回复 支持 反对

使用道具 举报

 楼主| tktrung 发表于 2016-2-19 23:24:43 | 显示全部楼层
neostar2008 发表于 2016-2-19 12:34
第一题不用Set存,用Trie存应该会节省点空间,不知道是不是面试官想要的
当然LZ的方法也很好

我总感觉用Trie的话,好说但下手写代码好难啊,估计在优化乱扯的时候提到
回复 支持 反对

使用道具 举报

JamesJi 发表于 2016-2-19 23:37:36 | 显示全部楼层
他家饭盒··反正我只吃了fruit cup,那个taco简直不能忍,纯素没有肉
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-4 14:13:06 | 显示全部楼层
第一题不明白楼主什么意思,能麻烦加个例子,方便大家理解吗?谢谢!
回复 支持 反对

使用道具 举报

wrf91324 发表于 2016-3-24 12:14:05 | 显示全部楼层
第一题写了个Trie数版本

public class Solution {

        private class Trie{
                private final static int R = 256;
                private class Node {.1point3acres缃
                        int value = 0;
                        Node[] next;
                        Node() {
                                next =new Node[R];
                        }. From 1point 3acres bbs
                }

                private Node root = new Node();
                private int size = 0;
-google 1point3acres
                public void put(String s, int value) {
                        put(s, 0, root, value);
                }

                public Node put(String s, int index, Node root, int value) {
. visit 1point3acres.com for more.                        if (root == null) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                root = new Node();
                        }

                        if (index == s.length()) {. from: 1point3acres.com/bbs
                                if (root.value == 0) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                        size++;. visit 1point3acres.com for more.
                                }
                                root.value = value;
                                return root;
                        }

                        char c = s.charAt(index);
                        root.next[c] = put(s, index + 1, root.next[c], value);
                        return root;

                }


        }

        public int countDistincSubstring(String input) {
                if (input == null || input.length() == 0) {. visit 1point3acres.com for more.
                        return 0;
                }

                int size = input.length();
                int count = 0;
                Trie t = new Trie();-google 1point3acres
                for (int i = 0; i < size; i++) {
                        for (int j = i; j < size; j++) {
                                String sub = input.substring(i, j + 1);
                                t.put(sub, 1);. 1point3acres.com/bbs
                        }
                }

                return t.size;. From 1point 3acres bbs
        }

        public static void main(String[] args) {
                Solution sol = new Solution(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                String s = new String("abcd");
                int count = sol.countDistincSubstring(s);
                System.out.println(count);
        }. from: 1point3acres.com/bbs
}
回复 支持 反对

使用道具 举报

llatjob 发表于 2016-7-1 20:38:36 | 显示全部楼层
Jailf 发表于 2016-6-30 14:36
我感觉你就每次遍历时候数长度相同的substring有多少个不同的。
比如先遍历数完长度为1的,然后2的,这样 ...

这个解法赞一个
回复 支持 反对

使用道具 举报

lb5160482 发表于 2016-8-13 07:05:38 | 显示全部楼层
后缀数组都考到啊。。。。。。。
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-13 12:48:33 | 显示全部楼层
楼主请问一下~ 第一题 那些重复的substring也要算一次unique string里面的数量吗?~  比如 aab unique的就是a,b, aa, ab, aab 还是a不算呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 03:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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