Find an Item in a Sorted Array with Shifted Elements

Problem: You are given a sorted array with shifted elements. Elements can be shifted to the left or right by 'i' number of places. The sign of 'i' denotes the direction of the shift. For positive 'i' direction of shift is right and left for negative 'i'.

For example, consider the sorted array 2, 3, 4, 8, 10, 11. A shift of 3 places to the right would be denoted by i=2 and the shifted array would look like this: 10, 11, 2, 3, 4, 8,

For i=-2, the shifted array would look like: 4, 8, 10, 11, 2, 3.



Write code to find if a given number is present in this array.

Solution: The brute force method to search all elements in the array would yield an O(n) solution, so obviously that's not the best approach. We are not leveraging the sorted nature of the array in this case.

Now, how can we leverage the sorted nature of the array? Let assume that 'i' was 0. In that case the array would be sorted and not shifted at all (0 shift). Whats the fastest way to search in a sorted array? Binary Search! We can split the array in 2 halves and do a recursive search in one of the halves until we find the number we are looking for ( or not, if its not in the array ). This approach has a running time of O(log n), which is obviously better than n.

But, the fact that the array is shifted by 'i' number of elements complicates things a little bit. Now, instead of splitting the array in equal halves, we split the array at the shift index and do a recursive binary search. There are issues we need to tackle when the shift is greater than the length of the array or if the shift is negative. I guess the code below will make much more sense than my description of the solution.

Code: We will assume that we are provided with a method below that does binary search for us and won't bother implementing it here.

// myArray is the input array
// startIndex and endIndex are the indexes in the 
// array where the binary search starts and ends
// The method returns the index of the searchVal 
// if found in the array, else it returns -1

int BinarySearch(int[] myArray, int startIndex, int endIndex, int searchVal);


// this method will return the index of the searchVal 
// if found, else it return -1
int SearchElement(int[] myArray, int shift, int searchVal)
{
   // to take care of scenarios where the shift is more 
   // than the length of the array
   shift = shift % myArray.Length; 
   
   // -ve shift can be seen as positive shift equal to 
   // the length of the array - ( -ve shift) 
   if (shift < 0)
       shift = myArray.Length + shift;

   if(myArray[shift] <= searchVal &&  
      myArray[myArray.Length - 1] >= searchVal)
   {
      return BinarySearch(myArray, shift, myArray.Length - 1, searchVal);
   }
   else if(myArray[0] <= searchVal && 
           myArray[shift - 1] >= searchVal)
   {
      return BinarySearch(myArray, 0, shift-1, searchVal);
   }
   return -1;
}

Fibonacci Sequence Dynamic Programming

Problem: Write the code for nth Fibonacci number.

Solution: There are basically two approaches to solving the Fibonacci problem. Lets looks at the definition of Fibonacci series first.

The Fibonacci series is defined as follows

F(n) = 0 for n = 0
       1 for n = 1
       F(n-1) + F(n-2) for n > 1

If we translate that to the C language we get:

int RecursiveFibonacci(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
    return RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2);
}

Now, whats the running time of the above program. It's horrible!! It's exponential. Why? We have a lot of duplicate work being done on each recursive call.

Typically when you are doing duplicate work, Dynamic Programming can come to rescue. Now, I don't want to go into too much detail on dynamic programming, but you have 2 approaches to Dynamic Programming. One is the bottom up approach and the second is called the top down approach. Calculating F(n) given F(n-1) would be a bottom up approach and calculating F(n) by recursively calling F(n-1) and F(n-2) would be top down. For a thorough treatment of dynamic programming see a Algorithms text or this wikipedia entry.

We can improve the above RecursiveFibonacci function by caching results of previous calculations. Doing this greatly reduces the number of recursive calls and improves the program efficiency. This is an example of top down dynamic programming.

int RecursiveFibonacci(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
   
    if(cache[n] == null)
      cache[n] = RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2);
    return cache[n];
}

Now lets look at the bottom up dynamic programming approach. For a given n we would need to have F(n-1), F(n-2), F(n-3) ... F(0) already solved. In this case we'll start at the bottom and work our way up.

int GetFibonacci(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
   
    last1 = 0;
    last2 = 1;   
    ans = 0;

    for(int i=0; i < n-1; i++)
    {
       ans = last1 + last2;
       last1 = last2;
       last2 = ans; 
    }

    return ans;
}

We could have used a cache like we used in the top down approach, but all we really need is the last 2 results. We can get away with just using 2 variables. This is also an iterative solution which is better compared to the recursive one because of the absence of the stack overhead involved in recursive calls.

