Snapchat- 小车通过雷达区

https://warmland.gitbooks.io/algorithm/content/interview/snapchat-_xiao_che_tong_guo_lei_da_qu.html

题目描述： 有一条路，路两边可以想象为 y = 0 和y = 1两条直线。现在给你list of radar，每个雷达为(横坐标，纵坐标，辐射半径)。问你一辆车能否通过这条路。

分析& 代码

static class Radar {
    double x;
    double y;
    double r;
    public Radar(double x, double y, double r) {
        this.x = x;
        this.y = y;
        this.r = r;
    }
}

class Area {
    List<Radar> radars;
    double upperbound;
    double lowerbound;

    public Area() {
        radars = new ArrayList<Radar>();
        upperbound = 0;
        lowerbound = 1;
    }

    private boolean canMerge(Radar r1, Radar r2) {
        return Math.pow(r1.r + r2.r, 2) >= Math.pow(r1.x - r2.x, 2) + Math.pow(r1.y - r2.y, 2);
    }

    private boolean merge(Radar r) {
        for(Radar radar: radars) {
            if(canMerge(r, radar)) {
                upperbound = Math.max(upperbound, r.x + r.r);
                lowerbound = Math.min(lowerbound, r.y - r.r);
                radars.add(r);
                return true;
            }
        }
        return false;
    }

    private boolean cannotPass() {
        return upperbound >= 1 && lowerbound <= 0;
    }
}


