當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

【每日刷题3.12】5道算法+15道面试 - 阿V

發(fā)布時間：2023/12/29 编程问答 27 豆豆

生活随笔收集整理的這篇文章主要介紹了【每日刷题3.12】5道算法+15道面试 - 阿V 小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

感覺算法太占時間了，而且刷的差不多了，現(xiàn)在開始專攻面試！加油~明天阿里筆試。

面試題（一面-項目介紹+基礎(chǔ)面）

1. 自我介紹（游戲測試工程師）

看了多篇文章，說自我介紹不能太短，最好是三分鐘，哈哈哈，我盡力描述。

HR你們好，我叫zzw，21歲，來面試游戲測試工程師的，就讀于廣東工業(yè)大學(xué)數(shù)字媒體技術(shù)專業(yè)，是一名熱愛玩游戲又熱愛開發(fā)游戲的網(wǎng)癮少年，學(xué)校課程里的游戲開發(fā)大作業(yè)，都是完全負(fù)責(zé)程序代碼方面，當(dāng)然我也喜歡參與策劃，課外也熱愛自己搗鼓游戲開發(fā)，自己開發(fā)過幾款游戲demo，都剪成視頻上傳到了B站，最滿意的一款demo就是雷霆戰(zhàn)機(jī)，播放量過萬，在開發(fā)的過程中，遇到過許許多多的bug和問題，沒系統(tǒng)學(xué)過怎么測試，都是自己摸索出bug的源頭并修復(fù)。現(xiàn)在使用最頻繁的是C++，因為最近半年刷算法都是用C++。

當(dāng)然除了虛擬游戲，現(xiàn)實中我非常熱愛運動，因為沒有健康的體魄就玩不了游戲了，每天都會去跑步健身，之前愛好街舞，大二還擔(dān)任了一年的舞蹈俱樂部社長，舉辦過不少活動，榮獲四星級社團(tuán)。樂于與人交往，在與人交往的過程中，學(xué)習(xí)如何做人，如何更好的與人配合。

之所以選擇游戲測試工程師這個職業(yè)，因為很想從事游戲相關(guān)的職業(yè)，而所有職業(yè)中游戲測試工程師是最符合的，測試游戲可以令游戲質(zhì)量上升，因為是一名游戲玩家，舒服的游戲體驗是每個玩家都希望的，而測試游戲的過程中，可以學(xué)習(xí)到很多游戲開發(fā)的知識，這也是我渴望的。所以我想帶著興趣和夢想來擔(dān)任這份工作，以上就是我的自我介紹，謝謝大家。

2. 介紹項目

雷霆戰(zhàn)機(jī)項目：

游戲玩法：駕駛飛機(jī)躲避彈幕，吃比自己體型小的敵機(jī)進(jìn)行升級，類似于大魚吃小魚的玩法。

遇到難題（對于當(dāng)時的我來說）：

1. 飛機(jī)類型與子彈類型如何做到同時匹配，解決辦法是：將飛機(jī)類型和子彈類型用字典存儲在一起，修改飛機(jī)的時候同時修改子彈。

2.飛機(jī)升級，子彈數(shù)量增加要如何增加，就是如何均勻地分布在飛機(jī)周圍，解決辦法是：在飛機(jī)周圍提前創(chuàng)建好空對象，位置和編號都自己設(shè)定好，子彈增加時，獲取對應(yīng)編號的位置添加上去就行。

從中學(xué)習(xí)到了什么：

了解了飛行類游戲的玩法，相關(guān)設(shè)計模式的原理，例如：觀察者模式。以及子彈的規(guī)則生成，敵機(jī)屬性與AI的搭建。

3.?TCP和UDP的聯(lián)系和區(qū)別

?TCP（傳輸控制協(xié)議），是面向連接，可靠，基于字節(jié)流的傳輸協(xié)議，只支持單播，可以全雙工通信，擁有擁塞控制，流量控制。建立連接使用三報文握手，斷開連接使用四報文揮手。

UDP（用戶數(shù)據(jù)報協(xié)議），是無連接，不可靠，基于報文流的傳輸協(xié)議，支持單播、多播、廣播，不可以全雙工通信。

4.??設(shè)計一個可靠的UDP協(xié)議應(yīng)該怎么做？

?首先思考UDP怎么不可靠？UDP在傳輸過程中會出現(xiàn)丟包、數(shù)據(jù)不完整、亂序等問題。根據(jù)這些問題一一解決。

防止丟包：加入確認(rèn)和重傳機(jī)制，類似于TCP的Ack機(jī)制

數(shù)據(jù)不完整：加個16或32位的CRC驗證字段

亂序：加個數(shù)據(jù)包序列號SEQ

5.?微信是使用TCP還是UDP

?根據(jù)TCP和UDP的原理，微信的視頻通話，語音通話應(yīng)該使用了速度更加的UDP，而文本消息等使用TCP確保信息準(zhǔn)確。

但網(wǎng)上了解到，微信登陸驗證等采用HTTP，而文本消息，視頻通話等使用了TCP長連接，通過心跳包來維護(hù)長連接，300s一個心跳。

6.?進(jìn)程和線程的聯(lián)系和區(qū)別

?進(jìn)程是表示資源分配的基本單位，線程是進(jìn)程中執(zhí)行運算和調(diào)度的最小單位。

1. 一個線程只能屬于一個進(jìn)程，而一個進(jìn)程可以擁有多個線程。

2. 資源分配給進(jìn)程，同一進(jìn)程的所有線程共享該進(jìn)程的所有資源。

3. 進(jìn)程擁有獨立的地址空間，進(jìn)程都是建立在虛擬內(nèi)存的基礎(chǔ)上，而線程沒有獨立的地址空間。

4. 進(jìn)程比線程健壯，一個進(jìn)程崩潰不會影響其他進(jìn)程，而一個線程崩潰會導(dǎo)致整個進(jìn)程崩潰。

5. 進(jìn)程執(zhí)行開銷大，而線程依附于進(jìn)程，執(zhí)行開銷小。

7.??單例模式

?首先什么是單例模式？因程序需要，有時某個類只需要一個對象，例如：設(shè)備管理器，數(shù)據(jù)池等。

單例模式特點：1. 全局只有一個實例，禁止賦值和拷貝? 2.用戶通過接口獲取實例

實現(xiàn)單例的幾種方式；

1. 懶漢式(Lazy-Initialization)的方法是直到使用時才實例化對象，問題：

????????1.線程安全問題，不同線程同時創(chuàng)建該類，可能導(dǎo)致多個實例出現(xiàn)，解決辦法加鎖。

? ? ? ? 2.內(nèi)存泄漏，由于static申請在靜態(tài)存儲區(qū)，無法直接delete，只能靠系統(tǒng)自己處理。

#include <iostream> // version1: // with problems below: // 1. thread is not safe // 2. memory leakclass Singleton{ private:Singleton(){ //修改默認(rèn)構(gòu)造函數(shù)std::cout<<"constructor called!"<<std::endl;}Singleton(Singleton&)=delete; //刪除拷貝構(gòu)造函數(shù)Singleton& operator=(const Singleton&)=delete; //刪除賦值運算符函數(shù)static Singleton* m_instance_ptr; //創(chuàng)建靜態(tài)對象 public:~Singleton(){ //修改析構(gòu)函數(shù)std::cout<<"destructor called!"<<std::endl;}static Singleton* get_instance(){ //創(chuàng)建對象if(m_instance_ptr==nullptr){m_instance_ptr = new Singleton;}return m_instance_ptr;}void use() const { std::cout << "in use" << std::endl; } //const放函數(shù)后面表示該函數(shù)一切都不可修改 };Singleton* Singleton::m_instance_ptr = nullptr; //初始化單例對象為空int main(){Singleton* instance = Singleton::get_instance();Singleton* instance_2 = Singleton::get_instance();return 0; }

2. 線程安全、內(nèi)存安全的懶漢式單例（智能指針，鎖）

#include <iostream> #include <memory> // shared_ptr #include <mutex> // mutex// version 2: // with problems below fixed: // 1. thread is safe now // 2. memory doesn't leakclass Singleton { public:typedef std::shared_ptr<Singleton> Ptr; //使用智能指針~Singleton() {std::cout << "destructor called!" << std::endl;}Singleton(Singleton&) = delete; //禁止拷貝構(gòu)造函數(shù)Singleton& operator=(const Singleton&) = delete; //賦值運算符操作static Ptr get_instance() {// "double checked lock"if (m_instance_ptr == nullptr) {std::lock_guard<std::mutex> lk(m_mutex); //線程加鎖if (m_instance_ptr == nullptr) {m_instance_ptr = Ptr(new Singleton);}}return m_instance_ptr;}private:Singleton() {std::cout << "constructor called!" << std::endl;}static Ptr m_instance_ptr; //創(chuàng)建靜態(tài)對象static std::mutex m_mutex; };// initialization static variables out of class Singleton::Ptr Singleton::m_instance_ptr = nullptr; std::mutex Singleton::m_mutex;int main() {Singleton::Ptr instance = Singleton::get_instance();Singleton::Ptr instance2 = Singleton::get_instance();return 0; }

