腾讯微信安卓开发一面面经

1. 介绍自己的项目，问了项目的难点和创新点

2. 为什么算法转开发

3. 介绍C++智能指针

4. 下面两个样例的对象a有什么区别

(1)

Person a();

(2)

Person a;

a = Person();

5. coding

设置一个算法，有一下功能

1.LFUCache(int capacity) ：用数据结构的容量 capacity 初始化对象

http://2.int get(int key) ： 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。

3.void put(int key, int value) ： 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

#include <iostream>
#include <map>
#include <cstdio>
#include <vector>
using namespace std;
class LFUCache
{
    private:
        int capacity;
        map<int , int> cache, count;
    public:
        LFUCache(int capacity1): capacity(capacity1) {}
        int get(int key)
        {
            if(cache.count(key) == 1) 
            { 
                count[key] += 1;
                return cache[key];
            }
            return -1;
        } 
        void put(int key, int value)
        {
            int min = 1e9, index = -1;
            if(cache.size() == capacity)
            {
                for(map<int, int>::iterator it = count.begin(); it != count.end(); ++it)
                {
                    if(it->second < min) 
                    {
                        min = it->second;
                        index = it->first;
                    }
                }
                cache.erase(index);
            }
            
            cache[key] = value;
            count[key] += 1;
        }

};
int main() 
{
    LFUCache cache(3);
    cout << cache.get(0) << endl;
    int a[5] = {1, 2, 4, 3, 4};
    for(int i = 0; i < 5; ++i)
    {
        cache.put(a[i], i);
    }
    // 2 1
    // 4 4
    // 3 3
    // for(int i = 0; i < 5; ++i)
    // {
    //     cout << cache.get(a[i]) << endl;
    // }
    cout << cache.get(1) << endl;
    cout << cache.get(2) << endl;
    cout << cache.get(3) << endl;
    cout << cache.get(4) << endl;
    return 0;    
}