面试| “讲究的是一个叛逆”

面试 | “主打的是一个叛逆”

面试官：你周围的同学都学什么语言呢？

我： JAVA ，前端比较多。

面试官：那你为什么要选C++？

我：主打的是一个叛逆吧啊哈哈…..

……

遇到的实习岗位的几个面试题，有一个代码题我忘了是啥了，和一些比较关键的问题吧

笔试

字符串反转

没什么好说的，不允许使用额外内存那就用指针换呗，用c的写法，用的两个指针

void reverse(char* cstr){
     int length = sizeof(str);//这里我使用的是sizeof
    char *left = str;
    char *right = str + length - 2 ;//不需要反转字符串\0

    while (left < right) {
        // 交换左右两个字符
        char temp = *left;
        *left = *right;
        *right = temp;
        left++;
        right--;
    }
}

二叉树最大深度

这玩意，写了个伪代码出来（题目上写着伪代码也可）。思路没毛病，递归，求当前节点的最大深度（迭代也可以），比较左右子数的最大深度就行。

递归的实现

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};//定义一个二叉树节点结构体

//递归调用
int maxDepth(TreeNode* root){
    if(root == NULL){
        return 0;
    }//根为0就为0
    int leftDepth = MaxDepth(root->left);
    int rightDepth = MaxDepth(root->right);
    int depth = maxDepth(root);
    return std::max(leftDepth, rightDepth) + 1;

}

迭代的实现

int maxDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
	//用队列存放二叉树结构
    std::queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        int levelSize = q.size(); // 当前层的节点数
        // 将当前层的所有节点出队，并将下一层的节点入队
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();

            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
        depth++; // 深度加一，表示已经遍历完一层
    }
    return depth;
}

最长递增序列子串长度

草稿上想了一会补出来了使用的滑动窗口双指针的方法，有很多小问题。并且我感觉动态规划也是可以做到的，参照下方的最大回文子串实现

滑动窗口的实现

int longestSubSize(vector<int>& nums){
    
    int n = nums.size();
    if (n <= 1) {
        return n;
    }

    int left = 0; // 左指针
    int maxLen = 1; // 最长递增子序列的长度
    int curLen = 1; // 当前子序列的长度
    for (int right = 1; right < n; ++right) {
        if (nums[right] > nums[right - 1]) {
            curLen++;
            maxLen = max(maxLen, curLen);
        } else {
            left = right;
            curLen = 1;
        }
    }
    return maxLen;
    
}

动态规划的题解

  int longestSubSize(vector<int>& nums){
    
  int n = nums.size();
    if (n == 0) {
        return 0;
    }
    // 创建一个动态规划数组，dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
    std::vector<int> dp(n, 1);
    // 初始化最大长度为1
    int maxLen = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            // 如果 nums[i] 大于 nums[j]，则可以将 nums[i] 添加到以 nums[j] 结尾的子序列中
            if (nums[i] > nums[j]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
        // 更新最大长度
        maxLen = std::max(maxLen, dp[i]);
    }
    return maxLen;
    
}

最大回文子串

暴力写法想了半天天，感觉暴力相当的捞。不是代码捞，是写代码的人捞，现在重新回顾一下发现LeetCode以前还做过，丢人了我去，这题我甚至还超过动态规划的题解 。超过也不见得能当场写出来就是了

暴力的写法当时没有写完，时间不够了，（在题目下方写了个动归，面试官看了看没说话 XP）总得来说就是。两个for循环找子串，把所有满足的子串存起来，最后比较最大子串并返回。

暴力的写法

bool isHuiwen(string &s, int start, int end) {
    while (start < end) {
        if (s[start] != s[end]) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}


string longestHuiwenSub(string& s) {
    int n = s.length();
    if (n <= 1) {
        return s;
    }
    string longest = "";
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            if (isHuiwen(s, i, j) && (j - i + 1) > longest.length()) {
                longest = s.substr(i, j - i + 1);
            }
        }
    }

    return longest;
}

