CareerCup

Good. +1.

I didn't go with bitset, but all in all I implemented the ArrayList using boolean arrays. I guess they didn't like my answer, got a reject!

@adi: Lot of factors go into a reject. Your performance on any one particular question cannot be the determining factor (unless it raises a clear red flag/ is a phone interview etc).

Here is an implementation of the first approach.

#include<stdio.h>
#include<stdlib.h>

typedef enum {false, true} bool;

typedef struct BVect_s {
    char *val;
    int len;
    int numBit;
} BVect;

int initialize(BVect *v){
    v->val = (char *)malloc(sizeof(char));
    v->len = 1;
    v->numBit = 0;
    return 0;
}

bool get(BVect *v, int pos){
    if(v->numBit <= pos)
        return false;
    int s = sizeof(char);
    return v->val[pos/s]&(1<<(pos%s))?true:false;
}

int set(BVect *v, int pos, bool a){
    if(pos >= v->numBit)
        return 1;
    int s = sizeof(char);
    if(a)
        v->val[pos/s] = v->val[pos/s]|(1<<(pos%s));
    else
        v->val[pos/s] = v->val[pos/s]&~(1<<(pos%s));
    return 0;
}

int doubleLen(BVect *v){
    v->len *= 2;
    return v->val = realloc(v->val, sizeof(char)*v->len);
}

int append(BVect *v, bool a){
    if(v->val == NULL)
        initialize(v);
    if(v->numBit == v->len*8)
        doubleLen(v);
    v->numBit++;
    return set(v, v->numBit-1, a);
}

/*driver function to test*/
int main(){
    char op;
    int val, pos;
    BVect *t;
    while(1){
        scanf("%c", &op);
        switch(op){
            case 'a':
                scanf("%d", &val);
                append(t, val);
                break;
            case 's':
                scanf("%d", &pos);
                scanf("%d", &val);
                set(t, pos, val);
                break;
            case 'g':
                scanf("%d", &pos);
                printf("%d\n", get(t, pos));
        }
    }
    return 0;
}

@karaamaati: Thanks for adding code, but there's one critical mistake. It would be nice if you could edit your response to correct it. sizeof(char) is always 1, so you aren't really using bits here. You wanted the constant CHAR_BITS (use #include <limits.h>), which will (usually) be equal to 8. I also notice that in some places, you've directly used the constant 8, so you should convert those usages to CHAR_BITS as well for consistency.

There are some smaller stylistic issues too, for example "return condition ? true: false;" can be simplified to "return condition;". "complicatedThingThatTakesLotsOfTyping = complicatedThingThatTakesLotsOfTyping & expression" can be simplified to "complicatedThingThatTakesLotsOfTyping &= expression".

FWIW, std::vector<bool> is specialized to optimize space etc and can be used directly.

Here is an implementation.

#include <stdlib.h>
#include <iostream>
using namespace std;

class vectorBool{
  int* neg;
  int neg_size;
  int size;
public:
  vectorBool();
  ~vectorBool();
  void append(bool b);
  bool get(int index);
  void set(int index, bool b);
  int length();
  void display();
};

vectorBool::vectorBool(){
  neg = NULL;
  neg_size = 0;
  size = 0;
}

vectorBool::~vectorBool(){
}

void  vectorBool::append(bool b){
  if( b == false){
    int* newNeg = new int[neg_size+1];
    newNeg[neg_size] = size;
    if( neg ){
      for( int i = 0; i < neg_size; i++){
	newNeg[i] = neg[i]; 
      }     
      delete neg;
      neg = newNeg;
    }
    else{
      neg = newNeg;
    }
    neg_size++;
  }
  size++;
};

bool vectorBool::get(int index){
  if( index < 0 || index >= size ){
    cout << "Invalid Index!" << endl;
    exit (-1);
  }
  for( int i = 0; i < neg_size; i++){
    if ( index == neg[i] )
      return false;
  }
  return true;
}

void vectorBool::set(int index, bool b){
  if ( index < 0 ){
    exit (-1);
  }
  if ( index < size ){
    bool change_neg = false;
    for(int i = 0; i < neg_size; i++ ){
      if ( index == neg [i] ){
	  change_neg = true;
	  if( b == true){
	      int* newNeg = new int [ neg_size - 1];
	      for(int i = 0; i < index; i++){
	         newNeg[i] = neg[i];
	      }
	     for(int i = index+1; i < neg_size; i++){
	         newNeg[i-1] = neg[i];
	     }
	     neg_size--;
	     delete neg;
	     neg = newNeg;
	     break;
         }
      }
    }
    if(! change_neg){
      if( b == false){
	   int* newNeg = new int[neg_size+1];
	   neg[neg_size] = index;
	   neg_size++;
      }
    }	
  }
  else{
    append( b );
  }
}

int vectorBool::length(){
  return size;
}

void vectorBool::display(){
  cout << "neg: ";
  for(int i = 0; i< neg_size; i++)
    cout << neg[i] << ' ';
  cout << endl;
  cout << "neg_size: " << neg_size << endl;
  cout << "size: " << size << endl;
}

int main(){
  vectorBool v;
  v.append(false);
  v.append(true);
  v.append(false);
  v.set(2, true);
  v.append(false);
  v.display();
}