## Microsoft Interview Question

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

A 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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

The first question to ask is: do we treat nested circle lazily or not? Second, a circle of two nodes included?

In general, I think it is well possible to just use a modified DFS or BFS. When you see a visited, you know you get a circle.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Tarjan's Algorithm for strongly connected graphs

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hello. Can you provide some constraints on problem input?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
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);
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);
}
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;
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.