1821 字

5 分钟

面试算法学习1

2023-08-11

algorithm

meeting

algorithm

蛇形矩阵#

微软面试题

题目描述#

输入两个整数 $n$ 和 $m$ ，输出一个 $n$ 行 $m$ 列的矩阵，将数字 $1$ 到 $n \times m$ 按照回字蛇形填充至矩阵中。

具体矩阵形式可参考样例。

输入格式#

输入共一行，包含两个整数 $n$ 和 $m$ 。

输出格式#

输出满足要求的矩阵。

矩阵占 $n$ 行，每行包含 $m$ 个空格隔开的整数。

数据范围#

$1 \le n,m \le 100$

解法#

模拟法：#

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int N = 110;
6
int n,m,a[N][N];
7
int main(){
8
    cin>>n>>m;
9
    int l = 0,r = m-1, t = 0,d = n-1,cnt=1;
10
    while(l<=r || t <= d){
11
        for(int i=l;i<=r && t<=d;i++) a[t][i] = cnt++;t++;
12
        for(int i=t;i<=d && l<=r;i++) a[i][r] = cnt++;r--;
13
        for(int i=r;i>=l && t<=d;i--) a[d][i] = cnt++;d--;
14
        for(int i=d;i>=t && l<=r;i--) a[i][l] = cnt++;l++;
15
    }
16
    for(int i=0;i<n;i++)
17
        for(int j=0;j<m;j++)
18
            cout<<a[i][j]<<" \\n"[j==m-1];
19

20
    return 0;
21
}

触底模拟：#

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int N = 110;
6
int n,m,a[N][N],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
7
int main(){
8
    cin>>n>>m;int x=0,y=0;
9
    for(int i=1,u=0;i<=n*m;i++){
10
        a[x][y] = i;
11
        x += dx[u];y += dy[u];
12
        if(a[x][y] || x<0 || y<0 || x>=n || y>=m)
13
            x-=dx[u],y-=dy[u],u = (u+1)%4,
14
            x += dx[u],y += dy[u];
15
    }
16

17
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
18
        cout<<a[i][j]<<" \\n"[j==m-1];
19
    return 0;
20
}

单链表快速排序#

旷视面试题

题目描述#

给定一个单链表，请使用快速排序算法对其排序。

要求：期望平均时间复杂度为 $O(nlogn)$ ，期望额外空间复杂度为 $O(logn)$ 。

思考题： 如果只能改变链表结构，不能修改每个节点的val值该如何做呢？

数据范围#

链表中的所有数大小均在 $int$ 范围内，链表长度在 $[0, 10000]$ 。

本题数据完全随机生成。

解法#

思路与普通的快排基本一致，将链表根据一个val分成小于val、等于val、大于val三段，再对前后两段递归进行快排，对于排序完的三段从前到后进行拼接即可完成。

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    ListNode* quickSortList(ListNode* head) {
12
        if(!head || !head->next) return head;
13

14
        auto left = new ListNode(-1),mid=new ListNode(-1),right=new ListNode(-1),
15
            ltail = left,mtail = mid,rtail = right;
16
        int val = head->val;
17

18
        for(auto p=head;p;p = p->next){
19
            if(p->val < val) ltail = ltail->next = p;
20
            else if(p->val == val) mtail = mtail->next = p;
21
            else rtail = rtail->next = p;
22
        }
23

24
        ltail->next = mtail->next = rtail->next = NULL;
25
        left->next = quickSortList(left->next);
26
        right->next = quickSortList(right->next);
27

28
        get_tail(left)->next = mid->next;
29
        get_tail(left)->next = right->next;
30

31
        auto p = left->next;
32
        delete left;delete mid;delete right;
33
        return p;
34
    }
35

36
    ListNode* get_tail(ListNode* head) {
37
        while (head->next) head = head->next;
38
        return head;
39
    }
40
};

寻找峰值#

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

提示：

1 <= nums.length <= 1000
231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

解法#

可以发现当存在斜坡时，顺着高点的方向就可以找到答案。

1
class Solution {
2
public:
3
    int findPeakElement(vector<int>& nums) {
4
        int l=0,r = nums.size()-1;
5
        while(l<r){
6
            int mid = (l+r) >> 1;
7
            long long lm = mid-1,rm = mid+1;
8
            if(lm<0) lm = INT_MIN-1ll;
9
            else lm = nums[lm];
10
            if(rm>=nums.size()) rm = INT_MIN-1ll;
11
            else rm = nums[rm];
12
            long long key = nums[mid];
13
            if(key>lm && key>rm)
14
                return mid;
15
            else if(key>lm &&rm>key)
16
                l = mid+1;
17
            else
18
                r = mid-1;
19
        }return l;
20
    }
21
};

寻找矩阵的极小值#

微软面试题

题目描述#

给定一个 $n \times n$ 的矩阵，矩阵中包含 $n \times n$ 个 互不相同 的整数。

定义极小值：如果一个数的值比与它相邻的所有数字的值都小，则这个数值就被称为极小值。

一个数的相邻数字是指其上下左右四个方向相邻的四个数字，另外注意，处于边界或角落的数的相邻数字可能少于四个。

要求在 $O(nlogn)$ 的时间复杂度之内找出任意一个极小值的位置，并输出它在第几行第几列。

本题中矩阵是隐藏的，你可以通过我们预设的 $int$ 函数 $query$ 来获得矩阵中某个位置的数值是多少。

