2025年专业面试题目解答方法及答案.docxVIP

2025年专业面试题目解答方法及答案

【题型一：算法与数据结构】

题目1：给定一个长度为n的整数数组，其中恰好有一个元素出现一次，其余每个元素均出现两次，要求O(n)时间、O(1)额外空间找出唯一出现一次的元素。

解答方法：异或运算满足交换律、结合律与自反性，即a⊕a=0，a⊕0=a。遍历数组，将所有元素依次异或，最终剩余结果即为只出现一次的数字。

代码实现：

```cpp

intsingleNumber(vectorintnums){

intans=0;

for(intx:nums)ans^=x;

returnans;

}

```

复杂度：时间O(n)，空间O(1)。

追问：若数组中恰好有两个元素各出现一次，其余出现两次，如何找出这两个数？

答：先整体异或得到a⊕b，取其二进制任意一位1作为mask，将数组分为两组分别异或，即可分别得到a与b。

题目2：实现一个LRU缓存，要求get与put均为O(1)。

解答方法：双向链表+哈希表。链表按访问时间排序，哈希表存储key到链表节点的映射。

get操作：若key存在，将对应节点移到链表头部并返回value；否则返回-1。

put操作：若key存在，更新value并移到头部；若不存在，新建节点插入头部，若容量超限则删除尾部节点并在哈希表中移除对应key。

C++实现：

```cpp

structNode{

intkey,value;

Nodeprev,next;

Node(intk,intv):key(k),value(v),prev(nullptr),next(nullptr){}

};

classLRUCache{

unordered_mapint,Nodemp;

Nodehead,tail;

intcap,sz;

voidaddToHead(Nodenode){

node-next=head-next;

node-prev=head;

head-next-prev=node;

head-next=node;

}

voidremove(Nodenode){

node-prev-next=node-next;

node-next-prev=node-prev;

}

public:

LRUCache(intcapacity):cap(capacity),sz(0){

head=newNode(0,0);

tail=newNode(0,0);

head-next=tail;tail-prev=head;

}

intget(intkey){

if(mp.count(key)){

Nodenode=mp[key];

remove(node);

addToHead(node);

returnnode-value;

}

return-1;

}

voidput(intkey,intvalue){

if(mp.count(key)){

Nodenode=mp[key];

node-value=value;

remove(node);addToHead(node);

}else{

if(sz==cap){

Nodelast=tail-prev;

remove(last);

mp.erase(last-key);

deletelast;sz--;

}

Nodenode=newNode(key,value);

addToHead(node);

mp[key]=node;sz++;

}

}

};

```

追问：如何支持多线程并发？

答：在get/put前后加读写锁，或使用concurrent_hash_m