《剑指Offer》第二章笔记(上)

Posted on 2023-05-24 Edited on 2022-02-11 In Reading , Books , Computer Science

第二章面试需要的基础知识 (上)

2.1 面试官谈到

“C++的==基础知识==，如面向对象的特性、构造函数、析构函数、动态绑定等，能够反映出应聘者是否善于==把握问题本质==，有没有==耐心深入一个问题==。另外还有常用的==设计模式、UML图==等，这些都能体现应聘者是否有==软件工程方面的经验==。” ——王海波（Autodesk，软件工程师）

“对基础知识的考查我特别重视C++中对==内存的使用管理==。我觉得内存管理是C++程序员特别要注意的，因为内存的使用和管理会影响程序的效率和稳定性。” ——蓝诚（Autodesk，软件工程师）

“基础知识反映了一个人的基本能力和基础素质，是以后工作中最核心的能力要求。我一般考查：（1）==数据结构和算法==；（2）==编程能力==；（3）部分==数学知识==，如概率；（4）==问题的分析和推理==能力。” ——张晓禹（百度，技术经理）

“我比较重视四块基础知识：（1）==编程基本功==（特别喜欢字符串处理这一类的问题）；（2）==并发控制==；（3）==算法、复杂度==；（4）==语言的基本概念==。” ——张珺（百度，高级软件工程师）

“我会考查编程基础、计算机系统基础知识、算法以及设计能力。这些是一个软件工程师的最基本的东西，这些方面表现出色的人，我们一般认为是有发展潜力的。” ——韩伟东（盛大，高级研究员）

“（1）==对OS的理解程度==。这些知识对于工作中常遇到的==内存管理、文件操作、程序性能、多线程、程序安全==等有重要帮助。对于OS理解比较深入的人对于偏底层的工作上手一般比较快。（2）对于一门==编程语言的掌握程度==。一个热爱编程的人应该会对某种语言有比较深入的了解。通常这样的人对于新的编程语言上手也比较快，而且理解比较深入。（3）常用的==算法和数据结构==。不了解这些的程序员基本只能写写‘Hello World’。” ——陈黎明（微软，SDE II）

2.2 编程语言

面试官要么==直接问语言的语法==，要么要求应聘者==用一种语言解决一个问题==并由此考察其对语言的熟练程度。

不同公司开发用的语言不尽相同，例如：底层开发 (如驱动) 更习惯用C，Linux下有很多用C++的，Windows下很多用C#的，跨平台开发可能更喜欢Java，苹果相关的开发可能是Objective C，还有用脚本语言如Perl、Python开发短小精致的小应用的公司。

本书: C++/C#。

2.2.1 C++

总的来说，不管应聘者去什么公司求职，都应该在一定程度上掌握C++。

通常语言面试会有三种类型。

第一种类型：面试官直接询问对==C++概念==的理解。例如，对C++关键字的理解程度:

在C++中，有哪4个与类型转换相关的关键字？这些关键字各有什么特点，应该在什么场合下使用？

例如，sizeof的概念:

面试官：定义一个空的类型，里面没有任何成员变量和成员函数。对该类型求sizeof，得到的结果是多少？ 应聘者：答案是1。 面试官：为什么不是0？ 应聘者：空类型的实例中不包含任何信息，本来求sizeof应该是0，但是当我们声明该类型的实例的时候，它必须在内存中占有一定的空间，否则无法使用这些实例。至于占用多少内存，由编译器决定。Visual Studio中每个空类型的实例占用1字节的空间。 面试官：如果在该类型中添加一个构造函数和析构函数，再对该类型求sizeof，得到的结果又是多少？ 应聘者：和前面一样，还是1。调用构造函数和析构函数只需要知道函数的地址即可，而这些函数的地址只与类型相关，而与类型的实例无关，编译器也不会因为这两个函数而在实例内添加任何额外的信息。 面试官：那如果把析构函数标记为虚函数呢？ 应聘者：C++的编译器一旦发现一个类型中有虚拟函数，就会为该类型生成虚函数表，并在该类型的每一个实例中添加一个指向虚函数表的指针。在32位的机器上，一个指针占4字节的空间，因此求sizeof得到4；如果是64位的机器，一个指针占8字节的空间，因此求sizeof则得到8。

第二种类型：面试官要求应聘者==分析一段代码的运行结果==。所给的代码一般包含==复杂微妙的语法特性==，要求应聘者对C++考点有着非常透彻的理解。例如，给出如下的代码并提供三个选项: A. 编译错误; B. 编译成功，运行时崩溃; C. 编译运行正常，输出10:

