微软 新鲜 onsite 真诚的天竺友人们

最后一题是找凸包吗

T大农民伯伯 发表于 2018-10-27 09:54
最后一题是找凸包吗

给一堆多边形，多边形都相邻挨在一起，然后返回这些多边形组成的最大多边形的那个边。

我觉得楼主很厉害诶 操作系统的知识非常扎实

请问楼主，面试是可以用任意语言吗

请教下楼主 多边形那个题的思路， 谢谢！

lz可以介绍一下左右括号的followup都有什么吗，谢谢

hjr01211 发表于 2018-10-28 01:43
请问楼主，面试是可以用任意语言吗

对的，什么都可以的

myway2012 发表于 2018-10-28 01:58
请教下楼主 多边形那个题的思路， 谢谢！

hi，那个题目就是你有很多边
边可以写成x y坐标表示的class, 一个边可以又两点表示

class line {
     int x1, x2;
     int y1, y2;
}

然后一个多边形就好多好多边，比如可以写成这样

class shape{
    vector<line*> lines;
}

然后给你比如这样的图形，左边一个平行四边形 abfd，右边一个三角形 fce ，要返回组成的最大的多边形的边 which is a b c d e
     
  
        b  
     -------  / \    c
a  /       f/     \
    ------  --------
    d        e

然后 f 这个边 很有意思，在内存里面是重复的，在平行四边形有一个比如叫f1，在三角形有一个比如叫f2
这题天竺大哥说是一定是点点相连，不会有分离的四边形，所以只要看一遍所有边，然后把重复的边去了就行。但是因为f是分成俩出现的，所以不能看line pointer是否一样，方法是
用string 表示每一个line，f1 = "x1 y1 x2 y2"，然后放在哈希表里面，如果出现一样的线，那么x1 x2 y1 y2一定一样。
但是就算是一样的line，可能f1是 x1 y1 x2 y2， f2是x2 y2 x1 y1，所以我每次要看俩点颠倒是否也一样。
遍历一下，查一下哈希表，然后就可以了

睡不醒的小新 发表于 2018-10-28 03:00
lz可以介绍一下左右括号的followup都有什么吗，谢谢

问了比如stack的内存，一些常见的big o 时间复杂度，然后问我还能不能用别的数据结构做。如果有1千万长度的怎么办，还有比如是不是可以看如果左括号数量超过string size 一半其实就可以直接return了。最后随意问了下用分布式能不能判断左右括号对其。

unknowncyan 发表于 2018-10-28 00:36
我觉得楼主很厉害诶 操作系统的知识非常扎实

谢谢一直在准备fb pe的面试，就看了蛮多linux