抄的动态规划的题解

string longestPalindrome(string& s) {
    int n = s.length();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int start = 0; // 记录最长回文子串的起始位置
    int maxLen = 1; // 记录最长回文子串的长度

    // 单个字符都是回文
    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
    }

    // 枚举长度
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                if (len == 2 || dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    if (len > maxLen) {
                        maxLen = len;
                        start = i;
                    }
                }
            }
        }
    }

    return s.substr(start, maxLen);
}

双指针的解法

我感觉双指针也是没有问题的。在评论区翻找一会确实发现了双指针的写法（内核是中心扩展），也顺便贴上来，并做好注释。

string longestPalindrome(string& s) {
    int n = s.length();
    if (n <= 1) {
        return s;
    }
    int start = 0; // 记录最长回文子串的起始位置
    int maxLen = 1; // 记录最长回文子串的长度
    for (int i = 0; i < n; ++i) {
        // 以当前字符为中心向左右扩展
        int left = i, right = i;
        // 向右扩展
        while (right < n - 1 && s[right] == s[right + 1]) {
            right++;
        }
        // 向外扩展，直到不是回文串为止
        while (left > 0 && right < n - 1 && s[left - 1] == s[right + 1]) {
            left--;
            right++;
        }
        // 计算当前回文子串的长度
        int curLen = right - left + 1;
        // 更新最长回文子串的信息
        if (curLen > maxLen) {
            maxLen = curLen;
            start = left;
        }
    }

    return s.substr(start, maxLen);

面试提问与回答

32位下的进程模型

面试官：32位下的进程模型你知道吗？

我：嗯，代码段那些吗？

面试官： 地址，内存位置（我这里也记不太清是怎么问的了）

我： 首先是内核，然后是栈，未使用内存 ，嗯有4G， 用户区有3G，我要不画一下吧。

除了栈区和堆区地址生长方向画反了（但是我嘴上说对了栈是向上，堆区是向下），动态库加载去跟未用空间画反了以外，嗯，应该跟该图一致。

C++特性

面试官：C++11 14 17 20 这些特性有了解吗？

我：我比较了解 C++11 ，20 的特性有看了一些，比如说，协程，和import 关键词 模块导入等等

面试官：也就是说主用 C++11 了？你常用常见的C++特性有哪些呢？

我：最常用的就是 智能指针了吧

面试官：说说看，比如 Shared_ptr 和 unique_ptr 和 week_ptr的区别，和你怎么作用呢

我： 顾名思义的，共享就是共享，但是只有一份，共享指针维护了一个引用变量，如果有人引用就++，这个++是原子操作，但是这个指针本身并不是线程安全的。嗯，唯一就是唯一，只能有一个人用也只有一份，弱，嗯，我实际不怎么用，但是一般配合Shared_ptr的解决循环引用的问题。

面试官：还有呢？

我： 还有lambda函数 ，qt里常常用，连接信号的槽函数，我常常是使用lambda写的。

视频服务器实现

面试官：你这个项目服务器部署在Linux？用到了什么模块？能说说吗

我：嗯，有http模块 ，数据库模块，使用的是sqlite3 也可以是 MySQL，都提供了不同的借口。
嗯、还有一个日志模块，异步的，通过封装好的进程类使用，进程之间通过本地套接字进行通信。
嗯，利用http模块，哦，还有开源的openssl库，利用md5的加密签名吧，跟数据库模块实现了一个客户端登录的验证。

vlc

面试官：你这个项目的客户端，是用的vlc的客户端？那你的基于Qt是在哪里体现的呢？

我：不是不是，嗯，我用的不是vlc现成的客户端，虽然vlc现成的客户端界面也是qt写的就是了，
我主要是使用官网开源编译的sdk,并进行了一个封装，在qt里进行调用，自己写的界面。

面试官：也就是说是个换皮咯？

我：嗯对对对

面试官：能给我看看界面，比如截图什么的吗？

我：呃，那个，手机里并没有存，，但是笔记本里有，没有带来。

RTSP，视频的推拉流的处理

面试官：我看你的这个视频服务器，用到了什么协议，视频流推拉流怎么处理

我：用到了 RTSP的协议， 嗯视频编码用到了 H264,

面试官：嗯嗯，你这个服务器利用RTSP 拉流给客户端，那你的客户端是怎么处理这个视频流的？

我：这个，，，嗯，我刚刚说了我封装了VLC 现有的SDK，我对底层的实现怎么处理这个视频流没有太多了解，我只进行了一个封装函数的调用，就是拉流，这一块我不太清楚。。直接就是输入RTSP//地址就调用了。

这里回答是有误的，目前我对这一块的理解不深，暂时没有什么头绪，等我整明白了在更新本段。

Epoll select poll 的区别

面试官：你说说Epoll select poll的区别？

我：嗯 首先，在系统上，epoll 只能在Linux下使用，select可以在Windows和Linux都可以使用

可以处理的IO socket select有个上限，具体的值是1024,但是实际上嗯，他也可以修改，epoll没有这个限制，嗯epoll的….

面试官：你说的这些不是重点，主要是机制

我： 嗯，哦， epoll是事件驱动的，但是select 嗯。。。好像也是啊。嗯epoll有两种不同的触发方式？边沿和水平？边沿的触发是

面试官：(打断)这也不是关键。

我：嗯，epoll他底层不是线性的找事件，我记得，内核维护一个红黑树队列好像找事件特别快。select维护的是个数组，需要遍历轮序，找事件比较慢？

面试官： （似乎听不下去了）select 的轮询是线性的，监视的文件描述符需要都遍历一遍时间复杂度是 O(n)。epoll呢轮询不是线性的，一有事件就立即返回。时间复杂度一般是O(1);

正确答案：

1. 性能差异：
   • select：在调用 select 函数后，它会遍历所有的文件描述符，查找其中是否有事件就绪，这导致其性能在处理大量文件描述符时较差。
   • epoll：epoll 使用了更高效的数据结构，可以在事件就绪时立即返回，而不需要遍历所有的文件描述符。这使得 epoll 在处理大量文件描述符时具有更好的性能。。
2. 事件触发方式：
   • select：select 使用水平触发（LT）方式，即当文件描述符上有数据可读或可写时，会一直通知应用程序，直到应用程序处理完数据。这可能会导致频繁的事件通知，需要应用程序自行管理缓冲区。
   • epoll：epoll 支持水平触发（LT）和边缘触发（ET）两种触发方式。边缘触发只在状态变化时通知应用程序，需要应用程序自行管理缓冲区，而水平触发会一直通知应用程序直到数据读取完毕或写入完毕。
3. 文件描述符数量限制：
   • select：根据操作系统的不同，select 通常有文件描述符数量的限制，这个限制通常是较小的，例如1024或2048个。
   • epoll：epoll 没有文件描述符数量的限制，可以处理大量文件描述符，因此适用于高性能服务器应用程序。
4. 支持的事件类型：
   • select：主要用于监视可读、可写和异常等基本事件。
   • epoll：支持多种事件类型，包括可读、可写、错误、边缘触发等。这使得 epoll 更灵活，可以更精细地控制事件的处理。

总的来说，epoll 在性能和功能上通常优于 select，特别适用于需要处理大量文件描述符的高性能服务器应用程序。但需要注意的是，epoll 是Linux特有的，不跨平台，而 select 在不同操作系统上都有支持。因此，选择使用哪种机制取决于应用程序的需求和目标平台。

UDP 问到了，跟上一篇文章一样说的，面试官也没有给予反馈。

还有一些情景题，面试官并没有进行评价，不知道是答的错还是对，有点蛋疼。。。

总结

做题，还是不习惯纸上写，没有IDE 脑子一片混沌，诶，只能努力适应吧，面试的表达能力，还是不太行，专业术语用的少了些

笔试，技术面1 技术面2，人事面，然后回去等通知，通知是待定，正在商议。有点无语。