Fork me on GitHub

校招Java笔试题目

收集了部分宣讲会公司的校招笔试题目。

公司A笔试题目

读程序写结果

第一题

public class Main {
    static class NULL{
        public NULL(){
            System.out.println("Hello Construction method");
        }
        void print(){
            System.out.println("Hello print");
        }
    }
    public static void main(String[] args){
        ((NULL)null).print();
    }
}

运行结果:报NullPointerException类型错误

解析:null型是可以强制转换为任何类型的,所以(NULL)null是合法的,但是null强转之后是一个无效对象。print是一个非静态方法,故抛出空指针异常。若print为静态方法,即使null为无效对象,但调用静态方法无需创建对象,不需实例化,故输出Hello print,且不报错。

第二题

public class Main {
    static class Pet{
        static{
            System.out.println("Pet Static");
        }
        {
            System.out.println("Pet Non-Static");
        }
        public Pet(){
            System.out.println("Pet Construction method");
        }
        void print(){
            System.out.println("Pet Print");
        }
        static void eat(){
            System.out.println("Pet eat");
        }
    }
    static class Cat extends Pet{
        static{
            System.out.println("Cat Static");
        }
        {
            System.out.println("Cat Non-Static");
        }
        public Cat(){
            super();
            System.out.println("Cat Construction method");
        }
        void print(){
            System.out.println("Cat Print");
        }
        static void eat(){
            System.out.println("Cat eat");
        }
    }
    public static void main(String[] args){
        new Cat().print();
        new Pet().print();
        Cat.eat();
    }
}

运行结果:输出如下:

Pet Static
Cat Static
Pet Non-Static
Pet Construction method
Cat Non-Static
Cat Construction method
Cat Print

Pet Non-Static
Pet Construction method
Pet Print

Cat eat

为了方便查看,我在结果中多加了两行本不存在的空行。如运行结果所示,执行顺序为:

父类静态块>子类静态块>父类非静态块>父类构造方法>子类非静态块>子类构造方法>子类静态方法

如果只调用子类的静态方法,则:

父类静态块>子类静态块>子类静态方法

而且可以看出,静态块在实例时调用一次,在后来的实例调用中便不再执行。这是因为静态变量在内存中只有一个拷贝(节省内存),JVM只为静态分配一次内存,在加载类的过程中完成静态变量的内存分配。

问答题

forward与redirect的区别

forward(请求转发):是服务器请求资源,服务器访问目标url,把目标url的相应内容读取过来,再把这些内容发给浏览器。因为这个跳转是在服务器实现的,浏览器无法得知这部分内容的地址,所以浏览器的url地址未发生变化。

redirect(重定向):服务端发送一个状态码,浏览器据此去请求那个地址并获取显示新内容,所以浏览器的url地址发生了变化。

数据库查询问题(后续更新)

从一个大小为一千万的数组中找出最小的n个数(类似于TOPK问题)

这道题中处理数据量大,目标数据量适中,结合情况考虑,效率比较高的就是用最大堆来解决。

最大堆构建类:

