C-DOT interview experience

C-DOT is a telecommunications R&D company which works for government of INDIA

They shortlisted 5 people based on the CGPA. 

They asked my class placement representative about the courses we had in our academics a day before the interview.

The questions are mainly from the interesting subjects told by the candidate

My interview went as follows:

1. tell me about your self.
2. tell me about your family, interests,strengths& weakness.
3.  interesting subjects (Data Structures,Computer networks & Cryptography)
4. what are the cryptographic techniques in use.
5. tell how AES works
6. how two nodes communicate using AES
7. what is aloha
8. how performance in aloha can be increased
9. what is ARP
10. what is BOOTP
11. how BOOTP differ from RARP
12. write a program to print non duplicate elements in a array (value of an elements is from 1 to 100)
13. what is priority invertion
14. what is deadlock
15. how deadlock can be removed
16. what is meant by a signal
17. we have a multi tasking problem. For this multi process is better or multi thread is better 

My friend interview went as follows:

1. Strength and weakness
2. Hobbies
3. Introduce yourself 
4. What is super scalar architecture?
5. What are the applications of queues in os?
6. Difference mutex and semaphore
7. Fragmentation
8. Character stuffing
9. HTTP
10. Write a c program to reverse a single linked list?
11. Priority inversion
12. Synchronization
13. Pipelining
14. Explain my project

Clockwise/Spiral rule to know the type in C

What is str in the fallowing decleration

char *str[10];

What is fp in the fallowing decleration

     char *(*fp)( int, float *);

Click here to know answer

Programs on Bit Manipulation

Swap adjacent bits of an unsigned integer

unsigned int swap_adjacent_bit(unsigned int num)

{

    unsigned int even_mask = 0xAAAAAAAA;

    unsigned int odd_mask = 0x55555555;

    return (   ((num & even_mask)>>1) | ((num & odd_mask)<<1) );

}
TC = O(1)
SC = O(1)

or

unsigned int swapAdjacent(unsigned int number)
{
return ((0X55555555&number)<<1)||((number&0xaaaaaaaa)>>1);

}
TC = O(1)
SC = O(1)

Add two numbers without using arithmetic operators

int add(int m,int n)

{

int x;

while(n)

{

x=m|n;

n=(m^n)<<1;

m=x;

}

return x;

}
TC = O(log n)
SC = O(1)

 or 

int add(int m,int n)

{

return (m&n)?add((m&n)<<1,m^n):m^n;

}
TC = O(log n)
SC = O(log n)

Counting the number of set bits in a number

int cunt_bits(int n)

{

Int res=0,a[16]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4}

while(n)

{

res=res+a[n%16];

n=n>>4;

}

return res;

}

TC = Θ(n)
SC = O(1)

OR

int count_bits(int n)

{

int count=0;

while(n)

{

n=n&(n-1);// resets the right most set bit to zero 

count++;

}

}

TC = O(log n) or Θ(number of set bits)
SC = O(1)

How to find whether the number is power of two or not

int powof2(int number)

{

return !(number&(number-1))

}

 All the elements in an array of size n are repeated even number of times except one find the number that is repeated odd number of times

int findodd(int a[],int n)

{

int i,j=1,res=0,res1=0,res2=0;

for(i=0;i<n;i++)

{

res=res^a[i];

}

return res;

}

TC = Θ(n)
SC = O(1)