public boolean canCarPass(List<Radar> radars) {
    List<Area> area = new ArrayList<Area>();
    for(Radar radar: radars) {
        boolean merged = false;
        for(Area a: area) {
            merged = a.merge(radar);
            if(merged) {
                break;
            }
        }
        if(!merged) {
            Area a = new Area();
            a.radars.add(radar);
            area.add(a);
        }
    }
    for(Area a : area) {
        if(a.cannotPass()) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    RadarDetect rd = new RadarDetect();
    //List<Radar> radars = Arrays.asList(new Radar(1, 0.5, 0.49), new Radar(3, 1.5, 1), new Radar(3, 0.4, 0.3));
    List<Radar> radars = Arrays.asList(new Radar(1, 0, 1.5), new Radar(3, 1, 1.5));
    System.out.println(rd.canCarPass(radars));
}

Implement HashMap using BST

https://warmland.gitbooks.io/algorithm/content/interview/implement_hashmap_using_bst.html

把核心的逻辑都放在Node里面

所以Node的代码是：

public class MapNode<K extends Comparable<K>, V> {
    private K key;
    private V value;
    private MapNode<K, V> left;
    private MapNode<K, V> right;

    public MapNode(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public V put(K key, V value) {
        if(this.key.compareTo(key) == 0) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        } else if(this.key.compareTo(key) < 0) {
            if(right == null) {
                right = new MapNode(key, value);
                return null;
            } else {
                return right.put(key, value);
            }
        } else {
            if(left == null) {
                left = new MapNode(key, value);
                return null;
            } else {
                return left.put(key, value);
            }
        }
    }

    public V get(K key) {
        if(this.key.compareTo(key) == 0) {
            return this.value;
        } else if(this.key.compareTo(key) < 0) {
            return right == null? null: right.get(key);
        } else {
            return left == null? null: left.get(key);
        }
    }
}

Map部分的代码是：

public class ImplementHashmapUsingBST<K extends Comparable<K>, V> {
    MapNode<K, V> root;
    int size;

    public ImplementHashmapUsingBST() {
        size = 0;
    }

    public V get(K key) {
        if(root == null) {
            return null;
        }
        return root.get(key);
    }

    public V put(K key, V value) {
        if(root == null){
            root = new MapNode(key, value);
            return null;
        } else {
            V oldValue = root.put(key, value);
            if(oldValue == null) {
                size++;
                return null;
            }
            return oldValue;
        }
    }

    public static void main(String[] args) {
        ImplementHashmapUsingBST<String, String> sample = new ImplementHashmapUsingBST();
        sample.put("Apple", "Fruit");
        sample.put("Pork", "Meat");
        System.out.println(sample.get("Apple"));
    }

}

https://stackoverflow.com/questions/22996474/why-implement-a-hashtable-with-a-binary-search-tree

Snap_Diff

https://warmland.gitbooks.io/algorithm/content/interview/snapdiff.html

题意大概是实现linux里面的diff的功能，给你两个文件，如果f1比f2多的，就打印“-someContent”, 如果是f2比f1多的，就打印“+someContent”

思路大概就是

对f2简历一个map，来记录每个line的

对于f1里面每一个line
  如果map里面不包含这个line
     打印"-line"
  否则
     把这条记录的计数减一
     如果减完是0
       就删除

如果map还有剩的，就打印出来“+line”

代码：

public void printDiff(List<String> f1, List<String> f2) {
    Map<String, Integer> counter = new HashMap<>();
    for(String line: f2) {
        if(counter.containsKey(line)) {
            counter.put(line, counter.get(line) + 1);
        } else {
            counter.put(line, 1);
        }
    }
    for(String line: f1) {
        if(!counter.containsKey(line)) {
            System.out.println("-" + line);
        } else {
            if(counter.get(line) == 0) {
                counter.remove(line);
            } else {
                counter.put(line, counter.get(line) - 1);
            }
        }
    }
    for(Map.Entry<String, Integer> entry: counter.entrySet()) {
        for(int i = 0; i < entry.getValue(); i++) {
            System.out.println("+" + entry.getKey());
        }
    }
}

public static void main(String[] args) {
    SnapDiff sample = new SnapDiff();
    List<String> f1 = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E"));
    List<String> f2 = new ArrayList<>(Arrays.asList("A", "B", "D"));
    sample.printDiff(f1, f2);
}

Snapchat- Group Record using Union-find

Related: Group Contacts | tech::interview
https://warmland.gitbooks.io/algorithm/content/interview/snapchat-_group_record_using_union-find.html

// 题目是手机上的通讯录，每条记录只有(name, number)这种pair,有些记录名字重复，有些记录号码重复，让我返回一个list>， // 将所有记录按人分组。比较tricky的点在于(ABC,123), (ABC, 456), (BCD, 456) // 三条记录，第一条和第三条也属于同一个人。要求时间复杂度尽量小

uf算法我是明白的，但是我想的时候的困惑在于

1.ufMap里面存放什么，是map还是map还是别的什么

2.在group的时候，既要对name进行uf group又要对number进行group怎么操作

解决方案是这样的（既union-find部分的思路）

1.首先ufMap里面存<Record, Record>，初始化把所有entry过一遍，都存入，使它最初的root节点都是它自己

2. find部分。

　　1）首先找到这个record的root节点

　　2）然后把从这个record开始直到root节点所有的节点的root节点都更新成root

　　3）返回root

3. union部分，没什么特别的

　　1）对record1,record2找到root1,root2

　　2）如果root1 != root2，那么就设置其中一个是另外一个的root节点

完成union-find的部分，整个算法的整体思路是。

1.建立一个nameMap<nameString, Record>和一个numMap<number, Record>

2.对于所有entry走一遍，

　　1) 如果nameMap里面已经存在当前entry的name，那么就说明要union；否则就把[nameString, entry]加入map

　　2）如果numMap里面已经存在当前entry的number，那么就说明要union；否则就把[number, entry]加入map
3. 所以此刻ufMap里面已经有已经对于name和number group之后的结果，现在就需要把结果保存下来。

　　所以可以先建一个Map<String, List<Record>>整理好，再根据这个map得到List<List<Record>>

实际代码如下：

public class GroupRecord {
    static class Record {
        String name;
        int number;
        public Record(String name, int number) {
            this.name = name;
            this.number = number;
        }

        public String toString() {
            return "(" + name + "," + number + ")";
        }
    }

    public static List<List<Record>> group(List<Record> records) {
        Map<Record, Record> ufMap = new HashMap<Record, Record>();
        Map<String, Record> nameMap = new HashMap<>();
        Map<Integer, Record> numMap = new HashMap<>();
        for(Record entry: records) {
            ufMap.put(entry, entry);
        }
        for(Record entry: records) {
            if(nameMap.containsKey(entry.name)) {
                union(ufMap, entry, nameMap.get(entry.name));
            } else {
                nameMap.put(entry.name, entry);
            }
            if(numMap.containsKey(entry.number)) {
                union(ufMap, entry, numMap.get(entry.number));
            } else {
                numMap.put(entry.number, entry);
            }
        }
        Map<String, List<Record>> groupMap = new HashMap<>();
        for(Record entry: records) {
            Record root = find(ufMap, entry);
            List<Record> list = groupMap.get(root.name);
            if(list == null) {
                list = new ArrayList<Record>();
            }
            list.add(entry);
            groupMap.put(root.name, list);
        }
        List<List<Record>> res = new ArrayList<List<Record>>(groupMap.values());
        return res;
    }

