Interview FAQ III

1) Write an *unordered* tree into disk and reconstruct same tree.

Important point to note here is to replace the pointer information left node, right node etc with offset in file where left node, right node are placed.
Eg: Node a :
val 5
left 0x30001244 [node b]
right 0x30001264 [node c]
where node b and node c are placed in 0x30001244 and 0x30001264. When node a, node b, node c are written into a file at offsets 0, 16 and 32 then replace node as below when dumping iit into the disk
Eg: Node a :
val 5
left 16
right 32

2) Difference between process and thread. Process has its own address space, context switching is costlier.

Threads are light weight, they share the address space with main thread. Context switching is light weight complete register set many not be loaded and stored.

3) Using variable arguments

#include stdarg.h
#include stdio.h
/* Here n is the number of arguments */
void varArg(int n, ...)
{
va_list p;
va_start(p, n);
printf("count = %d: ", n);
while (n-- > 0) {
int i = va_arg(p, int);
printf("%d ", i);
}
printf("\n");
va_end(p);
}

int main()
{
varArg(1, 1);
varArg(3, 1, 2, 3);
return 0;
}

4) Function that accepts a function pointer
void PassPtr(int (*pt2Func)(float, char, char))

5) Function pointer that accepts a function pointer
void (*PassPtr) (int (*pt2Func)(float, char, char))

6) Write a recursion program to print elements in a linked list

printNode ( vNode *n)
{
if ( n == NULL)
return;
else
{
printf ("Value of node is %d\n", n->val);
printNode (n->next);
}
}

7) Difference between mutex and semaphore.

Mutex: Mutually exclusive. It is usually used to protect a critical region so that one thread uses the resources.
Semaphore: Mechanism to share more than one resource. For eg: if you have 5 resources you can use a counting semaphore with sem value 5. This makes sure that only 5 concurrent threads can access the semaphore.

In Vxworks mutex is a different from a binary semaphore as mutex can be released
only by the thread that owns the mutex. However binary semaphore can be released
by threads that dont own it.

8) Swapping two variables
a = a+b;
b= a-b;
b=a-b;

9) Program for counting number of bits set in a variable.

int count =0;
while ( (a= a>> 1 ))
{
if ( a & 0x1)
count++;
}

Interview FAQ I

1) Priority inversion ?

When a thread running at lower level holds the synchronization lock and is prempted by another thread running at elevated level then dead lock situation arises. In that case the priority of the thread holding the lock is temporarily increased so that it releases the lock soon. This is called priority inversion

2) Which synchronization primitive should I use ?

Spinlocks: Multiprocessor safe, busy wait, keeps on spinning on the processor until the lock is released.
Semaphore: Multiprocessor safe, sleep wait, process is moved to sleep queue if some one else is holding the lock. More than one resource can be protected using semaphores.
Mutex: Multiprocessor safe, sleep wait, process is moved to sleep queue if some one else is holding the lock. Its mutually exclusive lock, only one resource can be shared.

3) How to debug memory corruption without tools ?

You can write a wrapper function with boundaries defined and maintain accounting for malloc/calloc and free. You just need to compile this as a library and prload the library using LD_PRELOAD.

4) Compute the parity of byte with order 1:

Precompute the parity and do a lookup from the array by just indexing into the array.

5) Convert the string from "This is the string" to "string the is This".

Algorithm:

Do an inplace string reversal first.

Change "This is the string" to "gnirts eht si sihT"

Reverse characters of each word inplace.

"string eht si sihT"
"string the si sihT"
...

6) Little Endian/ Big Endian

union endian{
struct {
char a;
char b;
char c;
char d;
} en;
int p;
}k k1;

k1.p = 1;

if (k1.a == 1 )
{
printf" Little Endian";
}
else {
printf" Big Endian";
}

7) Determining the offset with in a struct p

((char *) 0 - (char *) (&((struct *p) 0)->offset))

C FAQ - III

FAQ - III

Deleting a node from single linked list without knowing previous pointer :

You need to make a copy of the next node on the current node and then free the next node ;)


Detecting loops in linked list:

Use two pointers one that moves node by node and the other moves two nodes at a time, if these
pointers meet then a loop is detected.

C FAQ - II

C FAQ – II

Bitwise operations

#include<stdio.h>

unsigned int swap( unsigned int p, int xp, int xy);
unsigned int setbit (unsigned int p, int xp);
unsigned int resetbit (unsigned int p, int xp);
unsigned int countbits (unsigned int p);

int main()
{
printf ("The values after swapping of 0xf001 is %x\n", swap (0xf001, 1, 15));
printf ("The values after setting of 0xf001 is %x\n", setbit (0xf001, 4));
printf ("The values after resetting of 0xf001 is %x\n", resetbit (0xf001, 4));
printf ("The values after counting of 0xf001 is %x\n", countbits (0xf001));
}

unsigned int swap( unsigned int p, int xp, int yp)
{
unsigned int x = p & (1 << xp);
unsigned int y = p & (1 << yp);

p = p ^ x ^ y; /* Reset those bits to zero */
if (yp > xp)
{
y = y >> (yp -xp);
x = x << (yp - xp);
y = x | y;
}
else
{
y = y >> (xp -yp);
x = x << (xp - yp);
y = x | y;
}
return (p | y);
}

unsigned int setbit (unsigned int p, int xp)
{
xp = 1 << xp;
return (p | xp);
}

unsigned int resetbit (unsigned int p, int xp)
{
xp = 1<< xp;
return (p & ~xp);
}

unsigned int countbits (unsigned int p)
{
int cnt=0;
while (p)
{
if (p & 1)
cnt++;
p = p>>1;
}
return cnt;
}

Output:

The values after swapping of 0xf001 is 7003
The values after setting of 0xf001 is f011
The values after resetting of 0xf001 is f001
The values after counting of 0xf001 is 5


FIFO Implementation

#include<stdio.h>

#define MAX 30

int FIFO[MAX];
int wptr,rptr;
int bcross;
int readfifo (int data);
int writefifo (int data);

int main()
{
int i;
int p;
for (i=0;i<MAX+3;i++)
writefifo (i);
for (i=0;i<MAX+3;i++)
printf ("data read from the fifo is %d\n", readfifo (i));
for (i=0;i<5;i++)
writefifo (i);
for (i=0;i<6;i++)
printf ("data read from the fifo is %d\n", readfifo (i));

}

int writefifo (int data)
{
if (wptr == rptr && (bcross == 1))
{
printf("Fifo Overflow detected \n");
return -1;
}
else if (wptr >= rptr && (bcross == 0))
{
FIFO[wptr++] = data;
}
else if (wptr < rptr && (bcross == 1))
{
FIFO[wptr++] = data;
}
else {
printf("FIFO corruption detected \n");
}
if (wptr == MAX)
{
wptr=0;
bcross=1;
}
return wptr;
}

int readfifo (int data)
{
if (wptr == rptr && (bcross == 0))
{
printf("Fifo Underrun detected \n");
return -1;
}
else if (rptr > wptr && (bcross == 1))
{
data= FIFO[rptr++];
}
else if (rptr <= wptr && (bcross == 0))
{
data=FIFO[rptr++];
}
else if (rptr == wptr && bcross == 1) {
data=FIFO[rptr++];
}
else {
printf( "Read corrupt \n");
printf("FIFO corruption detected \n");
}
if (rptr == MAX)
{
rptr=0;
bcross=0;
}
return data;
}

