Google interview questions #9


https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=463515

follow up是如果你是A,就是第一个选node的人,你选择哪个node可以赢。follow up只说了想法没有写code,优化到O(n)
第二轮是典型背包问题,给一些task,以及每个task的priority和需要用cpu的个数,假设有10个cpu,
求问能达到的最大priority的和,follow up是返回这个combination

第三轮是leetcode扒以吴,我用的bfs,问了下怎么优化hashmap少用一点空间,没想出来

第四轮是给两个string,source和target,求问最少需要repeat source几次才可以得到target,repeat完的string可以删除任意character。先是暴力解然后优化的。
报个timeline,9月中旬内推,9.25收到OA,10月底收到onsite,11.19面,12.6通知过hc
四轮都是华人面孔
第一轮是一个国人妹子,一上来愉快地闲聊了一会,然后到时间开始coding。有一个game是在binary tree里occupy尽可能多的node算是胜利,
有玩家A和B,除了第一次每一次只能选择和自己选过的node相连的node,假设已知A选择的node,求问B应该选择哪个node才能occupy最多的node。

想问一下第一题就是算出左子树,右子树,以及整个树的节点-左-右=父节点的节点树,最后选取最大的吗
请问一下第二题DP以后怎么找最佳方案的combination呢?
我没想出来如何从DP的三维数组中找到这个path。只有再次DFS了dp在计算的时候同时要记录你的最佳值的来源。这样最后可以从dp[item][cpu]倒着推回去。


https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=491317

  • 一个坐标系,上面有一堆的点point(x, y), 选出其中的两个点,这两个点连成的线,可以把坐标系里的点分成两半,两边的点的个数相同。这位大哥的口音太重了,我跟他交流的过程中完全听不太懂。先提出了暴力解法,最后再提示下想到了优化的方法:找出bottom left most point, 固定这个点选出的线,肯定能平分两半。
  • 一个tic-tac-toe游戏,输出所有可能的结果,具体输出什么样子自己定义。我是把所有的结果都encode成string.
  • 这轮算是唯一幸运的一轮了,面经中的那个MyLogger, 有个startTime, endTime. 最后按顺序把log打印出来
  • 午餐
  • 设计一个iterator. ['foo', 'foo', 'foo', 'bar] 第一个next() 返回('foo', 3). 再call 一遍 next(), 返回(‘bar', 1)
  • reducieble string. 这轮我也没怎么搞明白,对不住大家了。


我发现面试官都要把我的代码在电脑里记录下来,他们说feedback的时候要填。第五轮iterator那一轮,我和面试官讨论的比较多,在白板上把代码改的乱七八糟的,最后面试官照了一张白板的照片走了, 我感觉他回去之后也懒得去仔细看了,这轮要栽的样子。

第二轮是所有有一方win的结果吗?

是的,有win, 或者平局。invalid的局不考虑,比如说Player1已经赢了,Player2还在继续下
请问第一题怎么判断点在线的上部还是下部呢?

我没写完,面试官说这个helper function可以不用写,估计是嫌我太慢了吧

To determine which side of the line from A=(x1,y1) to B=(x2,y2) a point P=(x,y) falls on you need to compute the value:-
d=(x−x1)(y2−y1)−(y−y1)(x2−x1)
If d<0 then the point lies on one side of the line, and if d>0 then it lies on the other side. If d=0 then the point lies exactly line.

To see whether points on the left side of the line are those with positive or negative values compute the value for d for a point you know is to the left of the line, such as (x1−1,y1) and then compare the sign with the point you are interested in.
楼主,按照定理来说,他给的这个离散点矩阵,其中任意一个点,在这个矩阵中都能找到一个点,把这个矩阵一分为二,对于每一个新的点,按照我刚post上去的数学公式判断是否在上边或者下边,就可以了,这样时间复杂度就是O(N^2)


这一题我后来仔细写了一下,终于理解了烙印给的提示, 最下面最左边的点,可以保证其余点在这个点的一侧,然后对其余所有点按照斜率排序,如果斜率<0, 则 加上一个非常大的数,然后取中值,则一定满足条件。 完全不用写判断在哪侧的函数...
附上代码和测试用例。 测试用例我随即了1000次,每次随即100个点, 用leetcode maxpoint on one line的方法保证没有三个点在同一直线。测试用例全过。

我取了最下面最左边的点作为start point,保证了其余所有点在上半侧,然后将其余点按照斜率排序(注意负数加上一个很大的数保证),然后去中点。为了测试,我加上了判断哪侧的函数,实际这个函数用不到。

补充内容 (2019-3-7 14:55):
如果按照烙印的说法最左边最下面的点,那么斜率是负数似乎也不用加一个很大的值,直接按照斜率排序就好。
总的来说,这题刚出来很容易被这个"判断哪侧"搞慌...但是换个思路就柳暗花明了。
def split_points(points):
    # 去最左边最下面的点
    st = [1 << 32, 1 << 32]
    st_idx = None
    for i, (px, py) in enumerate(points):
        if px < st[0] or px == st[0] and py < st[1]:
            st = px, py
            st_idx = i
    points.pop(st_idx)
    INF = 1 << 31
    def cmp(p):
        k = (p[1] - st[1]) * 1.0 / (p[0] - st[0]) if p[0] != st[0] else INF
        return k
    # 按照斜率排序
    points = sorted(points, key=cmp)
    mid = points[len(points) / 2]
     
    return st, mid

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts