Friday, June 10, 2016

Google Interview Misc Part 8


http://www.1point3acres.com/bbs/thread-201356-1-1.html
给一批人, 这些人每人都花了一笔钱,
让算, 谁给谁多少钱, 能让所有人都达到平均数


public void calculate(int[] nums) {
                int sum = 0;
                for (int i : nums) {
                        sum += i;
                }
                double avg = sum * 1.0 / nums.length;
                double[] temp = new double[nums.length];
                for (int i = 0; i < nums.length; i++) {
                        temp[i] = avg - nums[i];
                }
                int cur1 = 0; //pos
                int cur2 = 0; //neg
                while (cur1 < nums.length) {
                        while (cur1 < nums.length && temp[cur1] <= 0) {
                                cur1++;
                        }
                        while (cur2 < nums.length && temp[cur2] >= 0) {
                                cur2++;
                        }
                        if (cur1 < nums.length && cur2 < nums.length) {
                                double min = Math.min(temp[cur1], -temp[cur2]);. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
                                System.out.println("" + cur2 + " gives " + (min) + " to " + cur1);
                                temp[cur1] -= min;
                                temp[cur2] += min;
                        }
                }
        }
http://www.1point3acres.com/bbs/thread-199194-1-1.html
给定一个句子, 和若干个搜索词, 求包含所有搜索词的最短句子长度.
Badmin was able to beat Bill at billiards, but Bill always beat Badmin badly at badminton.

给定搜索词: Query = [Badmin, Bill, beat]
返回 4. 因为子句(Bill always beat Badmin)是包含Query中所有单词的最短子句.

提示: 可以将子句看成倒排的形式如:

"Badmin" = [0, 12]
"Bill" = [5, 9]
"beat" = [4, 11]
其中倒排中的每个index是递增的, 可以利用这点剪枝(?)

这是我面试遇到的问题, 我只想到了暴力解, 就是用dfs枚举所有. 希望大家提供更好的解

这不和minimum window substring一样吗
http://www.1point3acres.com/bbs/thread-197372-1-1.html
1. Given a binary tree, find if there are two subtrees that are the same. (i.e. the tree structures are the same; the values on all corresponding nodes are the same). You should find the largest subtree and don’t use brute force.

我只想到 brute-force,或是用 Map 存整個第一棵樹再掃第二顆做比較,想請問有沒有更好的想法?
把Tree用DFS做serialization , 就变成了找substring的问题了,可以用kmp或者直接用内置方法做吧
参考pre-order遍历序列化一棵二叉树。然后build这个字符串的失败函数。假设某字符的失败函数值为最大,且这个子串不以空开头,即为最大重复子树

假设identical的子树share一个group id. NULL的group id是0.其它子树的group id按照group在后序遍历中第一次出现的时间顺序决定。
这样我们可以一边后序遍历子树,一边建两个hashmap:
(root value, group id of left, group id of right) -> group id of root
group id -> subtrees of this group
这样我们做一遍后序遍历同时维护层数最高、subtree数量>=2的group id就行了。

这个其实跟用整棵子树的serialization作为key做法差不多,只是对key作了压缩。
group id就是一个数字,对应一棵unique的子树。
比如一棵3个结点的树,根结点是10, 两个node是20, 20.
那么group id->node的hash table存的是
0: NULL
1: leftnode, right node
2: root node

(root val, left id, right id)->root id的hashtable存的是
(20, 0, 0) : 1
(10, 1, 1) : 2

所以返回group id 1下面的两个node.

2. Input a matrix, where every number is greater or equal to the numbers on its right and bottom. Output a sorted array

http://www.1point3acres.com/bbs/thread-190439-1-1.html
1. 友善印度小哥。说是考察一群学生的出勤率,如果连续3天来晚(L)就记作差(F),或者任意两天旷课(A)也记作F。成为F就一直是F了。考察30天后,有多少种F的排列组合。
楼主一开始以为是dp,像 decode ways 一样的用两个variables记录之前两天的结果就好了。然后就陷入泥沼了。小哥提示用 automata 解释。画出图来后楼主基本已经蒙了。呵呵,大家可以自己画一画。每一天可以有7种states, 楼主真的呵呵了。自从 valid number 之后就再没用过automata了。. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴

第一个题可以用2个automata的乘积么 The Product Construction for Automata
第一题就是HMM啊。做ML应该都知道。
恩 第一题仔细想想 还是dp的问题 其实也是一个HMM 每个时刻8个状态. 前一个天8个状态合起来求后一天的. 他提示automata 感觉反而能让人弄迷糊 实在是邪恶
int nPermute(int days){
    // Automata
    //    L      L      L
    // I --> L1 --> L2 --> F
    //    A      A
    // I --> A1 --> F
    // state I, I
    int[] dp1 = new int[2];
    // I, A1
    int[] dp2 = new int[2];
    // L1, I
    int[] dp3 = new int[2];
    // L1, A1
    int[] dp4 = new int[2];
    // L2, I
    int[] dp5 = new int[2];
    // L2, A1
    int[] dp6 = new int[2];
    // F. 
    int[] dp7 = new int[2];
    dp1[1] = 1; 
    dp2[1] = 1;
    dp3[1] = 1; 
    dp4[1] = 0; 
    dp5[1] = 1;
    dp6[1] = 0; 
    dp7[1] = 0; 
    for(int i = 1; i <= 30; ++i){
        int iLast = (i+1) % 2;
        int iNow = i % 2;
        // it is infact one HMM transition. 
        dp1[iNow] = dp1[iLast] + dp3[iLast] + dp5[ilast];
        dp2[iNow] = dp1[iLast]; 
        // ...
        // so on and so forth.
    }. 1point3acres.com/bbs
    return dp1[30%2] + ... dp7[30%2]; 
}
我只知道简单做法:
就是dfs 每一天三种可能 (这个要和你confirm)就是L   A  或者 good
然后递归30天后检查这种排法是否F,更新sum变量
可以在dfs过程中检查是否F,然后pass onto最后的检查. 鍥

2. 冷面沉默大叔。第一题two sum smaller。第二题 coin change。第三题 coin change 打出所有case。最后一题 shuffle tree。 答得很顺。

3. 披头金发小伙。先是个sql的问题,选每个周一的前几个data什么balabala的。小哥表达很不清楚。楼主乱答了一通。小伙啥也不说。第二题类似 one edit distance,要比较每种方法的好坏,反复说有木有除了sort,hashmap以外更好的。
. visit 1point3acres.com for more.
4. 木纳白人胖哥。Number of Islands II. 楼主用union-find默写完了。胖哥没多说,只是记。楼主有几个typo也帮忙提示了。然后问如何从union-find的tree里remove node。——。——. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴

5. 和蔼中国大姐。一道system design。 楼主把能记住的部分要求写一下:
做一个cinema的卖票web application。有很多users,在client side。server只有一个。要求�1point3acres璁哄潧
1. 每一个user一次可以看到10个空位。不同的user在同一时间不能看到相同的空位。
2. 如果这个user不满意这10个座位,可以refresh出另外10个,把当前的10个覆盖。
3. 每个user只能buy一个座,这个座必须是她看过的(包括之前覆盖过的和当前的10个)。买座位是通过输入座位号。
4. 买了一个座之后,其余user的当前看到的10个位置如果饱含这个座,要去掉,给个新的。
5. 如果有user要买没看过的座,视为malicious behavior,要制止。
6. user决定refresh或者buy的时间只有2s。


其余还有2个policy楼主记不清了。大姐问得很细,笑里藏刀地,包括用什么data structure,放在client还是server side,performance怎么办等等。哎,我估计architect才能答出来这题。

几天接到hr电话说挂在第三轮了的SQL了,因为楼主在最开始的self-estimation的说自己的SQL 是 6/10。我擦你呀啊!楼主的确是有很多SQL经验啊,但是每个SQL的API都不一样吧。。。况且楼主都是用的打包好的API啊。6分很高吗?多高是高啊。。



No comments:

Post a Comment

Labels

GeeksforGeeks (959) Algorithm (811) LeetCode (637) to-do (597) Review (339) Classic Algorithm (334) Classic Interview (299) Dynamic Programming (263) Google Interview (233) LeetCode - Review (228) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (118) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) List (58) Binary Tree (56) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Interval (38) Jobdu (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Array (33) Trie (33) prismoskills (33) Segment Tree (32) Space Optimization (32) Union-Find (32) Backtracking (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (26) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Queue (22) DFS + Review (21) Hash (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Bisection Method (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Divide and Conquer (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) System Design (8) Tech-Queries (8) Time Complexity (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Suffix Tree (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Kadane’s Algorithm (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts