When a browser makes a request to a server it does in the form of requests formatted by some rules so that the server can understand what resource the browser is asking for.A normal REST http header would look like this :

POST /enlighten/rest HTTP/1.1
Host: api.opencalais.com
Content-Type: application/x-www-form-urlencoded
Content-Length: length

licenseID=string&content=string&/paramsXML=string 

The response from the server side would look something like :

HTTP/1.1 200 OK
Content-Type: text/xml;charset=utf-8
Content-Length: length

string

Parts of the HTTP Request and their Significance

 Accept: audio/*; q=0.2, audio/basic 

The Accept request-header field can be used to specify certain media types which are acceptable for the response.If no Accept header field is present, then it is assumed that the client accepts all media types.

  Accept-Charset: iso-8859-5, unicode-1-1;q=0.8

The Accept-Charset request-header field can be used to indicate what character sets are acceptable for the response.The special value "*", if present in the Accept-Charset field, matches every character set (including ISO-8859-1) which is not mentioned elsewhere in the Accept-Charset field

  Accept-Encoding: gzip;q=1.0, identity; q=0.5, *;q=0

The Accept-Encoding request-header field is similar to Accept, but restricts the content-codings  that are acceptable in the response.

  Accept-Language: da, en-gb;q=0.8, en;q=0.7

Accept-Lnguages tells about the language that is preferred in the response of the output.

  Accept-Ranges: bytes

The Accept-Ranges response-header field allows the server to indicate its acceptance of range requests for a resource.This is what the internet download manager looks for to tell whether a particular resource is resumable or not.

  age-value = delta-seconds

The Age response-header field conveys the sender's estimate of the amount of time since the response (or its revalidation) was generated at the origin server. A cached response is "fresh" if its age does not exceed its freshness lifetime.Age values are non-negative decimal integers, representing time in seconds.

  Allow: GET, HEAD, PUT

The Allow entity-header field lists the set of methods supported by the resource identified by the Request-URI. The purpose of this field is strictly to inform the recipient of valid methods associated with the resource. An Allow header field MUST be present in a 405 (Method Not Allowed) response.

  Authorization  = "Authorization" ":" credentials

A user agent that wishes to authenticate itself with a server-- usually, but not necessarily, after receiving a 401 response--does so by including an Authorization request-header field with the request. The Authorization field value consists of credentials containing the authentication information of the user agent for the realm of the resource being requested.

  Cache-Control   = "Cache-Control" ":" 1#cache-directive

The Cache-Control general-header field is used to specify directives that MUST be obeyed by all caching mechanisms along the request/response chain. The directives specify behavior intended to prevent caches from adversely interfering with the request or response.

 The following Cache-Control response directives allow an origin server to override the default cacheability of a response:

public

Indicates that the response MAY be cached by any cache, even if it would normally be non-cacheable or cacheable only within a non- shared cache. (See also Authorization, section 14.8, for additional details.)

private

Indicates that all or part of the response message is intended for a single user and MUST NOT be cached by a shared cache. This allows an origin server to state that the specified parts of the

response are intended for only one user and are not a valid response for requests by other users. A private (non-shared) cache MAY cache the response.

Note: This usage of the word private only controls where the response may be cached, and cannot ensure the privacy of the message content.

no-cache

If the no-cache directive does not specify a field-name, then a cache MUST NOT use the response to satisfy a subsequent request without successful revalidation with the origin server.

  Connection: close

The Connection general-header field allows the sender to specify options that are desired for that particular connection and MUST NOT be communicated by proxies over further connections.

  Content-Length: 3495 

The Content-Length entity-header field indicates the size of the entity-body, in decimal number of OCTETs, sent to the recipient or, in the case of the HEAD method, the size of the entity-body that would have been sent had the request been a GET.

  Content-MD5   = "Content-MD5" ":" md5-digest
  md5-digest   = <base64 of 128 bit MD5 digest as per RFC 1864>

The Content-MD5 entity-header field, as defined in RFC 1864 [23], is an MD5 digest of the entity-body for the purpose of providing an end-to-end message integrity check (MIC) of the entity-body. (Note: a MIC is good for detecting accidental modification of the entity-body in transit, but is not proof against malicious attacks.)

For more headers information check RFC section for HTTP headers.

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;
}