在上面的代码中，A (A other)传入的参数other是A的一个实例。由于是传值参数，将形参复制到实参会调用复制构造函数。因此，如果允许复制构造函数传值 (像这个例子中这样)，就会在复制构造函数中调用复制构造函数，从而形成永无休止的递归调用、导致栈溢出。

因此，C++的标准不允许复制构造函数传递参数。在Visual Studio中将编译出错。要解决这个问题，可以将构造函数修改为A (const A&other)，即将传值参数改成常量引用。

第三种类型：要求应聘者写代码来==定义一个类型==或者==实现类型中的成员函数==。考察C++语法的代码题经常围绕在==构造函数==、==析构函数==和==运算符重载==中。

推荐的C++书单 (根据情况选择阅读的顺序):

《Effective C++》。适合面试前的C++突击。
《C++ Primer》。对C++语法的全面了解。
《Inside C++ Object Model》。深入了解C++对象的内部。
《The C++ Programming Language》。全面深入掌握C++。

面试题1: 赋值运算符函数

如下为类型CMyString的声明，请为该类型添加赋值运算符函数。

照片 2022-1-12 14 44 29

当面试官要求应聘者定义一个赋值运算符函数时，他会关注以下几点:

是否将返回值的类型声明为该类型的引用，并在函数结束前返回实例自身的引用 (即 *this)。只有返回一个引用 (而不是void)，才允许连续赋值。例如，对3个CMyString对象str1、str2、str3的连续赋值操作str1=str2=str3将不能通过编译。
是否将传入的参数类型声明为常量引用。如果传入的参数不是引用而是实例，那么从形参到实参会调用一次复制构造函数，产生消耗。同时，由于在该赋值运算符函数内不会改变传入的实例的状态，因此应该为传入的引用参数加上const关键字。
是否释放实例自身已有的内存。如果在分配新内存之前忘记释放自身已有的空间，则会造成内存泄漏。
是否判断传入的参数和当前的实例 (*this) 是不是同一实例。如果是同一实例，则不进行赋值操作而直接返回。如果事先不判断的话会在释放实例自身内存的时候造成严重的隐患: 传入的参数的内存也可能被释放。

经典的解法 (初级程序员)

CMyString& CMyString::operator =(const CMyString &str)
{
    if (this==&str)
        return *this;
    
    delete []m_pData;
    m_pData = NULL;
    
    m_pData = new char[strlen(str.m_pData)+1];
    strcpy(m_pData,str.m_pData);
    
    return *this;
}

考虑异常安全性的解法 (高级程序员)

上一个解法中，我们在分配内存之前先用delete释放了实例m_pData的内存。如果此时内存不足导致new char抛出异常，m_pData将是一个空指针，这样非常容易导致程序崩溃。即，一旦在赋值运算符函数内部抛出一个异常，CMyString的实例将不再保持有效的状态，这违背了==异常安全性 (Exception Safety)== 原则。

在赋值运算符函数中实现异常安全性的方法有两种。第一种，是先用new分配新的内容、再用delete释放已有的内容。这样只有在分配内容成功后再释放原来的内容，当分配内存失败时能确保原来的实例不被修改。第二种，是先创建一个临时的实例，再交换临时实例和原来的实例。代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
CMyString& CMyString::operator =(const CMyString &str)
{
    if (this != &str)
    {
        CMyString strTemp(str);
        
        char* pTemp = strTemp.m_pData;
        strTemp.m_pData = m_pData;
        m_pData = pTemp;
    }
    
    return *this;
}
由于临时实例strTemp是一个局部变量，程序运行到if外时也就离开了该变量的作用域，从而自动调用strTemp的析构函数，将strTemp.m_pData所指向的内存释放掉。由于strTemp.m_pData所指向的内存就是实例之前m_pData的内存，这就相当于自动调用析构函数释放实例的内存。

测试用例

将一个CMyString的实例赋值给另一个实例。

将一个CMyString的实例赋值给他自己。

连续赋值。

本题考点

考察对C++的基础语法的理解，如运算符函数、常量引用等。

考察对内存泄漏的理解。

对高级C++程序员，还考察对代码异常安全性的理解。

2.2.2 C

C#是微软在推出开发平台.NET时同步推出的编程语言。

C#可以看做是一门==以C++为基础==发展起来的一种托管语言，因此其很多关键字甚至语法都和C++相似。因此需要着重关注==C#与C++不同的语法特点==。例如:

