20 Essential C++ Interview Questions and Answers: Data Structures, Algorithms, and System Concepts

1. Difference Between HashMap and Map and Underlying Data Structures

In C++, unordered_map implements a hash table while map implements a red‑black tree. unordered_map does not guarantee element order and allows null keys (since C++11), using chaining for collisions; map keeps keys sorted and provides O(log N) insert, delete, and lookup.

2. Vector Underlying Implementation

vector

is a dynamic array that stores elements in contiguous memory. It maintains a pointer to the allocated block, a capacity (total allocated slots) and a size (actual element count). When capacity is exhausted, a larger block is allocated, existing elements are copied, and the old block is freed. This design gives random access and O(1) push/pop at the end, while middle insertions/deletions are slower due to potential copying.

3. Red‑Black Tree

A red‑black tree is a self‑balancing binary search tree. Each node is colored red or black, the root is black, all leaves (NULL) are black, red nodes cannot have red children, and every path from a node to its descendant leaves contains the same number of black nodes. These rules guarantee O(log N) search, insertion, and deletion. Insertion sets the new node red and fixes violations with rotations; deletion may also require rotations and recoloring.

4. Hash

Hash functions map arbitrary‑length input to a fixed‑size output. Good hash functions produce the same output for identical input, different outputs for different inputs, and have a constant output length. They are used for hash tables, cryptographic signatures, data integrity checks, and distributed system key placement (e.g., consistent hashing). Common functions include MD5, SHA‑1, SHA‑256, SHA‑3, and Blake2.

5. Binary Tree

A binary tree node has at most two children (left and right). Variants include complete binary trees, full binary trees, and binary search trees (BST) where left subtree values are ≤ the node and right subtree values are ≥ the node. Traversal methods: preorder, inorder, and postorder. Applications range from expression evaluation to database indexes and graphics.

6. Smart Pointers

C++ provides three main smart pointers in <memory>:

unique_ptr : exclusive ownership; moves ownership via std::move; destroys the object when the pointer goes out of scope.

shared_ptr : reference‑counted shared ownership; object is destroyed when the last shared_ptr is destroyed; created with std::make_shared.

weak_ptr : non‑owning reference to an object managed by shared_ptr; does not affect reference count; can be upgraded to shared_ptr via lock().

Smart pointers prevent memory leaks and dangling pointers but must be used carefully to avoid cyclic references.

7. Hand‑Written LRU Cache

#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;
class LRUCache {
private:
    int capacity;
    unordered_map<int, pair<int, list<int>::iterator>> cache; // key → (value, iterator)
    list<int> lruList; // stores usage order
public:
    LRUCache(int cap) { capacity = cap; }
    int get(int key) {
        if (cache.find(key) == cache.end()) return -1;
        lruList.erase(cache[key].second);
        lruList.push_front(key);
        cache[key].second = lruList.begin();
        return cache[key].first;
    }
    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            lruList.erase(cache[key].second);
            lruList.push_front(key);
            cache[key] = make_pair(value, lruList.begin());
            return;
        }
        if (cache.size() == capacity) {
            int lastKey = lruList.back();
            cache.erase(lastKey);
            lruList.pop_back();
        }
        lruList.push_front(key);
        cache[key] = make_pair(value, lruList.begin());
    }
};
int main() {
    LRUCache cache(2);
    cache.put(1,1);
    cache.put(2,2);
    cout << cache.get(1) << endl; // 1
    cache.put(3,3);
    cout << cache.get(2) << endl; // -1
    cache.put(4,4);
    cout << cache.get(1) << endl; // -1
    cout << cache.get(3) << endl; // 3
    cout << cache.get(4) << endl; // 4
    return 0;
}

The cache uses an unordered_map for O(1) look‑ups and a list to maintain LRU order; get moves the accessed key to the front, and put evicts the least‑recently used entry when full.

8. Hand‑Written memcpy

