C++ interview questions (5) -Algorithm

C++ interview Questions (1)
C++ interview Questions (2)
C++ interview questions (3)
C++ interview questions（4）


26.Describe hash table  and one simple rehashing policy.
A hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values (e.g., their telephone number)

The implementation of this calculation is the hash function f:

index = f(key, arrayLength)

The hash function calculates an index within the array from the data key. arrayLength is the size of the array.

The simplest rehashing policy is linear probing. Suppose a key K hashes to location i. Suppose other key occupies H[i]. The following function is used to generate alternative locations:

rehash(j) = (j + 1) mod n
where j is the location most recently probed and n the size of the hash table. Initially j = i, the hash code for K. Notice that this version of rehash does not depend on K.

Linear probing is a scheme in for resolving hash collisions of values of hash functions by sequentially searching the hash table for a free location.^[1]

newLocation = (startingValue + stepSize) % arraySize

The first source code is an implementation of a Hash Map with open addressing (linear probing) as collision resolution method.

// hashMapLinear[] is the hash map
void linearProbingInsert(int value){
    int probe = hash(value);
    while (hashMapLinear[probe]!=0){                            
        probe = fmod((probe+1),SIZE_HASH_MAP); 
    }
    hashMapLinear[probe] = value; 
}
 
int linearProbingSearch(int value){
    int probe = hash(value);  
    int i;
    for(i=0;i<size_hash_map ;i++){     
        if(hashMapLinear[probe]==value)
            return TRUE;                             
        probe = fmod((probe+1),SIZE_HASH_MAP);               
    }
    return FALSE;                                           
}

27. Describe Stacks and name a couple of places where stacks are useful. 
 A stack is a last in, first out (LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. Many virtual machines are also stack-oriented, including the p-code machine and the Java Virtual Machine.


Below is example to  to use stacks to check an input file for parentheses matches.
Algorithm: Read from input file, process on character, push , i.e ++ptr if "(",  pop, i.e. --ptr  if ")",   the parentheses missing when ptr < 0

--------------------------------------------------------------------

#include <fstream.h>
#include <stdlib.h>   // for exit(..)
#include <stdio.h>
#include "stack.h"

int main()
{
   char c;
   int k;
ifstream f;
  f.open( "input.txt" );

  if( ! f ){
    cout << "Error opening file. Quitting.\n";
    exit(-1);
  }

   //initialize

   stk_init();
      c = getchar();
      putchar(c);

   // loop through file one char at a time
   while (c!=EOF)
   {
     // process one character
     // push (,  pop if ),
     // check stack empty if \n,
     // ignore others
     // if error, move to next line
       if (c == '(')
       {
         stk_push(c);

       }
       else if (c == ')')
       {
            if (c !== '\n')    
            stk_pop(c);
            else if (c == '(')
            stk_push (c);
// pop stack, if empty have missing (
       }
       else if (c == '\n')
       {
         // check on missing )
         // set up for next line
         stk_init();
       }
       if (stk_error()) //skip rest of line

       else // get next char
       {
       }
     } // endwhile
   return 0;
}

stach.h as below:

#define STK_ERROR '?' 
/* Private data: */
#define MAX 50 
static int error;   /* error flag */
static char data[MAX];   /* the stack */
static int ptr;         /* stack pointer */

/* Function implementation */

void stk_init() {
   ptr = 0;
   error = 0;
}

void stk_push(char x) {
    if (ptr < MAX) {
        data[ptr++] = x;
        error = 0;
    }
    else
        error = 1;
}

char stk_pop(void) {
    if (ptr > 0) {
        int x = data[--ptr];
        error = 0;
        return x;
    } else {
        error = 1;
        return STK_ERROR;
    }
}

char stk_top(void) {
    if (ptr > 0) {
        error = 0;
        return data[ptr-1];
    } else {
        error = 1;
        return STK_ERROR;
    }
}

int stk_size(void) {
    return ptr;
}

int stk_error(void) {
    return error;
}