Question : What is the optimal algorithm to find the minimum element given a rotated sorted array of integers? A rotated sorted array of integers is the output array of a rotation operation performed on a sorted array. Eg:  3 5 6 1 2

Answer : One way to solve the above problem in linear time is to get the minima from the array using difference array and then finding the sign change from positive to negative.This will solve the problem in O(n) time.

/*
* Solution for O(n) time complexity
*/
int getRotationPoint(int *arr,int length)
{
    int *diff=(int *)malloc(sizeof(int)*length-1);
    if(length==1)
    return 0;
    assert(length>=2);
    for(int i=1;i0)?PS:NG;
    for(int i=0;i0)?PS:NG;
        if((sg==NG)&&(sign==PS))
        {
            index=i;
            break;
        }
        sign=sg;
    }
    return index+1;
}

However for an even tighter bound we modify the binary search algorithm and use it.We also could use the fact that for a sorted array, if the array were circular the index of the smallest would be the index after the largest element.Hence this solution is a O(log n) solution.

/*
* Solution for O(nlogn) time
*/
int getRotationPointBi(int *arr,int length)
{
    int first=0;
    int last=length-1;
    int middle=(last+first)/2;
    while(last>first)
    {
        middle=(last+first)/2;
        if(arr[first]>=arr[middle])
        last=middle;
        else if(arr[middle]>=arr[last])
        first=middle;
    }
    return middle+1;
}

Question : In a BST to every element add sum of elements greater than it.

Answer: The first thing is to notice that on doing this the resulting tree would be the reverse of the binary search tree. Implementing this  you should notice that the inorder travesal prints the elements in increasing order.Hence we need to modify the inorder traversal a bit to do this.Here is a sample C++/C code for insert and inorder for a BST.

#include<iostream>
#include<cstdlib>

using namespace std;

struct node
{
    int data;
    struct node *parent;
    struct node *left;
    struct node *right;
}*root;

typedef struct node node;

/**
*Makes a new node from the integer
*value and returns a pointer to the
*new created node
*/
node* makeNode(int num)
{
    node *temp=(node*)malloc(sizeof(node));
    temp->data=num;
    temp->right=NULL;
    temp->left=NULL;
    return temp;
}

/**
 * Inserting a node in a BST
 */
void insert(int num,node *T)
{
    if(T==NULL)
    root=makeNode(num);
    else
    {
        if(T->data>num)
        {
            if(T->left==NULL)
            T->left=makeNode(num);
            else
            insert(num,T->left);
        }
        else
        {
            if(T->right==NULL)
            T->right=makeNode(num);
            else
            insert(num,T->right);
        }
    }
}

/**
*Inorder traversal of the tree
*/
void inorder(node* T)
{
    if(T!=NULL)
    {
        inorder(T->left);
        cout<<T->data<<" ";
        inorder(T->right);
    }
}

Now to add the elements which are greater than a particular node we need to reverse the inorder by accessing the bigger elements i.e. right first and then the left. On accessing the right add the data to the data already collected and then change the node value accordingly.Hope you better understand by the code.

void chorder(node *T,int *data)
{
    if(T!=NULL)
    {
        chorder(T->right,data);
        *data+=T->data;
        T->data=*data;
        chorder(T->left,data);
    }
}

Notice that that data needs to be reference so that after being updated it is assigned to the other nodes.

PROBLEM : The problem is to rotate a matrix by 90. Fairly easy , just focus on double pointers if you are using C/C++ and make it for Clock Wise and anti clockwise.The code is as follows:

#include<iostream>
#include<cstdlib>
#define CL 0
#define ACL 1

using namespace std;

void printMatrix(int **matrix,int width,int height)
{
  for(int i=0;i<width;i++)
    {
      for(int j=0;j<height;j++)
 cout<<*(*(matrix+i)+j)<<" ";
      cout<<endl;
    }
}

void matrixRot90(int **matrix,int width,int height,int dir)
{
  //dir 0 for CL and 1 for ACL
  if(dir==CL)
    {
      for(int j=0;j<height;j++)
 {
   for(int i=width-1;i>=0;i--)
     cout<<*(*(matrix+i)+j)<<" ";
   cout<<endl;
 }
    }
  else
    {
      for(int j=height-1;j>=0;j--)
 {
   for(int i=0;i<width;i++)
     cout<<*(*(matrix+i)+j)<<" ";
   cout<<endl;
 }
    }
}

