<commit_before>---
layout:     post
categories: "tech"
title:      "2012年6月29日笔试"
subtitle:   "20120629 Interview"
author:     "Charles"
---

这是2012年6月29日，去某互联网公司面试时候做的一套笔试题。记录一下。
 
## 算法部分:
1.  用高效方法计算fibonacci数列
我首先想到的是递归函数。

{% highlight java %}
long fibonacci(long n){

    if(0==n){return 0;}

    else if(1==n){return 1;}

    else {return fibonacci(n-1)+fibonacci(n-2);}

}
{% endhighlight %}

不过这显然不符合高效率的要求，当n>1时候，调用次数T(n)=T(n-1)+T(n-2)+3，增长速度比fibonacci数列本身还快。而这很大程度上是由于重复计算引起的。所以考虑用动态规划，用数组来保存已经计算所得的值。但是这样一来，效率是提高了，大数组需要一个大的内存空间，对于内存的消耗也大幅度增加。

{% highlight java %}
long fibonacci2(long n){

    if(0==n){return 0;}

    else if(1==n){return 1;}

    else {

    long[n] ftemp;

    ftemp[0]=0;ftemp[1]=1;

    for(i=2;i<=n;i++){

        ftemp[i]=ftemp[i-1]+ftemp[i-2];

    }

    return ftemp[n]

    }

}
{% endhighlight %}

或者也可以使用一个中间值来存储计算结果。

{% highlight java %}
long fibonacci3(long n){

if(0==n){return 0;}

    else if(1==n){return 1;}

    else {

     long base1=1;

     long base2=1;

     long temp;

     for(long i=3;i<=n;i++){

          temp = base2;

          base2 += base1;

          base1 = temp;

     }

      return base2;

    }

}
{% endhighlight %}

2.  从字符串str中寻找子字符串op的算法。

我当时写了一个str.indexOf(op)。被面试官深深的鄙视了。在写上一句在在C/C++中字符串操作一般利用的是标准库中的strstr()函数，估计面试官就会杀了我了。哈哈.
其实际上即使是JAVA中的indexof()函数使用的也是一种效率相对底下的朴素检索算法，相对高效的是RK算法和KMP无回溯算法。

3.  熟悉的排序算法，并说明特点

这个下次单独开一个帖子，做一下记录吧。一般有插入排序、冒泡排序，这两者在数据有序时效率还好，相对稳定，不过较慢。而相对的选择排序、希尔排序、快速排序、堆排序，则较快速，不过不稳定。

## JAVA语言部分:
1.  考察了一个JAVA传参的问题。

2.  Hashmap和Hashtable的区别，ArrayList和Vector的区别，ArrayList和LinkedList的区别。
考的都是集合Collection API的内容。Collection是util包中的几个基本接口，有三个比较重要的子接口，List、Set、SortedList。而Map也是util包中的一个接口。

Hashtable和Hashmap都实现了Map接口，都采用key-value键值对取得数据。不同点：

* Hashmap采用非同步机制，必须调用Map m = Collections.synchronizedMap（hashMap）来达到同步的效果；而Hashtable采用同步机制，也就是说在一个时间点只能有一个线程可以修改哈希表，任何线程在执行hashtable的更新操作前需要获取对象锁，其他线程等待锁的释放。

---因此当有多个线程访问相同实例可能的时候，就应该采用Hashtable。反之在单线程访问的时候应该采用Hashmap，线程不安全的数据结构能带来刚好的性能。而且Hashmap有一个可以按插入顺序去除k-v对的子类LinkedHashMap，操作方便，多线程访问也可以采用Collections.synchronizedMap（hashMap）达到同步的目的，因此个人建议采用HashMap，相对灵活高效。

* Hashmap允许空值，也就是null作为key和value；

***

同上，Vector线程安全，同步了每一个方法，适用于多线程操作。而ArrayList线程不安全，但是高效，并且可以使用Collections.sychronizedList来实现同步，达到线程安全的目的，因此现在基本已经不推荐使用Veator类了。

