阿里的一道在线编程测试题

一道编码解码的题目
就是用
0xxxxxxx 表示0-127
10xxxxxx 10xxxxxx 表示128-65535
输入一个string，然后让你来解码，明明简单的很的一道编程题，硬是没做出来…
感觉自己有点紧张，而且状态很差，不过没关系，慢慢来吧。
感觉之后有笔试什么的还是在宿舍自习室里做吧，状态应该会好一些。
今天状态实在是差，大脑晕乎乎的做什么测试题呢，唉，下次注意一点吧。

有点尴尬的是求内推的时候称呼写错了，是师妹结果以为是师兄，尴尬尴尬……

蚂蚁金服公司电面

先吐槽一下你这没什么项目经历啊，挑一个可以的讲讲吧。
然后我挑了个本科毕业设计…确实没什么可讲的，现在想想应该挑资助中心项目的。然后感觉自己投了一个错误的岗位，或者说没有根据这个岗位来写我的简历…
数据库都怎么用？都用了啥数据库，了解其他数据库吗？
HBase MongoDB MySQL Oracle Redis

关系型数据库：关系模型指的就是二维表格模型，而一个关系型数据库就是由二维表及其之间的联系所组成的一个数据组织

非关系型数据库：以键值对存储，且结构不固定，每一个元组可以有不一样的字段，每个元组可以根据需要增加一些自己的键值对，这 样就不会局限于固定的结构，可以减少一些时间和空间的开销。
适合存储一些较为简单的数据

结构化查询语言（Structured Query Language）

1. 关系型数据库 V.S. 非关系型数据库

关系型数据库的最大特点就是事务的一致性：传统的关系型数据库读写操作都是事务的，具有ACID的特点，这个特性使得关系型数据库可以用于几乎所有对一致性有要求的系统中，如典型的银行系统。
但是，在网页应用中，尤其是SNS应用中，一致性却不是显得那么重要，用户A看到的内容和用户B看到同一用户C内容更新不一致是可以容忍的，或者 说，两个人看到同一好友的数据更新的时间差那么几秒是可以容忍的，因此，关系型数据库的最大特点在这里已经无用武之地，起码不是那么重要了。
相反地，关系型数据库为了维护一致性所付出的巨大代价就是其读写性能比较差，而像微博、facebook这类SNS的应用，对并发读写能力要求极 高，关系型数据库已经无法应付(在读方面，传统上为了克服关系型数据库缺陷，提高性能，都是增加一级memcache来静态化网页，而在SNS中，变化太 快，memchache已经无能为力了)，因此，必须用新的一种数据结构存储来代替关系数据库。
关系数据库的另一个特点就是其具有固定的表结构，因此，其扩展性极差，而在SNS中，系统的升级，功能的增加，往往意味着数据结构巨大变动，这一点关系型数据库也难以应付，需要新的结构化数据存储。
于是，非关系型数据库应运而生，由于不可能用一种数据结构化存储应付所有的新的需求，因此，非关系型数据库严格上不是一种数据库，应该是一种数据结构化存储方法的集合。
必须强调的是，数据的持久存储，尤其是海量数据的持久存储，还是需要一种关系数据库这员老将。

问我申请内存这些用的多不多…我说不多。
问我分布式有啥经历没…我说没有。
问我多进程多线程的用的多不多…我说不多。
问我啥了我忘了…
问我进程和线程的区别…

然后问了两道题

1. 两个数组，一个有1000万，一个有100万，求交集。
   我答了哈希，然后让我再想想，也没想出啥来。
2. 一个数组，求有多少个不同的数及其数目。
   我答了哈希，然后让我再想想，我想了想说排序再遍历。没了…

我觉得自己弱爆了…

然后晚上和师兄聊了聊，发现自己还是得多学习！

3.13 小米公司

1. 一个数，如何求根号数，不能调用系统函数，我说用二分，先设一个初始值，然后比较其平方和该数的大小，然后继续搜索对比。
   注意先判断数是大于1还是小于1。

2. 一个字符串，由一些单词组成，间隔符是空格，然后将其反转。
   我想了想，leetcode做过，只要先把整个反转，然后再把里面的每个word反转一下就可以了。

3. 一个系统，有一大堆的定时任务。
   每个任务包括开始时间、周期以及回调函数。
   然后问你怎么更有效率的执行。
   我说用哈希，直接存储时间，key是时间，value是任务的id。然后结束之后把这个map销毁掉，新建一个周期之后的map。
   问了下操作系统任务是怎么调度的，说队列，队列是用什么数据结构实现的。

