去哪儿 2021届春招JAVA笔试真题

选择题

1、工程师小驼准备在自己的服务中调用发送邮件验证码服务,但是当他访问API平台的时候,发现了两个一摸一样的api, /api/sendemailcode 但是这个服务提供了一个GET 方法接口和一个POST方法接口.同学们,如果你是小驼,那么如下四种说法,哪些可能是正确的 (A)

A.同一个业务意义的方法不可能同时是GET方法又是POST方法,所以这两者必有一个是错误的
B.这两个方法可能都是对的,需要根据业务场景进行选择,具体应咨询研发工程师
C.这个方法每调用一次,返回的code都不一样,所以应该保留GET方法
D.这个方法的语义是读取而不是操作,所以应选择POST方法
E.这个业务方法使用GET或POST两种方法都是不正确的,应该选择OPTIONS方法来实现

2、fastjson是近些年常用的一种序列化反序列化实用工具, 这个被国人广泛应用的工具是由我国工程师“温少”以一己之力开发并维护的.在2020年,这个工具被黑客攻击并多次得逞, 温少也毫不退缩,与黑客斗智斗勇,终于在2020年底摆平了黑客.

下面我们对温少着重修改的一段代码进行赏析,并判断以下哪些说法是正确的.(A,B)

    public Class checkAutoType(String typeName, Class expectClass, int features) {
        if (typeName == null) {
            return null;
        }
        if (autoTypeCheckHandlers != null) {
            for (AutoTypeCheckHandler h : autoTypeCheckHandlers) {
                Class type = h.handler(typeName, expectClass, features);
                if (type != null) {
                    return type;
                }
            }
        }
        final int safeModeMask = Feature.SafeMode.mask;
        boolean safeMode = this.safeMode
                || (features & safeModeMask) != 0
                || (JSON.DEFAULT_PARSER_FEATURE & safeModeMask) != 0;
        if (safeMode) {
            throw new JSONException("safeMode not support autoType : " + typeName);
        }
        if (typeName.length() >= 192 || typeName.length() < 3) {
            throw new JSONException("autoType is not support. " + typeName);
        }
…
}

A. typeName.length() >= 192 中的192并不是好的写法,因为没有体现数字所代表的业务意义,最好可以用常量进行定义
B.我们通常会用掩码来屏蔽对于代码逻辑中不重要的部分,以提升程序的整体运行效率.
C.依赖这个方法的下游API不需要对NULL进行处理,因为整个checkAuto Type方法不会返回NULL
D.从程序中可以看出, 处于安全模式是autoType功能可用的前提条件
E.掩码使用 & 与 ^ 与原值进行操作都是可以的, 得到的结果都是一样的

3、JDK8中，下面说法正确的有哪些?(C，D)

A.Java类装载器装载一个类时，先从自身ClassLoader寻找目标类，如果找不到类，再从父ClassLoader中寻找
B.如果实现了一个java.lang.String基础类，那么工程中所有引用java.lang.String类的代码都将自动引用这个新类实现
C.任意一个类，如果重写了equals方法，则必须重写hashcode方法。
D.interface的default 方法关键字是从JDK8版本开始引入的

4、观察下面两段代码并回答问题:

代码片段1

    private void method1(Node head) {
        Set data = new HashSet();
        while (head.next != null) {
            data.add(head.data);
            head = head.next;
            if (data.contains(head.data)) {
                System.out.println(“结果“);
                break;
            }
        }
    }

代码片段2:

    private void method2(Node head) {
        Node p1, p2;
        p1 = head.next;
        p2 = head.next.next;
        while (!p1.data.equals(p2.data)) {
            if (p2 == null || p2.next == null) {
                return;
            }
            p1 = p1.next;
            p2 = p2.next.next;
        }
        System.out.println(“结果”);
    }

请同学们判断哪些说法是正确的(D):

A.method1 与 method2 的业务含义并不相同, 分别适用于不同的数据结构
B.method1 与 method2 业务含义相同,但 method1 的时间复杂度为 O(n),性能更为突出
C. 这两个方法通常用于二叉树遍历, method2性能更佳
D. 从解决问题的角度看, method2 通常是性能更佳的解