面试官：C++中可以用struct和class来定义类型。这两种类型有什么区别？ 应聘者：如果没有标明成员函数或者成员变量的访问权限级别，在struct中默认的是public，而在class中默认的是private。 面试官：那在C#中呢？ 应聘者：C#和C++不一样。在C#中如果没有标明成员函数或者成员变量的访问权限级别，struct和class中都是private的。struct和class的区别是struct定义的是值类型，值类型的实例在栈上分配内存；而class定义的是引用类型，引用类型的实例在堆上分配内存。

和C++不同的是，C#中可以定义一个Finalizer和Dispose方法以释放资源。 Finalizer方法: 写法和C++析构函数一样都是后面跟类型名字。但C++析构函数的调用时机是确定的，C#的Finalizer在运行时(CLR)做垃圾回收时才会被调用。也就是说Finalizer的调用时机由运行时决定，因此对程序员来说是不确定的。

C#和C++的每个类型都有构造函数，但C#中可以为类型定义一个特殊的构造函数: 静态构造函数。特点: 在类型第一次被使用之前由运行时自动调用，而且保证只被调用一次。关于静态构造函数的面试题例如:

首先执行的是B的静态构造函数。静态构造函数先初始化类型的静态变量，再执行函数体内的语句。因此此处先打印a1再打印a3.

接下来执行的是B b = new B()，即调用B的普通构造函数。普通构造函数首先初始化成员变量，再执行函数体内的语句。因此此处先打印a2再打印a4。

因此，上述代码运行的输出的四行分别是a1, a3, a2和a4.

除了关注C#和C++的不同之处之外，还需要格外关注==C#的一些特有的功能==。例如反射、应用程序域 (AppDomain) 等。关于反射和应用程序域的例子:

上述代码首先创建一个名为NewDomain的应用程序域，并在该域中利用反射机制创建类型A的一个实例和类型B的一个实例。

A继承自MarshalByRefObject，而B不是。虽然A和B这两个类型的结构一样，但由于基类不同，在跨越应用领域边界时表现出的行为将非常不同。

先讨论A。由于A继承自MarshalByRefObject，那么a实际上只是在默认的域中的一个代理实例 (Proxy)，它指向位于NewDomain域中的A的一个实例。当调用a的方法SetNumber时，是在NewDomain域中调用这个方法，它将修改NewDomain域中的静态变量A.Number的值并设置为20. 而由于静态变量在每个应用程序域中都有一份独立的拷贝，修改NewDomain域中的静态变量A.Number 对默认域中的静态变量A.Number不会有任何影响。由于Console.WriteLine是在默认域中输出A.Number，因此输出的依然是10.

然后讨论B。由于B只是从Object继承而来的类型，它的实例穿越应用程序域的边界时，将会完整地复制实例。尽管上述代码试图在NewDomain域中生成B的实例，但会把实例b复制到默认域。此时调用方法b.SetNumber也是在默认域上进行，它将修改默认域上的A.Number并设为20。再在默认的域上调用Console.WriteLine时，它将输出20。

推荐的C#书单 (根据情况选择阅读的顺序):

《Professional C#》。在附录中详细说明了C#和其他语言的区别。
《CLR Via C#》(Jeffery Richter)。深入介绍了C#语言，同时对CLR和.NET做了全面的剖析。

面试题2: 实现Singleton模式

设计一个类，我们只能生成该类的一个实例。

只能生成一个实例的类即实现了==Singleton (单例) 模式==的类型。这是一个与==设计模式==相关的问题，设计模式在面向对象程序设计的面试中很重要。在常用的模式中，Singleton是唯一一个能够用短短几十行代码完整实现的模式。因此，写一个Singleton的类型是一个很常见的面试题。

不好的解法一: 只适用于单线程环境。 由于要求只能生成一个实例，因此我们必须把构造函数设为私有函数以禁止他人创建实例。可以定义一个静态的实例，在需要的时候创建该实例。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public sealed class Singleton1
{
    private Singleton1()
    {
    }
    
    private static Singleton1 instance = null;
  	private static Singleton1 Instance
    {
        get
        {
            if (instance == null)
                instance = new Singleton1();
            
            return instance;
        }
    }
}
上述代码在Singleton的静态属性Instance中，只有在instance为null时才创建一个实例，以避免重复创建。同时把构造函数定义为私有函数，这样就能确保只创建一个实例。

