Technical Interview Screen

1. Which is better - singly linked list or doubly linked list? What are the pros and cons of using each?
   In a Singly Linked List each node has pointer just to the next node and hence can be traversed  in only one direction whereas in a Doubly Linked List, each node has pointers to both previous and next nodes , hence can be traversed in both directions.While this kind of traversal makes deletion of nodes easier from a doubly linked list , because we now don’t have to traverse from head and keep track of previous node but it consumes more memory since it now has to store two pointers as compared to one in case of Singly Linked List.

function remove_node_singlyLinkedList(head, node)
   tempnode = head
   while (tempnode->next != node)
       tempnode = tempnode->next
   tempnode->next = node->next
end function

         Time Complexity - O(N)

function remove_node_doublyLinkedList(node)
   node->prev->next = node->next
   node->next->prev = node->prev
end function

Time Complexity - O(1)

2. What's the difference between Managed code and Native code? Give examples of each you have worked on.
    1) Managed code runs under CLR whereas native code does not run under CLR.
   2) Managed code takes advantages of memory management, security      
   and  threading services CLR provides,whereas these are missing for native
   code that directly runs on the machine.   
   3)The managed code is the one generated by C# and other .NET language compilers (IL) and gets finally converted to native code by JIT.The code in languages prior to .NET like VC++ get converted directly to native code and runs on the machine.eg COM components

3. What is thread safe code?  Give an example of times you’ve used thread safe code.
   Thread Safe code is one which runs in a manner that when multiple threads are running simultaneously and are in need of using shared memory, they do not step onto each other or in other words  access the shared memory exclusively.

Coding Questions

Please answer one or both of the following questions. Please do not use existing class libraries in your answer(s):

1. Write me a function that receives three integer inputs for the lengths of the sides of a triangle and returns one of four values to determine the triangle type (1=scalene, 2=isosceles, 3=equilateral, 4=error). Generate test cases for the function assuming another developer coded the function

int DetermineTriangleType(int firstSide, int secondSide, int thirdSide)

{

    if ((firstSide <=0) || (secondSide<=0) || (thirdSide<=0)) return 4;

    if ((firstSide==secondSide) && (secondSide==thirdSide) && (thirdSide==firstSide))

        return 3;

    if ((firstSide==secondSide) || (secondSide==thirdSide) || (thirdSide==firstSide))   

        return 2;

    if ((firstSide!=secondSide) && (secondSide!=thirdSide) && (thirdSide!=firstSide))

               return 3;

    return 4;

}

DetermineTriangleType(0,0,0)

DetermineTriangleType(-1,-2,-3)

DetermineTriangleType(1,0,2)

DetermineTriangleType(1,0,-2)

DetermineTriangleType(4,5,6)

DetermineTriangleType(4,4,2)

DetermineTriangleType(1,2,2)
DetermineTriangleType(1,3,1)

DetermineTriangleType(7,7,7)

2. Implement a circular queue of integers of user-specified size using a simple array. Provide routines to initialize(), enqueue() and dequeue() the queue. Make it thread safe.

class CircularQueue

{

int[] Queue;

int Head;

int Tail;

public CircularQueue(int size)

{

    Queue= new int [size];

    Head= -1;

    Tail= -1;

}

void enqueue(int newValue)

{

int newIndex=next(Tail);   

if (newIndex==Head) throw new ApplicationException(“Queue full”);

    Tail=newIndex;

   

Queue[Tail]=newValue;

    if (Head==-1) Head =0;

}

int dequeue()

{

          if (Head == -1) throw new ApplicationException(“Queue is empty”);

       int val= Queue[Head];

       Queue[Head] = 0;  //default value

       if (Head == Tail)

       {

           Head = Tail = -1;

       }

       else

       {

           Head = next(Head);

       }

       return val;

}

int  next(int index)

{

    return (index + 1) % Queue.Length;

}

              }