Output:
Fifo Overflow detected
Fifo Overflow detected
Fifo Overflow detected
data read from the fifo is 0
data read from the fifo is 1
data read from the fifo is 2
data read from the fifo is 3
data read from the fifo is 4
data read from the fifo is 5
data read from the fifo is 6
data read from the fifo is 7
data read from the fifo is 8
data read from the fifo is 9
data read from the fifo is 10
data read from the fifo is 11
data read from the fifo is 12
data read from the fifo is 13
data read from the fifo is 14
data read from the fifo is 15
data read from the fifo is 16
data read from the fifo is 17
data read from the fifo is 18
data read from the fifo is 19
data read from the fifo is 20
data read from the fifo is 21
data read from the fifo is 22
data read from the fifo is 23
data read from the fifo is 24
data read from the fifo is 25
data read from the fifo is 26
data read from the fifo is 27
data read from the fifo is 28
data read from the fifo is 29
Fifo Underrun detected
data read from the fifo is -1
Fifo Underrun detected
data read from the fifo is -1
Fifo Underrun detected
data read from the fifo is -1
data read from the fifo is 0
data read from the fifo is 1
data read from the fifo is 2
data read from the fifo is 3
data read from the fifo is 4
Fifo Underrun detected
data read from the fifo is -1

C++ basic programs

C++ - basics through simple programs

1) Program to illustrate memory allocation for objects

This is a program to illustrate, member functions [non virtual ] member functions are allocated in the code segment and not relative to the object.

#include <iostream.h>
using namespace std;

class corrupt{
int data;
public:
corrupt()
{
data=0;
}
void print()
{
cout<<"Print Function called \n";
// cout<<data;
}
};

int main ()
{
corrupt *p;
p =new corrupt;
p =NULL;
p->print();
}

Uncommenting the bold line would lead to segmentation violation, otherwise the program works fine though we have made object p to NULL. When the line in bold is uncommented obviously the function tries to dereference the this pointer and thus leads to segmentation fault.

Output:
Print Function called

2) Program to illustrate copy constructors

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


class car {

friend ostream & operator<<(ostream &os, car &c);

int wheels;
string model;
int price;
public:
car(int w, char *m, int p)
{
wheels=w;
model=m;
price=p;
}
car (car &c)
{
cout<< "Copy constructor called here\n";
model= "copy of " + c.model;
wheels= c.wheels;
price= c.price;
}
};

ostream & operator<<(ostream &os, car &c)
{
os <<"Car model name :"<<c.model<<endl;
os <<"Car price :"<<c.price<<endl;
os <<"Car wheels :"<<c.wheels<<endl;
return os;
}

void function (car c1, car c2)
{
cout<<c1;
cout<<c2;
}

int main()
{
car c1(4,"VW passat",14000);
car c2(4,"Toyota Yaaris",14000);
cout<<c1<<c2;
function (c1,c2);
}

Output:
Car model name :VW passat
Car price :14000
Car wheels :4
Car model name :Toyota Yaaris
Car price :14000
Car wheels :4
Copy constructor called here
Copy constructor called here
Car model name :copy of VW passat
Car price :14000
Car wheels :4
Car model name :copy of Toyota Yaaris
Car price :14000
Car wheels :4

3) Operator overloading

#include <iostream.h>

class vehicle {
int manucost;
int regn;
int tax;
public:
vehicle (int a, int b, int c)
{
manucost=a;
regn=b;
tax=c;
}
int operator+( vehicle &v1)
{
return (manucost + regn + tax + v1.manucost + v1.regn + v1.tax );
}
};

int main()
{
vehicle v1(10,1,1);
vehicle v2(20,2,2);
int tc= v1+v2;
cout<< "Total cost of the vehicle is :"<<tc<<endl;
}

Output:
Total cost of the vehicle is :36

4) Templates

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

template <class T> class array {
int currIndex;
int MaxElem;
int Size;
class T *p;
public:
array (int c, int m, int s)
{
currIndex=c;
MaxElem=m;
Size=s;
cout << "Constructor template \n";
p = new T [s];
}
arrayprint()
{
for (int i=0;i<=Size;i++)
{
cout<<p[i];
}
}
};

class myClass{
friend ostream & operator << (ostream &, myClass &);
string *p;
public:
myClass()
{
p = new string ("Hello World\n");
cout<<*p;
}
};

