(据说)华为的一道面试题

刷微博,看到一道面试题:

先说一下思路

默认题意为不能取重复的数字

总体来说,就是从可行解空间[1,1]~[20,20]中,逐步过滤,找到最终答案的过程。说一下过滤步骤:

  1. 首先A不确定两个数字,所以两数之和sum满足:4<=sum<=38
  2. 其次B也不确定,所以两数之积的分解方式可能有多种(本来以为可以用质因子个数>2来判别的,但是后来发现还要考虑两数在1到20之间)
  3. A知道数字了,所以sum的所有分解方式中,只有一个是让B不能确定的,即i+j=sum,切i*j的分解方式不止一种
  4. 这一步比较难:B知道乘积prod,对于prod分解的所有可能,都能得到其和sum,如果sum的所有分解中,只有一个是让B不能确定的;而且prod的分解只有一个是满足此关系的。则当前的prod,以及对应的让B不能确定的prod分解,即为所求解。

1和2很容易理解。3的话,如果sum的诸多分解方式中,都能被B确定,即ij只能唯一分解,那B就不会说不知道数字了。如果sum的诸多分解方式中,有多个不能被B确定,那A在第三步就不能确定数字了,因为A不确定B是在哪一组ij中。

4,B知道乘积prod,假设可以分解为 I_n, J_n 。对于每一组 I_n, J_n:

和为sum=I_n+J_n,且A知道这个sum,这时B推测sum可以分解为i_n+j_n:
  由于3的结论,所以sum对应的i_n*j_n的分解不唯一的情况只有一个
  如果sum对应的i_n*j_n分解不唯一的情况为0个,那么B在第二步就可以猜出
  如果sum对应的i_n*j_n分解不唯一的情况多于1个,那么A在第三步就猜不出来了
在所有的 I_n, J_n 中,满足如上条件的只有一个
如果都满足上述条件的多于一个,那么B在最后一步就无法确定哪一组I_n,J_n是正确答案了

当然,第四步也是在第三步的结果上过滤的

阅读更多

LeetCode 25. Reverse Nodes in k-Group

本文为LeetCode 25. Reverse Nodes in k-Group的题解。

题意

给定一个链表,k个一组反转链表。

k 是一个正数,且小于链表长度。如果按照k个一组,最后剩下的不组k,则不反转剩下的元素。

例子:

对于链表: 1->2->3->4->5

k = 2, 应返回: 2->1->4->3->5

k = 3, 应返回: 3->2->1->4->5

注意:

  • 只允许O(1)的空间复杂度。
  • 不可以改变节点的值。
阅读更多

LeetCode:991. Broken Calculator

此文为LeetCode 991. Broken Calculator的题解。

题意

有一台坏掉的计算器,能够显示一个数字,我们可以对这个数字做两个操作:

  • 二: 将显示的数字乘以2, 或者;
  • 减一: 将显示的数字减1.

初始时,计算器显示数字 X.

返回要得到数字Y需要的最小操作次数。

题解

如果X>Y,则只能执行减一操作。否则,如果Y是奇数,则上一步操作一定是X减一;如果Y是偶数,则上一步操作只能是X乘二

只需要通过上述规则,由Y反推X即可。

代码

阅读更多

LeetCode:1106. Parsing A Boolean Expression

本文是LeetCode 1106. Parsing A Boolean Expression的题解。

题意

给定一个String类型的布尔表达式expression,返回一个求值的结果。

表达式可以是:

  • "t", 表示为 True;
  • "f", 表示为 False;
  • "!(expr)", 将内部的 expr 结果取反;
  • "&(expr1,expr2,...)", 将内部的expr1, expr2, ...求与;
  • "|(expr1,expr2,...)", 将内部的expr1, expr2, ...求或。

题解

直接递归解释表达式就好,每层负责解释上述的一个规则就可以。

这儿有一个优化点:实现表达式惰性求值。

代码

/**
* https://www.robberphex.com/parsing-a-boolean-expression/
* Runtime: 1 ms, faster than 100.00% of Java online submissions for Parsing A Boolean Expression.
* Memory Usage: 38 MB, less than 100.00% of Java online submissions for Parsing A Boolean Expression.
*/
class Solution {
class Result {
/**
* 表达式结果
*/
boolean res;
/**
* 下次解析的起始位置
*/
int end;

阅读更多

LeetCode 1103:Distribute Candies to People

本文为LeetCode 1103:Distribute Candies to People的题解。

题意

我们用下面的方法给num_people个人分发一些糖果:

我们给第一个人1块糖,给第二个人2块糖,以此类推,直到我们给最后一个人n块糖。

然后,我们回到开始,给第一个人n + 1块糖,给第二个人n + 2块糖,以此类推,直到我们给最后一个人2 * n块糖。

这个过程不断重复(当重新走到队首的时候,我们每次比上次多给n个糖果),直到糖果分配结束。最后一个人将收到我们所有剩余的糖果。

返回一个数组(长度为num_people),该数组表示最终每个人得到的糖果数量。

题解

首先我们考虑能完整的分发几轮。

由于分发数量总体上就是从1到n*num_people的等差序列,n符合如下不等式:

阅读更多

LeetCode题解:Path In Zigzag Labelled Binary Tree

本文为LeetCode 1104. Path In Zigzag Labelled Binary Tree 的题解。

题目描述

一棵无穷的二叉树,每个节点都编号(label)了:对于奇数层(第1、3、5等层),从左向右编号。对于偶数层,从右向左编号。但是每层的编号还是最小2^(level-1),最大2^level-1

如图:

给你一个编号(label),输出从顶层到该节点经过的节点编号。

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

阅读更多

如何找到一个可用端口?

很多场景中,我们确实需要找一个空闲端口,比如启动一个子进程监听指定端口,然后通过这个端口与之通信

然后实现方式就有很多了:

VSCode的实现

比如VSCode,就是逐个连接,如果某个端口连接失败,并且错误不是ECONNREFUSED的话,那么就说明这个端口可用。

function doFindFreePort(startPort: number, giveUpAfter: number, clb: (port: number) => void): void {
if (giveUpAfter === 0) {
return clb(0);
}

const client = new net.Socket();

// If we can connect to the port it means the port is already taken so we continue searching
client.once('connect', () => {
    dispose(client);

    return doFindFreePort(startPort + 1, giveUpAfter - 1, clb);
});

client.once('data', () => {
    // this listener is required since node.js 8.x
});

client.once('error', (err: Error & { code?: string }) => {
    dispose(client);

    // If we receive any non ECONNREFUSED error, it means the port is used but we cannot connect
    if (err.code !== 'ECONNREFUSED') {
        return doFindFreePort(startPort + 1, giveUpAfter - 1, clb);
    }

    // Otherwise it means the port is free to use!
    return clb(startPort);
});

client.connect(startPort, '127.0.0.1');

}

这种方式完全混淆了“端口可以被监听”和“端口不能连接”这两个语义,虽然现在Linux上述代码能够正常工作,但是保不准哪天新添加一个类似ECONNREFUSED这样的错误码呢。

vscode-mono-debug的实现

然后继续找,发现vscode-mono-debug的实现:通过不指定端口的方式listen,让操作系统分配端口:

阅读更多

我们为什么使用Linux内核的TCP栈

本文是 Why we use the Linux kernel’s TCP stack 的翻译。

最近,有一篇文章提出了一个非常有趣的问题,我们为什么使用Linux内核的TCP栈? 这在Hacker News上引发了非常有趣的讨论。

在CloudFlare工作的时候,我也一直在想这个问题。我的经验主要来自于和数千台生产机器打交道,我也会从这个角度来尝试回答这个问题。

CC BY 2.0 图片 来自 John Vetterli

让我们从一个更加宽泛的问题开始——跑起来一个操作系统是为了啥?如果你仅仅打算运行一个应用程序,那么运行数百万行代码的内核听起来绝对是一个负担。

但,我们通常都决定跑一个操作系统,有两个原因。第一,操作系统层提供了硬件独立性,以及很容易使用的API。这样,我们就可以为任何机器写代码了——不仅仅是当前运行代码的这种机器。第二,操作系统提供了时分复用层。这让我们能同时运行多个程序。不管它是另一个http服务,还是仅仅是一个bash会话,这种不同进程共享资源的能力是非常重要的。所有由内核暴露出来的资源都是能够被多个进程共享的!

用户态网络

对于网络栈,这也没什么不同。运行通用操作系统的网络栈,我们能够运行多个网络程序。如果为了运行用户态网络栈,而让单个应用程序独享网卡硬件,那就会丢失这种能力。将一个网卡分配给另一个程序,那么很可能就没法同时与服务器进行ssh会话了。

这听起来很疯狂,但这正是很多用户态网络栈所建议的。通用术语叫“全内核旁路”(full kernel bypass)。即绕过内核,用户态进程直接使用网络硬件 。

阅读更多

vscjava.vscode-java-debug 0.18.0的新特性!

微软为VSCode开发了一个Java调试器 Debugger for Java。之前用这个很不爽,还和微软的人吐槽过VSCode在debug java的时候,只能看到HashMap等java自带数据结构的物理视图,比如一个HashMap,在 0.17.0 版本下debug时,是这样的:

里面很多实现的细节,但是一般在debug的时候,我们比较关注的是这个HashMap里面存储了哪些东西等,而不是这种具体实现。

然后0.18.0就实现了HashMap的逻辑视图,就是只查看数据,而不查看实现的视图:

在调试的时候方便了很多啊。

然后再仔细看了下Debugger for Java 的Changelog,发现还有一个比较有用的更新:

Add the source hyperlinks for the stack traces in the Debug Console output.

比如异常打印的StackTrace,在0.17.0是这样的:

阅读更多