4. 一个100万数字的数组，数字范围0-999999。让你找里面重叠的数字。
   我说了哈希，说了排序，然后没想到O(1)空间，O(n)时间来做的方法。
   然后提示了说用位图，没听说过…
   然后后来想了想，可以直接把数值i调换到i位置，假如i位置原值是i的话，那么i就是重复的。
   看了下位图，差不多就是这个意思，就比如说{1,1,1,0,1,0,1,1}来表示{3,5,7,8,2,1}的排序结果

想想这一类的题目做的也不少了，就是说用原有空间来替代哈希所需要的空间！！！

网易游戏公司电面，在线视频面试

首先问了之前在线笔试中没有做出来的题目的想法和思路，NTES那道题目。
然后问哪种语言比较熟悉…我说C++，然后换了个哥们问我C++。
然后我就傻逼了，啥都不会啊卧槽。

1. 问四种转换操作符有什么区别
2. static_cast

最常用的类型转换符，在正常状况下的类型转换，如把int转换为float，如：int i；float f； f=（float）i；或者f=static_cast<float>(i);

2. const_cast

用于取出const属性，把const类型的指针变为非const类型的指针，如：const int *fun(int x,int y){}　　int *ptr=const_cast<int *>(fun(2.3))

3. dynamic_cast

该操作符用于运行时检查该转换是否类型安全，但只在多态类型时合法，即该类至少具有一个虚拟方法。dynamic_cast与static_cast具有相同的基本语法，dynamic_cast主要用于类层次间的上行转换和下行转换，还可以用于类之间的交叉转换。在类层次间进行上行转换时，dynamic_cast和static_cast的效果是一样的；在进行下行转换时，dynamic_cast具有类型检查的功能，比static_cast更安全。如：

class C
{
　　//…C没有虚拟函数
}；
class T : public C {
　　//…
}
int main()
{
　　dynamic_cast<T*> (new C);//错误
}
此时如改为以下则是合法的：
class C
{
public:
　　virtual void m() {};// C现在是 多态
}

4. reinterpret_cast
   interpret是解释的意思，reinterpret即为重新解释，此标识符的意思即为数据的二进制形式重新解释，但是不改变其值。如：int i; char *ptr="hello freind!"; i=reinterpret_cast<int>(ptr);这个转换方式很少使用。
5. 问多态的实现
   我说用虚函数实现，通过基类指针来调用派生类。
6. 以对象管理资源的好处
   我说了有利于资源的释放。
7. 让写string的构造函数，拷贝函数和赋值运算
   完全不会…

class String
{
public:
    String(const char *str = NULL);
    String(const String &other);
    ~String(void);
    String & operator = (const String &other);

private:
    char *m_data;
};

String::String(const char *str)  //构造函数
{
    if (str == NULL) {
        m_data = new char[1];
        *m_data = '\0';
    }
    else {
        auto length = strlen(str);
        m_data = new char[length + 1];
        strcpy(m_data, str);
    }
}

String::~String() {
    delete [] m_data;
}

String & String::operator=(const String &other)
{
    if (this == &other)
        return *this;
    delete [] m_data;
    auto length = strlen(other.m_data);
    m_data = new char[length+1];
    strcpy(m_data, other.m_data);
    return *this;
}

String::String(const String &other) //拷贝构造函数
{
    auto length = strlen(other.m_data);
    m_data = new char[length + 1];
    strcpy(m_data, other.m_data);
}

5. 写sqrt(n)
   这个比较好写。
6. 是否了解一些比较前沿的技术。
   我说了解一些，比如新的非关系型数据库啊，Hbase之类的，看看博客啊之类的…
7. 让说一下项目中印象最深，启发最大的事情。
   我说了怀教那个项目，和别人之间的沟通…完全在瞎扯淡…
8. 聊了下最后一个项目。
   这个聊了比较多。
   最后还是惯例看有没有什么问题问他。
   我就问了工作内容工作职责啥的，没有问太多东西。
   主要用python，会用一些C++。

今日头条公司当面面试

1. const和static的区别以及基本用法。
   static作用：“改变生命周期” 或者 “改变作用域”

• 作用于变量：
  用static声明局部变量，使其变为静态存储方式(静态数据区)，作用域不变；用static声明外部变量，其本身就是静态变量，这只会改变其连接方式，使其只在本文件内部有效，而其他文件不可连接或引用该变量。
