Wednesday, 3 July 2013

Team Interview

Problem Statement

A survey team has a set of questions all of which can be answered in either ‘Yes’ or ‘No’. Team interviews some people and asks any two questions from the set it is available with (a questions may be repeated i.e. asked to several people). Each person in the city answers the question in one of the following way (let q1 and q2 be the questions asked): 

i) Either answer to q1 is ‘yes’ or answer to q2 is ‘yes’ or both. 
ii) Either answer to q1 is ‘yes’ or answer to q2 is ‘no’ or both. 
iii) Either answer to q1 is ‘no’ or answer to q2 is ‘yes’ or both. 
iv) Either answer to q1 is ‘no’ or answer to q2 is ‘no’ or both. 

After recording responses to all the questions, the team works on figuring out the answers to individual questions assuming that each person knows the answers to all the questions and also he tell the correct answer to the survey team (in the specified format). Although it is possible that this assumption is wrong and logically, answers to all the questions can’t be deduced from the responses. This means that no matter what are the answers to the questions, all the responses cannot be valid. 
                                      Given responses to all the questions, you have to tell whether it is possible to assign a ‘yes’ or ‘no’ answer to all the questions, so that responses of all the people stand valid? { whether a logical deduction is possible on the basis of responses or not}

Input/Output Specs

Input: 

Your First input will be Integer type i.e Number of total questions   (n) { q1, q2,………..qn } 

Your Second  input will be Integer type i.e   Number of total people interviewed   (m) 

Your Third input will be string Type Array 
which contains Response list { list of m elements pairs of one of the four types(1<= x,y <= n ) given pair as x#y. }

i) (x,y) which means “ either answer to ‘qx’ is ‘yes’ or answer to ‘qy’ is ‘yes’ or both” } 
ii) (x,-y) which means “ either answer to ‘qx’ is ‘yes’ or answer to ‘qy’ is ‘no’ or both” } 
iii) (-x,y) which means “ either answer to ‘qx’ is ‘no’ or answer to ‘qy’ is ‘yes’ or both” } 
iv) (-x,-y) which means “ either answer to ‘qx’ is ‘no’ or answer to ‘qy’ is ‘no’ or both” } 

Output:

Your output will be string type Yes/No (Case Sensitive)

Examples

Examples 1: 
n =3, m = 2 and response list is (-1,2),(-1,-2) then it is possible to assign an answer to q1 (‘Yes’) and q2 (either ‘Yes’ or ‘no’)which satisfies the given conditions. 

Examples 2: 
n =3, m = 3 and response list is (-1,2),(-1,-2)(1,2) then it is possible to assign an answer to q1 (‘Yes’) and q2 ( ‘Yes’ )which satisfies the given conditions. 

Examples 3:
n =3, m = 4 and response list is (1,2),(1,-2),(-1,-2), (-1,2), then it is not possible to assign answers to q1 and q2 satisfying the answers of all the four people. None of the four possibilities for (q1,q2) i.e. (‘Yes’,’Yes’),(‘Yes’,’No’),(‘No’,’Yes’),(‘No’,’No’) satisfies all the four responses.


using System;

public class AnswerYesOrNo
{
    public static string Result(int qno, int pno, string[] arr)
    {
        return combination.GetAnswer(qno, pno, arr);
    }
}
class Answer
{
    public const string Yes = "Yes";
    public const string No = "No";
    public const string Both = "Both";
}


class Question
{
    public int Number { setget; }

    public int NoCount { setget; }

    public int YesCount { setget; }

    public bool Both { setget; }

}

class combination
{

    public static string[] GetCombinations(string input)
    {
        string[] k = input.Split('#');
        int a = Convert.ToInt32(k[0]);
        int b = Convert.ToInt32(k[1]);

        string[] retcom = new string[4];

        retcom[0] = a + "#" + (-1 * b);
        retcom[1] = (-1 * a) + "#" + b;
        retcom[2] = (-1 * a) + "#" + (-1 * b);
        retcom[3] = input;
        return retcom;
    }

    public static bool Contains(string[] array, string h, ref int count)
    {
        bool result = false;
        foreach (string j in array)
        {
            if (j == h)
            {
                result = true;
            }
        }
        if (result)
            count++;
        return result;
    }

    public static bool OtherComNotExists(string response, string[] array)
    {
        int q1 = 0;
        int q2 = 0;

        if (response.Length == 3)
        {
            q1 = int.Parse(response[0].ToString());
            q2 = int.Parse(response[2].ToString());
        }
        else if (response.Length == 5)
        {
            q1 = int.Parse(response[1].ToString());
            q2 = int.Parse(response[4].ToString());
        }
        else
        {
            if (response[0] == '-')
            {
                q1 = int.Parse(response[1].ToString());
                q2 = int.Parse(response[3].ToString());
            }
            else
            {
                q1 = int.Parse(response[0].ToString());
                q2 = int.Parse(response[3].ToString());
            }
        }

        foreach (string h in array)
        {
            if (h.Contains(q1.ToString()))
            {
                if (!h.Contains(q2.ToString()))
                {
                    return false;
                }
            }

            if (h.Contains(q2.ToString()))
            {
                if (!h.Contains(q1.ToString()))
                {
                    return false;
                }
            }
        }
        return true;
    }

    public static string GetAnswer(int a, int b, string[] array)
    {
        if (b != array.Length)
            return "No";
        string[] alchecked = new string[a];
        Question[] ques = new Question[a];
        string result = "Yes";

        for (int i = 0; i < array.Length; i++)
        {
            string[] res = GetCombinations(array[i]);
            int j = 0;
            foreach (string chk in res)
            {
                int count = 0;
                if (Contains(array, chk, ref count))
                {
                    j++;
                }
            }
            if (j == 4)
            {
                if (!OtherComNotExists(array[i], array))
                    return result = "No";
            }
        }

        for (int i = 1; i <= a; i++)
        {
            ques[i - 1] = new Question() { Number = i };
        }

        foreach (string str in array)
        {
            string[] spl = str.Split('#');
            int q1 = Convert.ToInt32(spl[0]);
            int q2 = Convert.ToInt32(spl[1]);
            int[] qarray = new int[] { q1, q2 };
            foreach (int quest in qarray)
            {
                if (Math.Sign(quest) == -1)
                {
                    ques[(quest * -1) - 1].NoCount++;
                }
                else
                {
                    ques[quest - 1].YesCount++;
                }
            }
        }
        int bothcount = 0;
        int questionasked = 0;
        int totalyescount = 0;
        int totalnocount = 0;

        foreach (Question quesasked in ques)
        {
            if (quesasked.NoCount > 0 || quesasked.YesCount > 0)
            {
                questionasked++;
                if (quesasked.NoCount == quesasked.YesCount)
                {
                    quesasked.Both = true;
                    bothcount++;
                }
                if (!quesasked.Both)
                    if (quesasked.YesCount > quesasked.NoCount)
                    {
                        totalyescount++;
                    }
                    else
                    {
                        totalnocount++;
                    }
            }
        }

        if (questionasked <= a / 2)
            return "No";
        if (bothcount > totalyescount + totalnocount)
            return "No";

        if (bothcount <= (questionasked / 2) || totalnocount + totalyescount > bothcount)
            return "Yes";
        else
            return "No";
    }
}

No comments:

Post a Comment