***

而对于ArrayList和LinkedList的区别如下

* ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
* 对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
* 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
* 随机查找指定节点的操作get，ArrayList速度要快于LinkedList.

## 互现网部分:
1.  区别cookie和seesion。
一言以蔽之cookie是存储在客户端浏览器文件中的字符串。而Session是存储在服务器内容中的对象。

cookies会话保存在客户端浏览器中，主要用于标识用户和记录用户操作，比如用户的登录信息、浏览记录信息等。用户每次访问站点时，Web应用程序都可以读取cookie包含的信息。常用语用户的自动登录和购物车购物记录保存。

Session表示的是一个访问会话的过程。是基于访问会话的进程，记录了一个访问会话的开始到结束，当浏览器或进程关闭之后，session也就销除了。

两者都有过期时间的限制。

2.  区别HTTP协议中的POST和GET
简单说，Get是向服务器发索取数据的一种请求；而Post是向服务器提交数据的一种请求，要提交的数据位于信息头后面的实体中。

* get是把参数数据队列加到提交表单ACTION属性所指的URL中，值和表单内各个字段一一对应，在URL中可以看到。

* post是通过HTTP post机制，将表单内各个字段与其内容放置在HTML HEADER内一起传送到ACTION属性所指的URL地址。用户看不到这个过程。

3.  正则表达式找出HTML问中的图片链接。
我实在是记不住正则表达式负责的规则，当时就写了用JSoup或者HTTPParser可以很好的完成HTML文本解析的工作。

HTML中的图片链接格式为<img src="{{site.imageurl}}/thank-you-xiaoyan.jpg" alt="alt text" width="390" height="245" />

## 数据库部分：<commit_msg>fix build issue<commit_after>---
layout:     post
categories: "tech"
title:      "2012年6月29日笔试"
subtitle:   "20120629 Interview"
author:     "Charles"
---

这是2012年6月29日，去某互联网公司面试时候做的一套笔试题。记录一下。
 
## 算法部分:
1.  用高效方法计算fibonacci数列
我首先想到的是递归函数。

{% highlight java %}
long fibonacci(long n){

    if(0==n){return 0;}

    else if(1==n){return 1;}

    else {return fibonacci(n-1)+fibonacci(n-2);}

}
{% endhighlight %}

不过这显然不符合高效率的要求，当n>1时候，调用次数T(n)=T(n-1)+T(n-2)+3，增长速度比fibonacci数列本身还快。而这很大程度上是由于重复计算引起的。所以考虑用动态规划，用数组来保存已经计算所得的值。但是这样一来，效率是提高了，大数组需要一个大的内存空间，对于内存的消耗也大幅度增加。

{% highlight java %}
long fibonacci2(long n){

    if(0==n){return 0;}

    else if(1==n){return 1;}

    else {

    long[n] ftemp;

    ftemp[0]=0;ftemp[1]=1;

    for(i=2;i<=n;i++){

        ftemp[i]=ftemp[i-1]+ftemp[i-2];

    }

    return ftemp[n]

    }

}
{% endhighlight %}

或者也可以使用一个中间值来存储计算结果。

{% highlight java %}
long fibonacci3(long n){

if(0==n){return 0;}

    else if(1==n){return 1;}

    else {

     long base1=1;

     long base2=1;

     long temp;

     for(long i=3;i<=n;i++){

          temp = base2;

          base2 += base1;

          base1 = temp;

     }

      return base2;

    }

}
{% endhighlight %}

2.  从字符串str中寻找子字符串op的算法。

我当时写了一个str.indexOf(op)。被面试官深深的鄙视了。在写上一句在在C/C++中字符串操作一般利用的是标准库中的strstr()函数，估计面试官就会杀了我了。哈哈.
其实际上即使是JAVA中的indexof()函数使用的也是一种效率相对底下的朴素检索算法，相对高效的是RK算法和KMP无回溯算法。