例如， $query(a,b)$ 即可获得矩阵中第 $a$ 行第 $b$ 列的位置的数值。

注意：

矩阵的行和列均从 $0$ 开始编号。
query()函数的调用次数不能超过 $(n + 2) \times \lceil log_2n \rceil + n$ 。
答案不唯一，输出任意一个极小值的位置即可。

数据范围#

$1 \le n \le 300$ ，矩阵中的整数在int范围内。

解法#

与上题类似，同时通过调用次数可以获取提示：我们可以对 $log_2n$ 列遍历其中的n个数。具体做法是：

通过二分确定包含极小值的列，对该列进行遍历即可得到答案，其中二分的条件是一列的最小值与其所在行左右值的大小比较。

1
// Forward declaration of queryAPI.
2
// int query(int x, int y);
3
// return int means matrix[x][y].
4
class Solution {
5
public:
6
    vector<int> getMinimumValue(int n) {
7
        typedef long long ll;
8
        ll INF = 1e15;
9
        int l,r;l=0;r = n-1;
10

11
        while(l<r){
12
            int mid = l+r>>1;
13
            ll val = INF;
14
            int p=0;
15
            for(int i=0;i<n;i++){
16
                int t = query(i,mid);
17
                if(t < val)
18
                    val = t,p = i;
19
            }
20
            ll lt = mid ? query(p,mid-1):INF;
21
            ll rt = mid+1<n ? query(p,mid+1):INF;
22

23
            if(val<lt && val<rt)
24
                return {p,mid};
25
            if(lt<val)
26
                r = mid - 1;
27
            else
28
                l = mid + 1;
29
        }
30

31
        ll val = INF;int p=0;
32
        for(int i=0;i<n;i++){
33
            int t = query(i,r);
34
            if(t<val)
35
                val = t,p = i;
36
        }
37
        return {p,r};
38

39
    }
40
};

鸡蛋的硬度#

google面试题

输入格式#

输入包括多组数据，每组数据一行，包含两个正整数 $n$ 和 $m$ ，其中 $n$ 表示楼的高度， $m$ 表示你现在拥有的鸡蛋个数，这些鸡蛋硬度相同（即它们从同样高的地方掉下来要么都摔碎要么都不碎），并且小于等于 $n$ 。

你可以假定硬度为 $x$ 的鸡蛋从高度小于等于 $x$ 的地方摔无论如何都不会碎（没摔碎的鸡蛋可以继续使用），而只要从比 $x$ 高的地方扔必然会碎。

对每组输入数据，你可以假定鸡蛋的硬度在 $0$ 至 $n$ 之间，即在 $n+1$ 层扔鸡蛋一定会碎。

输出格式#

对于每一组输入，输出一个整数，表示使用最优策略在最坏情况下所需要的扔鸡蛋次数。

数据范围#

$1 \le n \le 100$ , $1 \le m \le 10$

样例解释#

最优策略指在最坏情况下所需要的扔鸡蛋次数最少的策略。

如果只有一个鸡蛋，你只能从第一层开始扔，在最坏的情况下，鸡蛋的硬度是100，所以需要扔100次。如果采用其他策略，你可能无法测出鸡蛋的硬度(比如你第一次在第二层的地方扔,结果碎了,这时你不能确定硬度是0还是1)，即在最坏情况下你需要扔无限次，所以第一组数据的答案是100。

解法#

dp1#

用f[i][j]来表示在区间长度为i中通过j个鸡蛋得到的最优策略。

对于每个鸡蛋j，可以考虑有两种情况：没用鸡蛋j，即f[i][j]=f[i][j-1]；使用了鸡蛋j，对于其1~i间有i种情况，令其中一种情况为k，此时会有两种情况：鸡蛋碎了（f[k-1][j-1]），鸡蛋没碎（f[i-k][j]），最坏情况即为两者取最大值，此时的最少策略为min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1)

1
#include<iostream>
2
#include<algorithm>
3
#include<cstring>
4
using namespace std;
5
const int N =110,M=11;
6
int n,m,f[N][M];
7

8
int main(){
9
    while(cin>>n>>m){
10
        for(int i=1;i<=n;i++) f[i][1] = i;
11
        for(int i=1;i<=m;i++) f[1][i] = 1;
12

13
        for(int i=2;i<=n;i++)
14
            for(int j=2;j<=m;j++){
15
                f[i][j] = f[i][j-1];
16
                for(int k=1;k<=i;k++)
17
                    f[i][j] = min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1);
18
            }
19
        cout<<f[n][m]<<endl;
20
    }return 0;
21
}

dp2#

与上一种方法不同，用f[i][j]来表示的是用在i次测量中用j个鸡蛋能测得的最大长度。

假设测量位置k，会有两种情况：鸡蛋碎了(f[i-1][j-1]，递归下半部分)或者不碎(f[i-1][j]，递归上半部分)。

f[i][j] = f[i-1][j]+f[i-1][j-1]+1;

1
#include<iostream>
2
#include<algorithm>
3
#include<cstring>
4
using namespace std;
5
const int N =110,M=11;
6
int n,m,f[N][M];
7

8
int main(){
9
    while(cin>>n>>m){
10
        for(int i=1;i<=n;i++){
11
            for(int j=1;j<=m;j++)
12
                f[i][j] = f[i-1][j]+f[i-1][j-1]+1;
13

14
            if(f[i][m] >= n){
15
                cout<<i<<endl;
16
                break;
17
            }
18
        }
19
    }return 0;
20
}

包含min函数的栈#