3.?最推薦的懶漢式單例(magic static )——局部靜態(tài)變量

#include <iostream>class Singleton { public:~Singleton(){std::cout<<"destructor called!"<<std::endl;}Singleton(const Singleton&)=delete;Singleton& operator=(const Singleton&)=delete;static Singleton& get_instance(){static Singleton instance;return instance;} private:Singleton(){std::cout<<"constructor called!"<<std::endl;} };int main(int argc, char *argv[]) {Singleton& instance_1 = Singleton::get_instance();Singleton& instance_2 = Singleton::get_instance();return 0; }

?8.??C++ STL是什么

?STL：標(biāo)準(zhǔn)模板庫，一些容器、算法和其他一些組件的集合，容器包括vector、list、set、map等

有什么作用呢？使用 STL 可以更加方便靈活地處理數(shù)據(jù)

9. 常見的數(shù)據(jù)結(jié)構(gòu)

?數(shù)組、隊列、堆、棧、樹、圖、鏈表等

?10.?C++內(nèi)存分配的方式

?有三種：靜態(tài)存儲區(qū)分配、棧上分配內(nèi)存和堆上分配內(nèi)存。、

靜態(tài)存儲區(qū)分配內(nèi)存：在程序編譯時就分配好了，程序的整個運行期間都存在，例如全局變量，static變量。

棧上分配內(nèi)存：系統(tǒng)自動分配，例如函數(shù)內(nèi)部的局部變量，隨著函數(shù)結(jié)束而刪除。

堆上分配內(nèi)存：動態(tài)分配內(nèi)存，例如new、malloc。

11.??malloc/free和new/delete的區(qū)別

?共同點：都是從堆上申請空間，并且需要用戶手動釋放。

不同點：

1. malloc和free是函數(shù)，new和delete是操作符

2. malloc申請的空間不會初始化，new可以初始化。

3. malloc申請空間要手動計算空間大小，new只需在其后輸入空間類型即可。

4. malloc的返回值是void*，new返回空間類型。

5. malloc申請空間失敗，返回NULL，new申請失敗，拋出異常。

12.??C++ vector 容器

?什么是vector？vector是一個封裝了動態(tài)大小數(shù)組的順序容器。

特性：

1. 容器內(nèi)元素按嚴(yán)格的線性順序排序，查找的時間復(fù)雜度為O（1）。

2. 添加元素時會進(jìn)行動態(tài)分配內(nèi)存，使其快速增刪。

常用函數(shù)：push_back(),pop_back(),empty() ,sort()等。

13.?HTTPS是什么？

想了解HTTPS是什么？就要先了解HTTP？就要了解TLS/SSL 工作原理及握手過程。

傳輸層安全性協(xié)議 TLS（Transport Layer Security），及其前身安全套接層 SSL（Secure Sockets Layer）是一種安全協(xié)議，目的是為互聯(lián)網(wǎng)通信提供安全及數(shù)據(jù)完整性保障。

HTTP：超文本傳輸協(xié)議（HTTP，HyperText Transfer Protocol）是互聯(lián)網(wǎng)上應(yīng)用最為廣泛的一種網(wǎng)絡(luò)協(xié)議。

HTTPS：是以安全為目標(biāo)的 HTTP?通道，是 HTTP?的安全版。HTTPS?的安全基礎(chǔ)是 SSL。SSL 協(xié)議位于?TCP/IP 協(xié)議與各種應(yīng)用層協(xié)議之間，為數(shù)據(jù)通訊提供安全支持。

14.??HTTP的請求有哪幾種？各有什么用？

1.GET：請求指定的頁面信息，并返回實體主體。

2.?HEAD：類似于get請求，只不過返回的響應(yīng)中沒有具體的內(nèi)容，用于獲取報頭。

3. POST：向指定資源提交數(shù)據(jù)進(jìn)行處理請求。

4. PUT：從客戶端向服務(wù)器傳送的數(shù)據(jù)取代指定的文檔內(nèi)容。

5. DELETE：請求服務(wù)器刪除指定的頁面。

6. CONNECT：將連接改為管道方式的代理服務(wù)器。

7. OPTIONS：允許客戶端查看服務(wù)器性能

8. TRACE：回顯服務(wù)器收到的請求，主要用于測試。

算法題

1.?兩個數(shù)對之間的最大乘積差

?貪心算法。

代碼詳情：

class Solution { public:int maxProductDifference(vector<int>& nums) {sort(nums.begin(), nums.end()); //排序數(shù)組return ((nums[nums.size()-1] * nums[nums.size()-2]) - (nums[0] * nums[1]));} };

?通過情況：

?2.?數(shù)組拆分 I