• 作用于函数：
  使用static用于函数定义时，对函数的连接方式产生影响，使得函数只在本文件内部有效，对其他文件是不可见的。这样的函数又叫作静态函数。使用静态函数的好处是，不用担心与其他文件的同名函数产生干扰，另外也是对函数本身的一种保护机制。
  如果想要其他文件可以引用本地函数，则要在函数定义时使用关键字extern，表示该函数是外部函数，可供其他文件调用。另外在要引用别的文件中定义的外部函数的文件中，使用extern声明要用的外部函数即可。

const作用: “只读(readonly)”

• 定义常量
  (1)const
  修饰变量，以下两种定义形式在本质上是一样的。它的含义是：const修饰的类型为TYPE的变量value是不可变的,readonly。
  TYPE const ValueName = value;
  const TYPE ValueName = value;
  (2)将const改为外部连接,作用于扩大至全局,编译时会分配内存,并且可以不进行初始化,仅仅作为声明,编译器认为在程序其他地方进行了定义.
  extend const int ValueName = value;
• 指针使用CONST
  (1) 指针本身是常量不可变
  char * const pContent;
  const (char*) pContent; ???
  (2) 指针所指向的内容是常量不可变
  const char *pContent;
  char const *pContent;
  (3) 两者都不可变
  const char* const pContent;
  (4) 还有其中区别方法，沿着*号划一条线：如果const位于*的左侧，则const就是用来修饰指针所指向的变量，即指针指向为常量；如果const位于*的右侧，const就是修饰指针本身，即指针本身是常量。sdfs
• 函数中使用CONST
  (1) const修饰函数参数
  a. 传递过来的参数在函数内不可以改变(无意义，因为Var本身就是形参)
  void function(const int Var);
  b. 参数指针所指内容为常量不可变
  void function(const char* Var);
  c. 参数指针本身为常量不可变(也无意义，因为char* Var也是形参)
  void function(char* const Var);
  d. 参数为引用，为了增加效率同时防止修改。修饰引用参数时：
  void function(const Class& Var); //引用参数在函数内不可以改变
  void function(const TYPE& Var); //引用参数在函数内为常量不可变
  这样的一个const引用传递和最普通的函数按值传递的效果是一模一样的,他禁止对引用的对象的一切修改,唯一不同的是按值传递会先建立一个类对象的副本, 然后传递过去,而它直接传递地址,所以这种传递比按值传递更有效.另外只有引用的const传递可以传递一个临时对象,因为临时对象都是const属性, 且是不可见的,他短时间存在一个局部域中,所以不能使用指针,只有引用的const传递能够捕捉到这个家伙.
  (2) const 修饰函数返回值
  const修饰函数返回值其实用的并不是很多，它的含义和const修饰普通变量以及指针的含义基本相同。
  a. const int fun1() //这个其实无意义，因为参数返回本身就是赋值。
  b. const int * fun2() //调用时
  const int *pValue = fun2(); //我们可以把fun2()看作成一个变量，即指针内容不可变。
  c. int* const fun3() //调用时
  int * const pValue = fun2(); //我们可以把fun2()看作成一个变量，即指针本身不可变。

2. 内存分配的使用场景

3. 一个数组求重复数字的问题，老问题。

4. 给一个数组，求其前k大的元素。
   可以用快速排序，找出前k大的，然后再对那一堆进行排序。

5. 给一堆字符串集合，假如两个集合有一样的元素则把两个合并。

基础知识还是太弱，然后人不够open！下次面试不要这么拘谨！好好准备一下自我介绍吧！然后结束的时候记得问下面试官有什么建议，然后讨论下之前问的题目！

HULU公司面试

一面
先扯项目扯了会，然后问了俩题
1.一个筛子 怎么将40个人随机分成4组，每组10人
2.一个长度为n字符串，只包含a和b，问有多少种有循环节的情况
第二题写代码

二面
扯了会项目，问一些设计方面的，比如一个非技术公司想让你设计开发官网，怎么搞
扯了挺久怎么搞怎么搞…
让写了道题，
sqrt，精确到k位小数点

微软面试

一面
问两个有序数组，如何确定其中位数，拓展一下，如何求第k大。
用二分的方法来做。
二面
问了下给定n个数，如何随机的取其中k个数。
假如不知道一共有多少个数字，怎么随机取。
然后问了下docker和虚拟机的区别，然后问了下海量图数据的管理与挖掘课程都讲了啥…

• Docker源自Linux核心的系统层功能，如控制资源的控制群组机制cgroups、命名空间Namespaces，还有实现层级化功能的共通档案系统AUFS等。
  Windows系统的docker，微软为了docker特意实现了几种系统层机制。
  Namespace解决的问题主要是环境隔离的问题
  Linux CGroup解决对计算机资源使用上的隔离