Given a number how to find it is divisible by 3 or not without using the modulo operator (It is good if you doesn't use multiplication & division operator also)

uint divisibleby3(uint number)

{

if(number<3)

return !number;

uint odd=0x55555555,even=0xaaaaaaaa;

odd= count(odd&number);

even= count(even&number);

if(odd>even)

return divisibleby3(odd-even);

return divisibleby3(even-odd);

}

uint count(uint number)

{

if(number==0)

return 0;

return 1+count(number&(number-1));

}

Programs on Linked List

Program to create a dummy single linked list

#include<stdio.h>

struct node

{

int data;

struct node *next;

};

typedef struct node * lnode;

main()

{

int ele,m,n,i;

lnode head=malloc(sizeof(struct node));

lnode temp,temp1;

if(head)

head->next=NULL;

addfirst(head,10);

temp1=head->next;

for(i=0;i<10;i++)

{

printf("enter the element to be added\n");

scanf("%d",&ele);

addfirst(head,ele);

}

print(head);

}

void addfirst(lnode head,int data)

{

lnode temp=malloc(sizeof(struct node));

temp->data=data;

temp->next=head->next;

head->next=temp;

}

void print(lnode head)

{

lnode temp=head->next;

while(temp)

{

printf("%d->",temp->data);

temp=temp->next;

}

printf("\n");

}

Given a singly-linked, find out the mid point of a single linked list

int middle(struct node *head)
{
struct node *slow,*fast;
slow=fast=head->next;
while(fast&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
return slow->data;
}

TC = Θ(n)
SC = O(1)

Program to check the loop in the single linked list

int findloop(lnode head)

{

lnode slow,fast;

slow=fast=head->next;

do

{

slow=slow->next;

if(fast==NULL || fast->next==NULL)

return 0;

fast=fast->next->next;

}

while(slow!=fast);

return 1;

}

TC = Θ(n)
SC = O(1)

Program to Reverse the single linked list

void reverse(lnode head)

{

lnode cur,temp;

cur=head->next;

head->next=NULL;

while(cur!=NULL)

{

temp=cur->next;

cur->next=head->next;

head->next=cur;

cur=temp;

}

}
Time Complexity (TC) = Θ(n)
Space Complexity (SC)= O(1)

Dynamic Programming

Write a program to print all the binary strings of length n and does not contain a specific string

C Language:

#include<stdio.h>
main()
{
char in[30];
int i,n,cnt=0;
printf("enter n value\n");
scanf("%d",&n);
printf("enter the pattern that you don't want in side the binary string\n");
scanf("%s",&in);
printf("all the patterns without %s are \n",in);
printall(in,n,&cnt);
printf("count = %d\n",cnt);
}
void printall(char in[], int n, int *cnt)
{
char out[30]="";
aux_printall(in,out,0,n,cnt);

}
void aux_printall(char in[], char out[], int d, int n, int *cnt)
{
if(d>strlen(in))
{
out[d]='\0';
if(strstr(out,in)!=NULL)
return;
}
if(d==n) // print output
{
out[n]='\0';
printf("%s\n",out);
(*cnt)++;
return;
}

out[d]='0';
aux_printall(in,out,d+1,n,cnt);
out[d]='1';
aux_printall(in,out,d+1,n,cnt);
}

Java:

import java.util.Scanner;

class Binary

{

       public static void main(String [] args)

    {

        Scanner input = new Scanner(System.in);

        int[] cnt = new int[1];

        cnt[0]=0;

        System.out.print("Enter n:\n");

        int n = input.nextInt();

        System.out.print("Enter string that you don't want inside the binery string \n");

        String  in = input.next();

        System.out.print("The binary strings of length "+n+" and without haveing "+in+" are\n");

        printall(in, n,cnt);

        System.out.println("the count is "+cnt[0]);

     

    }

    public static  void printall(String in, int n, int [] cnt)

    {

           String out="";

            int d=0;

            auxprintall(in,out,d,n,cnt);

    } 

    public static void auxprintall(String in, String out, int d, int n, int [] cnt)

    {

        if(out.contains(in))

        return;

        if(d==n)

        {

        System.out.println(out);

        cnt[0]++;

        return;

        }

        

        auxprintall(in,out+"0",d+1,n,cnt);

        auxprintall(in,out+"1",d+1,n,cnt);

    

    }

}

Write a program to print all the binary strings of length n

#include<stdio.h>
main()
{
int n;
printf("enter n value\n");
scanf("%d",&n);
printall(n);
}
void printall(int n)
{
char out[30]="";
aux_printall(out,0,n);

}
void aux_printall(char out[], int d, int n)
{
if(d==n) // print output
{
out[n]='\0';
printf("%s\n",out);
return;
}

out[d]='0';
aux_printall(out,d+1,n);
out[d]='1';
aux_printall(out,d+1,n);
}

N queen problem

#include<stdio.h>
int attck(int, int [], int);
main()
{
    int n;
    printf("enter the n value\n");
    scanf("%d",&n);
    nqn(n);
    }
void nqn(int n)
{
int a[20];
auxnqn(a,0,n);
}
void auxnqn(int a[],int d,int n)
{
 if(d==n){
print(a,n);
 return ;
 }
 for(int i=0;i<n;i++)
 {
  if(attack(i,a,d))
   continue;
 a[d]=i;
 auxnqn(a,d+1,n);
 }
}
void print(int a[],int n)
{
int i;
printf("( ");
for(i=0;i<n;++i)
printf(" %d ",a[i]);
printf(")\n");
}
int attack(int d,int a[],int n)
{
for(int i=0;i<n;++i)
{
if(a[i]==d || abs(a[i]-d)==abs(n-i))
return 1;
}
return 0;
}

Printing the all anagrams of a word

#include <stdio.h>
int check(char [],int , char );
int main()
{
   char a[10]="abcd";
   anagrams(a);
}
void anagrams(char in[])
{
char out[10];
int n;
n=strlen(in);
auxanagram(in,out,0,n);
}
void auxanagram(char in[],char out[],int d,int n)
{
int i;
if(d==n) // print output
{
out[n]='\0';
printf("%s\n",out);
return;
}
for(i=0;i<n;i++)
{
if(check(out,d,in[i]))  // Pruning logic
continue;
out[d]=in[i];
auxanagram(in,out,d+1,n);
}
}
int check(char out[],int d,char c)
{
int i;
for(i=0;i<d;i++)
if(out[i]==c)
return 1;
return 0;
}

Programs on cryptography

Finding the generator for group  * mod p (p is a prime number)

int gen(int p)
{
int i,j,k,l;
for(i=2;i<p;i++)
{
k=1;
      for(j=1;;j++)
      {
      k*=i;
      k%=p;
      printf("%d ",k);
      if(k==1)
      break;
      }
if(j==(p-1))
return i;
}

}

Finding the jacobi value

#include<stdio.h>
main()
{
int i,j,k,l,m,n;
i=1;
j=-1;
printf("enter the two numbers\n");
scanf("%d %d",&m,&n);
while(m>1)
{

      if(m%2==0)
      {
printf("in if \n");
            if(n%8==1 || n%8==7)
            {
                  i=i*1;
            }
            else
            i*=j;
      m/=2;
      }
      else if(m>n)
      {
printf("else if\n");
m=m%n;           
      }
      else
      {
printf("value is %d\n",(m%4)==3&&(n%4)==3);
            if((m%4)==3&&(n%4)==3)
            {
                  i*=j;
            printf("%d %d %d \n",i,m,n);
            }
            k=n;
            n=m;
            m=k;
printf("%d",i);
      }
printf(" %d %d %d\n",i,m,n);
}

}
 

Finding m^-1 mod n using extended euclidean algorithm

int exeu(int m,int n)
{
int i,j,k,l,a1=1,a2=0,a3,b1=0,b2=1,b3,c1,c2,c3;
      if(m>n)
      {
            i=m;
            j=n;
      }
      else
      {
            i=n;
            j=m;
      }
a3=i;
b3=j;
      while(b3>0)
      {
      c1=a1-(a3/b3)*b1;
      c2=a2-(a3/b3)*b2;
      c3=a3%b3;
      a1=b1;
      a2=b2;
      a3=b3;
      b1=c1;
      b2=c2;
      b3=c3;
      }
            if(i==m)
            {
                  if(a1>0)
                  return a1;
                  else return n+a1;
            }
            else
            {
                  if(a2>0)
                  return a2;
                  else return n+a2;
            }
}

 Elgamal cryptosystem in C

#include<stdio.h>
main()
{
int i,j,k,l,m,x,n,p,g,c1=1,c2=1,c3=1;
printf("enter the prime number do you want to take\n");
scanf("%d",&p);
g=gen(p);
printf("enter the private key do you want to take\n");
scanf("%d",&x);
int y=1;
      for(i=0;i<x;i++)
      {
      y*=g;
      y%=p;
      }
printf("the public key of the crypto system is (%d %d %d)\n",g,y,p);
printf("the encryption proccess\n");
printf("enter the number do you want to encrypt\n");
scanf("%d",&m);

printf("the random number you want to take\n");
      scanf("%d",&k);
      for(i=0;i<k;i++)
      {
      c1*=g;
      c2*=y;
      c1%=p;
      c2%=p;
      }
c2*=m;
printf("the encrypted message is (%d %d)\n",c1,c2);
printf("the decryption process is \n");
            for(i=0;i<x;i++)
            c3*=c1;
c3=exeu(c3,p);
n=c2*c3;
n%=p;
printf("the decrypted message is %d \n",n);
}

int exeu(int m,int n)
{
int i,j,k,l,a1=1,a2=0,a3,b1=0,b2=1,b3,c1,c2,c3;
      if(m>n)
      {
            i=m;
            j=n;
      }
      else
      {
            i=n;
            j=m;
      }
a3=i;
b3=j;
      while(b3>0)
      {
      c1=a1-(a3/b3)*b1;
      c2=a2-(a3/b3)*b2;
      c3=a3%b3;
      a1=b1;
      a2=b2;
      a3=b3;
      b1=c1;
      b2=c2;
      b3=c3;
      }
            if(i==m)
            {
                  if(a1>0)
                  return a1;
                  else return n+a1;
            }
            else
            {
                  if(a2>0)
                  return a2;
                  else return n+a2;
            }
}
int gen(int p)
{
int i,j,k,l;
for(i=2;i<p;i++)
{
k=1;
      for(j=1;;j++)
      {
      k*=i;
      k%=p;
      if(k==1)
      break;
      }
if(j==(p-1))
return i;
}
}
 

RSA algorithm in C

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<unistd.h>
int FLAG=1;
void check(int e,int phi)
{

int i;

for(i=3;e%i==0 && phi%i==0;i+2)

{

FLAG = 1;

return;

}

FLAG = 0;

}
main()
{

int f,i,j,k,phi,p,q,n,g,d,e,w,c,s,v,b[10];
char a[100],ac[100],as[100],qw[100],qe[100],qt[100],qy[100];
printf("enter the two prime numbers\n");
scanf("%d",&p);
scanf("%d",&q);
n=m*n;
phi=(p-1)*(q-1);

do

{

printf("enter the e value which is co-prime to %d\n",phi);
scanf("%d",&e);

check(e,(m-1)*(n-1));

}while(FLAG==1);

for(i=2;i<phi;i++)
{
d=(e*i)%l;
if(d==1)
break;
}
d=i;
printf("%d",d);
printf("the public keys are\n");
printf("(%d %d) \n",e,n);
printf("the private keys are\n");
printf("(%d %d) \n",d,n);
printf("enter the text\n");
scanf("%s",a);
v=strlen(a);
for(i=0;i<v;i++)
{
g=a[i];
c=1;
for(j=0;j<e;j++)
{
c=(c*g)%n;
}
b[i]=c;
as[i]=b[i];
}
printf("the encrypted form is\n");
for(i=0;i<v;i++)
printf("%d ",b[i]);
printf("\n");


for(i=0;i<v;i++)
{
g=b[i];
c=1;
for(j=0;j<d;j++)
{
c=(c*g)%n;
}
ac[i]=c;
}
printf("the decrypted form is\n");
printf("%s\n",ac);
}

Backtracking

This is the most important technique for gaming companies
Some of the standard programs are as fallows

Printing the all anagrams of a word

N queen problem

Write a program to print all the binary strings of length n

Write a program to print all the binary strings of length n and does not contain a specific string

programs on Strings

Program to reverse the order of words in a sentence

example: 

Input: my name is aravind

output: aravind is name my

#include<stdio.h>
#include<string.h>
main()
{
int i,j,k,l,m;
char a[40],temp;
printf("enter the sentence\n");
gets(a);
k=strlen(a);
for(i=0;i<k/2;i++)
{
temp=a[i];
a[i]=a[k-i-1];
a[k-i-1]=temp;
}
a[k]=' ';
i=0;
while(i<k)
{
j=i;
while(a[i]!=' ')
i++;
l=i-1;
for(m=0;m<(l-j+1)/2;m++)
{
temp=a[j+m];
a[j+m]=a[l-m];
a[l-m]=temp;
}
i++;
}
for(i=0;i<k;i++)
printf("%c",a[i]);
printf("\n");
}

TC = Θ(n)
SC = O(1)

Count vowels/consonants in a string. 

example: "alpha" as input and output is 2, 3

void count(char a[], int b[])

{

int i;

for(i=0;a[i]!='\0';i++)

{

if(a[i]=='a'||a[i]=='e'||a[i]=='i'||a[i]=='o'||a[i]=='u')

b[0]++;

else

b[1]++;

}

}

Change case of every character (lower to uppper and upper to lower). 

example: input: AlpHa and output is aLPhA

void convert(char a[])

{

int i;

for(i=0;a[i]!='\0';i++)

{

if(a[i]<='Z'&&a[i]>='A')

a[i]=a[i]-'A'+'a';

else

a[i]=a[i]-'a'+'A';

}

}

Using standard phone mapping convert a string to a number representation. 

example: Input: cat and output: 228

void convert(char a[],char b[])

{

int i;

for(i=0;a[i]!='\0';i++)

{

b[i]=numberofchar(a[i]);

}

b[i]='\0';

}

char numberofchar(char c)

{

if(c=='a'||c=='b'||c=='c')

return '2';

if(c=='d'||c=='e'||c=='f')

return '3';

if(c=='g'||c=='h'||c=='i')

return '4';

if(c=='j'||c=='k'||c=='l')

return '5';

if(c=='m'||c=='n'||c=='o')

return '6';

if(c=='p'||c=='q'||c=='r'||c=='s')

return '7';

if(c=='t'||c=='u'||c=='v')

return '8';

if(c=='w'||c=='x'||c=='y'||c=='z')

return '9';

}

Given (abc, 2) -> abcabc. Repeat whole string two times one after another.

void repeatstring(char a[],int n)

{

int i,j,k=0;

char b[20];\\temporary array to store the given array

for(i=0;a[i]!='\0';i++)

b[i]=a[i];

b[i]='\0';

for(i=0;i<n;i++)

for(j=0;b[j]!='\0';j++)

a[k++]=b[j];

a[k]='\0';

}

Given (abc, 2) -> aabbcc. Repeat each char and Expand the string. 

void repeatchar(char a[],int n)

{

int i,j,m=0;

char b[100]; \\temporary array  to store the given string

for(i=0;a[i]!='\0';i++)

b[i]=a[i];

b[i]='\0';

for(i=0;b[i]!='\0';i++)

for(j=0;j<n;j++)

a[m++]=b[i];

a[m]='\0';

}

Remove all digits in a given string

void removedigits(char a[])

{

int i,j=0;

for(i=0;a[i]!='\0';i++)

{

if(a[i]<'0'|| a[i]>'9')

{

a[j++]=a[i];

}

}

a[j]='\0';

}