C# Corner Delhi Chapter "How to Crack the Coding Interview": Discussion of Test

Structs in the C language

Why can't we have a situation as in the following:

struct Node{
   int data;
   Node link;
};

Memory allocation of objects of type Node will require infinite memory because of the nested definition. But the same problem will not exist if a link field inside the struct is a Node* (a pointer to a Node, not a Node). Hence the following is allowed.

struct Node{
   int data;
   Node* link;
};

This forms the basis of data structures allocated on the heap (linked list and Binary trees).

Programs covered

The following is a function that traverses a linked list in a forward direction:

void printList(Node* head)
{
   while(head->link != NULL)
   {
      printf("%d", head->data);
      head = head->link;
   }
}

The following is a recursive version of the preceding code:

void printList(Node* head)
{
   if(head == NULL){ return ; }

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

   printList(head->link);
}

We said that a recursive function takes more time and more memory than the non-recursive counterpart and hence is never recommended. But in some cases (like implementing a Binary Tree and Graph algorithms) it is very convenient to write recursive algorithms because the problem can be visualized in terms of sub-problems.

For example, consider the problem of printing the list in reverse order. The recursive code is very easy, we just need to change the function from tail recursion to head recursion:

void printList(Node* head)
{
   if(head == NULL){ return ; }

   printList(head->link);

   printf("%d", head->data);
}

But if we want to write a non-recursive function for it then it will be a challenge.

Question: write a non-recursive function that will print the list in reverse order (last node to first node).

Searching in an Array

Given an Array of numbers a0, a1, a2, …. an and a number x. Write a function that will return i, such that:

ai == x

If x is not in the Array, then return -1 (which means “Not Found”).

Signature of the function

int search(int *arr, int n, int x);

Linear Search

• Start the search from the first element and continue until you get the element (or reach end of the array).
  
  Code:
  

  /** Function searches data in an array arr of size n.
  * If finds data in arr, then it returns the index of first
  * occurrence of array.
  * Else returns -1 to indicate that data is not found in array. */
  int linearSearch(int * arr, int n , int data){
     for(int i=0; i<n; i++){
        if(arr[i] == data)
        return i;
     }
     return -1;
  }

  Time taken by the function.
  
  
• Best Case: O(1): When the element is found at the first index.
  
  
• Worst Case: O(n): If an element is not found in the array at all.
  
  
• Avg Case: O(n): If found at the first position then 1 comparison, if at the second position then 2 comparisons and so on. If found at the last position then n comparisons.

Linear Search Facts

• Array may not be sorted.
  
  
• The later we find the element in the array the more time will it take.
  
  
• The performance improves if the value to be searched for is more likely to be near the start of the array than toward its end.
  
  
• If you are ordering the array then place values that are more likely to be searched than others toward the beginning of the array.
  
  
• If the array size is small then use a linear search.
  
  
• When the list items are arranged in order of decreasing probability and these probabilities are geometrically distributed, the cost of the linear search is only O(1), which is faster than for a Binary Search.
  
  
• Can be applied to linked lists or other lists that do not have an index (for example File).

Binary Search Algorithm

• Array must be sorted.
  
  
• Dichotomic Divide and Conquer Algorithm.
  
  
• Halves the number of elements to be searched with each iteration.
  
  
• If data == Middle element of array.
  
  
  • Element found, return the middle index.
    
    
• Else
  
  
  • If data < Middle element of array.
    
    
    • Repeat the algorithm for the left half of the array.
      
      
  • Else
    
    
    • Repeat the algorithm for the right half of the array.
      
      
• If there is no remaining array to be searched then not found.

Code

/** Non-Recursive Function */

int bSearch(int * arr, int n, int data){
    int l=0, h=n-1, m;

    while(l <= h){
        m = (l + h) / 2;

        if(arr[m] == data)
            return m;               // FOUND.
        else if(arr[m] < data)
            l = m + 1;
        else
            h = m – 1;
    }
    return -1;                  // NOT FOUND
}

/** Recursive Function */

int bSearch(int * arr, int l , int h, int data){

    if(l > h || arr[l] > data || arr[h] < data)
        return -1;          // NOT FOUND.
    else
    {
        int m = (l+h)/2;

        if(arr[m] == data)
            return m;       // FOUND.
        else if (arr[m]<data)
            return bSearch(arr, m+1, h, data)
        else
            return bSearch(arr, l, m-1, data);
    }
}

Time Complexity

Best case: O( 1 ) Found at the middle of an entire array

Worst case: O( lg (n) ) not found

Average case: O( lg (n) )

Space Complexity

Non-Recursive: O(1)

Recursive: O( lg(n) )



• Example of applicability: dictionary, telephone directory.
  
  
• A Binary Search Tree follows a similar methodology. Just that the tree may not be perfectly balanced (In an array, mid actually divides the array in two equal halves).

Questions Discussed

Q1. A sorted array is rotated around a pivot. For example:

• Input Array
• Rotated Array

Write code to find the pivot position of the rotation of the array (above: 2).

Q2. Write a function to search in a pivoted array (the pivot is given).

Q3. Given an array of numbers and a number x, write a function to search for two elements in the array, whose sum is x.

Q4. Given an array of integers where each number is repeated an even number of times except for one integer that is repeating an odd number of times. Find that number.

Q5. Given an array of integers of size N-1 where all the integers are unique and are in the range of 1 to N. One integer is missing, write the code to find the missing integer.

Assignment Questions

1. Write code to search in a matrix sorted by row and by column.
   
   
2. Write code to search for an element in a Binary Search Tree.