    private static Record find(Map<Record, Record> ufMap, Record record) {
        Record root = record;
        while(!ufMap.get(root).equals(root)) {
            root = ufMap.get(root);
        }
        Record cur = record;
        while(!cur.equals(root)) {
            ufMap.put(record, root);
            cur = ufMap.get(cur);
        }
        return root;
    }

    private static void union(Map<Record, Record> ufMap, Record r1, Record r2) {
        Record root1 = find(ufMap, r1);
        Record root2 = find(ufMap, r2);
        if(!root1.equals(root2)) {
            ufMap.put(root1, root2);
        }
    }

    public static void main(String[] args) {
        List<List<Record>> res = new ArrayList<List<Record>>();
        ArrayList<Record> records = new ArrayList<>();
        records.add(new Record("ABC",123));
        records.add(new Record("ABC",456));
        records.add(new Record("BCD",456));

        records.add(new Record("AD",342));
        records.add(new Record("AddD",11));
        records.add(new Record("DFX",34));
        records.add(new Record("AD",34));
        records.add(new Record("AD",11));

        res = group(records);
        System.out.println(res);
    }
}

Snapchat - ColorSum

https://warmland.gitbooks.io/algorithm/content/interview/snapchat_-_colorsum.html

给一些RGB的点，比如(86, 5, 211), (128, 99, 5), 再一个target点，看使用这些给的点能不能叠加得到target，每个点只能用一次

就是最基本的backtracking

public class ColorSum {
    static class Color {
        int r;
        int g;
        int b;
        public Color(int r, int g, int b) {
            this.r = r;
            this.g = g;
            this.b = b;
        }

        public void add(Color color) {
            this.r = (this.r + color.r > 255)? 255: (this.r + color.r);
            this.g = (this.g + color.g > 255)? 255: (this.g + color.g);
            this.b = (this.b + color.b > 255)? 255: (this.b + color.b);
        }

        public boolean substract(Color color) {
            if(color.r > this.r || color.g > this.g || color.b > this.b) {
                return false;
            }
            this.r = this.r - color.r;
            this.g = this.g - color.g;
            this.b = this.b - color.b;
            return true;
        }

        public boolean equalsZero() {
            return r == 0 && g == 0 && b == 0;
        }

        public String toString() {
            return "(" + r + ", " + g + ", " + b + ")";
        }
    }

    public boolean canSum(List<Color> colors, Color target) {
        if(colors == null || colors.size() == 0 || target == null) {
            return false;
        }
        return helper(colors, 0, target);
    }

    private boolean helper(List<Color> colors, int index, Color target) {
        if(target.equalsZero()) {
            return true;
        }
        for(int i = index; i < colors.size(); i++) {
            if(target.substract(colors.get(i))) {
                if(helper(colors, i + 1, target)) {
                    return true;
                }
                target.add(colors.get(i));
            }
        }
        return false;
    }

    public static void main(String[] args) {
        ColorSum sample = new ColorSum();
        List<Color> colors = new ArrayList<>();
        colors.add(new Color(86, 5, 211));
        colors.add(new Color(128, 99, 5));
        colors.add(new Color(92, 25, 6));
        colors.add(new Color(16, 45, 4));
        Color target = new Color(236, 169, 15);
        System.out.println(sample.canSum(colors, target));
    }
}

Snapchat - IPFilter

https://warmland.gitbooks.io/algorithm/content/interview/snapchat_-_ipfilter.html

首先说一下IP，二进制表示的IP有32位，一般8位一分隔，转换成十进制，就是0.0.0.0 ~ 255.255.255.255

给你一些IP的规则，比如"7.7.7.7/8","123.2.67.3/8"，这个代表着比如7.7.7.7所对应的32位的表示，00000111*4，8表示取前8位，把所有以00000111开头的ip地址都看成一组，如果在这组内就被filter掉。

所以思路是：