hulu面试题

题目描述#

设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。

push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元素

数据范围#

操作命令总数 $[0,100]$ 。

样例#

1
MStack minStack = new MStack();
2
minStack.push(-1);
3
minStack.push(3);
4
minStack.push(-4);
5
minStack.getM();   --> Returns -4.
6
minStack.pop();
7
minStack.top();      --> Returns 3.
8
minStack.getM();   --> Returns -1.

解法#

方法一#

直接通过一个数组来存存入数时当前位的最小值即可。

1
class MinStack {
2
public:
3
    /** initialize your data structure here. */
4
    int len;
5
    int a[110],ck[110];
6

7
    MinStack() {
8
        len = a[0] = ck[0] = 0;
9
    }
10

11
    void push(int x) {
12
        a[len] = x;
13
        ck[len] = min(len?ck[len-1]:x,x);
14
        len++;
15
    }
16

17
    void pop() {
18
        len--;
19
    }
20

21
    int top() {
22
        return a[len-1];
23
    }
24

25
    int getMin() {
26
        return ck[len-1];
27
    }
28
};

方法二#

通过一个单调栈来维护最小值。

通过ck.top() >= x来使存在ck中的为单调递减的最小值。当进行pop时，只要不与ck当前的最小值相等就不需要对ck进行更新。获取最小值时获取ck.top()即可。

1
class MinStack {
2
public:
3
    /** initialize your data structure here. */
4
    stack<int> a;
5
    stack<int> ck;
6

7
    MinStack() {
8

9
    }
10

11
    void push(int x) {
12
        a.push(x);
13
        if(ck.empty() || ck.top() >= x)
14
            ck.push(x);
15
    }
16

17
    void pop() {
18
        if(ck.top() == a.top())
19
            ck.pop();
20
        a.pop();
21
    }
22

23
    int top() {
24
        return a.top();
25
    }
26

27
    int getMin() {
28
        return ck.top();
29
    }
30
};

链表中环的入口结点#

阿里面试题

题目描述#

给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

数据范围#

节点 val 值取值范围 $[1,1000]$ 。节点 val 值各不相同。链表长度 $[0,500]$ 。

样例#

19_69ba6d14f5-QQ%E6%88%AA%E5%9B%BE20181202023846.png

1
给定如上所示的链表：
2
[1, 2, 3, 4, 5, 6]
3
2
4
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。
5
则输出环的入口节点3.

解法#

可以发现val值不同且范围只有1000，使用用个数组记录下用过的val值对应的节点就行了。当再访问到记录过的val时，就是发生了循环。

1
class Solution {
2
public:
3
    ListNode *entryNodeOfLoop(ListNode *head) {
4
        ListNode* ck[1010];
5

6
        for(auto p=head;p;p=p->next){
7
            int val = p->val;
8
            if(ck[val])
9
                return ck[val];
10
            ck[val] = p;
11
        }return NULL;
12
    }
13
};

1079 字

5 分钟

Interview Algorithm Study 1

2023-08-11

algorithm

meeting

algorithm

Spiral Matrix#

Microsoft interview question

Problem Description#

Input two integers $n$ and $m$ , output an $n$ by $m$ matrix, filling numbers from $1$ to $n \times m$ in a spiral snake pattern.

The exact matrix form can be referenced from the sample.

Input format#

The input consists of a single line containing two integers $n$ and $m$ .

Output format#

Output the required matrix.

The matrix has $n$ rows, each row containing $m$ integers separated by spaces.

Constraints#

$1 \le n,m \le 100$

Solution#

Simulation Method:#

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int N = 110;
6
int n,m,a[N][N];
7
int main(){
8
    cin>>n>>m;
9
    int l = 0,r = m-1, t = 0,d = n-1,cnt=1;
10
    while(l<=r || t <= d){
11
        for(int i=l;i<=r && t<=d;i++) a[t][i] = cnt++;t++;
12
        for(int i=t;i<=d && l<=r;i++) a[i][r] = cnt++;r--;
13
        for(int i=r;i>=l && t<=d;i--) a[d][i] = cnt++;d--;
14
        for(int i=d;i>=t && l<=r;i--) a[i][l] = cnt++;l++;
15
    }
16
    for(int i=0;i<n;i++)
17
        for(int j=0;j<m;j++)
18
            cout<<a[i][j]<<" \\n"[j==m-1];
19

20
    return 0;
21
}

Boundary-following Simulation:#

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int N = 110;
6
int n,m,a[N][N],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
7
int main(){
8
    cin>>n>>m;int x=0,y=0;
9
    for(int i=1,u=0;i<=n*m;i++){
10
        a[x][y] = i;
11
        x += dx[u];y += dy[u];
12
        if(a[x][y] || x<0 || y<0 || x>=n || y>=m)
13
            x-=dx[u],y-=dy[u],u = (u+1)%4,
14
            x += dx[u],y += dy[u];
15
    }
16

17
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
18
        cout<<a[i][j]<<" \\n"[j==m-1];
19
    return 0;
20
}

Quick Sort on a Singly Linked List#

Megvii interview question

Problem Description#

Given a singly linked list, sort it using the quicksort algorithm.

Requirements: expected average time complexity is $O(n \log n)$ and expected additional space complexity is $O(\log n)$ .

Thought question: If you can only change the structure of the list and cannot modify each node’s val, how would you do it?

Constraints#

All numbers in the list are within the int range, and the list length is in $[0, 10000]$ .

The data for this problem is completely randomly generated.