5、90后的朋友们对一款叫做《三国杀》的卡牌游戏都很熟悉。这个游戏每个玩家需要选择一个人物，原则上，每个玩家在轮到自己抓牌时可以抓两张牌，但是其最基础的版本中有两个人物可以有机会在摸牌阶段多抓牌，分别是周瑜，他的技能英姿可以在抓牌开始阶段抓3张牌，另一个人物是甄姬，她的技能洛神可以从卡牌顶部翻牌，当拿到黑色花色的牌的时候，拿走这张牌，继续抓牌，当拿到红色花色的牌的时候，这样牌要扔掉，同时再抓两张手牌。假设2名玩家，一名选择甄姬、一名选择周瑜，背扣的卡牌有104张，分别为52张黑色牌和52张红色牌，那么在这种情况下，周瑜抓牌和甄姬抓牌相比，谁在抓牌后获得更多手牌的可能性更大？下面哪些说法是正确的？(A)

A.周瑜
B.甄姬
C.随着抓牌回合数增加，甄姬的累积抓牌量更大
D.随着抓牌回合数增加，累积抓牌量趋近一样多

6、请大家阅读下面的说明文档,并回答问题:

public class ThreadPoolExecutor
extends AbstractExecutorService
An ExecutorService that executes each submitted task using one of possibly several pooled threads, normally configured using Executors factory methods.
Thread pools address two different problems: they usually provide improved performance when executing large numbers of asynchronous tasks, due to reduced per-task invocation overhead, and they provide a means of bounding and managing the resources, including threads, consumed when executing a collection of tasks. Each ThreadPoolExecutor also maintains some basic statistics, such as the number of completed tasks.
To be useful across a wide range of contexts, this class provides many adjustable parameters and extensibility hooks. However, programmers are urged to use the more convenient Executors factory methods Executors.newCachedThreadPool() (unbounded thread pool, with automatic thread reclamation), Executors.newFixedThreadPool(int) (fixed size thread pool) and Executors.newSingleThreadExecutor() (single background thread), that preconfigure settings for the most common usage scenarios. Otherwise, use the following guide when manually configuring and tuning this class:
Core and maximum pool sizes
A ThreadPoolExecutor will automatically adjust the pool size (see getPoolSize()) according to the bounds set by corePoolSize (see getCorePoolSize()) and maximumPoolSize (see getMaximumPoolSize()). When a new task is submitted in method execute(java.lang.Runnable), and fewer than corePoolSize threads are running, a new thread is created to handle the request, even if other worker threads are idle. If there are more than corePoolSize but less than maximumPoolSize threads running, a new thread will be created only if the queue is full. By setting corePoolSize and maximumPoolSize the same, you create a fixed-size thread pool. By setting maximumPoolSize to an essentially unbounded value such as Integer.MAX_VALUE, you allow the pool to accommodate an arbitrary number of concurrent tasks. Most typically, core and maximum pool sizes are set only upon construction, but they may also be changed dynamically using setCorePoolSize(int) and setMaximumPoolSize(int).
On-demand construction
By default, even core threads are initially created and started only when new tasks arrive, but this can be overridden dynamically using method prestartCoreThread() or prestartAllCoreThreads(). You probably want to prestart threads if you construct the pool with a non-empty queue.
Creating new threads
New threads are created using a ThreadFactory. If not otherwise specified, a Executors.defaultThreadFactory() is used, that creates threads to all be in the same ThreadGroup and with the same NORM_PRIORITY priority and non-daemon status. By supplying a different ThreadFactory, you can alter the thread's name, thread group, priority, daemon status, etc. If a ThreadFactory fails to create a thread when asked by returning null from newThread, the executor will continue, but might not be able to execute any tasks. Threads should possess the "modifyThread" RuntimePermission. If worker threads or other threads using the pool do not possess this permission, service may be degraded: configuration changes may not take effect in a timely manner, and a shutdown pool may remain in a state in which termination is possible but not completed.
Keep-alive times
If the pool currently has more than corePoolSize threads, excess threads will be terminated if they have been idle for more than the keepAliveTime (see getKeepAliveTime(java.util.concurrent.TimeUnit)). This provides a means of reducing resource consumption when the pool is not being actively used. If the pool becomes more active later, new threads will be constructed. This parameter can also be changed dynamically using method setKeepAliveTime(long, java.util.concurrent.TimeUnit). Using a value of Long.MAX_VALUE TimeUnit.NANOSECONDS effectively disables idle threads from ever terminating prior to shut down. By default, the keep-alive policy applies only when there are more than corePoolSizeThreads. But method allowCoreThreadTimeOut(boolean) can be used to apply this time-out policy to core threads as well, so long as the keepAliveTime value is non-zero.
Queuing
Any BlockingQueue may be used to transfer and hold submitted tasks. The use of this queue interacts with pool sizing:
If fewer than corePoolSize threads are running, the Executor always prefers adding a new thread rather than queuing.
If corePoolSize or more threads are running, the Executor always prefers queuing a request rather than adding a new thread.
If a request cannot be queued, a new thread is created unless this would exceed maximumPoolSize, in which case, the task will be rejected.
There are three general strategies for queuing:
Direct handoffs. A good default choice for a work queue is a SynchronousQueue that hands off tasks to threads without otherwise holding them. Here, an attempt to queue a task will fail if no threads are immediately available to run it, so a new thread will be constructed. This policy avoids lockups when handling sets of requests that might have internal dependencies. Direct handoffs generally require unbounded maximumPoolSizes to avoid rejection of new submitted tasks. This in turn admits the possibility of unbounded thread growth when commands continue to arrive on average faster than they can be processed.
Unbounded queues. Using an unbounded queue (for example a LinkedBlockingQueue without a predefined capacity) will cause new tasks to wait in the queue when all corePoolSize threads are busy. Thus, no more than corePoolSize threads will ever be created. (And the value of the maximumPoolSize therefore doesn't have any effect.) This may be appropriate when each task is completely independent of others, so tasks cannot affect each others execution; for example, in a web page server. While this style of queuing can be useful in smoothing out transient bursts of requests, it admits the possibility of unbounded work queue growth when commands continue to arrive on average faster than they can be processed.
Bounded queues. A bounded queue (for example, an ArrayBlockingQueue) helps prevent resource exhaustion when used with finite maximumPoolSizes, but can be more difficult to tune and control. Queue sizes and maximum pool sizes may be traded off for each other: Using large queues and small pools minimizes CPU usage, OS resources, and context-switching overhead, but can lead to artificially low throughput. If tasks frequently block (for example if they are I/O bound), a system may be able to schedule time for more threads than you otherwise allow. Use of small queues generally requires larger pool sizes, which keeps CPUs busier but may encounter unacceptable scheduling overhead, which also decreases throughput.
Rejected tasks
New tasks submitted in method execute(java.lang.Runnable) will be rejected when the Executor has been shut down, and also when the Executor uses finite bounds for both maximum threads and work queue capacity, and is saturated. In either case, the execute method invokes the RejectedExecutionHandler.rejectedExecution(java.lang.Runnable, java.util.concurrent.ThreadPoolExecutor) method of its RejectedExecutionHandler. Four predefined handler policies are provided:
In the default ThreadPoolExecutor.AbortPolicy, the handler throws a runtime RejectedExecutionException upon rejection.
In ThreadPoolExecutor.CallerRunsPolicy, the thread that invokes execute itself runs the task. This provides a simple feedback control mechanism that will slow down the rate that new tasks are submitted.
In ThreadPoolExecutor.DiscardPolicy, a task that cannot be executed is simply dropped.
In ThreadPoolExecutor.DiscardOldestPolicy, if the executor is not shut down, the task at the head of the work queue is dropped, and then execution is retried (which can fail again, causing this to be repeated.)
It is possible to define and use other kinds of RejectedExecutionHandler classes. Doing so requires some care especially when policies are designed to work only under particular capacity or queuing policies.

请同学们阅读完毕后在下面的选项中找到那些是正确的选项():

A. ThreadPoolExecutor 是一款线程池组件(A, D)
B. 在无界队列策略下, 线程池可以创建的线程数大于核心线程数,但小于最大线程数
C. 直接传递模式下, 等待队列是无限长的, 有因为等待队列过长而导致内存溢出的风险
D. 在无界队列策略下,当核心线程耗尽后,待执行任务会先进入等待队列,待等待队列长度超过最大值后, 再建立新的线程,直到达到最大线程数

编程题

1、给定一个数组，求数组中重复次数第K多的那个元素。

时间复杂度：O(nlogn)
空间复杂度：O(n)

输入：arr = [1,3,3,7,2,3,3,2,2,8] k=2
输出：2

2、在某个对数字进行加密的系统，对于x位的数字，会对中间的[start, end)位改为大小写敏感的字母后存储，start最小为0，从左边开始数。

比如11位的电话号码，会对第[3, 7)进行加密，12312340000加密为123AbCd0000，结果一次操作操作失误把号码的所有字母都转换成了小写，比如123AbCd0000变成了123abcd0000。给出x, start, end和一个操作失误后的号码，求所有可能的操作失误前的号码。

时间限制：1000ms
输入：x start end 操作失误后的号码（以空格分隔）
输出：每行一个可能的操作失误前的号码
输入样例：
11 3 7 123abcd0000

输出样例
123abcd0000
123abcD0000
....
123ABCD0000

3、去哪网酒店后端报价数据存储格结构如以下格式所示：

2021-05-01～2021-05-02:188表示2021-05-01入住，2021-05-02离店，入住一天的价格是￥188。
现有多组这样的日期价格段，请将其合并，合并的规则如下：
1)价格相同，日期段相邻或者重叠的需要合并
2)相同日期的价格已后面录入的为准
例子1：
2021-08-01～2021-08-31:388
2021-08-25～2021-09-30:388
合并后就是
2021-08-01～2021-09-30:388
例子2：
2021-08-01～2021-12-31:388
2021-10-01～2021-10-07:588
合并之后就是
2021-08-01～2021-10-01:388
2021-10-01～2021-10-07:588

