Microsoft Interview Question
Country: India
Interview Type: Written Test
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace ConsoleApplication49
{
class Program
{
static void Main(string[] args)
{
// input file, for example:
// 4
// 1 1 0 0;
// 0 0 1 0;
// 0 0 0 1;
// 1 1 0 0.
// first line - it is number of nodes.
string[] input_data = File.ReadAllText(@"G:\input.txt").Split(new char[] {' ','\r','\n','\t'},StringSplitOptions.RemoveEmptyEntries);
int j = 0;
int i = 0;
int n = int.Parse(input_data[0]);
int[,] matrix = new int[n,n];
// get matrix with graph
for (int k = 1; k < input_data.Length; k++)
{
if (input_data[k] == ";" || input_data[k] == ".")
{
i = 0;
j++;
}
else
{
matrix[j,i] = int.Parse(input_data[k]);
i++;
}
}
// count number of cycle
var num_cycle = GetNumberCycle(matrix);
Console.WriteLine(num_cycle);
Console.ReadKey();
}
static int GetNumberCycle(int[,] matrix)
{
int cycle = 0;
int n = (int)Math.Sqrt(matrix.Length);
int[] d = new int[n]; // it is array of nodes which was visited
for (int j = 0; j < n; j++)
{
d[j] = 1;
for (int i = 0; i < n; i++)
{
if (matrix[j, i] == 1)
{
if(d[i] == 1) cycle++;
else d[i] = 1;
}
}
}
return cycle;
}
}
}
The problem you want to solve is #CYCLE. Unless P=NP, it cannot be solved, for a proof look at the chapter on Counting Complexity in Arora and Barak. It is a gadget construction that reduces solving Hamiltonian path to #CYCLE and hence unless P=NP, Hamiltonian cycle - a NP-Complete problem cannot have a poly time solution.
- Hossein October 27, 2015A graph can have exponential number of cycles. Actually it can have even more - in a complete graph, consider any permutation and its a cycle hence atleast n! cycles. Actually a complete graph has exactly (n+1)! cycles which is O(nn)