//Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB memory. Follow up with what you would do if you have only 10 MB of memory.
//reference source:
//in that page MEMORY LIMITS SECTION
//below is c++solution
//Note : please create a file with name appropriately or download one from https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2010.%20Sorting%20and%20Searching/Q10_07_Missing_Int
PARTA:
#include <iostream>
#include <bitset>
#include <fstream>
#include <iomanip>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0X1F
#define N 2147483647
using namespace std;
void setBit(int i, int *a)
{
a[i>>SHIFT] |= (1<<(i&MASK));
}
void clearBit(int i,int *a)
{
a[i>>SHIFT] &= ~(1<<(i&MASK));
}
int testBit(int i,int *a)
{
return a[i>>SHIFT] & (1<<(i&MASK));
}
void findNumber(){
int a[1+N/BITSPERWORD];
const char* filename = "input1.txt";
ifstream inFile(filename,std::ios::in);
// Make sure the file stream is good
if(!inFile) {
cout << endl << "Failed to open file " << filename;
}
int n = 0;
while(inFile)
{
inFile>>n;
clearBit(n,a);
setBit(n,a);
}
for(int i=0;i<N;i++)
{
if(!testBit(i, a))
{
cout<<i;
}
}
}
int main(int argc, const char * argv[]) {
// insert code here...
std::cout << "Hello, World!\n";
findNumber();
return 0;
}
partB Follow UP:
#include <iostream>
#include <bitset>
#include <fstream>
#include <iomanip>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0X1F
#define N 2147483647
#define RANGESIZE 100
/* 1 << (i & MASK): left shift from 0 to 31, represents 2^i
i >> SHIFT: array index
0-31 a[0]
32-63 a[1]
64-95 a[2]
... ...
*/
//set rangeSIZE as 1048576 which == 2power20 if the array can hols size of 10MB which == 2power 20
//#define RANGESIZE 1048576
using namespace std;
void setBit(int i, int *a)
{
a[i>>SHIFT] |= (1<<(i&MASK));
}
//below function will clear the bit as below
//for eg if we have
//i 32 a is the bitvector
//i>>SHIFT will shift the i from 32 to 1 so we are accessing index =1 in the array a
//i&MASK will transform MASK from 31 to 23
//1<<(i&MASK) will left shift 1 and make 23 bit position as 1
//hence a[i>>SHIFT] & (1<<(i&MASK)) which check if 23rd position is 0 or 1 which indictes the presence of the number throught bit position
void clearBit(int i,int *a)
{
a[i>>SHIFT] &= ~(1<<(i&MASK));
}
int testBit(int i,int *a)
{
return a[i>>SHIFT] & (1<<(i&MASK));
}
bool checkFile(ifstream *inFile)
{
if(!(*inFile))
{
return false;
}
return true;
}
void getCountPerBlock(const char* filename,int *blocks)
{
ifstream inFile(filename,std::ios::in);
if(checkFile(&inFile)==true)
{
int n = 0;
while(!inFile.eof())
{
inFile>>n;
blocks[n/RANGESIZE]++;
}
}
else
{
cout << endl << "Failed to open file ";
}
}
int getMissingIndex(int *blocks,int size)
{
for(int i=0;i<size;i++)
{
if(blocks[i]<RANGESIZE)
{
return i;
}
}
return -1;
}
void setBitVector(int missingIndex,const char* fileName,int *blocks,int size,int *bitVector,int bitVectorSize)
{
int startRange = RANGESIZE*missingIndex;
int endRange = RANGESIZE*missingIndex+RANGESIZE-1;
int offSet = 0;
ifstream inFile(fileName,std::ios::in);
if(checkFile(&inFile)==true)
{
int n = 0;
while(!inFile.eof())
{
inFile>>n;
if(n>=startRange && n<=endRange)
{
offSet = n - (missingIndex*RANGESIZE);
clearBit(offSet,bitVector);
setBit(offSet,bitVector);
}
}
}
else
{
cout << endl << "Failed to open file ";
}
}
int findZeroBit(int *bitArray,int size)
{
for(int i=0;i<RANGESIZE;i++)
{
if(!testBit(i,bitArray))
{
return i;
}
}
return -1;
}
void disp(int *blocks,int size)
{
for(int i=0;i<size;i++)
{
cout<<blocks[i];
}
}
void setArray(int *blocks,int size)
{
for(int i=0;i<size;i++)
{
blocks[i]=0 ;
}
}
void findNumber(){
//change this value to INT_MAX when we test for a file which contains 1GB of consecutive numbers
int maxInt = 500;
//if the RAM size is 10 MB or the array size is of 2power20 == 10 MB set the rangesize as below
const char* filename = "input2.txt";
int blocks[maxInt/RANGESIZE+1];
int bitVector[RANGESIZE/BITSPERWORD+1];
int bitVectorSize = (int)(sizeof(blocks)/sizeof(blocks[0]));
int size = (int)(sizeof(blocks)/sizeof(blocks[0]));
setArray(blocks,size);
getCountPerBlock(filename,blocks);
int missingIndex = getMissingIndex(blocks,size);
if(missingIndex!=-1)
{
cout<<missingIndex;
setBitVector(missingIndex,filename,blocks,size,bitVector,bitVectorSize);
int offset = findZeroBit(bitVector,bitVectorSize);
if(offset!=-1)
{
int missingValue = RANGESIZE*missingIndex +offset;
cout<<"missig value is"<<missingValue;
}
}
else{
cout<<"There is no missing value";
}
}
int main(int argc, const char * argv[]) {
findNumber();
return 0;
}
