바이트 입력 가능 여부를 결정하는 몇 가지 질문

그러자 면접관이 질문을 하기 시작했습니다.

바이트 알고리즘 질문이 쉽지 않다는 말을 들었던 내 친구가 생각했다. 뭐야, 너의 간단한 질문은 별로 어렵지 않지?

3.1 프로그래밍 질문 1

请写一个函数：string ConvertNum(string src, int src_base, int dst_base)

测试用例：
ConvertNum("FF", 16, 10) = "255"
ConvertNum("077", 8, 10) = "63"
ConvertNum("10", 16, 10) = "16"

假设：
参数：src_base/dst_base = 2, 8, 10, 16 src >= "0"
假设没有任何前缀；
假设参数都正确；
假设参数都是非负数

면접관은

을 20분 이내에 완료해야 합니다. 빠를수록 좋습니다. 모든 테스트 사례를 통과해야 하며 코드가 필요합니다. 최대한 간결합니다.

친구

오랜만에 이런 질문에 답을 못했는데 분명히 생각하지 못했어요, 수술이 되었어요. 호랑이처럼 맹렬해서 그래서 더 이상 세부 사항이 잘못되지 않습니다.

문제 해결 아이디어(주로 지식 포인트 검토:)

1. 문자열을 정수로 변환하는 atoi 함수 구현

2. 정수에서 문자열로의 함수 itoa 구현.

겉으로는 단순해 보이는 기본 질문이지만 많은 것을 검토하고

"분할 및 정복"이라는 아이디어를 채택해야 합니다. 친구가 면접관에게 말했습니다. 저는 평소에 리트코드를 브러싱하는데, 갑자기 이런 질문을 쓰는 것이 불편해졌습니다.

면접관이 대답했습니다. 그럼 매우 흥미로운 유사한 질문을 살펴보겠습니다.

면접관이 질문을 하기 시작했습니다.

3.2 面试题二

C++
typedef struct LinkListNode {
  int value;
  struct LinkListNode* left;
  struct LinkListNode* right;
} LN, *PLN;

bool IsBranch(PLN root, int *nodes, int length)
   1
  / \
 2   3
    / \
   4   5
      / \
     6   7
     
1 T
0 F
2, 3 F
1, 2, 3 T
1, 3, 5, 6 T
6, 5, 3, 1 T

面试官提示

面试官出完题之后，笑了笑说提示一下哈，本题可以找规律。

朋友

做了一段时间之后，大部分写出来了，但是还是有些细节没考虑好。

解题思路

将这颗树看成一个族谱，如果输入的是一颗子树的话，必须要有父亲节点，比如 1, 3, 6，由于 6 没有父亲节点，所以输出肯定是 F；如果只有兄弟节点的话，同样输出也是 F。

面试官问 你刷题的时候，最擅长刷哪种类型的题目，数组 or 链表 or 二叉树 or 排序 or...?

朋友一想，最近自己刷 链表 的题目比较多，递归、迭代以及增加虚拟头节点等等解法都掌握了，而且听了慕课网 liuyubobo 老师的算法课中的链表部分，于是自豪地说 链表。

面试官说 那就看看链表的算法题吧。

朋友露出笑容问道 面试官，你不会出一道 hard 的链表题吧？

面试官哈哈大笑，答道 我还是有节操的，不会坑你的，不过如果你通过了这一面，下一面的算法题估计比较难。

说完面试官出题了。

3.3 面试题三

给定一个单链表，在链表中把 L 个节点到 R 个节点这一部分进行反转。

示例1：
输入
[1, 2, 3, 4, 5]  1, 3
输出
{3, 2, 1, 4, 5}

朋友一看，面露喜色，这么简单的，而且这不跟力扣中某道题类似嘛？

面试官好像看出来啥了，笑着问 你如果做过这道题的话，你就说做过，我再给你换道题。

朋友答道 确实做过，哈哈。

面试官开始换题（出题）。

3.4 面试题四

将一个链表 m 位置到 n 位置之间的区间反转，要求时间复杂度，空间复杂度。

例如：
给出的链表为 1->2->3->4->5->NULL，返回 1->4->3->2->5->NULL.

注意：
给出的满足一下条件：
1 ≤ m ≤ n ≤ 链表长度。

朋友一看，笑了，心想这不就是 leetcode 92. 反转链表 II 的原题嘛？于是乎很诚实地跟面试官说 这题我做过。

面试官面露微笑，说 继续换题，不过不用担心，我不坑你，做一道合并两个排序链表的题。

朋友听到 合并两个排序数组，心中一顿窃喜，这不还是 leetcode 原题嘛？

3.5 面试题五

合并排序数组
typedef struct LinkListNode {
  int value;
  struct LinkListNode *next;
}LN, *PLN;

示例：
listA 升序（1, 3, 5, 7, 9）
listB 降序（8, 6, 4, 2, 0）
返回：升序（0, 9）
PLN mergeLinkList(PLN listA, PLN listB)

面试官果真不坑人，笑着说我提示一下哈 为了简单一点，这道题你可以不用考虑这两个链表中有相同值得节点。