Solve problems that are commonly asked in C++ coding interviews related to common data structures.

Ace the C++ Coding Interview

Data structures are among the fundamentals of computer science and are often a core decision in developing efficient programs. They are categorized as a vital benchmark of computer science knowledge when it comes to industry interviews. This module contains a detailed review of common data structures in C++. We'll also become well-equipped with different data structures by implementing them.
By the end of this module, we'll have expertise in solving problems in data structures.

Data Structures


# Complete Implementation
In the previous lessons, we discussed each aspect of a hash table in detail. Below, you can find the complete hash table class. 

#include "Hash.h"

#include <iostream>

using namespace std;

HashEntry::HashEntry() {
  key = "";
  value = -1;
  next = NULL;
}
HashEntry::HashEntry(string k, int val) {
  key = k;
  value = val;
}

// Class to represent entire hash table

HashTable::HashTable(int s) {
  bucket = new HashEntry * [s];
  //Initialise all elements of array as NULL
  for (int i = 0; i < s; i++)
    bucket[i] = NULL;
  slots = s;
  size = 0;
}
int HashTable::getSize() { // return size of table
  return size;
}
bool HashTable::isEmpty() { // if table is empty return true
  return getSize() == 0;
}

int HashTable::getIndex(string key) {
  //hashCode is a built in function of Strings
  //takes key and size of the list

  int Key = 0;
  for (int i = 0; i < key.length(); i++) {
    Key = 37 * Key + key[i];
  }
  if (Key < 0)
    Key *= -1;

  return Key % slots;
}

void HashTable::insert(string key, int value) {
  // Apply hash function to find index for given key
  int hashIndex = getIndex(key);
  //cout << "hashIndex : " << hashIndex  <<endl;
  if (bucket[hashIndex] == NULL) {

    bucket[hashIndex] = new HashEntry(key, value);
    size++;
  } else { //find next free space

    HashEntry * temp = bucket[hashIndex];;
    while (temp -> next != NULL) {
      temp = temp -> next;
    }
    temp -> next = new HashEntry(key, value);
    size++;

  }
}

void HashTable::display() {
  HashEntry * temp;
  for (int i = 0; i < slots; i++) {
    if (bucket[i] != NULL) {
      cout << "HashIndex : " << i << " ";
      temp = bucket[i];
      while (temp != NULL) {
        cout << "(key = " << temp -> key << " , value = " << temp -> value << " )";
        temp = temp -> next;
      }
    }
    cout << endl;
  }
}

void HashTable::resize() {
  cout << "resize" << endl;
  slots *= 2;
  HashEntry ** tempBucket = new HashEntry * [slots];
  int hashIndex;
  HashEntry * tmp;
  for (int i = 0; i < slots; i++)
    tempBucket[i] = NULL;
  HashEntry * temp;
  for (int i = 0; i < slots / 2; i++) {
    if (bucket[i] != NULL) {

      temp = bucket[i];
      while (temp != NULL) {
        hashIndex = getIndex(temp -> key);
        if (tempBucket[hashIndex] == NULL)
          tempBucket[hashIndex] = new HashEntry(temp -> key, temp -> value);
        else { //find next free space

          tmp = tempBucket[hashIndex];;
          while (tmp -> next != NULL) {
            tmp = tmp -> next;
          }
          tmp -> next = new HashEntry(temp -> key, temp -> value);
        }
        temp = temp -> next;
      }
    }
  }
  bucket = tempBucket;
}

int HashTable::search(string key) {
  int hashIndex = getIndex(key);
  if (bucket[hashIndex] == NULL) {
    cout << "Value Not Found!" << endl;
    return -1;
  }

  if (bucket[hashIndex] -> key == key) {
    return bucket[hashIndex] -> value;
  } else { //find next free space

    HashEntry * temp = bucket[hashIndex];

    while (temp != NULL) {
      if (temp -> key == key) {
        return temp -> value;
      }

      temp = temp -> next;
    }
    cout << "Value Not Found!" << endl;
    return -1;
  }
}

void HashTable::Delete(string key) {
  int hashIndex = getIndex(key);
  if (bucket[hashIndex] == NULL) {
    cout << "Value To Be Deleted Not Found!" << endl;
    return;
  }
  if (bucket[hashIndex] -> key == key) {
    if (bucket[hashIndex] -> next != NULL) {
      bucket[hashIndex] = bucket[hashIndex] -> next;

    } else {
      bucket[hashIndex] = NULL;
    }
  } else { //find next free space

    HashEntry * temp = bucket[hashIndex];
    HashEntry * prev = bucket[hashIndex];
    while (temp != NULL) {

      if (temp -> key == key) {
        if (temp -> next != NULL) {
          prev -> next = temp -> next;
          temp = temp -> next;
        } else
          prev -> next = NULL;

        return;
      }
      prev = temp;
      temp = temp -> next;
    }
    cout << "Value to be deleted not Found!" << endl;
  }
}

#include <iostream>

using namespace std;

class HashEntry {
  public:
    string key;
    int value;
    HashEntry * next;
    
    HashEntry();
    HashEntry(string k, int val);
};

class HashTable {
  HashEntry ** bucket;
  int slots;
  int size;

  public:
    HashTable(int s);
    int getSize();
    bool isEmpty();
    int getIndex(string key);
    void insert(string key, int value);
    void display();
    void resize();
    int search(string key);
    void Delete(string key);
};

#include "Hash.h"

int main() {

    HashTable ht(4);
    ht.insert("London",2);

    ht.insert("London",10);
    ht.insert("New York",15);
    ht.insert("Tokyo",7);
    ht.insert("Bangkok",2);
    ht.insert("Beijing",6);
    ht.insert("Islamabad",9);
    ht.insert("New Delhi",17);
    ht.insert("Moscow",12);
    ht.display();
    ht.resize();
    ht.display();
    ht.insert("Amsterdam",5);
    ht.insert("Paris",13);
    ht.insert("Istanbul",19);
    ht.insert("Kuala Lumpur",1);
    ht.insert("Jakarta",8);
    ht.insert("Glasgow",3);
    ht.insert("Seattle",14);
    cout << ht.search("London") << endl;
    cout << ht.search("Moscow") << endl;
    cout << ht.search("Berlin") << endl;
    ht.display();
    ht.Delete("London");
    ht.display();
    ht.Delete("Moscow");
    ht.display();
    ht.Delete("Istanbul");
    ht.display();
}

runHash


# Overview
To sum up the discussion here, hash tables are the ideal data structure when you have a large amount of data, and you need all basic operations to work in constant time. The challenge with hash tables comes in the form of deciding the optimized hash function. The large memory cost must also be taken care of. 

Here are the time complexities for basic hash table operations:

Operation | Average | Worst 
--- | --- | ---
Search | `O(1)` | `O(n)`
Insertion | `O(1)` | `O(n)`
Deletion | `O(1)` |`O(n)`

---



Let's combine all the different operations discussed previously and test out the functionality of our complete hash table class.

A Quick Overview of Hash Tables

Complete