#programming interview questions
Determine cycles in graphs
Topological sort discussed in the previous blog post can help detect cycles. It is a linear ordering of all vertices along a horizontal line so that all the directed edges go from left to right. If the time taken to visit the next element is less than any of the predecessors then we have a cycle.
Bellman-Ford algorithm can work with negative-weight edges in the input graph. If there are no cycles, the algorithm takes gives the shortest paths and their weights. It relaxes each edge of the graph once and then determines cycle.
Bellman-Ford(G, w, s)
Initialize-single-source(G,s)
for i = 1 to number of vertices -1
    for each edge (u,v) belongs to edges E in G
          relax(u,v,w)
for each edge(u,v) belongs to edges E in G
     if (v.d  > u.d  + w(u,v))
         return False
return True

In a plane n points (X and Y) is given. How will you find out the maximum collinear points. Extend this algorithm for points (X, Y and Z) in 3D plane.
int Get MaxCollinear(List<Point> p)
{
var collinear = new List<Tuple<int,int,int>>();
for (int i =0; i < p.Count; i++)
   for (int j =0; j < p.Count; j++)
     for (int k =0; k<p.Count;k++)
    {
            if (p[i] ==p[j] || p[j] == p[k] || p[k] == p[i]) continue;
            if (collinear.contains(p[i],p[j],p[k])) continue;
            if (isCollinear(p[i],p[j],p[k]))  collinear.Add(p[i],p[j],p[k]);
     }
var ret = Merge(collinear);
return ret.count();
}

bool isCollinear(Point p, Point q, Point r)
{
if (q.x >= min(p.x,r.x) && q.x<= max(p.x,r.x)
    && q.y >= min(p.y,r.y) && q.y <= max(p.y,r.y)))
   return True;
return False;
}
List<Point> Merge(List<Tuple<int,int,int>> collinear)
{
// two points are common between entries
var max = new List<Point>()
{
for (int i =0 i < collinear.count; i++){
   var ret = new List<Point>();
   for (int j =0; j <collinear.count; j++)
    {
          if ( i != j  && collinear[i].Intersects(collinear[j]).Count > 2){
                       ret.add(collinear[i].items);
                       ret.add(collinear[j].items);
          }
    }
    if (ret.Count > max.Count)
          ret.CopyTo(ref max);
}
return max;
}