public class MaxHeap {
    // 堆的存储结构 - 数组
    private int[] data;
    // 将一个数组传入构造方法,并转换成一个大根堆
    public MaxHeap(int[] data){
        this.data = data;
        buildHeap();
    }
    // 将数组转换成最大堆
    private void buildHeap(){
        // 完全二叉树只有数组下标小于或等于 (data.length) / 2 - 1 的元素有孩子结点,遍历这些结点。
        // *比如上面的图中,数组有10个元素, (data.length) / 2 - 1的值为4,a[4]有孩子结点,但a[5]没有*
        for (int i = (data.length) / 2 - 1; i >= 0; i--){
            // 对有孩子结点的元素heapify
            heapify(i);
        }
    }
    private void heapify(int i){
        // 获取左右结点的数组下标
        int l = left(i);
        int r = right(i);
        // 这是一个临时变量,表示 跟结点、左结点、右结点中最大的值的结点的下标
        int biggest = i;
        // 存在左结点,且左结点的值小于根结点的值
        if (l < data.length && data[l] > data[i])
            biggest = l;
        // 存在右结点,且右结点的值小于以上比较的较大值
        if (r < data.length && data[r] > data[biggest])
            biggest = r;
        // 左右结点的值都小于根节点,直接return,不做任何操作
        if (i == biggest)
            return;
        // 交换根节点和左右结点中最大的那个值,把根节点的值替换下去
        swap(i, biggest);
        // 由于替换后左右子树会被影响,所以要对受影响的子树再进行heapify
        heapify(biggest);
    }
    // 获取右结点的数组下标
    private int right(int i){
        return (i + 1) << 1;
    }
    // 获取左结点的数组下标
    private int left(int i){
        return ((i + 1) << 1) - 1;
    }
    // 交换元素位置
    private void swap(int i, int j){
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
    // 获取对中的最大的元素,根元素
    public int getRoot(){
        return data[0];
    }
    // 替换根元素,并重新heapify
    public void setRoot(int root){
        data[0] = root;
        heapify(0);
    }
}

数据的获取与处理:

public class TopK{
    public static void main(String[] args){    
        // 源数据
        int[] data = {56,275,12,6,45,478,41,1236,456,12,546,45};
        // 获取Topk
        int k=6;
        int[] topk = topK(data, k);
        //对获取后的数组进行排序,方便查看结果
        Arrays.sort(topk);
        for(int i=0;i<k;i++){
            System.out.println(topk[i]);
        }
    }
    // 从data数组中获取最大的k个数
    private static int[] topK(int[] data,int k){
        // 先取K个元素放入一个数组topk中
        int[] topk = new int[k];
        for(int i = 0;i< k;i++){
            topk[i] = data[i];
        }
        // 转换成最大堆
        MaxHeap heap=new MaxHeap(topk);
        // 从k开始,遍历data
        for(int i= k;i<data.length;i++){
            int root = heap.getRoot();
            // 当数据小于堆中最小的数(根节点)时,替换堆中的根节点,再转换成堆
            if(data[i] < root){
                heap.setRoot(data[i]);
            }
        }
        return topk;
    }
}

如果求的数是最大的n个数的话,则写成相应的最小堆就可以了

但是,这也有一个问题,就是笔试卷子上的空白部分根本写不下这么多啊,,,差不多就只够写topK的方法,emmmmmm,头疼

从一个字符串中找出出现频率最高的字符;若有多个字符出现次数相同,则输出最先出现的那个字符

static void printWord(String str){
        List<Character> list=new ArrayList<>();
        //先不重复记录元素
        Set<Character> set=new HashSet<>();
        for(int i=0;i<str.length();i++){
            set.add(str.charAt(i));
        }
        String tmpStr=str;
        Iterator<Character> iterator=set.iterator();
        int maxCount=-1;
        Character maxCharacter=null;
        //记录各个元素出现的次数
        Map<Character,Integer> map=new HashMap<Character,Integer>();
        while (iterator.hasNext()){
            //依次获取set中的元素
            Character chara=iterator.next();
            int count=0;
            int index=-1;
            //查询字符在字符串中的位置,若不为-1,则表明存在,然后截取当前位置至末尾位置的字符串,继续查询,直至不存在
            while ((index=tmpStr.indexOf(chara))!=-1){
                count+=1;
                tmpStr=tmpStr.substring(index+1);
            }
            map.put(chara,count);

            if(count>maxCount){
                maxCharacter=chara;
                maxCount=count;
            }

            tmpStr=str;
            count=0;
        }
        //找出记录最高次数的字符组
        iterator=set.iterator();
        while (iterator.hasNext()){
            Character chara=iterator.next();
            if(map.get(chara)==maxCount){
                list.add(chara);
            }
        }
        //对字符组各个元素出现的位置进行重记录并排序
        Map<Integer,Character> indexMap=new HashMap<>();
        for(int i=0;i<list.size();i++){
            indexMap.put(str.indexOf(list.get(i)),list.get(i));
        }
        Map<Integer,Character> sortMap=new TreeMap<>(indexMap);
        for(Map.Entry entry:sortMap.entrySet()){
            System.out.println("Key:"+entry.getKey()+";Value:"+entry.getValue());
        }
    }

这道题主要考查各种集合类(或称容器类)的特点及用法,要灵活应用各种集合类之间的转换。

集合类统分为两大类:

1、Collection:独立元素序列
注:collection是一个集合接口,而collections是一个包装类

(1)List接口
1)LinkedList类
允许null元素。提供额外的get、remove、insert方法,发生在首尾部。可用作堆栈(stack)、队列(queue)或双向队列(deque)。
2)ArrayList类
允许所有元素。
两个list均为非同步,若多线程同时访问一个list,须自己实现访问同步
3)Vector
类似于ArrayList,但是是同步的。
4)Stack类
继承于Vector,可实现后进先出的堆栈。
(2)Set接口
Set是一种不包含重复元素的Collection,包括最多只有一个null元素。
容器类主要有HashSet和TreeSet。
1)HashSet
不允许出现重复元素。不保证元素的插入顺序不变,会有混乱情况。允许有null元素但最多有一个。
2)TreeSet
这个类的元素会按照“升序”自动排列元素。