int main(void)
{
  int width,height;
  cin>>width>>height;
  int **matrix=(int**)malloc(sizeof(int**)*width);
  for(int i=0;i<width;i++)
    *(matrix+i)=(int*)malloc(sizeof(int)*height);
  for(int i=0;i<width;i++)
    for(int j=0;j<height;j++)
      cin>>*(*(matrix+i)+j);
  cout<<"Original Matrix::";
  printMatrix(matrix,width,height);
  cout<<"After clockwise rotation ::\n\n";
  matrixRot90(matrix,width,height,CL);
  cout<<"After anticlockwise rotation ::\n\n";
  matrixRot90(matrix,width,height,ACL);
  return 0;
}

PROBLEM : Given a directed graph check whether the graph contains a cycle or not.

SOLUTION : In a graph containing a cycle suppose vi,...vk are the vertices that constitute the cycle and suppose that the backedge is from vk to vi then on applying dfs to the graph "when the dfs covers the edge from vk to vi then vi must have already been visited." vi will already be in the recursion stack when the edge will be covered.Hence we know a cycle is present.Thus the given graph will not be cyclic.

Thus for each node visited earlier we need to store the recursion stack to tell whether a edge points to a node already in the recursion stack.Then it would be a back edge.In this way this algorithm can be modified to find in a graph:

• The number of back edges
• The components i.e. the trees in a forest
• The number of cycles = number of back edges .. etc

The cpp code for the following :

#include<iostream>
#include<list>

using namespace std;

class Graph
{
    int V; //number of vertices
    list<int> *adj; //pointer to array containing adjacency lists
    bool isCyclicUtil(int v,bool visited[],bool *rs);

    public:
        Graph(int v);
        void addEdge(int v,int w);
        bool isCyclic();
};

Graph::Graph(int v)
{
    this->V=v;
    adj=new list<int>[V];
}

void Graph::addEdge(int v,int w)
{
    adj[v].push_back(w);
}

bool Graph::isCyclicUtil(int v,bool visited[],bool *rs)
{
    if(visited[v]==false)
    {
        visited[v]=true;
        rs[v]=true;
        list<int>::iterator i;
        for(i=adj[v].begin();i!=adj[v].end();++i)
        {
            if(!visited[*i] && isCyclicUtil(*i,visited,rs))
            return true;
            else if(rs[*i])
            return true;
        }
    }
    rs[v]=false;
    return false;
}

bool Graph::isCyclic()
{
    bool *visited=new bool[V];
    bool *rs=new bool[V];
    for(int i=0;i<V;i++)
    {
        visited[i]=false;
        rs[i]=false;
    }
    for(int i=0;i<V;i++)
    if(isCyclicUtil(i,visited,rs))
        return true;
    return false;
}

int main()
{
    Graph g(4);
    g.addEdge(0,1);
    g.addEdge(0,2);
    g.addEdge(1,2);
    g.addEdge(2,0);
    g.addEdge(2,3);
    g.addEdge(3,3);

    if(g.isCyclic())
    cout<<"Graph contains a cycle"<<endl;
    else
    cout<<"Graph doesnot contain a cycle"<<endl;
    return 0;
}

Given a binary tree, print all the nodes in the Zigzag order.For eg.


 
 For the given tree the answer should be : 1324567

Answer:This question is fairly simple if we keep a flag to decide whether we want to print it in normal order or to print it in reverse order.The pseudo algorithm for the implementation of this is as follows:

def print(Queue Q,int order)
{
    newQueue=new Queue();
    while(iterate over Q)
    {
      node=Q[iter];
      newQueue.enqueue(node.rightchild());
      newQueue.enqueue(node.leftchild());
    }
    if(order==0)
    Q.reverse();
    while(Q.size()>0)
    print(Q.dequeue());
    if(newQueue.size()>0)
    print(newQueue,~order);
}

You should also start with:

Q.enqueue(Tree.root);
print(Q,0);

So you always used sqrt() function to find out the square roots of a number .. So what if i ask you to write a function that will display the square root without using the math library functions.. STUNNED ?
       Well lets try to figure out what we do in finding the square root of a number.So how do we start.The first thing that comes into my mind is that square root can be any real value less than the given number.Hence there are infinite possibilities and we cannot loop through to check if multiplying the number to itself will give us the number.That would be a never ending process and we do not know the increment value.So what do we do now ?
       Ok.What if we take any number as the initial guess and start.When we find the square of the number is greater than the number than we know we have to select a number that is less than the current and if it is smaller than choose a greater number.In this way after a fixed number of iterations we will eventually reach near to the square root.This method is also called as Approximation by Bisection.