Solution#

The approach is basically the same as ordinary quicksort: partition the list into three parts based on a value: less than the value, equal to the value, and greater than the value; recursively quicksort the front and back sections, and then concatenate the three parts in order.

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    ListNode* quickSortList(ListNode* head) {
12
        if(!head || !head->next) return head;
13

14
        auto left = new ListNode(-1),mid=new ListNode(-1),right=new ListNode(-1),
15
            ltail = left,mtail = mid,rtail = right;
16
        int val = head->val;
17

18
        for(auto p=head;p;p = p->next){
19
            if(p->val < val) ltail = ltail->next = p;
20
            else if(p->val == val) mtail = mtail->next = p;
21
            else rtail = rtail->next = p;
22
        }
23

24
        ltail->next = mtail->next = rtail->next = NULL;
25
        left->next = quickSortList(left->next);
26
        right->next = quickSortList(right->next);
27

28
        get_tail(left)->next = mid->next;
29
        get_tail(left)->next = right->next;
30

31
        auto p = left->next;
32
        delete left;delete mid;delete right;
33
        return p;
34
    }
35

36
    ListNode* get_tail(ListNode* head) {
37
        while (head->next) head = head->next;
38
        return head;
39
    }
40
};

Find Peak Element#

A peak element is an element that is strictly greater than its left and right neighbors.

Given an integer array nums, find a peak element and return its index. The array may contain multiple peaks; in that case, you may return the index of any one of the peaks.

You may assume nums[-1] = nums[n] = -∞.

You must implement an algorithm with time complexity O(log n) to solve this problem.

Hint:

1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
For all valid i, nums[i] != nums[i + 1]

Solution#

One can observe that when there is a slope, following the direction of the higher point leads to the answer.

1
class Solution {
2
public:
3
    int findPeakElement(vector<int>& nums) {
4
        int l=0,r = nums.size()-1;
5
        while(l<r){
6
            int mid = (l+r) >> 1;
7
            long long lm = mid-1,rm = mid+1;
8
            if(lm<0) lm = INT_MIN-1ll;
9
            else lm = nums[lm];
10
            if(rm>=nums.size()) rm = INT_MIN-1ll;
11
            else rm = nums[rm];
12
            long long key = nums[mid];
13
            if(key>lm && key>rm)
14
                return mid;
15
            else if(key>lm &&rm>key)
16
                l = mid+1;
17
            else
18
                r = mid-1;
19
        }return l;
20
    }
21
};

Find a Local Minimum in a Matrix#

Microsoft interview question

Problem Description#

Given an $n \times n$ matrix containing $n \times n$ pairwise distinct integers.

Define a local minimum as a value that is smaller than all of its adjacent numbers. An adjacent number is one of the four directions (up, down, left, right). Numbers on the border or corner may have fewer than four neighbors.

You must find any local minimum in $O(n \log n)$ time and output its position as its row index and column index.

The matrix is hidden, and you can obtain values via the predefined function query. For example, query(a,b) returns the value at row a, column b.

Notes:

Rows and columns are 0-based.
The number of query() calls must not exceed $(n + 2) \times \lceil \log_2 n \rceil + n$ .
The answer is not unique; output any one local minimum’s position.

Data Range#

$1 \le n \le 300$ , matrix values fit in int.

Solution#

Similar to the previous problem, and the call limit gives a hint: we can scan n numbers across log2(n) columns. The approach is to binary search for the column containing a local minimum, then scan that column to obtain the answer, where the binary search condition compares the minimum value in a column with its left and right neighbors.

1
// Forward declaration of queryAPI.
2
// int query(int x, int y);
3
// return int means matrix[x][y].
4
class Solution {
5
public:
6
    vector<int> getMinimumValue(int n) {
7
        typedef long long ll;
8
        ll INF = 1e15;
9
        int l,r;l=0;r = n-1;
10

11
        while(l<r){
12
            int mid = l+r>>1;
13
            ll val = INF;
14
            int p=0;
15
            for(int i=0;i<n;i++){
16
                int t = query(i,mid);
17
                if(t < val)
18
                    val = t,p = i;
19
            }
20
            ll lt = mid ? query(p,mid-1):INF;
21
            ll rt = mid+1<n ? query(p,mid+1):INF;
22

23
            if(val<lt && val<rt)
24
                return {p,mid};
25
            if(lt<val)
26
                r = mid - 1;
27
            else
28
                l = mid + 1;
29
        }
30

31
        ll val = INF;int p=0;
32
        for(int i=0;i<n;i++){
33
            int t = query(i,r);
34
            if(t<val)
35
                val = t,p = i;
36
        }
37
        return {p,r};
38

39
    }
40
};

Egg Dropping Problem#

Google interview question

Input Format#

The input consists of multiple test cases, each on one line containing two positive integers $n$ and $m$ , where $n$ is the height of the building and $m$ is the number of eggs you have. All eggs have the same hardness (i.e., they either all break or all do not break when dropped from the same height), and $m \le n$ .

You may assume the hardness is between $0$ and $n$ , i.e., dropping from the $(n+1)$ -th floor will certainly break.

Output Format#

For each test case, output a single integer representing the minimum number of egg drops required in the worst case with the optimal strategy.

Data Range#

$1 \le n \le 100$ , $1 \le m \le 10$

Sample Explanation#

An optimal strategy minimizes the number of drops in the worst case.

