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)

- Hossein October 27, 2015 | Flag Reply
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.

- CallMeK October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tarjan's Algorithm for strongly connected graphs

- revanthpobala October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hello. Can you provide some constraints on problem input?

- Serge Aktanorovich October 28, 2015 | Flag Reply
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.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;
        }
    }
}

- Trushnikov.Ivan December 22, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More