• 海量图数据的管理与挖掘主要讲了一些数据挖掘有关的算法，讲了一些老的算法以及比较新的一些paper提出的算法，比如
  • 频繁模式挖掘，在一个数据集中频繁出现的模式(一些项、子序列、子结构等)
    应用：销售记录里的啤酒与尿布，牛奶与面包。Apriori算法，例子见这里。
    1）支持度：表示某个item集合在数据表中出现的比例。
    2）K-项候选集：由K-1项频繁集组合而成，支持度大于等于指定支持度的含有K个项的集合，供计算K项频繁集使用。
    3）K-项频繁集：支持度大于等于指定支持度的含有k个项的集合，由K项候选集计算而得。
  • 图上的可达性问题研究
  • 挖掘网络上的最大影响力节点（比如说推广手机的预算是100万元，预计每个新浪博主的宣传费是1万元，如何利用这100万元预算，使这款手机在新浪微博上的推广效果最好?）

三面
问了俩题，一道是求字符串中最长不重复子串，然后扩展下，怎么求可以有一个字母重复两次的。
另一道是说一个矩阵，矩阵数值表示高度，问一个球从高处往低处最多能降低多少。

宜信大数据面试

被虐翻了…问了许多基础知识各种不会
问如何删除链表里的重复元素。

多态的实现
一般继承及多重继承看这里
菱形继承看这里

哈希表是如何实现的
哈希表类项中必须存储key，因为碰撞的存在，往往不能够通过散列函数直接得到地址，还需要进一步的判断，因此列表项中需要存储key值。
解决hash冲突的办法

• 开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
• 再哈希法
• 链地址法
• 建立一个公共溢出区

面向对象语言的特性
多态和继承

问各种排序算法，详细的可以看看这里。

1. 冒泡排序
   它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来，直到没有任何一对数字需要交换。
2. 选择排序
   在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
   再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
   以此类推，直到所有元素均排序完毕
3. 插入排序
   插入排序的工作原理是，对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
4. 希尔排序
   希尔排序，也称递减增量排序算法，实质是分组插入排序。
5. 归并排序
   归并排序的思想就是先递归分解数组，再合并数组。
6. 快速排序
   “挖坑填数+分治法”，
   首先令i =L; j = R; 将a[i]挖出形成第一个坑，称a[i]为基准数。
   然后j--由后向前找比基准数小的数，找到后挖出此数填入前一个坑a[i]中，再i++由前向后找比基准数大的数，找到后也挖出此数填到前一个坑a[j]中。
   重复进行这种“挖坑填数”直到i==j。再将基准数填入a[i]中，这样i之前的数都比基准数小，i之后的数都比基准数大。
   因此将数组分成二部分再分别重复上述步骤就完成了排序。
7. 堆排序
   堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。二叉堆是一个近似完全二叉树 。

各种排序算法指标对比（[图片来源](http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/)）

智力题：一排犯人，1，2，3，4，5，前面的可以看到后面人身上穿的衣服，有红黑两种，不能看到自己的。从1开始报自己身上衣服颜色，报对了活，报错了枪毙。犯人们可以提前商量好，问如何报使得犯人死的最少。

测试工具：apache ab
测试一般要考虑一下几点：
Thoughput吞吐量，Latency响应时间，资源利用（CPU/MEM/IO/Bandwidth…），成功率，系统稳定性
这次测试属于局域网环境进行，排除了外网的网速限制及不稳定性
延迟在1s左右，然后大概能够支持的并发用户数量大概是
反正都在扯淡…

滴滴新锐计划面试

一共三面
感觉没问什么c++基础题，就主要问了问项目，出了几道简单算法题让你写
一面：
扯项目，让写个链表去重
二面：
扯项目，
给一堆元素，假如一个元素大于另一个元素的两倍，则能组成一对，问最多能有多少对。
想了想，只能想到暴力方法…然后换了道简单的。
一个三角形的数组，如下

     [1]
    [2, 3]
  [3, 4, 5]
[6, 4, 6, 3]

问从最顶端到最底端数值和最小是多少。每个元素只能和上下层的相邻元素连接，比如说第三层的4可以和第二层的2，3连接，第三层的3只可以和第二层的2连接。一道简单的dp题。
三面：
又扯项目，感觉现在扯项目扯的很溜了。然后让写链表反转…
然后就结束了。