面试需要的基础知识

台上一分钟，台下十年功：编程语言、数据结构、算法等

无笔记不读书，本系列总结《剑指offer》相关内容，第一章面试前的准备已与简历制作相融合：做一份简洁又有料的简历。本文主要是面试所需的基本功：编程语言、数据结构、算法、设计模式、位运算等等等。

一、编程语言

C/C++、Java、C#、Python、PHP、Object-C、Perl

1.C/C++

小北接触的第一门语言。推荐书籍《Effective C++》：C++中常出现的问题及解决方法；《C++ primer》C++语法大全；《Inside C++ Object Model》：深入C++对象的内部；《The C++ Programming Language》：全面了解。

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

（2）定义一个空类型，里面没有任何成员变量和成员函数，对该类型求sizeof，得到的结果是几？

（3）题目c++中不允许复制构造函数传值参数的理解

（4）面试题（一）赋值运算符函数

（5）C++中可以用struct和class来定义类型，这两种类型有什么区别？

2.C#

（6）C#中可以用struct和class来定义类型，这两种类型有什么区别？

（7）面试题（二）设计一个类，我们只能生成该类的一个实例。

二、数据结构

数组、字符串、链表、树、栈、队列

1.数组

创建数组先指定大小，根据大小分配内存。因此空间效率不是很好，经常会有空闲区域没有得到充分利用。由于数组内存是连续的，根据下标存取数据的时间效率为O(1)，时间效率很高。

用数组实现哈希表：把数组下标设为哈希表的键值（Key），而把数组中的每一个值设为哈希表的值（Value）。

为了解决数组空间效率不高的问题，设计了很多动态数组，如C++的STL中的vector。为了避免浪费，先为数组分配一个较小的空间，然后往数组中加数据，当数据的数目超过数组的容量时，再重新分配一块更大的空间（STL的vector每次扩容时，新容量是前一次的两倍），把之前的数组复制到新的数组中，再把之前的内存释放，从而减少内存浪费。

数组的名字也是一个指针，该指针指向数组的第一个元素。指针访问数组时，避免数组越界报错。

（1）面试题（三）二维数组中的查找

（2）搜索二维矩阵 II 

2.字符串

字符串是由若干字符组成的序列。在C/C++中每个字符串都以"\0"作为结尾，因此，每一个字符串都有一个额外开销，注意不要越界。如：

//越界，复制字符串到str至少需要11个字节的数组，不要忽略"\0"
char str[10];
strcopy(str,"0123456789");

为了节省内存，C/C++把常量字符串放到单独的一个内存区域。当几个指针赋给相同的常量字符串时，它们实际上会指向相同的内存地址；用常量内存初始化数组，情况会略有不同。

char str1[] = "hello world";
char str2[] = "hello world";
// str1 ≠ str2
char* str3 = "hello world";
char* str4 = "hello world"; 
// str3 == str4

str1 和 str2 是两个字符串数组（char[]），我们会为它们分配两个长度为 12 个字节的空间，并把”hello world”的内容分别复制到数组中去。显然这是两个初始地址不同的数组，因此 str1 和 str2 的值也不相同。

str3 和 str4 是两个指针，我们无需为它们分配内存以存储字符串的内容，而只需要把它们指向“hello world”在内存中的地址就可以了。由于”hello world”是常量字符串，它在内存中只有一个拷贝。

在C#中，封装字符串的类型System.String有一个非常特殊的性质：String中的内容是不能改变的。一旦试图改变String的内容，就会产生一个新的实例。

String str = "hello";
str.ToUpper();
str.Inser(0,"world");

虽然我们对str做了ToUpper和Insert两个操作，但操作的结果都是生一个新的String实例并在返回值中返回，str本身的内容都不会发生改变，因此str最终的内容不变。由此可见，试图多次改变String的内容，改变之后的值只可以通过返回值得到。用String做连续多次修改，每一次修改都会产生一个临时对象，这样开销太大。为此C#定义一个新的与字符串相关的类型StringBuilder，它能容纳修改后的结果。

（1）面试题（四）替换空格

（2）合并数组

3.链表

链表空间效率比数组高