Microsoft Developer Interview Questions

---------------------------- Interview 1 ---------------------------------
- Why is a database useful? Why not use a file instead?
- What are stored procedures and what are the benefits?
- Write a program to get the nth Fibonacci number
- Discussion about patterns and practices
- What is database normalization? When would you use it and when would you not? What data can be left denormalized in a database? What are the benefits or drawbacks of normalization?
- Discussion on asp.net request processing and page life cycle
- Discussion on asp.net view state and session state management options. What is preferred?
- Write a program to merge two arrays while removing duplicate elements
- Write a program to find acronyms ("Interview Question" becomes "I.Q.")
- Why did you choose the C language for the above?
- What do you do at work when you don't have work?
- What was the most challenging technical problem you solved recently?
- Design discussion on web services on how to build scalable web services
- Discussion about concepts of threading and what are the threading options available in .NET
- Why does the UI get unresponsive when running a long operation on a single thread?
- Coding Question: You are given a sorted array but the elements are shifted to the left or right by 'i' number of places. Write code to find if a given number is present in this array.
- Coding Question: Write a program to merge two sorted arrays. First array has extra space at the end to accommodate the second array.
- Why didn't you apply to Microsoft yet?
- Why should I hire you?
------------------------- Interview 2 ---------------------------------
- How do you resolve Asp.net view-state encryption problems on server farm?
- How many indexes for a query from a web page having 10 search fields?
- How do you debug a performance issue with a web page?
- What are the pros and cons of ADO.NET Transactions vs Transactions within a stored procedure.
- When do you call your code complete?
- What test cases do you put in your unit tests?
- What is a star schema in the data warehousing world?
- Write code to print a 2 dimensional matrix in spiral sequence
- Write code to remove characters present in string S1 from string S2.
- Discussion about Storing log file (10 Meg) in database vs on the file system. What are pro and cons of each approach?
- What steps are necessary to protect payment or user data in an e-commerce application?
- Write a hashing function for a hashtable that can contain 1 million rows.
- Design Question: Given a tree control in a Windows User Interface. How would you read information from a database and display it in the tree control. The tree has arbitrary levels and each level can contain arbitrary number of items in it.
- Design a SQL table to store the folder and file system hierarchy. This table has to also support search for the file/folder name.

Linked List: Merged List Problem

Problem: There are 2 singly linked lists (list1 and list2) that merge at one of the nodes and share the nodes there onwards. The goal is to find the node where these linked lists merge or join.

Solution 1:

1. Find length of both linked lists, say len1 and len2.
2. Make current pointers for both lists equidistant from the common node. If one of the lists is longer we need to advance its current pointer by len1 - len2 (assuming list1 is longer). Now both current pointers should be equidistant from the common node. If both lists are same len, do nothing in step 2.
3. Traverse both lists simultaneously while comparing the current pointers for equality. At ant point if they are equal we have found the first common node. If we reach the end of the lists without find the common node then the lists do not overlap.

Solution 2 : This solution only tells if the lists are joined, not where though. Interesting technique nevertheless.

1. Update the tail of one of the lists to point to the head of the other.
2. Now use the linked list cycle/loop detection technique to find if there is a loop in the combined list.
3. If there is a loop then the list have node(s) in common, otherwise they don't.

Linked List: Reverse

Question: Given the head pointer to a singly linked list reverse the list.

Solution 1: Recursive Approach - We can recursively traverse the linked list till we arrive at the last but one node. We then set the next pointer of the last node to point to the current node. We keep reversing the links as we unwind the recursive calls.

Code:

// Takes a pointer to the head node of a singly linked list
// and returns the new head pointer for the reversed list
Node * Reverse(Node * head)
{
   Node *newHead = Recursive_Reverse(head);
   head->next = NULL;      // since the first node is the last node now
                           // we need to set it's next pointer to NULL
   return newHead;
}

Node * Recursive_Reverse(Node * node)
{
   Node *nextNode = node->next;
   if(nextNode == NULL)       // if the list has only one node
   {                          // we don't need to reverse it
       return node;
   }

   if(nextNode->next == NULL) // if nextNode is the last node we terminate the recursion
   {
       nextNode->next = node; // reverse the link
       return nextNode;       // return the ptr to the last node
                              // this will become the new head pointer
   }
   Node *head = Reverse(node->next); //recursively call Reverse
   nextNode->next = node;     // reverse the link
   return head;             
}