If you have only one egg, you can only start from the first floor; in the worst case, the hardness is 100, so you need 100 drops. If you use another strategy, you might not be able to determine the egg hardness (for example, if you drop on the second floor first and it breaks, you cannot determine whether the hardness is 0 or 1), i.e., in the worst case you would need infinitely many drops, so the answer for the first test case is 100.

Solution#

dp1#

Let f[i][j] denote the optimal number of drops for an interval of length i with j eggs.

For each egg j, there are two possibilities: not using egg j, i.e., f[i][j] = f[i][j-1]; using egg j, for the i positions 1..i there are i cases, choose one k; if the egg breaks we have f[k-1][j-1], if not we have f[i-k][j]. The worst-case is max(f[k-1][j-1], f[i-k][j]); the minimal strategy is min(f[i][j], max(f[k-1][j-1], f[i-k][j]) + 1).

1
#include<iostream>
2
#include<algorithm>
3
#include<cstring>
4
using namespace std;
5
const int N =110,M=11;
6
int n,m,f[N][M];
7

8
int main(){
9
    while(cin>>n>>m){
10
        for(int i=1;i<=n;i++) f[i][1] = i;
11
        for(int i=1;i<=m;i++) f[1][i] = 1;
12

13
        for(int i=2;i<=n;i++)
14
            for(int j=2;j<=m;j++){
15
                f[i][j] = f[i][j-1];
16
                for(int k=1;k<=i;k++)
17
                    f[i][j] = min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1);
18
            }
19
        cout<<f[n][m]<<endl;
20
    }return 0;
21
}

dp2#

Different from the previous method, let f[i][j] denote the maximum number of floors that can be tested with i moves and j eggs.

Assume the tested floor is k; there are two cases: the egg breaks (f[i-1][j-1], recurse to the lower part) or does not break (f[i-1][j], recurse upper part).

f[i][j] = f[i-1][j]+f[i-1][j-1]+1;

1
#include<iostream>
2
#include<algorithm>
3
#include<cstring>
4
using namespace std;
5
const int N =110,M=11;
6
int n,m,f[N][M];
7

8
int main(){
9
    while(cin>>n>>m){
10
        for(int i=1;i<=n;i++){
11
            for(int j=1;j<=m;j++)
12
                f[i][j] = f[i-1][j]+f[i-1][j-1]+1;
13

14
            if(f[i][m] >= n){
15
                cout<<i<<endl;
16
                break;
17
            }
18
        }
19
    }return 0;
20
}

Stack with min function#

Hulu interview question

Problem Description#

Design a stack that supports push, pop, top, and can retrieve the minimum element in O(1) time.

push(x) – push element x onto the stack
pop() – remove the top element
top() – get the top element
getMin() – get the minimum element in the stack

Constraints#

Total number of operations in [0,100].

Example#

1
MStack minStack = new MStack();
2
minStack.push(-1);
3
minStack.push(3);
4
minStack.push(-4);
5
minStack.getM();   --> Returns -4.
6
minStack.pop();
7
minStack.top();      --> Returns 3.
8
minStack.getM();   --> Returns -1.

Solution#

Method 1#

Directly store, for each position, the minimum value up to that position in an array.

1
class MinStack {
2
public:
3
    /** initialize your data structure here. */
4
    int len;
5
    int a[110],ck[110];
6

7
    MinStack() {
8
        len = a[0] = ck[0] = 0;
9
    }
10

11
    void push(int x) {
12
        a[len] = x;
13
        ck[len] = min(len?ck[len-1]:x,x);
14
        len++;
15
    }
16

17
    void pop() {
18
        len--;
19
    }
20

21
    int top() {
22
        return a[len-1];
23
    }
24

25
    int getMin() {
26
        return ck[len-1];
27
    }
28
};

Method 2#

Maintain the minimum values with a monotonic stack.

Keep ck as a monotone decreasing stack of minima by using ck.top() >= x. When popping, if the popped value equals the current minimum, pop from ck; otherwise, ck remains. The minimum is ck.top().

1
class MinStack {
2
public:
3
    /** initialize your data structure here. */
4
    stack<int> a;
5
    stack<int> ck;
6

7
    MinStack() {
8

9
    }
10

11
    void push(int x) {
12
        a.push(x);
13
        if(ck.empty() || ck.top() >= x)
14
            ck.push(x);
15
    }
16

17
    void pop() {
18
        if(ck.top() == a.top())
19
            ck.pop();
20
        a.pop();
21
    }
22

23
    int top() {
24
        return a.top();
25
    }
26

27
    int getMin() {
28
        return ck.top();
29
    }
30
};

Entry Node of Loop in Linked List#

Alibaba interview question

Problem Description#

Given a linked list, if it contains a loop, output the entry node of the loop.

If there is no loop, output null.

Constraints#

Node val range is [1,1000]. Node values are all distinct. List length is in [0,500].

Sample#

19_69ba6d14f5-QQ%E6%88%AA%E5%9B%BE20181202023846.png

1
Given the linked list as shown above:
2
[1, 2, 3, 4, 5, 6]
3
2
4
Note that 2 denotes the node with index 2, and node indices start at 0. So the node with index 2 has val equal to 3.
5
Then the entry node of the loop is the one with value 3.

Solution#

It turns out that with distinct values and a range up to 1000, you can use an array to record the first node seen for each value. When you visit a value that has already been recorded, you have found the loop.

