一家小公司android实习岗

昨天面试一家公司的android实习岗，竟然有一轮笔试和两轮面试。
笔试题：1.有一百万个整数，其中大概90%在区间[0,1000]内，剩下的在(1000,2147483648]之间。对这些数进行从小到大排序。

这道题当时没有想出什么好的方法，于是手写了一个归并排序上去，然后第一轮的面试官告诉我用桶排序，然而我之前只是听过并不了解。问我归并排序的时间复杂度。

2.将一个数组中的0全部放到数组的底部而不改变其他元素的顺序，要求空间复杂度为O（1）
我当时想的是限制了空间复杂度的话肯定不能创建新的数组了，所以我写了一个冒泡排序的改版，把所有0全部沉底了，然后问我这个算法的复杂度，我说是O（n2），然后问我有没有更快的，我说那用堆排序。他问我堆排序的复杂度，我说是O（nlogn），然后问我有没有O(n)的方法，我想不到就作罢了。

刚刚想出来了给一下答案：

public static void sort(int a[])
{    
    int numOfNotZero=0;    
    for( int i=0;i<a.length;i++)
  {        
       if (a[i] != 0)
    {         if (i != numOfNotZero)
       {           
              a[numOfNotZero] = a[i];           
        }            
           numOfNotZero++;       
    }   
  }    
    for(int i=numOfNotZero;i<a.length;i++)   
  {        
      a[i] = 0;    
  }
}

第一轮面试
1.图片的三级缓存是怎么实现的
2.软件升级时，数据库也发生了变动，怎么处理数据库同步？
3.说一说其中一个项目是怎么实现的
4.handle和service的区别
5.arraylist和LinkList的区别
6.httpclient的具体实现

第二轮面试：
1.图片三级缓存中的LRU算法是怎么实现的？
2.handle和Thread的区别
3.handle和service的区别
4.线程和service的区别
5.重写和重载的区别
6.面向对象的特性
7.接口的优势

然后就gg了