Форум программистов, компьютерный форум, киберфорум
Наши страницы
Loafer
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Задача с собеседования №1

Запись от Loafer размещена 12.08.2018 в 19:00

Проходил я собеседование в одну из крупных компаний России. Целью была проверка уровня своих знаний. В этом блоге я хочу выложить свои решения ко всем задачам, которые мне были выданы.

Начнем с первой задачи. Задача звучит следующим образом: реализовать LRU-кэш. Что такое LRU-кэш можно прочитать здесь. Если вкратце, то это такая структура данных, которая:
  1. вставляет элемент в начало и удаляет с конца, если кэш полон;
  2. если к некоторому элементу обратились по ключу, то он перемещается в начало.
Собственно, само решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <string>
 
struct Node
{
  Node(int key_, std::string value_):
  key(key_),
  value(value_)
  {}
  int key;
  std::string value;
};
 
class LruCache
{
public:
  LruCache(std::size_t size):
  _current_size(0),
  _size(size)
  {}
  
  void insert(int key, std::string value)
  {
    if (_current_size < _size)
    {
      insert_new_node(key, value);
      _current_size++;
    }
    else
    {
      struct Node & last_node = _values.back();
      _key_pointers.erase(last_node.key);
      _values.pop_back();
      insert_new_node(key, value);
    }
  }
  
  std::string find(int key)
  {
    auto iter = _key_pointers.find(key);
    if (iter == _key_pointers.end())
      return "";
    
    _values.splice(_values.begin(), _values, iter->second);
    iter->second = _values.begin();
    return (*_values.begin()).value;
  }
  
  void display()
  {
    std::cout << "=== content ===\n";
    std::for_each(_values.begin(),
                  _values.end(),
                  [] (struct Node node) { std::cout << node.key << " -> " << node.value << '\n'; });
    std::cout.flush();
    
    std::cout << "=== debug content ===\n";
    std::for_each(_key_pointers.begin(),
                  _key_pointers.end(),
                  [] (const auto & key_pointer) { std::cout << "key: " << key_pointer.first << " -> " << "value: " << (*key_pointer.second).value << '\n'; });
    std::cout.flush();
  }
  
private:
  void insert_new_node(int key, std::string value)
  {
    _values.push_front(Node(key, value));
    _key_pointers.emplace(key, _values.begin());
  }
  
private:
  std::size_t _current_size;
  std::size_t _size;
  
  std::list<struct Node> _values;
  std::map<int, std::list<struct Node>::iterator> _key_pointers;
};
 
int main()
{
  LruCache lru(5);
  lru.insert(5, "aaa");
  lru.insert(1, "bbb");
  lru.insert(4, "ccc");
  lru.insert(3, "ddd");
  lru.insert(2, "eee");
  lru.display();
  lru.insert(55, "fff");
  lru.display();
  lru.insert(11, "ggg");
  lru.display();
  
  std::string find_value = lru.find(4);
  if (find_value != "")
  {
    std::cout << "find_value: " << find_value << std::endl;
    lru.display();
  }
  
  find_value = lru.find(55);
  if (find_value != "")
  {
    std::cout << "find_value: " << find_value << std::endl;
    lru.display();
  }
  
  return 0;
}
Хочу отметить, что можно реализовать более общее решение, используя шаблоны. Но для простоты будем предполагать, что ключ является целочисленным значением, а сами данные - строкой. Не претендую на то, что решение эффективно и если есть какие-нибудь замечания, то с радостью их прочту в комментариях.
Размещено в C++
Просмотров 93 Комментарии 0
Всего комментариев 0
Комментарии
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru