昨天面试一家公司的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了
网友评论