Interview Experiences

待字闺中

1.最少插入字符

题目 给定字符串,可以通过插入字符,使其变为回文。求最少插入字符的数量。

例如:
ab最少插入1个字符,变为*b*ab
aa最少插入0个字符
abcd最少插入3个字符,*dcb*abcd

分析 递归式为: > fmi(str, l, r) = (str[l] == str[r]) ? fmi(str, l+1, r-1) : (min(fmi(str, i+1, r), fmi(str,l, r-1))+1)

通过上面的式子,有经验的、熟练的同学,很直接的就能看出来,存在重复的子问题,这就意味着,我们可以将子问题的解缓存使用。如果,没有直接能够看出来的同学们,还是可以按照我们之前的方法,把递归树画出来吧,那样更加一目了然。

Dynamic Programming Time: O(n^2), Space: O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* M[j][i] = the minimum number of chars to insert of substring S[j...i];
* Base case:
* M[0][0] = 0;
* Induction rule:
* M[j][i] = s[i] == s[j] ? M[j+1][i-1] : min(M[j+1][i], M[j][i-1]) + 1;
*/
int fmiDP(String S) {
int length = S.length();
int[] M = new int[length][length];
for (int i = 1; i < length; i++) {
for (int j = i - 1; j >= 0; j--) {
M[j][i] = s.charAt(i) == s.charAt(j) ? M[j + 1][i - 1] : Math.min(M[j + 1][i], M[j][i - 1]) + 1;
}
}
return M[0][length-1];
}


2.数对数目

题目 给定两个数组X和Y,元素都是正数。请找出满足如下条件的数对的数目: $ x^y > y^x $, 即x的y次方>y的x次方, x来自X数组,y来自Y数组

[思考5分钟~]

分析 假设数组X的长度为m,数组Y的长度为n 最直接的暴力法,时间复杂度为O(m*n),但这样的话,并不需要都是正数这个条件的。那么,我们该如何优化呢?

\(x^y > y^x\),对于x和y来讲,有什么规律呢?该如何发现呢? 这里其实有规律的,大多数的条件下,当 y > x 的时候,\(x^y > y^x\),但是有一些例外: 1,2,3,4几个数,需要特殊的考虑,比如24=42。这个大家可以通过在纸上写写画画来得到,相对繁琐,我们就不进一步分析了。

我们可否对于原式做一些数学变换呢?使得式子变化简单。如何去做呢? 这个式子的复杂体现在两边都是指数的形式,如何变化一下呢?我们很自然的就想到,逆运算对数运算。则,两边取对数可得: $log_ x^y > log(y^x) $ ---> \(ylog_x > xlog_y\)。 这里同学们可能要问,可以直接取对数么?取对数之后,大小关系仍旧满足么?这里是有两点保证的:

对数函数的性质,单调递增
题目中的说明:元素都是正数

对于式子:ylog(x)>xlog(y),x和y都是正数,则进一步有:两边同时除以xy,则:log(x)/x >log(y)/y。这个式子,看起来也复杂,但是,x和y都在各自的一边,要简单的多。 对于log(x)/x >log(y)/y,

数组X和Y分别计算log(x)/x,log(y)/y
然后对Y进行排序O(nlogn)
遍历X数组,对于每一个x,在Y中,进行二分查找,即可。

总的时间复杂度为O(nlogn + mlogn).


3.巧妙变换 (Reorder Array)

原题输入数组[a1, a2, ... , an, b1, b2,..., bn],构造函数,使得输出为,[a1, b1, a2, b2, ... , an, bn],注意:方法要是in-place的分析 在下面介绍方法的时候,我们都以[a1,a2,a3,a4,b1,b2,b3,b4]为例。 方法1 最容易想到的方法通过观察输入输出的格式,直接通过将b1进行交换,直至目标的位置,其他元素也如此操作。直到完成变换。如下的过程:

确定b1的位置,b1要和前面3个元素依次交换。 a1 b1 a2 a3 a4 b2 b3 b4 确定b2的位置,b2要和前面的2个元素一次交换,同样为了保证in-place。注意交换次数少了一次。 a1 b1 a2 b2 a3 a4 b3 b4 依次确定b3和b4的位置,b4是最后的元素,不需进行交换,b3需要交换一次。 a1 b1 a2 b2 a3 b3 a4 b4 通过上面的分析,则整体的交换次数,3+2+1=6,不失一般性(n-1)+…+1,Time: O(n^2)

