開頭簡單的自我介紹，面試官和我聊了聊天緩解個人緊張狀況，然后就讓開屏幕共享開視頻做題目，做完以后，問了一些問題，就讓等通知了，估計是涼了，不過這里且把當時做的筆試題目復盤一下吧！題目是ai做的題解，唉，AI都比我強，比我面試的時候解釋的強多了，未來該何去何從啊...
微*團隊筆試題
45分鐘
一、填空題
1、請計算32位機器上如下代碼輸出值：
void Func(char str[100]){
cout<<sizeof(str)<<endl;
}
int main(){
char str[] = "Hello";
char *p = str;
int n = 10;
void *p1 = malloc(100);
cout<<sizeof(str)<<endl;//6
cout<<sizeof(p)<<endl; //8
cout<<sizeof(p1)<<endl; //8
cout<<sizeof(n)<<endl;//4
Func(str);//8
return 0;
}
2、請問運行Test函數(shù)會有出現(xiàn)結果： 段錯誤_____
#include <bits/stdc++.h>
using namespace std;
void GetMemory(char *p){
p = (char *)malloc(100);
}
void Test(void) {
char *str = NULL;
GetMemory(str);
strcpy(str, "hello world");
printf("%s\n",str);
}
int main(){
Test();
return 0;
}
這段代碼會出現(xiàn)段錯誤的原因是在GetMemory函數(shù)中，雖然p指針指向了分配的內(nèi)存空間，但是由于p是傳遞的指針副本，函數(shù)結束后并不會改變原來的指針str，因此在Test函數(shù)中使用str指針時，它仍然是NULL指針，所以會出現(xiàn)段錯誤。
為了解決這個問題，可以將GetMemory函數(shù)的參數(shù)改為指向指針的指針，這樣就可以改變原來的指針了。修改后的代碼如下：
#include <bits/stdc++.h>
using namespace std;
void GetMemory(char **p){
*p = (char *)malloc(100);
}
void Test(void) {
char *str = NULL;
GetMemory(&str); // 傳遞指向指針的指針
strcpy(str, "hello world");
printf("%s\n",str);
}
int main(){
Test();
return 0;
}
3、static局部變量與普通局部變量有什么區(qū)別
static局部變量和普通局部變量的主要區(qū)別在于它們的生命周期和作用域。
普通局部變量的生命周期只存在于函數(shù)調(diào)用期間，當函數(shù)返回時，它所占用的內(nèi)存空間會被釋放。因此，每次函數(shù)調(diào)用時，都會重新創(chuàng)建一個新的局部變量。
而static局部變量的生命周期則存在于整個程序運行期間，即使函數(shù)返回，它所占用的內(nèi)存空間也不會被釋放。因此，static局部變量在第一次創(chuàng)建后就一直存在于內(nèi)存中，下次函數(shù)調(diào)用時可以繼續(xù)使用之前的值。
另外，static局部變量的作用域僅限于定義它的函數(shù)內(nèi)部，但是它在函數(shù)調(diào)用期間保持其值不變，因此可以用來實現(xiàn)函數(shù)內(nèi)部的計數(shù)器或狀態(tài)標記等功能。
總之，static局部變量和普通局部變量都是在函數(shù)內(nèi)部定義的局部變量，但是它們的生命周期和作用域有所不同。
4、寫出下列代碼的輸出內(nèi)容
include <stdio.h>
int inc(int a){
return (++a);
}
int multi(int* a, int *b, int* c){
return(*c = *a * *b);
}
typedef int (*FUNC1 ) (int in);
typedef int (*FUNC2) (int*, int*, int*);
void show(FUNC2 fun, int arg1, int* arg2){
FUNC1 p = &inc;
int temp = p(arg1);
fun(&temp, &arg1, arg2);
printf(" %d\n", *arg2);
}
main(){
int a;
show(multi, 10, &a);
return 0;
}
110
5、請找出下面代碼中的所有錯誤
說明：以下代碼是把一個字符串倒序，如“abcd”倒序后變?yōu)椤癲cba”
#include "string.h"
main()
{
char* src = "hello , world";
char* dest = NULL;
int len = strlen(src);
dest = (char*) malloc(len );
char* d = dest;
char* s = src[len];
while(len-- != 0 )
d++ = s--;
printf("%s", dest);
return 0;
}
#include <string.h>
#include <stdlib.h> // 需要包含stdlib.h頭文件
int main() { // main函數(shù)需要指定返回值類型int
const char* src = "hello , world"; // src是指向字符串常量的指針，需要加上const關鍵字
char* dest = NULL;
int len = strlen(src);
dest = (char*) malloc(len + 1); // 分配的內(nèi)存空間應該是len+1，因為字符串以'\0'結尾
char* d = dest + len - 1; // d指向dest的最后一個字符
const char* s = src; // s指向src的第一個字符
while(len-- != 0) {
*d-- = *s++; // 將s所指向的字符賦值給d所指向的字符，并將d和s分別向前和向后移動一位
}
*d = '\0'; // 需要在dest的末尾添加'\0'，使其成為一個以'\0'結尾的字符串
printf("%s", dest);
free(dest); // 釋放動態(tài)分配的內(nèi)存
return 0;
}
/*
忘記包含stdlib.h頭文件，導致編譯器無法識別malloc和free函數(shù)。
src是指向字符串常量的指針，需要加上const關鍵字。
分配的內(nèi)存空間應該是len+1，因為字符串以'\0'結尾。
d指向dest的最后一個字符，而不是dest的第一個字符。
s指向src的第一個字符，而不是src的最后一個字符。
在while循環(huán)中，需要將s所指向的字符賦值給d所指向的字符，并將d和s分別向前和向后移動一位。
需要在dest的末尾添加'\0'，使其成為一個以'\0'結尾的字符串。
在程序結束前需要釋放動態(tài)分配的內(nèi)存
*/
6.請問下面代碼是否合法，為什么？
uint16_t wId = 2; //合法賦值
uint16_t* p1 = &wId; //合法，p1指向wld
uint32_t *p2 = p1; //原因是在將uint16_t類型的指針p1賦值給uint32_t類型的指針p2時，發(fā)生了類型不匹配的錯誤。p1指向的是一個16位的無符號整數(shù)，而p2指向的是一個32位的無符號整數(shù)，這兩種類型的指針所指向的數(shù)據(jù)的大小不同。因此，將p1賦值給p2會導致指針類型不匹配的錯誤。
uint32_t dwId = *p2; //程序試圖將一個32位的無符號整數(shù)賦值給一個16位的無符號整數(shù)，這會導致截斷錯誤。具體來說，如果dwId的值大于16位無符號整數(shù)的最大值（65535），則只會保留低16位，高16位會被截斷。這可能會導致程序邏輯錯誤或崩潰。
二、編程題
請編寫能直接實現(xiàn)strstr()函數(shù)功能的代碼(在str1中找到是否包含str2，若包含返回str1中匹配的起始指針)
char* strstr(const char* str1, const char* str2) {
if (*str2 == '\0') {
return (char*) str1;
}
const char* p1 = str1;
while (*p1 != '\0') {
const char* p1_begin = p1;
const char* p2 = str2;
while (*p1 != '\0' && *p2 != '\0' && *p1 == *p2) {
p1++;
p2++;
}
if (*p2 == '\0') {
return (char*) p1_begin;
}
if (*p1 == '\0') {
return nullptr;
}
p1 = p1_begin + 1;
}
return nullptr;
}
/*
該函數(shù)首先判斷str2是否為空字符串，如果是，則直接返回str1的起始指針。然后在str1中循環(huán)查找，每次從當前位置開始，與str2逐個字符比較，如果匹配成功，則繼續(xù)比較下一個字符，否則從下一個位置開始重新比較。如果str2匹配完了，則返回當前位置的起始指針；如果str1匹配完了，則表示沒有找到，返回nullptr。
*/
//kmp算法
#include <iostream>
#include <vector>
using namespace std;
// 計算next數(shù)組
void getNext(string pattern, vector<int>& next) {
int n = pattern.size();
next.resize(n);
next[0] = -1;
int j = -1;
for (int i = 1; i < n; i++) {
while (j >= 0 && pattern[i] != pattern[j + 1]) {
j = next[j];
}
if (pattern[i] == pattern[j + 1]) {
j++;
}
next[i] = j;
}
}
// KMP算法
int kmp(string text, string pattern) {
int n = text.size();
int m = pattern.size();
if (m == 0) {
return 0;
}
vector<int> next;
getNext(pattern, next);
int j = -1;
for (int i = 0; i < n; i++) {
while (j >= 0 && text[i] != pattern[j + 1]) {
j = next[j];
}
if (text[i] == pattern[j + 1]) {
j++;
}
if (j == m - 1) {
return i - j;
}
}
return -1;
}
int main() {
string text = "ababcabcacbab";
string pattern = "abcac";
int pos = kmp(text, pattern);
if (pos == -1) {
cout << "Pattern not found in text" << endl;
} else {
cout << "Pattern found in text at position " << pos << endl;
}
return 0;
}
KMP算法的思路是，在匹配字符串的過程中，當發(fā)現(xiàn)某個字符不匹配時，不需要從頭開始重新匹配，而是利用已經(jīng)匹配的信息，盡可能地減少比較次數(shù)。
具體實現(xiàn)上，首先需要計算出模式串的next數(shù)組，next數(shù)組表示當匹配失敗時，應該將模式串向右移動幾位。然后在匹配字符串的過程中，利用next數(shù)組進行跳轉(zhuǎn)。如果當前字符匹配成功，則繼續(xù)比較下一個字符；如果匹配失敗，則根據(jù)next數(shù)組跳轉(zhuǎn)到模式串的某個位置，重新開始比較。
在上面的代碼中，getNext函數(shù)計算模式串的next數(shù)組，kmp函數(shù)實現(xiàn)了KMP算法。
三、算法（以下兩題，任選一題）
1、用拉鏈法實現(xiàn)hash，接口：插入，查找，刪除
hash函數(shù)，可以不實現(xiàn)
要求要用鏈表實現(xiàn)
#include <iostream>
#include <vector>
using namespace std;
// 哈希表節(jié)點
struct HashNode {
int key;
int value;
HashNode* next;
HashNode(int k, int v) : key(k), value(v), next(nullptr) {}
};
// 哈希表
class HashTable {
private:
vector<HashNode*> table;
int capacity;
int size;
// 計算哈希值
int hash(int key) {
return key % capacity;
}
public:
// 構造函數(shù)
HashTable(int cap) : capacity(cap), size(0) {
table.resize(capacity, nullptr);
}
// 插入元素
void insert(int key, int value) {
int index = hash(key);
HashNode* node = table[index];
while (node != nullptr) {
if (node->key == key) {
node->value = value;
return;
}
node = node->next;
}
node = new HashNode(key, value);
node->next = table[index];
table[index] = node;
size++;
}
// 查找元素
bool find(int key, int& value) {
int index = hash(key);
HashNode* node = table[index];
while (node != nullptr) {
if (node->key == key) {
value = node->value;
return true;
}
node = node->next;
}
return false;
}
// 刪除元素
bool remove(int key) {
int index = hash(key);
HashNode* node = table[index];
HashNode* prev = nullptr;
while (node != nullptr) {
if (node->key == key) {
if (prev == nullptr) {
table[index] = node->next;
} else {
prev->next = node->next;
}
delete node;
size--;
return true;
}
prev = node;
node = node->next;
}
return false;
}
};
int main() {
HashTable hashTable(10);
hashTable.insert(1, 10);
hashTable.insert(2, 20);
hashTable.insert(3, 30);
int value;
if (hashTable.find(2, value)) {
cout << "Value of key 2 is " << value << endl;
} else {
cout << "Key 2 not found" << endl;
}
if (hashTable.remove(3)) {
cout << "Key 3 removed" << endl;
} else {
cout << "Key 3 not found" << endl;
}
return 0;
}
/*
哈希表是一種常用的數(shù)據(jù)結構，它可以實現(xiàn)快速的查找、插入和刪除操作。哈希表的核心思想是將鍵映射到一個存儲位置，這個存儲位置就是哈希值。為了解決哈希沖突，可以使用拉鏈法，即將每個哈希值對應的元素放在一個鏈表中。
上面的代碼中，HashTable類表示哈希表，HashNode結構體表示哈希表的節(jié)點。哈希表使用vector實現(xiàn)，每個元素是一個指向鏈表頭節(jié)點的指針。插入、查找、刪除操作都需要計算出哈希值，然后在相應的鏈表中進行操作。
*/
2、實現(xiàn)一個大根堆，兩個過程：
a、構建堆文章來源：http://www.zghlxwxcb.cn/news/detail-482196.html
b、彈出堆頂數(shù)據(jù)文章來源地址http://www.zghlxwxcb.cn/news/detail-482196.html
#include <iostream>
#include <vector>
using namespace std;
// 構建大根堆
void buildMaxHeap(vector<int>& nums) {
int n = nums.size();
for (int i = n / 2 - 1; i >= 0; i--) { // 從最后一個非葉子節(jié)點開始調(diào)整
int j = i;
while (j * 2 + 1 < n) { // 如果有左孩子
int k = j * 2 + 1; // 左孩子的下標
if (k + 1 < n && nums[k + 1] > nums[k]) { // 如果有右孩子且右孩子比左孩子大
k++; // 右孩子的下標
}
if (nums[k] > nums[j]) { // 如果孩子比父節(jié)點大
swap(nums[k], nums[j]); // 交換父節(jié)點和孩子
j = k; // 繼續(xù)向下調(diào)整
} else {
break;
}
}
}
}
// 彈出堆頂元素
int popMaxHeap(vector<int>& nums) {
int n = nums.size();
int maxVal = nums[0];
nums[0] = nums[n - 1]; // 把最后一個元素放到堆頂
nums.pop_back(); // 刪除最后一個元素
n--;
int i = 0;
while (i * 2 + 1 < n) { // 如果有左孩子
int j = i * 2 + 1; // 左孩子的下標
if (j + 1 < n && nums[j + 1] > nums[j]) { // 如果有右孩子且右孩子比左孩子大
j++; // 右孩子的下標
}
if (nums[j] > nums[i]) { // 如果孩子比父節(jié)點大
swap(nums[j], nums[i]); // 交換父節(jié)點和孩子
i = j; // 繼續(xù)向下調(diào)整
} else {
break;
}
}
return maxVal;
}
int main() {
vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
buildMaxHeap(nums);
while (!nums.empty()) {
cout << popMaxHeap(nums) << " ";
}
cout << endl;
return 0;
}
/*
大根堆是一種常用的數(shù)據(jù)結構，它可以實現(xiàn)快速的查找最大值、插入和刪除操作。大根堆的核心思想是將元素按照完全二叉樹的形式存儲，并且滿足每個節(jié)點的值都大于等于其左右孩子節(jié)點的值。
上面的代碼中，buildMaxHeap函數(shù)用于構建大根堆，popMaxHeap函數(shù)用于彈出堆頂元素。構建大根堆的過程是從最后一個非葉子節(jié)點開始，依次向上調(diào)整每個節(jié)點，使得整個堆滿足大根堆的性質(zhì)。彈出堆頂元素的過程是把最后一個元素放到堆頂，然后依次向下調(diào)整每個節(jié)點，使得整個堆重新滿足大根堆的性質(zhì)。
*/
到了這里，關于記一次后臺開發(fā)面試拷打過程的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