1
class Solution {
2
public:
3
    ListNode *entryNodeOfLoop(ListNode *head) {
4
        ListNode* ck[1010];
5

6
        for(auto p=head;p;p=p->next){
7
            int val = p->val;
8
            if(ck[val])
9
                return ck[val];
10
            ck[val] = p;
11
        }return NULL;
12
    }
13
};

2266 字

6 分钟

面接アルゴリズム学習1

2023-08-11

algorithm

meeting

algorithm

ジグザグ行列#

マイクロソフトの面接問題

問題の説明#

入力は2つの整数 $n$ および $m$ を受け取り、 $n$ 行 $m$ 列の行列を出力する。数字 $1$ から $n \times m$ までをジグザグ蛇行の形で行列に埋める。

具体的な行列の形はサンプルを参照してください。

入力形式#

入力は1行で、2つの整数 $n$ と $m$ を含む。

出力形式#

条件を満たす行列を出力する。

行列は $n$ 行で、各行には $m$ 個の空白で区切られた整数が含まれる。

データ範囲#

$1 \le n,m \le 100$

解法#

シミュレーション法：#

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int N = 110;
6
int n,m,a[N][N];
7
int main(){
8
    cin>>n>>m;
9
    int l = 0,r = m-1, t = 0,d = n-1,cnt=1;
10
    while(l<=r || t <= d){
11
        for(int i=l;i<=r && t<=d;i++) a[t][i] = cnt++;t++;
12
        for(int i=t;i<=d && l<=r;i++) a[i][r] = cnt++;r--;
13
        for(int i=r;i>=l && t<=d;i--) a[d][i] = cnt++;d--;
14
        for(int i=d;i>=t && l<=r;i--) a[i][l] = cnt++;l++;
15
    }
16
    for(int i=0;i<n;i++)
17
        for(int j=0;j<m;j++)
18
            cout<<a[i][j]<<" \\n"[j==m-1];
19

20
    return 0;
21
}

ボトムアップのシミュレーション：#

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int N = 110;
6
int n,m,a[N][N],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
7
int main(){
8
    cin>>n>>m;int x=0,y=0;
9
    for(int i=1,u=0;i<=n*m;i++){
10
        a[x][y] = i;
11
        x += dx[u];y += dy[u];
12
        if(a[x][y] || x<0 || y<0 || x>=n || y>=m)
13
            x-=dx[u],y-=dy[u],u = (u+1)%4,
14
            x += dx[u],y += dy[u];
15
    }
16

17
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
18
        cout<<a[i][j]<<" \\n"[j==m-1];
19
    return 0;
20
}

単方向リストのクイックソート#

Megviiの面接問題

問題の説明#

与えられた単方向リストを、クイックソートアルゴリズムでソートしてください。

要求：平均時間計算量は $O(n \log n)$ 、追加の空間計算量は $O(\log n)$ 。

考察問題：リストの各ノードの val 値を変更せずに、構造だけを変える方法は？

データ範囲#

リスト中の全ての数は $int$ 範囲、リストの長さは $[0, 10000]$ 。

本問のデータは完全にランダムに生成。

解法#

通常のクイックソートとほぼ同様の考え方で、リストをある val で、小なり・等しい・大きいの3段に分け、前後の2段を再帰的にソートしてから、並べ替えた3段を前から後ろへ結合して完成。

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    ListNode* quickSortList(ListNode* head) {
12
        if(!head || !head->next) return head;
13

14
        auto left = new ListNode(-1),mid=new ListNode(-1),right=new ListNode(-1),
15
            ltail = left,mtail = mid,rtail = right;
16
        int val = head->val;
17

18
        for(auto p=head;p;p = p->next){
19
            if(p->val < val) ltail = ltail->next = p;
20
            else if(p->val == val) mtail = mtail->next = p;
21
            else rtail = rtail->next = p;
22
        }
23

24
        ltail->next = mtail->next = rtail->next = NULL;
25
        left->next = quickSortList(left->next);
26
        right->next = quickSortList(right->next);
27

28
        get_tail(left)->next = mid->next;
29
        get_tail(left)->next = right->next;
30

31
        auto p = left->next;
32
        delete left;delete mid;delete right;
33
        return p;
34
    }
35

36
    ListNode* get_tail(ListNode* head) {
37
        while (head->next) head = head->next;
38
        return head;
39
    }
40
};

峰値の探索#

峰値は、値が左右の隣接値より厳密に大きい要素を指します。

整数配列 nums が与えられ、峰値要素を見つけてそのインデックスを返してください。配列には複数の峰値が含まれることがあります。その場合、任意の峰値の位置を返せば良いです。

nums[-1] = nums[n] = -∞ を仮定します。

この問題を O(log n) の時間計算量で解く必要があります。

ヒント：

1 <= nums.length <= 1000
-2の31乗 <= nums[i] <= 2の31乗 - 1
有効な i に対して nums[i] != nums[i + 1]

解法#

傾斜が存在する場合、山の方向に沿って答えを見つけることができます。

1
class Solution {
2
public:
3
    int findPeakElement(vector<int>& nums) {
4
        int l=0,r = nums.size()-1;
5
        while(l<r){
6
            int mid = (l+r) >> 1;
7
            long long lm = mid-1,rm = mid+1;
8
            if(lm<0) lm = INT_MIN-1ll;
9
            else lm = nums[lm];
10
            if(rm>=nums.size()) rm = INT_MIN-1ll;
11
            else rm = nums[rm];
12
            long long key = nums[mid];
13
            if(key>lm && key>rm)
14
                return mid;
15
            else if(key>lm &&rm>key)
16
                l = mid+1;
17
            else
18
                r = mid-1;
19
        }return l;
20
    }
21
};

