Exercises

1. Last K Lines: print the last K lines of an input file using C++.

• How to efficiently purge the oldest line from the array? Circular array.

1. Reverse String: reverse a null-terminated string.

• Do it in place?

1. Hash Table vs STL Map: compare and contrast a hash table and an STL map.

• How is a hash table implemented? Hashing and chaining to handle collisions.
• How is an STL map implemented? Binary search tree based on the keys.

1. Virtual Functions: how do virtual functions work in C++?

• What is a virtual table?

1. Shallow vs Deep Copy: what is the difference between deep copy and shallow copy.

• Values or objects?

1. Volatile: what is the significance of the keyword volatile in C?

• In what situation may the value of the volatile variable be changed?

1. Virtual Base Class: why does a destructor in base class need to be declared virtual?

• When are virtual functions useful?

1. Copy Node: copy a Node data structure recursively. A Node may point to two other Nodes.

• How to copy the entire data structure? Graph traversal with a “visited” set.

1. Smart Pointer: write a smart pointer class.

• How does smart pointers work?

1. Malloc: write an aligned malloc and free function.

• How to manage dynamic memory?

1. 2D Alloc: allocates a two-dimensional array arr[n][m].

• Instead of common practice of allocating n blocks of memory, can the entire array be allocated at once?