ostream& operator << (ostream &os, myClass &my){
os << my.p;
return os;
}

int main( int argc, char * argv[])
{
array<myClass> p(4,5,7);
return 1;
}

Output:

Constructor template
Hello World
Hello World
Hello World
Hello World
Hello World
Hello World
Hello World

5) Using STL containers

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


class Names{
friend ostream & operator << (ostream &, Names &);
int number;
public:
Names(int a)
{
number=a;
}
int display()
{
return number;
}
};

vector <Names>v;

ostream & operator << (ostream &os, Names &name){
os<<name.number;
return os;
}

int main ()
{
// append elements with values 1 to 6
for (int i=1; i<=6; ++i) {
v.push_back(i);
}

for (vector<Names>::iterator it=v.begin(); it!=v.end(); ++it) {
cout<<"Object value :"<<*it<< endl;
}

}

Output:

Object value :1
Object value :2
Object value :3
Object value :4
Object value :5
Object value :6

About me: Typical software engineer working from US. I like to visit places and spend time with friends.

C- Data structures FAQ

1) This program helps illustrates single link list manipulation

#include
#include "malloc.h"

typedef struct node {
int data;
struct node *next;
}node;
node *head;
void createlist (int data);
void destroylist ();
void reverselist (node *child, node *parent);

int main (int argc, char *argv[])
{
int cnt;
int data;
int i;
scanf ("%d", &cnt);
for (i=0;i<=cnt;i++) { scanf("%d",&data); createlist(data); } reverselist(head->next, head);
destroylist();
return 0;
}

void createlist (int data)
{
node *ptr;
node *tmp;
if ((ptr = (node *) malloc (sizeof (node))) == NULL)
{
printf ("Memory allocation failed \n");
exit (-1);
}
ptr->data=data;
if (head == NULL)
head = ptr;
else {
tmp = head;
while (tmp->next != NULL)
tmp = tmp->next;
tmp->next = ptr;
}
}

void destroylist()
{
node *tmp = head;
node *tmp1;
while (tmp != NULL)
{
tmp1 = tmp;
printf("Nodes values %d\n", tmp->data);
tmp = tmp->next;
free (tmp1);
}
}

void reverselist (node *child, node *parent)
{
if ( child != NULL )
{
reverselist(child->next, child);
child->next = parent;
}
else {
head->next = NULL;
head = parent;
}
}

2) Double link list manipulation

#include
#include "malloc.h"

typedef struct node {
int data;
struct node *next;
struct node *prev;
}node;
node *head;
void createlist (int data);
void destroylist ();
void reverselist (node *n);
void insertnode (int data, node *n);
int main (int argc, char *argv[])
{
int cnt;
int data;
int i;
scanf ("%d", &cnt);
for (i=0;i<=cnt;i++) { scanf("%d",&data); createlist(data); } reverselist(head); insertnode(10000, head->next->next);
destroylist();
return 0;
}

void createlist (int data)
{
node *ptr;
node *tmp;
if ((ptr = (node *) malloc (sizeof (node))) == NULL)
{
printf ("Memory allocation failed \n");
exit (-1);
}
ptr->data=data;
ptr->next= NULL;
if (head == NULL)
{
head = ptr;
head->prev = NULL;
}
else {
tmp = head;
while (tmp->next != NULL)
tmp = tmp->next;
tmp->next = ptr;
ptr->prev = tmp;
}
}

void destroylist()
{
node *tmp = head;
node *tmp1;
while (tmp != NULL)
{
tmp1 = tmp;
printf("Nodes values %d\n", tmp->data);
tmp = tmp->next;
free (tmp1);
}
}

void reverselist (node *n)
{
node *tmp;
if ( n->next != NULL )
{
reverselist(n->next);
tmp = n->next;
n->next = n->prev;
n->prev =tmp;
}
else {
head = n;
n->next = n->prev;
n->prev = NULL;
}
}