The standard memcpy copies a block of memory. Below is a simple manual implementation:

#include <iostream>
void myMemcpy(void* dest, const void* src, size_t size) {
    char* d = static_cast<char*>(dest);
    const char* s = static_cast<const char*>(src);
    for (size_t i = 0; i < size; ++i) {
        d[i] = s[i];
    }
}
int main() {
    int source[] = {1,2,3,4,5};
    int destination[5];
    myMemcpy(destination, source, sizeof(source));
    for (const auto& e : destination) cout << e << " ";
    return 0;
}

In production code, the standard library memcpy or safer alternatives should be preferred for performance and correctness.

9. Hand‑Written Linked List Operations

Examples include sorting a singly linked list via merge‑sort, reversing a list, detecting a cycle with Floyd’s algorithm, and merging two sorted lists. Each function manipulates ListNode structures and demonstrates classic pointer techniques.

10. TCP Three‑Way Handshake and Four‑Way Teardown

The three‑way handshake establishes a reliable TCP connection: SYN → SYN+ACK → ACK. The four‑way teardown gracefully closes the connection: FIN → ACK → FIN → ACK, ensuring both sides have finished data transmission.

11. TCP vs. UDP

Reliability: TCP is connection‑oriented and guarantees ordered delivery with retransmission; UDP is connection‑less and best‑effort.

Speed: UDP is faster due to lack of handshake and congestion control.

Message size: UDP packets are limited to 64 KB; TCP streams have no fixed limit.

Use cases: TCP for file transfer, email, etc.; UDP for real‑time audio/video, gaming, DNS.

12. UDP Reliability Techniques

UDP itself provides no reliability; applications add their own mechanisms such as sequence numbers, acknowledgments, or forward error correction when loss‑tolerance is low.

13. Multithreading and Thread Pools

Multithreading runs multiple threads concurrently, each with its own execution context. A thread pool pre‑creates a set of worker threads that are reused for tasks, reducing the overhead of thread creation and allowing controlled concurrency.

14. Process vs. Thread and Inter‑Process Communication (IPC)

Processes have separate memory spaces; threads share the same address space.

Process creation and context switching are heavier than thread operations.

IPC mechanisms include pipes, named pipes, shared memory, message queues, semaphores, and sockets.

15. MySQL Indexes, B+ Tree, and Transactions

MySQL indexes accelerate query lookup; the default index type is a B+ tree, which provides balanced search, range queries, and ordered traversal. Transactions group statements into an atomic unit, obeying ACID properties; they are controlled with BEGIN, COMMIT, and ROLLBACK.

16. Redis Cache Consistency, Expiration, and Cache Breakdown

Consistency: keep cache and data source synchronized via write‑through or publish/subscribe updates.

Expiration: set TTL on keys to automatically evict stale data.

Cache breakdown: mitigate hot‑key miss storms with short TTLs, mutex locks, or request coalescing.

17. Locking Mechanisms

Distributed lock (e.g., Redis, Zookeeper) for cross‑node exclusivity.

Transaction lock for database isolation.

Process‑level locks using file locks or semaphores.

Deadlock detection and avoidance strategies.

Optimistic lock (version check) vs. pessimistic lock (exclusive lock).

18. Asynchronous vs. Synchronous Execution

Synchronous code blocks until an operation finishes; asynchronous code dispatches work to the background and continues, later receiving results via callbacks, futures, or events. Asynchrony improves responsiveness for I/O‑bound or long‑running tasks.

19. Blocking vs. Non‑Blocking I/O

Blocking calls suspend the thread until the operation completes. Non‑blocking calls return immediately, allowing the program to poll or be notified when the operation is ready, which enables higher concurrency.

20. Bloom Filter

A Bloom filter is a space‑efficient probabilistic data structure for set membership queries. It uses a bit array and multiple hash functions; adding an element sets bits, and querying checks those bits. It offers O(1) query time with a controllable false‑positive rate but no false negatives.