This is a collection of common C++ classes and templates that we often use, and thus are perfect opportunities for interviewers to quiz on to see if the candidate is comfortable with the language, can write clean code, and is aware about the internals of the language.

Smart Pointers

General Smart Pointer

template <typename T>
class AutoPtr {
    T *ptr;

    AutoPtr(T *ptr = nullptr) : ptr(ptr) {}
    ~AutoPtr() {
      delete ptr;
    }

    // Copy constructor [Moves the pointer to self]
    AutoPtr(AutoPtr &other) {
      ptr = other.ptr;
      other.ptr = nullptr;
    }

    // Copy assignment operator [Moves the pointer to self]
    AutoPtr& operator=(AutoPtr &other) {
      if (this == &other)
        return *this;

      delete ptr; // Free any existing resource
      ptr = other.ptr;
      other.ptr = nullptr;
    }

    // Overloading the operators for convinience
    T& operator*() const { return *ptr; }
    T* operator->() const { return ptr; }

}

Problems with `AutoPtr`:

When passed to function by value, the pointer is moved to the function and the memory would be freed when the function returns. Thus in the original function, this can lead to a dangling pointer.
This deletes using the non-array delete operator, and thus if the pointer was allocated using new[], it would lead to undefined behaviour.

Thus they were replaced by std::unique_ptr, std::shared_ptr, and std::weak_ptr in C++11.

Unique Pointer

template<typename T>
class UniquePtr {
  T *ptr;

public:
  UniquePtr(T* ptr = nullptr): ptr(ptr) {}
  ~UniquePtr() {
    delete ptr;
  }

  // Disable the copy assignment and copy constructor
  UniquePtr(UniquePtr &ptr) = delete;
  UniquePtr& operator=(UniquePtr &other) = delete;

  // Move constructor
  UniquePtr(UniquePtr &&other) {
    ptr = other.ptr;
    other.ptr = nullptr;
  }

  // Move assignment operator
  void operator=(UniquePtr &&other) {
    ptr = other.ptr;
    other.ptr = nullptr;
  }

  // Overloading Opertor
  T& operator*() const { return *this; }
  T* operator->() const {return this; }
};

Shared Pointer

template<typename T>
class SharedPtr {
    T *ptr;
    int *count;

  void cleanUp() {
    (*count)--;
    if (*count == 0) {
      delete ptr;
      delete count;
    }
  }

  public:
    SharedPtr(T *ptr = nullptr): ptr(ptr) {
      if (ptr)
        count = new int(1);
      else
        count = new int(0);
    }

    ~SharedPtr() { cleanUp(); }

    // Copy constructor
    SharedPtr(SharedPtr &other) {
      ptr = other.ptr;
      count = other.count;
      if (ptr)
        (*count)++;
    }

    // Copy assignment operator
    SharedPtr& operator=(SharedPtr &other) {
      cleanUp();

      ptr = other.ptr;
      count = other.count;
      if (ptr)
        (*count)++;

      return *this;
    }

    // Move constructor
    SharedPtr(SharedPtr &&other) {
      ptr = other.ptr;
      count = other.count;
      other.ptr = nullptr;
      other.count = nullptr;
    }

    // Move assignment operator
    SharedPtr& operator=(SharedPtr &&other) {
      cleanUp();

      ptr = other.ptr;
      count = other.count;
      other.ptr = nullptr;
      other.count = nullptr;
    }

    // Overloading operators
    T& operator*() const { return *ptr; }
    T* operator->() const { return ptr; }
}

Hit Counter

Base Variant

You need to implement a HitCounter class that supports the following operations:

HitCounter() Initializes the object of the class.
void hit(int timestamp) Records a hit that happened at the given timestamp.
int getHits(int timestamp) Returns the number of hits in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (i.e. the timestamp is monotonically increasing).

1
class HitCounter {
2
  // Front of the queue will have the oldest timestamp
3
  // Monotonically increasing timestamps
4
  dequeue<pair<int, int>> hits;
5
  int curCnt;
6

7
  const int MAX_TIME = 5 * 60;
8

9
  void removeOldHits(int timestamp) {
10
    while (!hits.empty() && hits.front().first <= timestamp - MAX_TIME) {
11
      curCnt -= hits.front().second;
12
      hits.pop_front();
13
    }
14
  }
15

16
public:
17
  HitCounter(): curCnt(0) {}
18

19
  void hit(int timestamp) {
20
    removeOldHits(timestamp);
21
    if (!hits.empty() && hits.back().first == timestamp)
22
      hits.back().second++;
23
    else
24
      hits.push_back({timestamp, 1});
25
    curCnt++;
26
  }
27

28
  int getHits(int timestamp) {
29
    removeOldHits(timestamp);
30
    return curCnt;
31
  }
32
};