方法2 同样针对上面的例子: 第一步:交换最中间的一对元素,得到 a1 a2 a3 b1 a4 b2 b3 b4 第二步:交换最中间的两对元素,得到 a1 a2 b1 a3 b2 a4 b3 b4 第三步:交换最中间的三对元素,得到 a1 b1 a2 b2 a3 b3 a4 b4 完毕,得到结果。 在上面的交换中,交换的次数分别为1,2,3,推而广之,1,…,n-1,则时间复杂度仍旧是O(n^2)

Details see here link


4.绝对值最

原题给定一个数组,我们可以找到两个不相交的子数组A和B,A中的数字和为sum(A), B中的元素和为sum(B)。找到这样的A和B,满足sum(A) - sum(B)的绝对值是最大的。 例如:[2, -1 -2, 1, -4, 2, 8]划分为A=[-1, -2, 1, -4], B=[2, 8], 最大的值为16

首先我们来看看题目有哪些要点:
    1. 子数组是不相交的
    2. 差的绝对值最大

那我们自然而然能够想到:找到的两个不相交的子数组,一个值要很小,一个值要很大。这样才能够保证差的绝对值最大。那如何找到这样的数组呢?我们从不相交的这个条件入手。

看题目中例子: 0 1 2 3 4 5 6 2 -1 -2 1 4 2 8

看上面的表格,如果两个子数组不想交,我们有六个位置,作为划分的备选,0和1之间、1和2之间、2和3之间,直到5和6之间。 对于任意的i,我们得到了两部分[0, i-1]和[i, n-1]。接下来,就是在这两部分中,找到一个和最小的子数组A,以及和最大的子数组B。那么A-B的绝对值,就是i这个划分下,满足条件的两个数组的差的最大值。对于,所有的i而言,这个绝对值最大时的A和B就是我们要找到的。

思路通顺了,接下来要确定,找到在i处划分,和最大以及和最小的子数组的方法。 我们单独的考虑,给定一个数组,求和最大的子数组以及和最小的子数组。 先分析和最大的子数组,这个问题,是比较经典的问题了,但是我们这里要处理的是,求得每一个i左侧的最大连续子数组。

作如下分析,假设数组为X, 假设max_until表示,以i位置结尾的连续子数组的最大和。max_until和max_until[i-1]是什么关系呢?

如果X + max_until[i - 1] > max_until[i - 1] and X + max_until[i - 1] > X。那么X应该加入到连续子数组中,max_until = max_until[i-1] + X.
否则max_until = X,连续子数组只有一个元素。

但是,我们要的并不是以i结尾的子数组,尽管给的例子中是这样的,我们要的是i之前的所有连续子数组中,和最大的。并不一定包括i。要如何处理呢?我们再开辟子数组max_left表示[0,i]中连续子数组的最大值。那这个值要如何求得呢?我们在遍历数组,求得max_until的时候,max_left只需要在max_until和此前保存的最大值里取最大的即可。也就是一次遍历,就可以完全求得max_until数组和max_left数组。同理可以求得min_until以及min_left数组。 这是处理的划分的左半部分。那么右半部分呢? 右半部分的思路也是一样的,只不过,我们在遍历数组的时候,需要从右向左进行遍历。 总结整个方法的流程如下:

从左向右遍历数组,计算max_left和min_left数组,O(n)时间复杂度
从右向左遍历数组,计算max_right和min_right数组,O(n)时间复杂度
然后对于每一个i,i从1开始到n-1,计算max_left[i - 1] - min_right, max_right - min_left[i - 1]。选取绝对值最大的。

方法的整体空间复杂度为O(n),时间复杂度也是O(n)。 总结这个题目,其实是采用动态规划解决最大连续子数组和问题的变种,又多了一层思考。面试者在遇到一个新的题目的时候,不要慌乱,对问题进行仔细分析,进而对其进行分解,分解为自己熟悉的问题。那问题也就解决了。