[笔试]昨天google笔试的题目分析

ngkpux

级别: 经院本科

发帖: 1586

铜板: 2193

人品值: 2089

贡献值: 15

交易币: 0

好评度: 1575

信誉值: 0

金币: 0

所在楼道

只看楼主更多操作楼层直达

0 发表于: 2008-06-08

选择题+三道算法题

选择题没什么难的  最后一道考的数据库使用什么存储结构不会做。。

算法题
第一题没什么好说
第二题可破坏一个数组A[0..N-1]的条件下使用最少的内存判断是否存在相同的元素
   我的做法是堆排序  时间O(NlogN) 空间O(1) 复杂度上来看应该最优了
第三题已知每个点的父节点，求这棵树的最大独立集
   用递归求解  类似动态规划  但是不存在重叠子状态  经典算法问题了
   预处理每个节点的子节点存在一张表里
   时间O(N）空间O(N）

大家做的结果是这样吗？

选择题不算成绩