This function uses a deque to store the hits, and a curCnt to store the total number of hits. The removeOldHits function is used to remove the hits that are older than 5 minutes. One salient feature of this implementation is that it does not store the hits for each second, but rather stores the number of hits at each second, and thus this implementation would gracefully handle the case when there are multiple hits at the same second. If the same was not a requirement, we could have used a queue instead of a deque to store the hits.

Time Complexity:
- hit: $O(300)$
- getHits: $O(300)$

Unordered Timestamps

Implement the same interface as above, but now the timestamps are not guaranteed to be in order.

1
class HitCounter {
2
  map<int, int> hits;
3
  const int MAX_TIME = 5 * 60;
4

5
public:
6
  HitCounter() {}
7

8
  void hit(int timestamp) {
9
    hits[timestamp]++;
10
  }
11

12
  int getHits(int timestamp) {
13
    int cnt = 0;
14
    for (int time = timestamp - MAX_TIME + 1; time <= timestamp; time++) {
15
      if (hits.find(time) != hits.end())
16
        cnt += hits[time];
17
    }
18
    return cnt;
19
  }
20
};

Time Complexity:
- hit: $O(log(n))$
- getHits: $O(300 \cdot log(n))$
where $n$ is the number of unique timestamps

Concurrent Hit Counter

Implement the same interface as above, but now the class needs to be thread-safe. You can assume that the threads would be calling the same in chronological order.

1
class HitCounter {
2
  mutex mtx;
3
  deque<pair<int, int>> hits;
4
  int curCnt;
5

6
  const int MAX_TIME = 5 * 60;
7

8
  void removeOldHits(int timestamp) {
9
    while (!hits.empty() && hits.front().first <= timestamp - MAX_TIME) {
10
      curCnt -= hits.front().second;
11
      hits.pop_front();
12
    }
13
  }
14

15
public:
16
  HitCounter(): curCnt(0) {}
17

18
  void hit(int timestamp) {
19
    lock_guard<mutex> lock(mtx);
20

21
    removeOldHits(timestamp);
22
    if (!hits.empty() && hits.back().first == timestamp)
23
      hits.back().second++;
24
    else
25
      hits.push_back({timestamp, 1});
26
    curCnt++;
27
  }
28

29
  int getHits(int timestamp) {
30
    lock_guard<mutex> lock(mtx);
31

32
    removeOldHits(timestamp);
33
    return curCnt;
34
  }
35
};

Infinite Timestamps in the Past

In this variant, we want the hit counter to be able to answer queries of all the time in the past, and the solution should use constant memory. Some inaccuracy is allowed in the answer. To handle the same, we would make use of buckets of size of powers of 2, so that the older buckets store more points and are updated less frequently.

1
class HitCouter;
2

3
class Bucket
4
{
5
    int quantum;
6
    int cnt;
7
    int lastUpdate;
8

9
    friend class HitCouter;
10

11
public:
12
    Bucket(int p)
13
    {
14
        quantum = 1 << p;
15
        cnt = 0;
16
        lastUpdate = 0;
17
    }
18
};
19

20
class HitCouter
21
{
22
    int MAX_BUCKETS = 12;
23
    vector<Bucket> buckets;
24
    int curTime;
25

26
    void shiftBuckets(int deltaTime)
27
    {
28
        if (!deltaTime)
29
            return;
30

31
        // Last bucket represents liftime hits, and should not be shifted
32
        for (int i = 0; i < MAX_BUCKETS - 1; i++)
33
        {
34
            Bucket &b = buckets[i];
35
            if (curTime - b.lastUpdate >= b.quantum)
36
            {
37
                buckets[i + 1].cnt += b.cnt;
38
                buckets[i].lastUpdate = curTime;
39
                buckets[i].cnt = 0;
40
            }
41
        }
42
    }
43

44
    void update(int timestamp)
45
    {
46
        int deltaTime = timestamp - curTime;
47
        curTime = timestamp;
48
        shiftBuckets(deltaTime);
49
    }
50

51
public:
52
    HitCouter()
53
    {
54
        curTime = 0;
55
        for (int i = 0; i < MAX_BUCKETS; i++)
56
            buckets.emplace_back(i);
57
    }
58

59
    void hit(int timestamp)
60
    {
61
        update(timestamp);
62
        buckets[0].cnt++;
63
    }
64

65
    int getHits(int timestamp, int prevTime)
66
    {
67
        update(timestamp);
68

69
        int cnt = 0;
70
        int idx = 0;
71
        for (; idx < MAX_BUCKETS; idx++)
72
        {
73
            if (prevTime >= buckets[idx].quantum)
74
                cnt += buckets[idx].cnt;
75
            else
76
                break;
77
        }
78

79
        return cnt;
80
    }
81
};