void insertnode (int data, node *n)
{
node *ptr;
node *tmp;
if ((ptr = (node *) malloc (sizeof (node))) == NULL)
{
printf ("Memory allocation failed \n");
exit (-1);
}
ptr->data=data;
ptr->next=NULL;
ptr->prev=NULL;
if (head == NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
}
else
{
ptr->next=n->next;
ptr->prev=n;
if (ptr->next != NULL)
ptr->next->prev = ptr;
n->next=ptr;
}
}

3) Binary tree

#include

typedef struct node {
int data;
struct node *left;
struct node *right;
}node;
node *root;
void createlist (int );
void mirror (node * );
void display (node *n);
int main (int argc, char *argv[])
{
int data;
int count;
int i;
scanf("%d", &count);
for (i=0;idata = data;
tmp->left = NULL;
tmp->right = NULL;
if (root == NULL)
{
root=tmp;
return;
}
tmp1= &root;
while (*tmp1 != NULL)
{
if ( data < (*tmp1)->data)
tmp1= & (*tmp1)->left;
else
tmp1= & (*tmp1)->right;
}
*tmp1=tmp;
}

void display(node *n)
{
if (n == NULL)
{
return;
}
if (n->left != NULL)
{
display(n->left );
}
printf("Node data is %d\n", n->data);
if (n->right != NULL)
{
display(n->right );
}
}

void mirror(node *n)
{
node *tmp;
if (n == NULL)
return;
else if (n->left != NULL)
{
mirror(n->left);
}
else if (n->right != NULL)
{
mirror(n->right);
}
tmp = n->right;
n->right = n->left;
n->left = tmp;
}

4) State machine

#include
enum STATES {
stateA,
stateB,
stateC,
stateD,
stateE,
stateF
};
int statetransition (int currentState, int input);
int main (int argc, char *argv[])
{
enum STATES inputstate= stateA;
enum STATES currstate;
currstate=statetransition(inputstate, 'a');
printf("Current state is %d\n", currstate);
currstate=statetransition(inputstate, 'b');
printf("Current state is %d\n", currstate);
}
int statetransition (int currentState, int input)
{
int outstate;
switch (input) {
case 'a':
outstate=stateA;
break;
case 'b':
if(currentState == stateA)
outstate=stateB;
else
outstate=stateA;
break;
case 'c':
if(currentState == stateB)
outstate=stateC;
else
outstate=stateA;
break;
case 'd':
if(currentState == stateC)
outstate=stateD;
else
outstate=stateA;
break;
case 'e':
if (currentState == stateD)
outstate=stateE;
else
outstate=stateA;
break;
case 'f':
if (currentState == stateE)
outstate=stateF;
else
outstate=stateA;
break;
default:
outstate=stateA;
break;
}
return outstate;
}

Solaris dbx debugger - is it a bug ?

Today we were trying to attach a process to dbx debugger to check memory leaks and corruption. It was very difficult to figure out what was going on with dbx, most of the times dbx would complain "check -leaks not turned on" though it was turned on or would crash with SIGSEGV.

Tools Version: Studio 09
OS : Solaris 10

To reproduce the problem

setenv LD_AUDIT /rtcaudit.so
RUN THE APPLICATION
unsetenv LD_AUDIT

dbx a.out
dbx> check -all
dbx> attach
dbx> showleaks

However the following steps fixed the problem

setenv LD_AUDIT /rtcaudit.so
RUN THE APPLICATION
unsetenv LD_AUDIT

dbx - PID
dbx> check -all
dbx> cont
dbx> Ctrl-C
dbx> showleaks

In either ways its difficult to set LD_AUDIT because some of the application we debug may crash. So the better solution would be to prelink libumem.a which is a slab based alocator with REDZONEs. These REDZONEs make it easy for the detection of memory corruption. For a detailed usage of libumem to determine memory related issues please see the following URL

http://access1.sun.com/techarticles/libumem.html