2、Map:一组成对的键值对对象
Map提供key到value的映射。同一个map中不能包含相同的key,且一个key只能映射一个value。

(1)Hashtable类
实现一个key-value映射的哈希表。任何非空对象都可以作为key或value。添加数据使用put(key,value),取出数据使用get(key)。
此处涉及到了HashCode。简要说明:使用自定义的类作为key时,两个实例化的对象的HashCode不一定相同,即使看起来内容是一样的,但在存放为key时,很可能会作为两个不同的对象存放(equal结果为false)。而两个不同的对象,HashCode值也有可能是一样的,又可能作为一个对象存放(equal结果为true)。这种现象称为冲突。(详见标签页)
(2)HashMap类
两类的区别:(详见标签页)
1)继承不同(即父类不同)
2)HashTable中的方法是同步的,而HashMap缺省情况下是非同步的,需自己另写同步方法
3)HashTable中,任意键不允许出现null值。HashMap中,null可作为key但只有一个;null可作为value且存在多个。所以HashMap判断某键是否存在使用containsKey()方法,万不能使用get()方法。
4)遍历方式不同
5)HashCode使用不同
6)两类实例化的数组的初始化大小及扩容速度不同

公司B笔试题目

在浏览器中输入网址后,浏览器、个人电脑、网络、服务器都发生了什么?详细描述

这个问题是一个比较难的问题,真要细致答起来面非常广。用谷歌一查,很多答案都很详细,甚至涉及到了电路,还有各种网络协议……

其中大家最推崇的一篇解答是外文的,虽然我不能完全解读,但还是贴一下这篇文章《What really happens when you navigate to a URL》

所以还是回归到问题,在不尽量涉及很深度的情况下,知乎这个问题下的一些答案有趣又不失专业,我依个人的理解加以概括一下。

步骤1:访问本地缓存

要想访问网页,必须先获取到域名所对应的服务器的IP地址。这里的本地缓存包括三个:浏览器缓存、系统的hosts文件和本地DNS解析器的缓存。浏览器会先访问自身缓存,再访问hosts文件,最后访问本地DNS解析器的缓存。在这步中,如果获取到了IP地址,则直接跳到第4步;如果没有,则进行下一步。

步骤2:本地DNS解析器

这一步,浏览器向本地DNS解析器发送一个递归循环的查询请求。本地DNS解析器,是TCP/IP参数中设置的首选DNS服务器。解析器在收到查询后,对本地配置区域资源进行查询,如果域名包含在其中,则返回IP地址;如果没有,本地DNS解析器再对包含网址映射关系的缓存进行解析,如果有,则调用这个IP地址映射,但此解析不具有权威性。

步骤3:网络DNS服务器

因为这一步涉及到了三种DNS服务器,分别为根DNS服务器,顶级DNS服务器和权威DNS服务器,所以我直接概括为网络DNS服务器。

这一步,本地DNS服务器向上一级的DNS服务器发送的是迭代循环的查询请求。每一级DNS服务器对域名进行解析,如果不能解析,则向该级的上一级DNS服务器转发请求,直至得到解析。最后将IP地址返回给本地DNS解析器,再返回给浏览器。

步骤4:与服务器建立连接

浏览器将一些信息封装为一个http请求,这个请求里包含了求的方法GET,请求的路径“/”,请求的主机名,客户机的类型以及一些其他的信息。

接下来就是建立连接,即有名的“三次握手”。客户机的TCP进程向服务器主机发送一个创建连接的SYN请求。当服务器主机收到请求后,如果请求的端口号正在等待连接,则会为这一条TCP连接分配资源,并发送一个SYNACK报文段作为应答。客户机收到报文段,也为该连接分配资源。此时,连接已经建立。客户机向服务器主机再发送另一个报文段,对允许连接的报文段进行确认,这就是“三次握手”。而http请求,则在第三次发送请求的时候携带发送。

步骤5:服务器处理请求

这部分对应的就是后端了。服务器根据请求,将请求的信息也封装为一段http报文,返回给客户机。这段http报文,应该是一段包含了HTML、CSS、JS和图片等信息的内容。

步骤6:浏览器解析内容渲染页面

哎,个人最讨厌网页了,详细的内容我就直接将别人的贴在这里吧。