def sqrt(x,epsilon):
    assert((x>0)&&(epsilon>0)),"Initial Conditions not met"
    low=0
    high=x
    val=(low+high)/2
    count=1
    while val**2-x>epsilon and crt<100:
        crt+=1
        if(val**2>x)
            high=val
        else:
            low=val
        val=(high+low)/2
   return val

However even this cannot find to much approximation and what if in count number of times it doesn't reach the required value.For this we have another method called the Newtons method where we use the initial guess to make a better guess.It works like taking 1 as the initial guess.Then

1+(2/1)=3  3/2=1.5
1.5+(2/1.5)=2.83  2.83/2=1.416 ~ 1.414 sqrt of 2

Hence using Newtons Method of Approximation we get:

float sqrt(float x)
{
 float ng;
 float g=x/2;
 float d=(g*g)-x;
 d=(d>0)?d:-d;
 while(d>EPS)
 {
  ng=(g+(x/g))*0.5;
  g=ng;
  d=(g*g)-x;
  d=(d>0)?d:-d;
  //cout<<g<<endl;
 }
 return g;
}

Credits : Excerpt taken from here

NACHOS was rewritten in JAVA and thus it is now platform independent and can run on any machine ( provided jre and jdk are installed on it , ofcourse ).

So here's how to install it in Ubuntu ( theres nothing which can be called as "Installation" , its juz copying and pasting ! )

So first you need to get this Nachos-java.tar.gz file from here.

Just "untar" it in your home folder by :

tar -xf nachos-java.tar.gz

Now you'll get a folder named nachos with various files in it . ( make sure you paste this folder in your home directory )

You need to grant executable permission to $HOME/nachos/bin/nachos file
To do this :
chmod  777  $HOME/nachos/bin/nachos

Next thing , download the mips.x86-linux.xgcc.tar.gz from here.

Untar this file also in your home directory :

tar -xf  mips.x86-linux.xgcc.tar.gz

Okey , now we need to edit some configuration files , here's how :

• The nachos/test/Makefile ,  open this file with gedit and add the following lines just after the comments at the top :

        ARCHDIR = $HOME/mips.x86-linux.xgcc  
        
        Or just download this edited Makefile and replace the original one.

• The .profile file in your home directory (its hidden !), editing it wrongly can lead to troubles , better download this edited .profile and replace the original one. 

And with this we must be done . Now goto nachos/proj1/ and run :

make 

this compiles the BLAHBLAH.java files to BLAHBLAH.class files and stuff .

nachos

This runs the nachOS !

If you see an output like this shown below , you're done !

For creating processes in Linux we need to use the library available in Unix unistd.h . The normal process for creating a child process is as follows:

#include<stdio.h>
#inlcude<unistd.h>
int main()
{
      pid_t pid;   //the process id
      if(pid=fork()<0)
      {
          printf("Failed to create the childd process\n");
          exit(0);
       }
      if(pid==0)
       {
           //work to be done by the parent process
        }
      else
       {
           //the child process here
        }
     return 0;
}

To find out how much over overhead does this cost to the system let us create multiple child processes.This is usually done this way:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<unistd.h>
#include<assert.h>
#define NUM_PROCESSES 100

struct timeval t1,t2;

int main()
{
      pid_t pid[NUM_PROCESSES];
      int i;
      //clock_t start,stop;
      //double t=0.0;
      //assert((start=clock())!=-1);
      gettimeofday(&t1,NULL);
      for(i=0;i<NUM_PROCESSES;i++)
      {
         if((pid[i]=fork())<0)
       {
         perror("fork error\n");
       }
     else if(pid[i]==0)
       {
         //do work with the child
         printf ("[log]Created child process number:%d\n",i);
         exit(0);
       }
      }
      int status;
      pid_t rstatus;
      int n=NUM_PROCESSES;
      while(n>0)
    {
      rstatus=wait(&status);
      --n;
    }
      //stop=clock();
      //t=(double)(stop-start);
      //printf("Time taken ::%f\n",t);
      gettimeofday(&t2,NULL);
      printf("---------------time taken is::%ld----------------\n",t2.tv_usec-t1.tv_usec);
      return 0;
}
So we calculated the system time taken for creating 10 processes was : In micro seconds the total amount of time taken was about 15,441.To compare this to thread creation process we wrote a program with same number of threads as the number of processes i.e. 100 .Again we use the gettimeofday function to get the time taken for spawning the threads.The program for thread is as follows:

