找工作过程中碰到的一些算法题
Categories: share
Z公司
机考题1
输入描述：n行时分秒字符串
输出：先按秒升序，再按分升序，再按分升序
* 如下的样例，这购买的时间为
* 12:30:10
* 12:15:12
* 15:20:14
* 正确的排序结果应该是这样的：
* 12:30:10
* 12:15:12
* 15:20:14
*
* 12:30:10
* 12:15:10
* 11:20:14
* 的正确排序结果如下:
* 12:15:10
* 12:30:10
* 11:20:14
机考题2
提取给定字符串中的数字：
比如给你c12m23b3n4t56
提取的数字为:12，23，3，4，56总共5个数字
示例
输入：
"kur1su alan0233"
输出：
[1,233]
R公司
机考1
输入描述
一个ASCII字符串，其中字符没有顺序，字符可以重复。输入字符串的长度<=30。
输出描述
一个新的字符串，该新字符串中字符在输入字符串中只出现一次，且该新字符串按照ASCII码从小到大的顺序排列。如果输入字符串中字符出现的次数都是大于1，则无需输出。
示例 1
收起
输入
e1fghabcd1234efgh
输出
1234abcd
说明
只出现一次的字符包括’a’,’b’,’c’,’d’,’1’,’2’,’3’,’4’，按照ASCII码升序后组成的新字符串为1234abcd
机考2
解析输入的字符串数组，提取出字符串中的时间戳信息，并且将字符串按照时间戳排序后，输出到控制台。
输入描述
第1行指定数组的size；
第2行到第n+1行，每行为一个独立的字符串，n为size的值。
每行的字符串由" / - : "和字母、数字组成，时间戳在字符串中的位置不确定，时间戳格式为：2019-01-01T07:30:20，表示2019年1月1日，7点30分20秒。时间为24小时制。
输出描述
将输入的字符串按照时间戳进行从小到大排序后，输出。符合如下规则：
1、如果时间戳信息相同，按照字符串长度从小到大进行排序；
2、如果长度相同，则按照从首字符开始的ASCII码值比较，从小到大进行排序；
3、如果两个字符串完全一样，则只需要输出一个。
补充说明
考生不需要考虑时间格式不符合的情况。
示例 1
输入
5
my/2019-01-01T09:00:01
my/2019-01-01T09:00:01
abc/2018-12-24T08:00:00/test/you
1/2018-12-24T08:00:00/test/Test1
123/2018-12-24T08:00:09/test/me
输出
1/2018-12-24T08:00:00/test/Test1
abc/2018-12-24T08:00:00/test/you
123/2018-12-24T08:00:09/test/me
my/2019-01-01T09:00:01
说明
每行字符串中如果存在多个时间戳，以第一个为准；时间戳固定为"yyyy-MM-dd'T'HH:mm:ss"的格式
H公司
机考1
输入描述：
第一行为N，表示访问历史日志的条数，。
接下来N行，每一行为一个RESTful API的URL地址，约束地址中仅包含英文字母和连接符/，最大层级为10，每层级字符串最大长度为10。
最后一行为层级L和要查询的关键字。
输出描述
输出给定层级上，关键字出现的频次，使用完全匹配方式（大小写敏感）。
e.g.
输入：
5
/hcompany/computing/no/one
/hcompany/computing
/hcompany
/hcompany/cloud/no/one
/hcompany/wireless/no/one
2 computing
输出：
2
机考2
测试用例只通过了80%。机考，提交代码的时候没有提示哪些测试用例没通过，所以也没法调试具体是代码哪部分逻辑出错。
给你一个字符串 s，字符串s首尾相连成一个环形 ，请你在环中找出 'o' 字符出现了偶数次最长子字符串的长度。
输入描述
输入是一串小写字母组成的字符串
输出描述
输出是一个整数
补充说明
1 <= s.length <= 5 x 10^5
s 只包含小写英文字母
示例：
输入
alolobo
输出
6
说明
最长子字符串之一是 "alolob"，它包含'o' 2个。
输入
looxdolx
输出
复制
7
说明
最长子字符串是 "oxdolxl"，由于是首尾连接在一起的，所以最后一个 'x' 和开头的 'l'是连接在一起的，此字符串包含 2 个'o' 。
输入
bcbcbc
输出
6
说明
这个示例中，字符串 "bcbcbc" 本身就是最长的，因为 'o' 都出现了 0 次。
机考3
孙悟空爱吃蟠桃，有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有N颗桃树，每颗树上都有桃子，守卫将在H小时后回来。
孙悟空可以决定他吃蟠桃的速度K（个/小时），每个小时选一颗桃树，并从树上吃掉K个，如果树上的桃子少于K个，则全部吃掉，并且这一小时剩余的时间里不再吃桃。
孙悟空喜欢慢慢吃，但又想在守卫回来前吃完桃子。
请返回孙悟空可以在H小时内吃掉所有桃子的最小速度K（K为整数）。如果以任何速度都吃不完所有桃子，则返回0。
输入描述：
第一行输入为N个数字，N表示桃树的数量，这N个数字表示每棵桃树上蟠桃的数量。
第二行输入为一个数字，表示守卫离开的时间H。
其中数字通过空格分割，N、H为正整数，每棵树上都有蟠桃，且0<N<10000，0<H<10000。
输出描述：
吃掉所有蟠桃的最小速度K，无解或输入异常时输出0
以下是测试用例：
输入：
2 3 4 5
4
输出：
5
输入：
2 3 4 5
3
输出：
0
输入：
30 11 23 4 20
6
输出：
23
类似题目： https://leetcode-cn.com/problems/koko-eating-bananas/description/
技术面手撕代码1
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
技术面手撕代码2
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
输入：nums = [4,5,6,7,0,1,2]， target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 = target <= 10^4
-104 <= 目标 <= 104
技术面手撕代码3
寿司店周年庆，正在举办优惠活动回馈新老客户。寿司转盘上总共有n盘寿司，prices[i]是第i盘寿司的价格，如果客户选择了第i盘寿司，寿司店免费赠送客户下一盘寿司j，前提是prices[j]<prices[i]，如果没有满足条件的j，则不赠送寿司。
给你一个数组prices，返回一个数组，其中第i个元素存放着客户选择第i盘寿司后得到的寿司的总价格。
1 <= prices.length <= 10^5
1 <= prices[i] <= 10^3
输入：prices = [8,4,6,2,3]
输出：[12,6,8,2,5]
输入：prices = [1,2,3,4,5]
输出：[1,3,4,5,6]
输入：prices = [10,1,1,6]
输出：[11,1,1,7]
B公司
机考题
给定一个字符串，统计每个字符的出现次数（不区分大小写），然后将字符按次数降序输出。如果字符的次数相同，则按字符升序输出。
例如：
输入：We Attack at Dawn
输出：atwcdekn
说明：a出现4次数最多，a首先输出；c和d都只出现了一次，但c在d前面，所以现输出c再输出d。
总的来说，主要都是考一些基本的逻辑，没有考我比较头疼的动态规划之类的算法。