• 13.4 深拷贝和浅拷贝有什么区别,如何使用?

    题目 深拷贝和浅拷贝的区别是什么?你会如何使用它们? 解答 浅拷贝并不复制数据,只复制指向数据的指针,因此是多个指针指向同一份数据。 深拷贝会复制原始数据,每个指针指向一份独立的数据。通过下面的代码, 可以清楚地看出它们的区别: struct Test{ char *ptr; }; void shallow_copy(Test &src, Test &dest){ dest.ptr = src.ptr; } void deep_copy(Test &src, Test &dest){ dest.ptr = (char*)malloc(strlen(src.ptr) + 1); memcpy(dest.ptr, src.ptr); } 浅拷贝在构造和删除对象时容……
  • 13.3 C++中的虚函数是如何工作的?

    题目 C++中的虚函数是如何工作的? 解答 虚函数依赖虚函数表进行工作。如果一个类中,有函数被关键词virtual进行修饰, 那么一个虚函数表就会被构建起来保存这个类中虚函数的地址。同时, 编译器会为这个类添加一个隐藏指针指向虚函数表。如果在派生类中没有重写虚函数, 那么,派生类中虚表存储的是父类虚函数的地址。每当虚函数被调用时, 虚表会决定具体去调用哪个函数。因此,C++中的动态绑定是通过虚函数表机制进行的。 当我们用基类指针指向派生类时,虚表指针vptr指向派生类的虚函数表。 这个机制可以保证派生类中的虚函数被调用……
  • 13.2 浅析哈希表和STL map

    题目 对比哈希表和STL map。哈希表是怎么实现的?如果输入数据规模不大, 我们可以使用什么数据结构来代替哈希表。 解答 对比哈希表和STL map 在哈希表中,实值的存储位置由其键值对应的哈希函数值决定。因此, 存储在哈希表中的值是无序的。在哈希表中插入元素和查找元素的时间复杂度都是O(1)。 (假设冲突很少)。实现一个哈希表,冲突处理是必须要考虑的。 对于STL中的map,键/值对在其中是根据键进行排序的。它使用一根红黑树来保存数据, 因此插入和查找元素的时间复杂度都是O(logn)。而且不需要处理冲突问题。 STL中的map适合以下情……
  • 13.1 用C++写一个函数,输出文件的最后k行。

    题目 用C++写一个函数,打印输入文件的最后k行。 解答 一种方法是打开文件两次,第一次计算文件的行数N,第二次打开文件,跳过N-K行, 然后开始输出。如果文件很大,这种方法的时间开销会非常大。 我们希望可以只打开文件一次,就可以输出文件中的最后k行。 我们可以开一个大小为k的字符串数组,然后将文件中的每一行循环读入。 怎么样循环读入呢?就是将k行字符串保存到字符串数组后, 在读第k+1时,将它保存到数组的第1个元素,依次类推。这样一来, 实际上文件中第i行的字符串会被保存到数组的第i%k的位置。最后当文件读完时, 数组……
  • code123
    12.7 如何设计一个支持TB级别数据的数据库

    12.7 如何设计一个支持TB级别数据的数据库

    题目 让你来设计一个能存储TB级数据的数据库,而且要能支持高效的区间查询(范围查询), 你会怎么做? 解答 首先要明确,并不是所有的字段……
  • 12.6 10亿个url,每个url对应一个网页,如何检测重复的网页?

    题目 你有10亿个url,每个url对应一个非常大的网页。你怎么检测重复的网页? 解答 网页大,数量多,要把它们载入内存是不现实的。 因此我们需要一个更简短的方式来表示这些网页。而hash表正是干这事的。 我们将网页内容做哈希,而不是url,这里不同url可能对应相同的网页内容。 将每个网页转换为一个哈希值后,我们就得到了10亿个哈希值, 很明显,两两对比也是非常耗时的O(n2 )。因此我们需要使用其它高效的方法。 根据以上分析,我们可以推出满足条件的以下算法: 遍历网页,并计算每个网页的哈希值。 检查哈希值是否已经在哈希表……
  • 12.5 如果让你设计一个网络爬虫,你怎么避免陷入无限循环?

    题目 如果让你设计一个网络爬虫,你怎么避免陷入无限循环? 解答 看完这题,建议用python写个爬虫,对此就能理解的多一些,而且还可以做出好玩的东西。 话说爬虫为什么会陷入循环呢?答案很简单,当我们重新去解析一个已经解析过的网页时, 就会陷入无限循环。这意味着我们会重新访问那个网页的所有链接, 然后不久后又会访问到这个网页。最简单的例子就是,网页A包含了网页B的链接, 而网页B又包含了网页A的链接,那它们之间就会形成一个闭环。 那么我们怎样防止访问已经访问过的页面呢,答案也很简单,设置一个标志即可。 整个互联网……
  • 12.4 数组去重(限制内存为4kb)

    题目 有一个数组,里面的数在1到N之间,N最大为32000.数组中可能有重复的元素(即有的元素 存在2份),你并不知道N是多少。给你4KB的内存,你怎么把数组中重复的元素打印出来。 解答 我们有4KB的内存,一共有4 * 210 * 8位,大于32000,所以我们可以用Bit Map 来做这道题目。题目很简单,不过我们可以把代码写得漂亮一些。 我们可以写一个Bit Map类来完成基本的位操作。为了代码的简洁, 我们假设程序是运行在32位机器上,即int是32位的。如果考虑代码的通用性, 也可以将32替换成sizeof(int)*8。 代码如下: #include <……
  • 12.3 在40亿个整数值中查找特定数据

    题目 给你一个文件,里面包含40亿个整数,写一个算法找出该文件中不包含的一个整数, 假设你有1GB内存可用。 如果你只有10MB的内存呢? 解答 我们先来做个算术题,40亿个整数大概有多大? 40 * 10^8 * 4B = 16GB (大约值,因为不是按照2的幂来做单位换算) 12 40 * 10^8 * 4B = 16GB (大约值,因为不是按照2的幂来做单位换算)  这个明显无法一次性装入内存中。但是,如果我们用计算机中的一位来表示某个数出现与否, 就可以减少内存使用量。……
  • 12.2 如何为社交网站(如facebook,新浪微博)设计数据结构

    题目 你会怎样给一个非常大型的社交网站设计数据结构(比如Facebook,LinkedIn)? 设计一个算法来找到任意两个人之间的联系,比如:我 -> Bob -> Susan -> Jason -> 你 解答 方法: 首先,我们先不去考虑数据规模。先从简单的入手。 我们可以把每个人看作一个结点,如果两个人之间是朋友,则这两个结点间有一条边, 这样一来我们就可以构建出一个图。假设我们将“人”这个类设计如下: class Person { Person[] friends; // Other info } 12345 c……
  • 12.1 股价信息摘要整合方案

    题目 如果你要为5000家公司的股价信息整合摘要,你会怎么做? 你要负责摘要的开发,部署,监控和维护。描述你能想到的不同方法, 及为什么你会推荐这些方法。摘要以逗号分隔的格式经由FTP进行交付,每个交易日一次。 每日有1000个用户在web应用程序中使用这些摘要信息。 解答 假设我们有一些脚本在每日结束时通过FTP获取数据。我们把数据存储在哪? 我们怎样存储数据有助于我们对数据进行分析? 方案一 将数据保存在文本文件中。这样子的话,管理和更新都非常麻烦,而且难以查询。 保存无组织的文本文件是一种非常低效的方法。 方案二 ……
  • 11.1-11.6 程序员面试—测试技能测试

    题目11.1 Find the mistake(s) in the following code: unsigned int i; for (i = 100; i <= 0; --i) printf(“%dn”, i); 1234 unsigned int i;for (i = 100; i <= 0; --i)    printf(“%dn”, i);  解答11.1 简单题。不过不能粗心,否则可能会以为把i <= 0改为i >= 0就OK了。 这就把一个错误改成了另一个错误。因为i的数据类型是unsigned int, 是恒大于等于0的,这一改就把本来一次都不执行的循环,……
  • code123
    10.1-10.7 程序员面试——数学相关题目

    10.1-10.7 程序员面试——数学相关题目

    题目10.1 你有一个篮球架,可以在以下游戏中选择一个来玩。 游戏1:投一次球,进了算赢。 游戏2:投三次球,至少要进2个才算赢。 如果命……
  • 9.7 写一个函数模拟叠罗汉节目

    题目 马戏团设计了这样一个节目:叠罗汉。一群人往上叠,每个人都踩在另一个人的肩膀上。 要求上面的人要比下面的人矮而且比下面的人轻。给出每个人的身高和体重, 写一个函数计算叠罗汉节目中最多可以叠多少人? 例子: 输入(身高 体重):(65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) 输出:最多可叠人数:6 (从上到下是:(56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)) 解答 给定了(身高 体重)序列,要求我们排序。不过由于要排序的对象是一个结构, 我们可以先按其中的一个指标进行排序,比如说身高。身高……
  • 9.6 在一个矩阵中找出特定的数

    题目 给出一个矩阵,其中每一行和每一列都是有序的,写一个函数在矩阵中找出指定的数。 解答 我们假设这个矩阵每一行都是递增的,每一列也都是递增的,并把这些数据存入文件 9.6.in(如下),其中开头的两个数5 5表示该矩阵是5*5的。 5 5 1 2 3 4 5 3 7 8 9 11 5 9 10 17 18 7 12 15 19 23 9 13 16 20 25 1234567 5 51 2 3 4 53 7 8 9 115 9 10 17 187 12 15 19 239 13 16 20 25  这个矩阵是有序的,因此我们要利用这一点,当矩阵中元素……