1. 建立ipRule的trie，提供搜索的功能
2. 搜索

分析& 代码

public List<String> filter(List<String> rules, List<String> IPs) {
    if(rules == null || rules.size() == 0 || IPs == null || IPs.size() == 0) {
        return IPs;
    }
    Trie ruleTrie = new Trie();
    prepareRule(ruleTrie, rules);
    List<String> res = new ArrayList<String>();
    filterIPs(IPs, ruleTrie, res);
    return res;
}


private void prepareRule(Trie ruleTrie, List<String> rules) {
    for(String rule: rules) {
        StringBuilder sb = new StringBuilder();
        String[] parts = rule.split("/");
        int bits = Integer.parseInt(parts[1]);
        String[] ipBlocks = parts[0].split("\\.");
        for(String block: ipBlocks) {
            String blockStr = Integer.toBinaryString(Integer.parseInt(block));
            int leadingZeros = 8 - blockStr.length();
            while(leadingZeros-- > 0) {
                sb.append("0");
            }
            sb.append(blockStr);
        }
        String curRule = sb.toString().substring(0, bits);
        ruleTrie.insert(curRule);
    }
}

private void filterIPs(List<String> IPs, Trie ruleTrie, List<String> res) {
    for(String ip: IPs) {
        StringBuilder sb = new StringBuilder();
        String[] ipBlocks = ip.split("\\.");
        for(String block: ipBlocks) {
            String blockStr = Integer.toBinaryString(Integer.parseInt(block));
            int leadingZeros = 8 - blockStr.length();
            while(leadingZeros-- > 0) {
                sb.append("0");
            }
            sb.append(blockStr);
        }
        String binaryIP = sb.toString();
        if(!ruleTrie.startsWith(binaryIP)) {
            res.add(ip);
        }
    }
}


class TrieNode {
    char c;
    boolean isLeaf;
    TrieNode[] children;

    public TrieNode() {
        children = new TrieNode[2];
        isLeaf = false;
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String s) {
        if(s == null || s.length() == 0) {
            return;
        }
        TrieNode cur = root;
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int index = c - '0';
            if(cur.children[index] == null) {
                cur.children[index] = new TrieNode();
            }
            cur.children[index].c = c;
            cur = cur.children[index];
        }
        cur.isLeaf = true;
    }

    public boolean startsWith(String s) {
        TrieNode cur = root;
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int index = c - '0';
            if(cur.isLeaf == true) {
                return true;
            }
            if(cur.children[index] == null) {
                return false;
            }
            cur = cur.children[index];
        }
        return cur.isLeaf;
    }
}

public static void main(String[] args) {
    IPFilter sample = new IPFilter();
    List<String> rules = new ArrayList<String>(Arrays.asList("7.7.7.7/8","123.2.67.3/8"));
    List<String> IPs = new ArrayList<String>(Arrays.asList("23.2.4.1","7.3.4.1","5.1.2.3","123.2.67.3"));
    List<String> res = sample.filter(rules, IPs);
    System.out.println(res);
}

https://en.wikipedia.org/wiki/Subnetwork

Snapchat - 向左下角打印2D矩阵

https://warmland.gitbooks.io/algorithm/content/interview/snapchat_-_xiang_zuo_xia_jiao_da_yin_2d_ju_zhen.html

题目是这样的，给一个2d矩阵，向左下角打印矩阵，比如

1，2，3，4

5，6，7，8

9，10，11，12

结果是{{1}，{2，5}，{3，6，9}，{4，7，10}，{8，11}，{12}}

+

所以解题的重点是，结果里面的每一组，它们的横坐标+纵坐标是相等的，然后最大的可能是col+row-2

public List<List<Integer>> printMatrix(int[][] board) {
    int height = board.length;
    int width = board[0].length;
    List<List<Integer>> res = new ArrayList<>();
    if (width == 0 || height == 0) {
        return res;
    }
    int diagonal = width + height - 2;
    for (int sum = 0; sum <= diagonal; sum++) {
        List<Integer> cur = new ArrayList<>();
        for (int y = 0; y <= sum; y++) {
            int x = sum - y;
            if (y < height && x < width) {
                //cur.add(y * width + x + 1);
                cur.add(board[y][x]);
            }
        }
        res.add(cur);
    }
    return res;
}

Snapchat - 2D矩阵的combination

https://warmland.gitbooks.io/algorithm/content/interview/snapchat_-_2dju_zhen_de_combination.html

给一个整数n和一个整数m，n表示正方形边长，正方形初始值全为0。 比如 n=3,代表初始是这样的正方形：

000
000
000

若m=2，代表将其中的2个元素翻转为1，打印出可能得到的所有正方形： 比如

011
000
000

或

000
110
000

。。。

我用backtracking做的，但是时间复杂度没有答好，估计是跪这里了。 follow up是 生成的正方形中， 011 000 000 和 000 000 011 这种对称的正方形视为重复的，如何对之前的结果进行去重。

其实就是一个combination

public List<List<String>> generate(int n, int m) {
    List<List<String>> res = new ArrayList<>();
    char[][] board = new char[n][n];
    for(int i = 0; i < n; i++) {
        Arrays.fill(board[i], '0');
    }
    helper(res, board, n, m, 0, 0);
    return res;
}

private void helper(List<List<String>> res, char[][] board, int n, int m, int cnt, int index) {
    if(cnt == m) {
        List<String> curRes = new ArrayList<String>();
        for(int i = 0; i < n; i++) {
            curRes.add(new String(board[i]));
        }
        res.add(curRes);
        return;
    }
    for(int i = index; i < n * n; i++) {
        int row = i / n;
        int col = i % n;
        board[row][col] = '1';
        helper(res, board, n, m, cnt + 1, i + 1);
        board[row][col] = '0';
    }
}

检查重复，用的是笨方法，把res设成Set。每次往set里面添加的时候翻转一下然后再添加

if(cnt == m) {
    List<String> cur = Arrays.stream(board).map(String::valueOf).collect(Collectors.toList());
    List<String> reverse = new LinkedList<>(cur);
    Collections.reverse(reverse);
    if (!res.contains(cur) && !res.contains(reverse)) {
        res.add(cur);
    }
    return;
}

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=206115&page=2
横着或者竖着对称，没有旋转，就是生成的时候来判重
复杂度是 n^2 choose m. 楼主你是怎么处理重复的HashSet吗

Snap Interview Misc

1。meeting room的题目，
给一串meeting room 时间，问是否能够schedule，
【1，2】， 【3，4】，【5，6】

2. followup 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
给一串meeting room 时间，需要多少个meeting room

http://www.1point3acres.com/bbs/thread-282977-1-1.html

题目是离口73. 先让我用两个矩阵来写。然后说time space complexity。然后优化成了in－space。 秒杀。

问楼主有没有用过snapchat，楼主我工作都10年了，没有其他盆友用它啊，所以我说没有ative用过。 整个过程感觉小哥都很冷淡，然后也实在没有什么可以聊的了。一个小时的面提前了大概10分钟。

今天居然被拒了。实在不理解

如果跑出来的程序有bug，肯定会被拒

第一题很简单一bug自己改了，第二题没bug，面试官还是国人，还是挂了。唯一可能让他觉得不爽的可能是，中间第一题写完了后我的手机没电了，然后过了一会才连上

http://www.1point3acres.com/bbs/thread-190847-1-1.html

电面： LeetCode原题 Jump Game 1和2 onsite: 第一轮是个外国小哥，算术式Evaluation, 要求支持+-*/()。 第二轮是个国人大哥，一个2D平面有一堆雷达（雷达有x, y坐标，以及能探测到的范围r半径） 然后又一辆小车要从y=0和y=1的区间里面通过并且不能被雷达探测到。让写一个function看小车能不能通过。 雷达那题是这样的：一个tunnel， 范围是[0，1]中间有各种尺寸的雷达，(x, y, r)，一个小车只有不被雷达监测的地方可以通过，问给定一个List<Radar>判断小车能不能过去。这轮最成功，一点点和大哥分析出需求，做出来的。最后做完题，边走还边和大哥聊天，指出了在snapchat使用中有个小bug，大哥表示会反映一下 第三轮是个印度小哥，Game of Life原题 第四轮是个外国大叔，基本上纯behavior，最后问了一个很简单的题目，就是Leetcode Unique Path ii. 他家聊天会聊很久，大家要注意点聊天技巧。聊得开心就好

http://www.1point3acres.com/bbs/thread-286096-1-1.html