#include<stdio.h>
#include<unistd.h>
#include<stdlib.h>
#include<pthread.h>
#include<time.h>
#include<assert.h>
#define NUM_THREADS 100

struct timeval t1,t2;

void *PrintCreated(void *threadId)
{
  long tid;
  tid=(long)threadId;
  printf("[log]Created thread with thread id::%ld\n",tid);
  pthread_exit(NULL);
}

int main()
{
  pthread_t threads[NUM_THREADS];
  int rc;
  long t;
  /*clock_t start,stop;
  double tt=0.0;
  assert((start=clock())!=-1);*/
  gettimeofday(&t1,NULL);
  for(t=0;t<NUM_THREADS;t++)
    {
      //printf ("[log]Creating thread %ld\n",t);
      rc=pthread_create(&threads[t],NULL,PrintCreated,(void *)t);
      if(rc){
    perror("Error creating thread\n");
      }
    }
  /*stop=clock();
  tt=(double)(stop-start);
  printf("Cpu time taken:%f\n",tt);*/
  gettimeofday(&t2,NULL);
  printf("--------------time taken :: %ld----------------\n",t2.tv_usec-t1.tv_usec);
  pthread_exit(NULL);
}

The time taken for generating NUM_THREADS was 9453 milliseconds.Hence spawning of threads is 1.63 times faster than spawning of processes because in creating threads we donot need to create the data space and other things because threads share the data.

LINK :: Question

Required Concepts : Partial Difference

Explanation : A number n will be a possible answer if the number of people having n in their range is exactly n (Byteknights always tell truth and knaves lie ). Therefore for each a and b input we need to increment its value by 1 so that in the end we have an array that represents how many people have told element i to be in their range . Let this array be KNUM, then element i can be a byteknight if KNUM[i]=i

         Instead we store a partial difference array with diff[i]=knight[i]-knight[i-1] . Thus for each a,b we need to increase diff[a] and decrease diff[b+1] for ith entry.

Thus ,

                                      KNUM[i]=diff[0]+diff[1]...diff[i]

If every n is a value in between limits of ith bytelandian then he has to be a knight else for a value he can become a byteknave and this is needed to print the lexicographic smallest one. And since he will be a byteknave his limit should be excluded from the range of n we have taken as possible because he speaks lie always.

CODE EXPLAINED :

#include <cstdio>
#include <set>
using namespace std;

int main(){
    int T;          //the number of test cases
    for(scanf("%d", &T); T--; ){
        int N, lo[50000], hi[50000], diff[50002]={0};     

        //the arrays to store ranges and diff
        scanf("%d", &N);
        for(int i=0; i<N; i++){
            scanf("%d%d", lo+i, hi+i);
            diff[lo[i]]++;
            diff[hi[i]+1]--;
        }
        set<int> good;      //set of all possible byteknights
        int ans=0, count=0;
        //if knights[n]=n then it can be a byteknight and
        //knights[n]=sum diff[i] from 0 to n
        for(int i=0; i<=N; i++){
            count+=diff[i];
            if(count==i){
                ans++;
                good.insert(i);
            }
        }
        printf("%d\n", ans);
        for(int i=0; i<N; i++){
        //tells truth i.e all possible knights are in his range
         //he has to be a byteknight
            if(lo[i]<=*good.begin() && *good.rbegin()<=hi[i])  
                putchar('1');
            else{
                putchar('0');
      //is made a knave and his range can be excluded from good set
                good.erase(good.lower_bound(lo[i]), good.upper_bound(hi[i]));
            }
        }
        putchar('\n');
    }
    return 0;
}

From this week on we start solving problems on Codechef, Interviewstreet etc. . with the view to improve your problem solving skills ..
          Apart from the code we will give a detailed mathematical and logical explanation about the problem.So lets start with something easy ..

LINK :: Question 1

Required Concepts : Euclid Algorithm

