CareerCup

Bit Vector
hash Map

Bit vector can save space as we already know the range. 1 means the number is there and 0 means it is not there. inserting a number ans checking a num is O(1).
also searching is O(1)

Use int array of 1000, where index0-represents 1 and index-999 represnts 1000.
Add just increase the array value by 1
Delete just decrease the array value by 1
Search just check if array[number-1] >0
Get any number is similar to search

Forgot to mention with ques that numbers are unique in DS, means max of single occurrence of a number.

Forgot to mention with ques that numbers are unique in DS, means max of single occurrence of a number.

Forgot to mention with ques that numbers are unique in DS, means max of single occurrence of a number.

Create a prefix tree for every number that is added by using each digit as a node.
1. To insert, just move along the tree if the digits exist or create and move on. Do this 4 times for each number O(1)
2. Delete: Move down the tree 4 times using the digits and kill the root node (1)
3. Search: Move down the tree 4 times. If node missing, return -1 O(1)
4. Get any: Move down the tree 4 times choosing child nodes at random. Report the number O(1)

Hash table over a doubly linked list.
1. Insert - Head of linked list and in hash table. If already present just increase the count (can be stored in the linked list element).
2. Delete - Find node using hash table, decrease count. If count is zero, delete node (its doubly linked list so O(1))
3. Search - Hash table O(1)
4. Get any number - Return head of linked list or -1 if head is NULL

Hash table over a doubly linked list.
1. Insert - Head of linked list and in hash table. If already present just increase the count (can be stored in the linked list element).
2. Delete - Find node using hash table, decrease count. If count is zero, delete node (its doubly linked list so O(1))
3. Search - Hash table O(1)
4. Get any number - Return head of linked list or -1 if head is NULL

Q2. Given the following linked list, answer the questions:
L
‘B’ ‘E’ ‘S’ ‘T’
a) Determine the output of the following: (1 Pt each)
Note: Each part continue from the previous part.
node *P1=L,*P2=p1;
P1=(node*)malloc(sizeof(node));
P1->data=’E’;
1. P1->link=P2->link; P1->data= __E___
2. P2=P1->link->link; P2->data= __S___
3. P1=P2->link; P1->data= __T___
4. P2=P1->link; P2->data= __B___
b) Write one line of code to replace content of first node with
content of second node (in any linked list). (2 Pt)
L->data = L->link->data;
c) Write the code to delete the first node in the list. (2 Pts)
( assume last node points to null )
node *P = L;
L = L->link;
Free(P);

Use a doubly linked list and array.When a element i is to be stored create a node with value
i and add it to the linked list and store this node's address in the array at index i.when a
element is to be deleted find the node's address from the array and then delete it from
linked list and put null at the corresponding index in the array.When anyElement is called
return the first element of the linked list.

I think a bit vector will be the most optimum solution since we can have at the most one occurence of a number. We will need as much as 32 integers to store 1024 bits.

Insert : set_bit
Delete : reset_bit
Search : get_bit

class Bitset{
      private:
              int *bitset;
      public:
              Bitset() : bitset(NULL){};
              Bitset(int size): bitset(NULL)
              {
                       bitset=new int[size>>5];
              }

              bool search(int pos)
              {
                     int word=pos>>5;
                     int bitnum= pos&0x1F;
                     return ( bitset[word] & 1<<bitnum )!=0 ;
              }
               
              void insert(int pos)
              {
                     int word=pos>>5;
                     int bitnum=pos & 0x1F;
                     bitset[word] |= 1<<bitnum;
              } 
              
              void delete(int pos)
              {
                     int word=pos>>5;
                     int bitnum=pos & 0x1F;
                     if( !search (pos) ) bitset[word] |= 1<<bitnum;
              }