seattle电面，已跪。遇到了一道题，在提示下提出了一种错误的解法。上来分享一下。题目是给出一个数组，输出符合a^2+b^2=c^2 的(a,b,c)组合。 brute force很简单，三个for循环, O(n^3). 要求优化，提出了用3sum的想法去解，然后让写code。写完了之后，讨论了一些edge case, 然后挂了。 问题在于，3sum 的思想不适用于这里， 这个问题是a^2+b^2 －c^2 ＝0, 而不是a^2+b^2 ＋c^2 ＝0。 譬如（x, y, z, t) 选中 x, 然后 x^2 + y^2 < t^2, 这时既可以选择x^2 +z^2 和 t^2比较，也可以选择x^2 + y^2 和 z^2比较。假如是3sum, x + y +t <0, 只能是选择x + z+t 进行判断。 所以这个解法是错的。不知道大家有什么想法。但很显然，面试官没有发现这个错，否则在写之前就应该否定

       public static List<List<Integer>> getCompleteSquares(int[] nums) {
                List<List<Integer>> res = new ArrayList<>();
                if(nums == null || nums.length < 3) return res;
. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
                Arrays.sort(nums);
                //[1,2,3,4,5,6,7,8,9,10];
                //a^ + b^ = c^. visit 1point3acres.com for more.
                for(int i = nums.length - 1; i >= 2; i--) {
                        if(i != nums.length - 1 && nums[i] == nums[i+1]) continue;
                        int left = 0, right = i - 1;
                        while(left < right) {
                                int sum = nums[left] * nums[left] + nums[right] * nums[right];
                                if(sum < nums[i] * nums[i]) {
                                        left++;. 鍥磋鎴戜滑@1point 3 acres
                                }else if(sum > nums[i] * nums[i]) {
                                        right--;
                                }else{
                                        List<Integer> path = new ArrayList<>();. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
                                        path.add(nums[left]);. Waral 鍗氬鏈夋洿澶氭枃绔�,
                                        path.add(nums[right]);
                                        path.add(nums[i]);
                                        res.add(path);-google 1point3acres
                                        left++;
                                        right--;
                                        while(nums[left] == nums[left-1]) left++;
                                        while(nums[right] == nums[right+1]) right--;
                                }
                        }
                }
-google 1point3acres
                return res;
        }
. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
http://www.1point3acres.com/bbs/thread-168446-1-1.html

29号snapchat电面 第一题 给一个矩阵 ，对角线打印数字 比如 1  2  34  5 6  7  89  10 1112 13 14  15 输出 1 26 37 11 .1point3acres缃� 48 12 59 13 1014

直接将元素matrix(i, j), Then按顺序存到第i+j行     */     public static List<List<Integer>> printMatrix(int[][] nums) {         List<List<Integer>> res = new ArrayList<>();         if (nums == null || nums.length == 0)             return res;         int rows = nums.length + nums[0].length - 1;         for (int i = 0; i < rows; i++)             res.add(new ArrayList<>());         for (int i = 0; i < nums.length; i++) {. 1point3acres.com/bbs             for (int j = 0; j < nums[0].length; j++) {                 res.get(i + j).add(nums[i][j]);. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷             }. more info on 1point3acres.com         }         return res;     }

两个string一长T 一短S

find anagramsubstring of S in T in linear time

有史以来最简单店面。。。。。1。 如何给一个字符串去重后按字母表顺序排列输出。
2.   按反字母表顺序排列
http://www.1point3acres.com/bbs/thread-213778-1-1.html
之后写的很顺，改了几个syntax error， 跑了一下一遍就过了。 我当时还在庆幸自己运气好没漏写什么步骤。.1point3acres缃�
之后又问了follow up怎么提速， 我说有对称，小哥很满意，然后就结束了，还说让我等待next step。结果今天早上收到拒信，还不给feeback。我哪里可能有问题么？

刚跟recuriter 反馈过，拿到了加面机会。之前被弄错面的是nyc 新office，bar非常高，culturefit那块挂了。加面la

问了很多当前的项目问题，他们比较偏前端，javascript 算法题问了word ladder的变体，如果能发现就返回真，不能发现就返回假.1point3acres缃� 例子：{“abc”,"acd","abd","acc"}. From 1point 3acres bbs from: abc to: acc 然后又问了一些domain knowledge，bfs，dfs。。。