行列の極小値の探索#

マイクロソフトの面接問題

問題の説明#

$n \times n$ の行列を与える。行列には $n \times n$ 個の 互いに異なる 整数が含まれる。

極小値の定義：ある数値が、周囲の上下左右の4方向のいずれの値よりも小さい場合、その値は極小値と呼ばれます。

ある数の隣接数は、上下左右の4方向にある数を指します。境界や角にいる数の隣接数は4つ未満になることもあります。

$O(n \log n)$ の時間計算量で、任意の極小値の位置を見つけ、その行と列が何番目かを出力してください。

本問の行列は隠されています。事前に用意された int 関数 query で、行列中の任意の位置の数値を取得できます。

例えば query(a,b) は行列の第 $a$ 行第 $b$ 列の値を取得します。

注意：

行と列はともに0から始まります。
query() の呼び出し回数は $(n + 2) \times \lceil \log_2 n \rceil + n$ を超えてはいけません。
答えは一意ではないため、任意の極小値の位置を出力してください。

データ範囲#

$1 \le n \le 300$ 、行列中の整数は int 範囲。

解法#

前問と同様で、呼び出し回数をヒントとして利用します。 $\log_2 n$ 列を走査して、その列の最小値を含む行を調べます。ここで、二分の条件は、列の最小値とその行の左右の値の比較です。

1
// Forward declaration of queryAPI.
2
// int query(int x, int y);
3
// return int means matrix[x][y].
4
class Solution {
5
public:
6
    vector<int> getMinimumValue(int n) {
7
        typedef long long ll;
8
        ll INF = 1e15;
9
        int l,r;l=0;r = n-1;
10

11
        while(l<r){
12
            int mid = l+r>>1;
13
            ll val = INF;
14
            int p=0;
15
            for(int i=0;i<n;i++){
16
                int t = query(i,mid);
17
                if(t < val)
18
                    val = t,p = i;
19
            }
20
            ll lt = mid ? query(p,mid-1):INF;
21
            ll rt = mid+1<n ? query(p,mid+1):INF;
22

23
            if(val<lt && val<rt)
24
                return {p,mid};
25
            if(lt<val)
26
                r = mid - 1;
27
            else
28
                l = mid + 1;
29
        }
30

31
        ll val = INF;int p=0;
32
        for(int i=0;i<n;i++){
33
            int t = query(i,r);
34
            if(t<val)
35
                val = t,p = i;
36
        }
37
        return {p,r};
38

39
    }
40
};

卵の硬度#

Googleの面接問題

入力形式#

入力は複数のデータセットから成り、それぞれ1行に $n$ と $m$ の2つの正の整数が含まれます。 $n$ はビルの高度を、 $m$ は現在持っている卵の個数を表します。これらの卵の硬度は同じであり（同じ高さから落とすと、割れるか割れないかがすべて同じ）、 $n$ 以下です。

硬度が $x$ の卵は、高さが $x$ 以下の場所から投げても決して割れません（割れなかった卵は引き続き使用可能）、一方で $x$ より高い場所から投げると必ず割れます。

各データに対して、卵の硬度は $0$ から $n$ の範囲であると仮定します。つまり $n+1$ 層の高さから投げても必ず割れます。

出力形式#

各データセットについて、最適な戦略を用いた場合の最悪時に必要な投げ回数を1つの整数として出力します。

データ範囲#

$1 \le n \le 100$ , $1 \le m \le 10$

サンプルの説明#

最適戦略とは、最悪の場合の投げ回数を最小にする戦略のことです。

卵が1つしかない場合、最初の1階から投げるしかなく、最悪の場合硬度は 100 になるため、100 回投げる必要があります。別の戦略をとると、最悪の場合に硬度を測定できず、無限回投げる必要がある可能性があるため、最初のデータは 100 になります。

解法#

dp1#

長さ i の区間を j 個の卵で得られる最適戦略を表す。

卵 j を使う場合、使わない場合 f[i][j] = f[i][j-1]、使用する場合は区間の 1〜i のうちいくつかの k を選ぶ。このとき、卵が割れる場合（f[k-1][j-1]）、割れない場合（f[i-k][j]）、最悪はこの二者の大きさの最大値。最小の戦略は min(f[i][j], max(f[k-1][j-1], f[i-k][j]) + 1)

1
#include<iostream>
2
#include<algorithm>
3
#include<cstring>
4
using namespace std;
5
const int N =110,M=11;
6
int n,m,f[N][M];
7

8
int main(){
9
    while(cin>>n>>m){
10
        for(int i=1;i<=n;i++) f[i][1] = i;
11
        for(int i=1;i<=m;i++) f[1][i] = 1;
12

13
        for(int i=2;i<=n;i++)
14
            for(int j=2;j<=m;j++){
15
                f[i][j] = f[i][j-1];
16
                for(int k=1;k<=i;k++)
17
                    f[i][j] = min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1);
18
            }
19
        cout<<f[n][m]<<endl;
20
    }return 0;
21
}

dp2#

異なる方法として、f[i][j] は i 回の測定で j 個の卵を使って得られる最大長さを表す。

測定位置 k を仮定すると、卵が割れる（f[i-1][j-1]、下半分を再帰）または割れない（f[i-1][j]、上半分を再帰）という二つのケース。