Well for both chefs we have A,B and C,D units that they can go .. so any length that is traversable by first chef is a multiple of gcd(A,B) and similarly any length that is traversable by second chef is a multiple of gcd(C,D) .. Hence units which are traversable by both are multiples of lcm=LCM(gcd(A,B),gcd(C,D)).Thus for the positive half of 1 to K number of such units equals K/lcm which is same on the other side of the rope. Hence our answer is 2*(K/lcm) + 1(bcz 0 is traversable by both as both can go forward and come back by same value).

typedef unsigned long long LL;
int T;
LL A,B,C,D,K;

LL gcd(LL a,LL b)    //euclid method for fast gcd
{
    if(b>a)
    return gcd(b,a);
    else
    return b==0?a:gcd(b,a%b);
}

int main()
{
    cin>>T;
    for(int i=0;i<T;i++)
    {
        cin>>A>>B>>C>>D>>K;
        LL n1=gcd(A,B);
        LL n2=gcd(C,D);
        LL den=gcd(n1,n2);
        LL S=n1/den;     //split the LCM part 1
        LL R=K/S;        //LCM part 2
        LL n4=R/n2;      //the final value
        cout<<(2*n4)+1<<endl;
    }
    return 0;
}

For finding LCM of a and b we used (a*b/gcd(a,b)) ..

Ever been troubled by segmentation faults .. now use gdb to take a closer inspection..

GDB stands for GNU Debugger which is a debugger for C and C++ .For any file you need to add -g to enable default debugging support.For enabling gdb just type gdb or gdb <filename> .If you did not mention the file earlier you can mention it by using the file command.
(gdb) file prog1.x
To run the program:
(gdb)run
If the program does have issues you will get information about where the program crashed i.e the line number and parameters to the function that caused the error.

The break command is used for setting the breakpoints in the program.For setting breakpoints in the file line pair use:
(gdb) break file.c:8
For breaking at a particular function use:
(gdb)break fib_func

To proceed to the next breakpoint use the continue statement:
(gdb)continue
To proceed one step at a time use the step statement:
(gdb)step

To print the value of the variables at any given time use the print command which prints the value of the variables and the print/x which gives the value of the variables mentioned in the program as hexadecimal.

Breakpoints stop the program at the points in the program ..whereas watchpoints watch over changes in the variables .
(gdb) watch i
whenever i is modified the program interrupts and prints out the old and the new values.Other useful commands are:
backtrace - produces a stack trace of the function calls that lead to a seg fault
finish - runs until the current function is finished
delete - deletes a specified breakpoint
info breakpoints - shows information about all declared breakpoints
                                                                                                                                                                                                                                                
Breakpoints are a tedious task of getting data always out of programs.To get specific
parts you can use conditional breakpoints like:
(gdb)break file1.c:6 if i >= ARRAYSIZE

So now you can try out various commands in your terminal and check out the gdb
manual for more details.

A Randomized Algorithm is one in which we use a randomizer or some kind of random number.Some decisions made in the algorithm depend on the output of the randomizer.Hence they have different runtime each time they are run even if the input is correct.
      Randomized algorithms can be divided into two categories:
Las Vegas Algorithms : These algorithms always give the correct output, however their runtime differ based on the output of the randomizer
Monte Carlo Algorithms: These algorithms give the correct answer for most of the cases however they may give incorrect answers for a small percent of values.

Primality testing using Miller-Rabin's Method: This algorithm makes use of Fermat theorem i.e. if n is prime than a^(n-1) %n=1 for any a<n.

Th2: The equation x^2%n=1 has exactly two solutions namely 1 and n-1
Th3: The equation x^2(mod n)=1 has roots other than 1 and n-1 then n is composite

The algorithm fails for some composite numbers (Carmichael numbers) for which every a that is less than and relatively prime to n will satisfy Fermats theorem.e.g 561 and 1105

Implementation:

int prime(int n,int alpha)
{
  int q=n-1;int i;
  int up=(int)alpha*log(n);
  int m,y,a,z,x;
  for(i=0;i<up;i++)
    {
      m=q;y=1;
      a=rand()%q+1;
      //choosing a random number in the range [1,n-1]
      z=a;
      //compute a^n-1 mod n
      while(m>0)
    {
      while(m%2==0)
        {
          x=z;
          z=(z*z)%n;
          if((z==1)&&(x!=1)&&(x!=q))
        return 0;
          m=(int)m/2;
        }
      m=m-1;y=(y*z)%n;
    }
      if(y!=1)
    return 0;
      //if a^n-1 mod n is not 1 n is not a prime
    }
  return 1;
}