问题：如果两个线程同时运行到判断instance是否为null的if语句，并且instance的确没有创建时，那么两个线程都会创建一个实例，此时类型Singleton1就不再满足单例模式的要求了。

不好的解法二: 虽然在多线程环境中工作，但效率不高。 为了保证在多线程环境下我们还是只能得到类型的一个实例，需要加上一个同步锁。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public sealed class Singleton2
{    
    private Singleton2()    
    {
    }
    
    private static readonly object syncObj = new Object();
    
    private static Singleton2 instance = null;    
    private static Singleton2 Instance    
    {        
        get        
        {
            lock (syncObj)
            {
                if (instance == null)
                instance = new Singleton2();
            }
            
            return instance;        
        }    
    }
}
还是假设有两个线程同时想创建一个实例。由于在一个时刻只有一个线程能得到同步锁，当第一个线程加上锁时，第二个线程只能等待。当第一个线程发现实例还没有创建时，它创建出一个实例。接着第一个线程释放同步锁，此时第二个线程可以加上同步锁，并运行接下来的代码。这个时候由于实例已经被第一个线程创建出来了，第二个线程就不会重复创建实例了。

问题: 每次通过属性Instance得到Singleton2的实例，都会试图加上一个同步锁，而加锁是一个非常耗时的操作，应该尽量避免。

可行的解法：加同步锁前后两次判断实例是否已经存在 实际上，我们只是在实例还未创建之前需要加锁，以保证只有一个线程创建出实例。如果实例已经创建，则没有必要再加锁了。

public sealed class Singleton3
{    
     private Singleton3()    
     {
     }

     private static readonly object syncObj = new Object();

     private static Singleton3 instance = null;    
     private static Singleton3 Instance    
     {        
         get        
         {
             if (instance==null)
             {
                 lock (syncObj)
                 {
                     if (instance == null)
                     instance = new Singleton3();
                 }
             }
             
             return instance;        
         }    
     }
}

Singleton3的实现比较复杂，容易出错。还可以进一步优化。

强烈推荐的解法一：利用静态构造函数 C#语法中有一个函数能够确保只会调用一次，就是静态构造函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public sealed class Singleton4
{    
  private Singleton4()    
  {
  }
  private static Singleton4 instance = new Singleton4();
  private static Singleton4 Instance    
  {        
      get        
      {
          return instance;        
      }    
  }
}
在初始化静态变量instance时创建一个实例，而C#在调用静态构造函数时初始化静态变量。由于运行时能保证只调用一次静态构造函数，也就保证只初始化一次instance。

但是，C#中调用静态构造函数的时机不是由程序员决定的，而是当运行时发现第一次使用一个类型的时候自动调用该类型的静态构造函数。即，在Singleton4中，实例instance并不是在第一次调用Singleton4.Instance的时候创建的，而是在第一次用到Singleton4的时候就会被创建 (比如调用Singleton4中的静态方法时，此时不需要创建实例)。

因此，如果按照Singleton4的方法实现单例模式，可能过早创建实例而降低了内存的使用效率。

强烈推荐的解法二：实现按需创建实例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public sealed class Singleton5
{    
  private Singleton5()    
  {
  }
  private static Singleton5 Instance    
  {        
      get        
      {
          return Nested.instance;
      }    
  }
  class Nested
  {
      static Nested()
      {
      }
      internal static readonly Singleton5 instance = new Singleton5();
  }
}
在上述Singleton5的代码中，其内部定义了一个私有类型Nested。当第一次用到这个嵌套类型的时候，会调用静态构造函数创建Singleton5的实例instance。而私有类型Nested只在属性Singleton5.Instance中被用到。

因此，当我们第一次试图通过属性Singleton5.Instance得到Singleton5的实例时，会自动调用私有类型Nested的静态构造函数创建实例instance。而如果我们不调用属性Singleton5.Instance，就不会触发运行时调用Nested，也就不会创建实例，做到了真正的按需创建，提高了空间的使用效率。

本题考点

考察对单例 (Singleton) 模式的理解。

考察对C#的基础语法的理解，如静态构造函数等。

考察对多线程编辑的理解。

本题扩展: 前面的5中单例模式的实现标记类为sealed，表示它们不能作为其他类的基类。现在，我们要求定义一个表示总统的类型President,并可以从该类型继承出FrenchPresident和AmericanPresident等类型。这些派生类都只能产生一个实例。该如何设计实现这些类型？

第二章 面试需要的基础知识 (上)