find all amicable numbers

https://warmland.gitbooks.io/algorithm/content/interview/snapchat_-_amicable_pair.html

Amicable number（相亲数）定义：

相亲数（Amicable Pair），又称亲和数、友爱数、友好数，指两个正整数中，彼此的全部约数之和（本身除外）与另一方相等。

例如220与284：

220的全部约数（除掉本身）相加是：1+2+4+5+10+11+20+22+44+55+110=284 284的全部约数（除掉本身）相加的和是：1+2+4+71+142=220

相关题目1：给定整数n，找到小于n的所有amicable number的和

相关知识：

　　1、比如36 = 2^2 + 3 ^2。那么它有两个2和三个3是它的质因数，它有（2+1）*（2+1）= 9个约数，因为可以选0个2，1个2或者3个2，对于3同理。

　　2. 还有一点：如果factorSum表示这个数所有约数的和，那么 b = factorSum(a), c = factorSum(b), 如果c == a 并且 a != b，那么a和b就是相亲对

所以这题的算法是，找到所有小于根号n的prime number。

对于所有小于n的整数：

　　res = 0;

　　sum = factorSum(i);

　　if(factorSum(sum) == i && i != sum) {

　　　　res += sum;

　　}

本道题目：给定整数n，求出所有小于n的相亲数

思路：

求出从1-n所有数的factorSum

for(int i = 2; i <= n / 2; i++) {
    for(int j = i * 2; j <= n; j += i) {
        factorSum[j] += i;
    }
}

道理是，比如n = 20 i = 2，那么4，6，8，10，...，20位置上的sum都+2

i = 3，那么6,9,12,15,18位置上的都+3

时间复杂度O(nlogn). 外层是O(n)内层是1/2+1/3+...+1/n ~ logn

然后统计

public class AmicableNumber {
    public List<List<Integer>> findAmicablePair(int n) {
        List<List<Integer>> res = new ArrayList<>();
        if(n <= 2) {
            return res;
        }
        int[] factorSum = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            factorSum[i] = 1;
        }
        for(int i = 2; i <= n / 2; i++) {
            for(int j = i * 2; j <= n; j += i) {
                factorSum[j] += i;
            }
        }
        //System.out.println(factorSum[10000] + " " + factorSum[23000] );
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 2; i <= n; i++) {
            if(map.containsKey(i) && factorSum[i] == map.get(i)) {
                ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(factorSum[i], i));
                res.add(list);
            } else {
                map.put(factorSum[i], i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        //[[220, 284], [1184, 1210], [2620, 2924], [5020, 5564], [6232, 6368], 
        //[10744, 10856], [12285, 14595], [17296, 18416], [66928, 66992]]
        AmicableNumber sample = new AmicableNumber();
        System.out.println(sample.findAmicablePair(66992));
    }
}

http://coderchen.blogspot.com/2015/11/find-all-amicable-numbers.html
输入一个正整数，找出所有小于这个数的amicable pairs。讨论了一下时间空间复杂度以及如何tradeoff，最后写了时间复杂度O(n^1.5)，空间复杂度O(n)的算法。

public List<int[]> findAmicable(int num) {

List<int[]> res = new ArrayList<>();

for (int i = 1; i <= num; i++) {

int factorSum = getFactorSum(i);

if (i < factorSum && factorSum <= num) {

int factorSum2 = getFactorSum(factorSum);

if (i == factorSum2) {

res.add(new int[] { i, factorSum });

}

}

}

return res;

}

private int getFactorSum(int num) {

int res = 1;

for (int i = 2; i <= Math.sqrt(num); i++) {

if (num % i == 0) {

res += i;

res += num / i;

}

}

return res;

}

public static void main(String args[]) {

Solution s = new Solution();

List<int[]> res = s.findAmicable(3000);

for (int[] arr : res) {

System.out.println(arr[0] + " " + arr[1]);

}

}

https://en.wikipedia.org/wiki/Amicable_numbers
Amicable numbers are two different numbers so related that the sum of the proper divisors of each is equal to the other number. 

The smallest pair of amicable numbers is (220, 284). They are amicable because the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, of which the sum is 284; and the proper divisors of 284 are 1, 2, 4, 71 and 142, of which the sum is 220.