3.  熟悉的排序算法，并说明特点

这个下次单独开一个帖子，做一下记录吧。一般有插入排序、冒泡排序，这两者在数据有序时效率还好，相对稳定，不过较慢。而相对的选择排序、希尔排序、快速排序、堆排序，则较快速，不过不稳定。

## JAVA语言部分:
1.  考察了一个JAVA传参的问题。

2.  Hashmap和Hashtable的区别，ArrayList和Vector的区别，ArrayList和LinkedList的区别。
考的都是集合Collection API的内容。Collection是util包中的几个基本接口，有三个比较重要的子接口，List、Set、SortedList。而Map也是util包中的一个接口。

Hashtable和Hashmap都实现了Map接口，都采用key-value键值对取得数据。不同点：

* Hashmap采用非同步机制，必须调用Map m = Collections.synchronizedMap（hashMap）来达到同步的效果；而Hashtable采用同步机制，也就是说在一个时间点只能有一个线程可以修改哈希表，任何线程在执行hashtable的更新操作前需要获取对象锁，其他线程等待锁的释放。

---因此当有多个线程访问相同实例可能的时候，就应该采用Hashtable。反之在单线程访问的时候应该采用Hashmap，线程不安全的数据结构能带来刚好的性能。而且Hashmap有一个可以按插入顺序去除k-v对的子类LinkedHashMap，操作方便，多线程访问也可以采用Collections.synchronizedMap（hashMap）达到同步的目的，因此个人建议采用HashMap，相对灵活高效。

* Hashmap允许空值，也就是null作为key和value；

***

同上，Vector线程安全，同步了每一个方法，适用于多线程操作。而ArrayList线程不安全，但是高效，并且可以使用Collections.sychronizedList来实现同步，达到线程安全的目的，因此现在基本已经不推荐使用Veator类了。

***

而对于ArrayList和LinkedList的区别如下

* ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
* 对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
* 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
* 随机查找指定节点的操作get，ArrayList速度要快于LinkedList.

## 互现网部分:
1.  区别cookie和seesion。
一言以蔽之cookie是存储在客户端浏览器文件中的字符串。而Session是存储在服务器内容中的对象。

cookies会话保存在客户端浏览器中，主要用于标识用户和记录用户操作，比如用户的登录信息、浏览记录信息等。用户每次访问站点时，Web应用程序都可以读取cookie包含的信息。常用语用户的自动登录和购物车购物记录保存。

Session表示的是一个访问会话的过程。是基于访问会话的进程，记录了一个访问会话的开始到结束，当浏览器或进程关闭之后，session也就销除了。

两者都有过期时间的限制。

2.  区别HTTP协议中的POST和GET
简单说，Get是向服务器发索取数据的一种请求；而Post是向服务器提交数据的一种请求，要提交的数据位于信息头后面的实体中。

* get是把参数数据队列加到提交表单ACTION属性所指的URL中，值和表单内各个字段一一对应，在URL中可以看到。

* post是通过HTTP post机制，将表单内各个字段与其内容放置在HTML HEADER内一起传送到ACTION属性所指的URL地址。用户看不到这个过程。

3.  正则表达式找出HTML问中的图片链接。
我实在是记不住正则表达式负责的规则，当时就写了用JSoup或者HTTPParser可以很好的完成HTML文本解析的工作。

HTML中的图片链接格式为`<img src="{{site.imageurl}}/thank-you-xiaoyan.jpg" alt="alt text" width="390" height="245" />`

## 数据库部分：
{'fraction_non_alphanumeric': 0.11819021237303785, 'fraction_numerical': 0.02246845183133272, 'mean_word_length': 6.672963400236127, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3423708', 'n_tokens_mistral': 4289, 'n_tokens_neox': 4756, 'n_words': 261}