Smart pointer in C++
Posted on April 5, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem Write a smart pointer (smart_ptr) class.
Solution As discussed here, smart pointers are C++ objects that simulate simple pointers by implementing operator-> and the unary operator*. In addition to sporting pointer syntax and semantics, smart pointers often perform useful tasks—such as memory management or locking—under the covers, thus freeing the application from carefully managing the lifetime of pointed-to objects. You can read more about it on the provided link.
[Read More]Take a pointer to a Node structure as a parameter and return a complete copy of the passed-in data structure
Posted on April 5, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem Write a method that takes a pointer to a Node structure as a parameter and returns a complete copy of the passed-in data structure. The Node structure contains two pointers to other Node structures.
Solution
The algorithm will maintain a mapping from a node address in the original structure to the corresponding node in the new structure. This mapping will allow us to discover previously copied nodes during a traditional depth first traversal of the structure.
[Read More]Destructor in base class needed to be virtual in C++
Posted on April 4, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem Why does a destructor in base class need to be declared virtual?
Follow up - Is it always required for base class to have virtual destructors?
Solution You want them to be virtual so that all subclass destructors are automatically called when the object is destroyed, even if it is destroyed through a pointer to the base class.
Calling a method with an object pointer always invokes:
[Read More]“volatile” keyword in C (and Java)
Posted on April 4, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
What is the significance of the keyword “volatile” in C?
Solution
Lets under stand volatile in C Volatile tells the compiler not to optimize anything that has to do with the volatile variable.There is only one reason to use it: When you interface with hardware.
Volatile informs the compiler that the value of the variable can change from the outside, without any update done by the code.
[Read More]Deep copy and shallow copy in C++
Posted on April 4, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem
Write a method that takes a pointer to a Node structure as a parameter and returns a complete copy of the passed-in data structure. The Node structure contains two pointers to other Node structures.
Solution
A shallow copy copies the array and maintains references or copies address to the original objects.
A deep copy will copy (clone) the objects too so they bear no relation to the original.
[Read More]Virtual functions in C++
Posted on April 3, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem How do virtual functions work in C++?
Solution Virtual functions are defined in a super class. It does not require implementation for the super class. But all the extended class have to implement the function. So, the derived class can override the behavior of the virtual function.
Example
For example, a Shape class can have a virtual draw function. Its derived class, e.g., Circle, has to implement its detailed draw function.
[Read More]Compare and contrast a hash table vs. an STL map
Posted on April 3, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem
Compare and contrast a hash table vs. an STL map. How is a hash table implemented? If the number of inputs is small, what data structure options can be used instead of a hash table?
Solution
Hash Table
In a hash table, a value is stored by applying hash function on a key. Thus, values are not stored in a hashtable in sorted order. Additionally, since hash tables use the key to find the index that will store the value, an insert/lookup can be done in amortized O(1) time (assuming only a few collisions in the hashtable).
[Read More]Print the last K lines of a file using C++
Posted on April 3, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Write a method to print the last K lines of an input file using C++.
Solution
Method 1 - Slow and fast file pointer pointer
Using the same idea from this article, we place two pointers to the file, the fast pointer and the slow pointer. The fast pointer is K lines ahead of the slow pointer. When the fast pointer reaches the EOF, we can start to print everything from the slow pointer, all the way to the end.
[Read More]Selection Sort
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
Selection Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of in-place comparison sort.
Pseudocode of selection sort
Get the smallest element and put it in the first position Get the next smallest element and put it in the 2nd position ….
[Read More]Bloom filters
Posted on January 7, 2012
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
The bloom filter is a data structure designed in 1970. It is similar to a hash table. They are more efficient than a hash table, but they do raise false positives at times.
Supported Operations
A bloom filter supports super fast lookup and insertion, just like a hash table. So why have this data structure?
Pros
It is much more space efficient.
It takes the space even less than that of the object.
[Read More]