秋招日寄|海康威视软件开发工程师-应用笔试20240904

试卷名称： 软件开发工程师-应用

开始时间： 2024-09-04 12:00 星期三

考试时长： 90 分钟

结束时间： 2024-09-05 23:59 星期四 

第一题：单选题*15

第二题：多选题*5

第三题：简答题*2

第四题：编程题*1（从C和C++选）

简答题1：

关键字static的作用

简答题2：

根据宏定义写出如下函数打印输出
#define MAX VAL(a,b) (a) > (b) ? (a) : (b)
#define MIN _vAL(a,b) (a) = (b) ? (a) : (b)
int max_min_test(void) {
    int a = 2, b = 1, ret = 0;
    ret = MAX_VAL(a, b) + 3;
    printf("%d\n", ret);
    ret = MIN_VAL(b, a) + 3;
    printf("%d\n", ret);
    return 0;
}

编程题：

题目描述：
输入两个链表，找出他们的第一个公共结点。链表结点定义如下：
struct ListNode {
    int m_nKey;
    ListNode* m_pNext;
};

假设链表1的长度为m，链表2的长度为n，求时间算法复杂度。

输入描述：
依次输入两个数组，
先输入第一个数组的长度，再输入数组值，然后输入第二个数组的长度，以及第二个数组值，
输入公共节点的值，
输入从第一个数组第几个值开始公共部分；
输入从第二个数组第几个值开始公共部分。

输出描述：
打印输出第一个公共节点的值，以及打印时间复杂度。

比如输入：
5
4 1 8 4 5
6
5 0 1 8 4 5
8
2
3

输出：
8
O(m+n)

#include <iostream>
using namespace std;

struct ListNode {
    int m_nKey;
    ListNode* m_pNext;
};

int getLength(ListNode* head) {
    int length = 0;
    while (head != nullptr) {
        length++;
        head = head->m_pNext;
    }
    return length;
}

ListNode* findFirstCommonNode(ListNode* head1, ListNode* head2) {
    int len1 = getLength(head1);
    int len2 = getLength(head2);

    if (len1 > len2) {
        int diff = len1 - len2;
        while (diff--) head1 = head1->m_pNext;
    } 
    
    else {
        int diff = len2 - len1;
        while (diff--) head2 = head2->m_pNext;
    }

    while (head1 != nullptr && head2 != nullptr) {
        if (head1 == head2) return head1;
        head1 = head1->m_pNext;
        head2 = head2->m_pNext;
    }
    return nullptr;
}

int main() {
    int m, n;
    cin >> m;

    ListNode* head1 = nullptr;
    ListNode* tail1 = nullptr;
    for (int i = 0; i < m; ++i) {
        int val;
        cin >> val;
        
        ListNode* newNode = new ListNode{val, nullptr};
        if (head1 == nullptr) head1 = tail1 = newNode;    
        else {
            tail1->m_pNext = newNode;
            tail1 = newNode;
        }
    }

    cin >> n;

    ListNode* head2 = nullptr;
    ListNode* tail2 = nullptr;
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        
        ListNode* newNode = new ListNode{val, nullptr};
        if (head2 == nullptr) head2 = tail2 = newNode;
        else {
            tail2->m_pNext = newNode;
            tail2 = newNode;
        }
    }

    int commonVal, index1, index2;
    cin >> commonVal >> index1 >> index2;

    ListNode* commonNode = new ListNode{commonVal, nullptr};
    tail1->m_pNext = commonNode;
    tail2->m_pNext = commonNode;

    for (int i = index1; i < m; ++i) {
        int val;
        cin >> val;
        ListNode* newNode = new ListNode{val, nullptr};
        commonNode->m_pNext = newNode;
        commonNode = newNode;
    }

    ListNode* result = findFirstCommonNode(head1, head2);
    if (result) cout << result->m_nKey << endl;

    cout << "O(m+n)" << endl;

    return 0;
}