浏览器如何渲染网页

请说明一下乐观锁与悲观锁

如何确保N个线程可以访问N个资源同时又不导致死锁

Unicode与UTF-8的联系与区别

简明扼要:Unicode是包括了世界上几乎所有已知符号的字符集,而UTF-8是针对Unicode在网上传输数据时的一种编码规则。

请用两个stack完成queue的入列出列

这个理解起来并不难,好比两摞硬币,第一摞硬币作为队头部分,将第二摞硬币倒转过来叠在第一摞硬币下面,那么,下面的那部分硬币就是队尾部分。此时,入列就是下面那一摞硬币的压栈,出列就是上面那一摞硬币的入栈。

Java代码:

import java.util.Stack;
public class StackToQueue {
    static Stack<Integer> stack1 = new Stack<Integer>();
    static Stack<Integer> stack2 = new Stack<Integer>();

    public void add(int node) {
        stack1.push(node);
    }

    public int remove() {
        if(stack2.isEmpty()){//pop时如果stack2为空则将stack1内元素倒置入stack2,取栈顶元素;
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

有2N+1个小于1万的数组,其中有2N个数为对,只有一个数与其他数完全不同,请找出这个数

这道题的答案让我大开眼界,或者说是我自己在学习的过程中忽视了很多最根本的东西吧。这道题采用了异或运算,短短四行代码,即可找出唯一的那一个数。

Java代码:

public static int getUnique(int[] A){
        int temp=0;
        for(int item:A)
            temp^=item;
        return temp;
    }

这道题的原理是利用数组里面的所有数的异或运算来找出不一样的那个数。那在这之前,我先复习一下异或运算是怎么计算的。

比如说3和6,表示为3^6。在运算的时候,要先把这两个数转换为二进制。那么3就是0011,6就是0110。
然后将这两个二进制数放在两行比较。

0011
0110

这就是计算机进行异或运算的根本了,对位进行异或运算,得出结果。规则中,0^1=1^0=1,0^0=1^1=0。这样,上面两个二进制数的异或运算结果就是0101,转换为十进制数,也就是5。所以3^6=5。

明白了怎么运算,那么第二个问题,为什么全部循环异或运算一遍就能筛出那个数呢?

我在过程中把每一次的运算结果输出了一遍,毫无规律,没想出原因。但放在整个循环看了一下,写成数学运算公式就很清楚了。整个循环的运算合起来就是:

1^2^3^4^5^1^2^3^4

异或运算中存在交换律,即A^B=B^A,所以上式可以转换为:

1^1^2^2^3^3^4^4^5

这样一来,就明白了。在计算的过程中,其他的数都相抵为0,只剩下一个5,0^5=5。所以,就轻松筛选出来了。

发散思考:1、如果题目是共有3N+1个数,其中为N组出现了3次的数,只有一个数不一样,那怎么办呢?

这道题还是可以利用二进制数的关系来做。把所有数转换为二进制,然后对所有数的所有位1出现的次数进行统计,然后再对每个位的统计得数进行除3判断。此时定义一个为0的结果数,如果为0,则说明该位上不存在那个单数的二进制数的位数,如果不为0,则将该位进行相应的位运算,加到结果数上,最后得出的结果就是该单数。

Java代码:

public static int singleNumber(int[] A){
        int bits[] =new int[32];
        for(int i=0;i<bits.length;i++){
            bits[i]=0;
        }
        for(int i=0;i<A.length;i++){
            for(int j=0;j<bits.length;j++){
                bits[j]+=((A[i]>>j)&1);         //进行位运算,并判断这个位上是否为1,是1则数组相应位加1
            }
        }
        int result=0;
        for(int i=0;i<32;i++){
            if(bits[i]%3 !=0)
                result+=(1 << i);
        }
        return result;
    }

据此得出经验:如果组数个数为偶数,采取异或运算;如果个数为奇数,则对求余的除数进行改变就行了。

2、如果题目是让我们寻找2个呢?

思路:分组异或

还是先按位运算,运算出最后结果时,得到的那个数的二进制数的位数为“1”的位上,就是那两个数的异或运算结果。假设数组为1,2,3,4,1,2,3,4,5,6,最后运算的结果为3,二进制数为0011,那么按照1出现的位数,我们将这个数组分为两个数组,第一组是二进制数末尾为1的数,有1,3,1,3,5,第二组是二进制数倒数第二位为1的数,只有一个6,然后每组再进行异或运算,得到的两个数就是结果了。

Java代码:

public class Solution {
    public void findNumsAppearOnce(int[] array, int[] num1, int[] num2)    {
        int length = array.length;
        if(length == 2){
            num1[0] = array[0];
            num2[0] = array[1];
            return;
        }
        int bitResult = 0;
        for(int i = 0; i < length; ++i){
            bitResult ^= array[i];
        }
        int index = findFirst1(bitResult);
        for(int i = 0; i < length; ++i){
            if(isBit1(array[i], index)){
                num1[0] ^= array[i];
            }else{
                num2[0] ^= array[i];
            }
        }
    }

    private int findFirst1(int bitResult){
        int index = 0;
        while(((bitResult & 1) == 0) && index < 32){
            bitResult >>= 1;
            index++;
        }
        return index;
    }

    private boolean isBit1(int target, int index){
        return ((target >> index) & 1) == 1;
    }
}

设数字1映射字符a,2映射b,如此类推,26映射z。那么给出一个数字串,请尽可能写出这个数字串的所有可能

这道题的关键在于,对给出的数字串,如何进行多种分割方法。比如说给出一个“111111”数字串,它的分割组合就有13种:

1 1 1 1 1 1        aaaaaa
11 1 1 1 1        kaaaa
1 11 1 1 1        akaaa
1 1 11 1 1        aakaa
1 1 1 11 1        aaaka
1 1 1 1 11        aaaak
11 11 1 1        kkaa
11 1 11 1        kaka
11 1 1 11        kaak
1 11 11 1        akka
1 11 1 11        akak
1 1 11 11        aakk
11 11 11        kkk

问题分为两个部分:1、怎么去分割得到两位数

标记一位数分割点和两位数分割点
对分割点进行组合

2、分割的时候如何控制分割次数

海盗博弈

这道题很有意思,有意思在它的结果与我的直觉中的答案大相径庭,所以我特意放上来,供玩乐一下。

题目内容:五个聪明绝顶却又很贪婪的海盗A,B,C,D,E得到了100金币。他们为了分这些金币,讨论出一个方案:从A开始,A要提出一个分金币的方案,如果这个方案得到了超过一半的票数,包括提议人的票,那么这个方案可以执行,否则A就要被扔到大海里喂鲨鱼,然后再由B来提一个方案。规则如上,以此类推。那么在每个人都想活命又想拿到最多金币的情况下,A应该如何分配金币呢?

在笔试的时候,我想起来这道题目似乎在《秦时明月之天行九歌》中出现过,只不过那里是三妾分金。这里的道理也是一样的。直觉上来看A为了得到大多数票,会把金币分给更多的人,自己只拿少量的金币。但仔细分析,却不是这样。这道题需要从末位分析。

末位是怎样的呢?E一个人的情况自不用分析。那么D、E呢?当只剩下D、E的时候,只要E坚持否决D的方案,D就会被喂鲨鱼,E就能拿到全部的金币。D为了活命,肯定不能让C死掉。C在明白D的意图的情况下,即使提出100,0,0的方案,D也只能赞同,不会否定。类推,B也明白C的意图,所以,B会想收买D、E,得到这两个人的票,所以,B会提出98,0,1,1的方案。相比C的方案,D、E明白自己已经占到了便宜,所以会赞同B的方案。那么最后,A在这个方案上,只要多花一点金币,拿到两个人的票就行了,那么A选谁呢?C是肯定要收买的,因为他的收买费只要一个金币,剩下只要花两个金币从D或E手里买一票就行了。所以最后,A的解决方案是97,0,1,2,0或97,0,1,0,2。

花絮:笔试完回到寝室,我跟小伙伴分享了这道题,大家各抒己见,但在一些小细节上产生了分歧。比如说,D只要提出0,100的分金币方案,E就不会杀D了啊,要是这样E你都杀D是不是太犯贱了啊;如果这样D能活的话,剩下后三个人的时候,C提出的方案应该是0,100,0,毕竟人家D能活,万一D心情不爽,投了一票反对票,你C不就死翘翘了么;…………;最后的参考答案因为有98,0,1,1,0或98,0,1,0,1的存在,小伙伴说,怎么可能有这种答案,D或E会觉得,卧槽,这方案跟B比,我根本没占到什么便宜啊,还被A你摆了一道脸色,不,我心情不爽,才不赞同A的方案,我就是要搞死你等等。然后那天晚上就跑题了,小伙伴就装逼会不会死的问题争论了两个半小时233333,对此我只能说:

-------------本文结束感谢您的阅读-------------