Home > programming > MGF的面试总结

MGF的面试总结


G的题目:
1.给定已排序数组,找一个数是否在里面出现和出现的次数
2.已知每天的股票价格,计算何时买卖获益最大
3.给两个用一种spatial tree(好像叫rp-tree之类)表示的黑白图片,如何找到公共的
黑色部分,假设两个图片的尺寸一样
4.描述快速排序和归并排序的实现,分析平均、最差时间复杂度,何时用哪个
5.解释C++的多态
6.一条直线上有N个站台,已知任何两点间直达列车的票价,求出从起点到终点的票价
最优的乘车方案。因为从A到B,再从B到C的价格可能比直接从A到C便宜
7.N个job,要求分配到M台机器上,每个机器可以被分配0-N个job,但有些job相互排斥
不能被放到一起执行,给出所有可能的分配方案
8.给N个元素,第i个元素有一个大于0的score(i),要求随机选出k个,每个元素可以被
选择任意多次,但保证被选择的概率要和score(i)成比例
9.N个矩形,所有矩形都有一条边在同一条直线上,他们相互可能有overlap,找出最后
得到的这个不规则图形的所有边界点

M的题目:
1.设计虚拟内存管理的类、接口和实现
2.给两颗树,如果节点深度相同且value相同,则这两个node是match的,两棵树上的节
点如果相互match,则它们的父节点必须也要match。假设一棵树上所有node的value都
不同,并且兄弟节点间不用考虑顺序,问给两棵树,如何求最大match的node数目。如
果value有重复,并且要求兄弟节点match的顺序一致,问如何求最大match数。
3.一个房间里的人有且只有一个名人,他不认识其他任何人,其它所有人都认识他,如
何找到这个名人。这个题目的解改进了几次,最后要求给O(n)时间且O(1)空间的解
4.一些开放式的问题,和machine learning、data mining相关的问题怎么解

F的题目:
1.给一个字符串,另外给一个匹配模式,模式里有.和*,写一个程序找出输入字符串中
第一个match这个模式的子串
2.设计fb的系统支持like那个button
3.给一个字符串,统计其中有几个单词
4.一个排序的数组,但rotate了几位,如何找一个给定的数是否在里面出现
5.层次打印一颗树,每层的节点打印完要换行,但除了层次周游的队列里可以存放node
pointer外,不允许使用O(n)的额外空间(比如记下每个节点的深度决定是否换行是不
允许的)
6.实现float sqrt(float f)
7.一个数组里有三种元素,比如1、2、3,如何排序使得数组有序。还是这个数组,但
里面每个元素是一个float,另外有个函数int map(float)可以给一个浮点数得到一个1
、2或3的整数,问这种情况如何排序使得map到1的元素在最前面,然后是2的,最后是3
的。map值一样的元素间顺序无所谓

Advertisements
Categories: programming
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: