Top Algorithms Interview Questions

The traveling salesman problem [TSP] is one of the combinatorial problems. The problem asks to find the shortest tour through a given set of n cities that visits each city exactly once before returning to the city where it started.The problem can be conveniently modeled by a weighted graph, with the graph‘s vertices representing the cities and the edge weights specifying the distances.
Then the problem can bestated as the problem of finding the shortest Hamiltonian circuit of the graph.
A Hamiltoniancircuit is defined as a cycle that passes through all the vertices of the graph exactly once.

Prim‘s algorithm constructs a minimum spanning tree through a sequence of expanding sub trees. The initial sub tree in such a sequence consists of a single vertex selected arbitrarily from the set V of the graph‘s vertices. On each iteration, the algorithm expands the current tree in the greedy manner by simply attaching to it the nearest vertex not in that tree.
A spanning tree for a connected graph is a tree whose vertex set is the same as the vertex set of the given graph, and whose edge set is a subset of the edge set of the given graph. i.e., any connected graph will have a spanning tree.
Weight of a spanning tree w (T) is the sum of weights of all edges in T. The Minimum spanning tree (MST) is a spanning tree with the smallest possible weight.

public static int recursive(int arr[], int low, int high, int key)
{
int mid = low + (high - low)/2;
if(arr[mid] == key)
{
return mid;
}
else if(arr[mid] < key)
{
return recursive(arr,mid+1,high,key);
}
else
{
return recursive(arr,low,mid-1,key);
}
}

int unorderedLinearSearch(int arr[], int size, int data)
{
int index;
for(int i = 0; i < size; i++)
{
if(arr[i] == data)
{
index = i;
break;
}
}
return index;
}