狗六月实习面经

第1题是要返回 strictly small 的string:

题干:
定义: 根据lexicographical order, 字母a最小,z最大;接下来比较每个字符串中最小字母的出现频率,如果A 的该频率小于B的该频率,则称A strictly smaller than B。
如:‘a’ <‘bb’, 因为左侧字符串中最小字母为‘a’其频率为1,而右侧字符串最小字母 ‘b’ 频率为2.

输入: def solution(A,B) 字符串A和B 每个都包含多个以空格间隔的子字符串,内容都是lowercase letter。如A = ‘abcd aabc bd’, B=‘aaa aa’
输出: 对于B 中每个子字符串,找出A 中有多少个子字符串比它 strictly smaller, 并返回这个数值。如上述AB的对应输出为 [3,2]

第2题要返回largest contiguous subarray:

题干:
输入:数组A (包含 dictinct integars),int K。 e.g. A = [1,4,3,2,5], K = 4;
取A中K个连续元素构建一系列子数组,如上则是[1,4,3,2], [4,3,2,5],返回largest contiguous subarray。
largest contiguous subarray定义:逐项比较两数组元素,对于第一对non-matching的元素,值大的数组larger.
e.g. X = [1,2,4,3,5], Y = [1,2,3,4,5], ----> X > Y, 因为X[2] > Y[2]。

预处理后:
B 也是就是 a(3次) 和 a(2次),A 是 a(1次),a(2次),b(1次)

保留一个size 为 K 的 int array存储当前 largest contiguous subarray, 同时用一个size为K的sliding window 去扫数组A。
我们比较1st digit,如果相等,就比较2nd digit,如此往下。。。
runtime 是 O(n * k)