Solution 2: We can also reverse the singly linked list using an iterative approach. For some this approach can be easier to understand. Basically, we maintain 3 pointers (prevNode, currentNode, and nextNode). At each step we save the next of the currentNode in the nextNode ptr and reverse the link. After this, we advance the previous and current pointers.

Code:

//Takes a pointer to the head of a linked list
//Returns the pointer to the new head (old tail) node
Node * Iterative_Reverse(Node *head)
{
   Node *prevNode = NULL;      //pointer to the previous node
   Node *nextNode = NULL;      //pointer to the next node
   Node *currentNode = head;   //pointer to the current node
   while(currentNode)
   {
       nextNode = currentNode->next; //save the pointer to the next node
                                     //otherwise we will lose it as we
                                     // overwrite it in the next step
       currentNode->next = prevNode; //reverse the link
      
       prevNode = currentNode; //set the current node as the previous node
                               //for the next iteration
       currentNode = nextNode; //advance the current pointer
   }
   return prevNode;
}

Linked List: Delete Node

Question: You are given a pointer to a node in a singly linked list. The head pointer is not available. Your task is to delete the specified node.

Solution: Typically, deleting a node from a singly linked list requires us to have the pointer to the node before the node to be deleted. We need this previous pointer so we can set it's Next pointer to the node after the specified node to be deleted. In this problem since we do not have the head pointer, we cannot walk the list and get the previous pointer.

We need to start thinking about what information does a linked list node have. Typically it has one or more data variables and a Next pointer that points to the next node in the linked list. If we were to overwrite the data in the specified node to be deleted from the next node in the list and delete this next node instead of the specified node, we would have effectively deleted the node. Technically, we don't delete the specified node but delete the next node after we copy data from it.

Note: This approach does not work in the case where the specified node to be deleted is the last node in the linked list.

Code: typedef struct _node

{
 int i;
 struct _node *next;
} Node;

void DeleteNode(Node *deleteThisNode)
{
  if(deleteThisNode->next != null)                  //only if the specified node is not the last node of the list
                                                    // this approach does not work in that case
  {
      deleteThisNode->i = deleteThisNode->next->i;  //copy data from the next node
      Node * freeThis = deleteThisNode->next;       //save the ptr to the next node, so we can free it
      deleteThisNode->next = deleteThisNode->next->next;  //point the Next pointer to the node after deleteThisNode->next
      free(freeThis);                               //don't forget to free memory
  }
}

Linked List: Find the middle element

Question: Given a singly linked list, find the node in the middle.

Solution 1: Walk the linked list to find the length of the list. Lets say n is the length of the list. Walk the list again upto ⌊ n/2 ⌋.

Solution 2: Use two pointers. Move one pointer at twice the speed of the second. When the 1st pointer reaches the end of the list, the 2nd pointer will be pointing to the middle node. Note: If the list has even number of nodes, the middle node will be floor of ⌊ n/2 ⌋.

Code:

Node * FindMiddle(Node *listHead)
{
  Node *ptr1, *ptr2;  // we need 2 pointers
  ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially

  int i=0;

  while(ptr1->next != NULL) // keep looping until we reach the tail
                              // (next will be NULL for the last node)
  {
      if(i == 0)
      {
          ptr1 = ptr1->next; //increment only the 1st pointer
          i=1;
      }
      else if( i == 1)
      {
          ptr1 = ptr1->next; //increment both pointers
          ptr2 = ptr2->next;
          i = 0;
      }
  }
  return ptr2;        //now return the ptr2 which points to the middle node
}

Linked List: Find n-th element from the tail

Question: Given a singly linked list find the n-th node from the back.

Solution 1: Reverse the linked list and select the n-th node from the head of the linked list.

Solution 2: Maintain 2 pointers n nodes apart. When the 1st pointer reaches the tail, the second pointer will be pointing to the desired node.

Notes: Both solutions take O(n) time but Solution 2 is more elegant.

Code:

//define the list node
typedef struct _node
{
 int i;
 struct _node *next;
} Node;

Node * FindNthFromBack(Node *listHead, int n)
{
    Node *ptr1, *ptr2;  // we need 2 pointers
    ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially

    while(ptr1->next != NULL) // keep looping until we reach the tail (next will be NULL for the last node)
    {
        if(n > 0)
        {
            ptr1 = ptr1->next; //increment only the 1st pointer
            n--;
        }
        else
        {
            ptr1 = ptr1->next; //increment both pointers
            ptr2 = ptr2->next;
        }
    }
    return ptr2;    //now return the ptr2 which points to the nth node from the tail
}