1
#include<iostream>
2
#include<algorithm>
3
#include<cstring>
4
using namespace std;
5
const int N =110,M=11;
6
int n,m,f[N][M];
7

8
int main(){
9
    while(cin>>n>>m){
10
        for(int i=1;i<=n;i++){
11
            for(int j=1;j<=m;j++)
12
                f[i][j] = f[i-1][j]+f[i-1][j-1]+1;
13

14
            if(f[i][m] >= n){
15
                cout<<i<<endl;
16
                break;
17
            }
18
        }
19
    }return 0;
20
}

最小値を含むスタック#

Huluの面接問題

問題の説明#

push，pop，top などの操作をサポートし、かつ最小値を O(1) で検索できるスタックを設計する。

push(x) – 要素 x をスタックに挿入
pop() – スタックのトップ要素を取り除く
top() – ストップ要素を得る
getMin() – スタック中の最小要素を得る

データ範囲#

操作コマンドの総数は [0,100]。

サンプル#

1
MStack minStack = new MStack();
2
minStack.push(-1);
3
minStack.push(3);
4
minStack.push(-4);
5
minStack.getM();   --> Returns -4.
6
minStack.pop();
7
minStack.top();      --> Returns 3.
8
minStack.getM();   --> Returns -1.

解法#

方法1#

挿入時にその時点の最小値を格納する形で、配列を直接使います。

1
class MinStack {
2
public:
3
    /** initialize your data structure here. */
4
    int len;
5
    int a[110],ck[110];
6

7
    MinStack() {
8
        len = a[0] = ck[0] = 0;
9
    }
10

11
    void push(int x) {
12
        a[len] = x;
13
        ck[len] = min(len?ck[len-1]:x,x);
14
        len++;
15
    }
16

17
    void pop() {
18
        len--;
19
    }
20

21
    int top() {
22
        return a[len-1];
23
    }
24

25
    int getMin() {
26
        return ck[len-1];
27
    }
28
};

方法2#

単調スタックを用いて最小値を維持します。

ck.top() >= x の場合、ck に格納される値は単調減少の最小値になります。pop の場合、ck の現在の最小値と一致しなければ ck の更新は不要です。最小値を取得するには ck.top() を使います。

1
class MinStack {
2
public:
3
    /** initialize your data structure here. */
4
    stack<int> a;
5
    stack<int> ck;
6

7
    MinStack() {
8

9
    }
10

11
    void push(int x) {
12
        a.push(x);
13
        if(ck.empty() || ck.top() >= x)
14
            ck.push(x);
15
    }
16

17
    void pop() {
18
        if(ck.top() == a.top())
19
            ck.pop();
20
        a.pop();
21
    }
22

23
    int top() {
24
        return a.top();
25
    }
26

27
    int getMin() {
28
        return ck.top();
29
    }
30
};

リンケージ内の環の入口結点#

アリババの面接問題

問題の説明#

リストが与えられ、もし環が含まれていれば、その環の入口ノードを出力してください。環が含まれていない場合は null を出力します。

データ範囲#

ノードの val の値は $[1,1000]$ 。ノードの val はすべて異なります。リストの長さは $[0,500]$ 。

サンプル#

1
上記のようなリスト：
2
[1, 2, 3, 4, 5, 6]
3
2
4
ここでの 2 は番号が 2 のノードを表します。ノード番号は 0 から始まるので、番号が 2 のノードは val が 3 のノードです。
5
したがって環の入口ノードは 3 です。

解法#

val の値は異なり範囲が 1000 に限定されていることから、既に出現した val 値に対応するノードを記録する配列を用いればよい。再度同じ val に出会うと、それが循環を示します。

1
class Solution {
2
public:
3
    ListNode *entryNodeOfLoop(ListNode *head) {
4
        ListNode* ck[1010];
5

6
        for(auto p=head;p;p=p->next){
7
            int val = p->val;
8
            if(ck[val])
9
                return ck[val];
10
            ck[val] = p;
11
        }return NULL;
12
    }
13
};

面试算法学习1

https://dreaife.tokyo/posts/interview-algorithms/

作者

dreaife

发布于

2023-08-11

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

rabbitMQ初识

docker初识

dreaife的休憩小栈

蛇形矩阵#

题目描述#

输入格式#

输出格式#

数据范围#

解法#

模拟法：#

触底模拟：#

单链表快速排序#

题目描述#

数据范围#

解法#

寻找峰值#

解法#

寻找矩阵的极小值#

题目描述#

数据范围#

解法#

鸡蛋的硬度#

输入格式#

输出格式#

数据范围#

样例解释#

解法#

dp1#

dp2#

包含min函数的栈#

题目描述#

数据范围#

样例#

解法#

方法一#

方法二#

链表中环的入口结点#

题目描述#

数据范围#

样例#

解法#

Spiral Matrix#

Problem Description#

Input format#

Output format#

Constraints#

Solution#

Simulation Method:#

Boundary-following Simulation:#

Quick Sort on a Singly Linked List#

Problem Description#

Constraints#

Solution#

Find Peak Element#

Solution#

Find a Local Minimum in a Matrix#

Problem Description#

Data Range#

Solution#

Egg Dropping Problem#

Input Format#

Output Format#

Data Range#

Sample Explanation#

Solution#

dp1#

dp2#

Stack with min function#

Problem Description#

Constraints#

Example#

Solution#

Method 1#

Method 2#

Entry Node of Loop in Linked List#

Problem Description#

Constraints#

Sample#

Solution#

ジグザグ行列#

問題の説明#

入力形式#