2021-10-07～2021-12-31:388

输入： 2021-05-09~~2021-05-24:788,2021-05-11~~2021-05-20:1088,2021-01-20~~2021-01-28:1088,2021-01-03~~2021-01-21:888,2021-03-11~~2021-03-20:188,2021-05-18~~2021-05-19:788,2021-06-16~~2021-06-25:188,2021-04-24~~2021-04-26:788,2021-03-06~~2021-03-12:788,2021-01-14~~2021-01-22:588,2021-05-07~~2021-05-19:888,2021-06-15~~2021-06-23:788,2021-04-15~~2021-04-19:788,2021-04-16~~2021-04-26:488,2021-04-15~~2021-04-24:188,2021-04-05~~2021-04-22:1088,2021-02-06~~2021-02-15:688,2021-06-17~~2021-06-25:588,2021-05-14~~2021-05-17:788,2021-02-12~~2021-02-20:988,2021-01-12~~2021-01-22:288,2021-03-01~~2021-03-15:188,2021-04-25~~2021-04-28:488,2021-02-13~~2021-02-26:388,2021-03-26~~2021-03-27:988,2021-06-10~~2021-06-18:388,2021-01-07~~2021-01-13:188,2021-04-16~~2021-04-20:688,2021-03-18~~2021-03-24:988,2021-05-20~~2021-05-26:288,2021-06-18~~2021-06-25:888,2021-03-25~~2021-03-27:788,2021-06-14~~2021-06-20:1088,2021-04-12~~2021-04-17:788,2021-04-10~~2021-04-27:188,2021-03-26~~2021-03-28:588,2021-02-22~~2021-02-24:588,2021-05-11~~2021-05-26:188,2021-01-05~~2021-01-27:988,2021-04-18~~2021-04-25:1088