Bloomberg水过店面

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

白人小哥，来就问下简历的，然后就上题。两道在collabedit实现，写完要跑testcase
1）give a string, find number of unique substring (given string could be extremely long, contained duplicate a

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

拜。一周后收到onsite。大家说中午那天是不是要自己准备下饭吃，他们家的饭盒那么

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

我感觉你就每次遍历时候数长度相同的substring有多少个不同的。
比如先遍历数完长度为1的，然后2的，这样就不用存所有的substring。
字符串长度为N, substring长度为M时，最多有N-M个不一样的，每次的空间就是M*（N-M)，这样最大的时候是当M = 1/2*N，空间就是1/4*N^2。

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出来，但是这题目说只要个数的话，感觉应该还是用后缀数组会好一些（少用空间了），而且时间上整体也会更优一些。。。。

第一题写了个Trie数版本

public class Solution {

        private class Trie{
                private final static int R = 256;
                private class Node {
                        int value = 0;
                        Node[] next;
                        Node() {
                                next =new Node[R];
                        }
                }

                private Node root = new Node();
                private int size = 0;

                public void put(String s, int value) {
                        put(s, 0, root, value);
                }

                public Node put(String s, int index, Node root, int value) {
                        if (root == null) {
                                root = new Node();
                        }

                        if (index == s.length()) {
                                if (root.value == 0) {
                                        size++;
                                }
                                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) {
                        return 0;
                }

                int size = input.length();
                int count = 0;
                Trie t = new Trie();
                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);
                        }
                }

                return t.size;
        }

        public static void main(String[] args) {
                Solution sol = new Solution();
                String s = new String("abcd");
                int count = sol.countDistincSubstring(s);
                System.out.println(count);
        }
}

第一题用后缀数组做比较好吧

elevenz 发表于 2016-2-19 11:57
第一题用后缀数组做比较好吧

能详细点吗？

第一题不用Set存，用Trie存应该会节省点空间，不知道是不是面试官想要的
当然LZ的方法也很好

elevenz 发表于 2016-2-19 13:42
https://en.wikipedia.org/wiki/Suffix_array
不知道能不能说清楚额。。。比如给的string是“asda”，先生 ...

受教了，多谢大神

neostar2008 发表于 2016-2-19 12:34
第一题不用Set存，用Trie存应该会节省点空间，不知道是不是面试官想要的
当然LZ的方法也很好

我总感觉用Trie的话，好说但下手写代码好难啊，估计在优化乱扯的时候提到

他家饭盒··反正我只吃了fruit cup，那个taco简直不能忍，纯素没有肉

第一题不明白楼主什么意思，能麻烦加个例子，方便大家理解吗？谢谢！