5
\$\begingroup\$

I have a coding problem for which I have attempted to solve with the below coding. However, my program is assessed as too slow in its execution and thus needs to be optimized to reduce the execution time. Please help me in optimizing my program and reducing the execution time.

Problem definition:

People connect with each other in an online community. A connection between Person I and Person J is represented as C I J. When two persons belonging to different communities connect, the net effect is merger of both communities which I and J belonged to.

We are only interested in finding out the communities with the member count being an even number. Your task is to find out those communities.

Input:

Input will consist of three parts:

  1. The total number of people on the social network (N)
  2. Queries

    • C I J, connect I and J * Q 0 0, print the number of communities with even member-count

-1 will represent end of input.

Output:

For each query Q, output the number of communities with even member-count

Sample Input:

5

Q 0 0

C 1 2

Q 0 0

C 2 3

Q 0 0

C 4 5

Q 0 0

-1

Output for above Sample Input:

0

1

0

1

Sample Input/Output Explanation:

For first query there are no members in any of the groups hence answer is 0. After C 1 2, there is a group (let's take it as G1) with 1 and 2 as members hence total count at this moment is 1.

After C 2 3 total members in G1 will become {1, 2, 3} hence there are no groups with even count.

After C 4 5 there formed a new group G2 with {4, 5} as members, hence the total groups with even count is 1

Java Program:

import java.util.*;
import java.io.*;

public class OnlineCommunity2 {

    /* Your master grid. */
    //public List<List<Integer>> lout = new ArrayList<List<Integer>>();
    public Object[] lout;
    public int loutn;

    /* Your inner grid */
    public List<Integer> lin = new ArrayList<Integer>();

    public static void main(String args[])
    {
        try{
            OnlineCommunity2 obj = new OnlineCommunity2();
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            int ub=1000000;
            int lb=1;
            int z=0;
            if(n>=lb && n<=ub)
            {
                obj.lout = new Object[n];
                obj.lout[z]=obj.lin;
                obj.loutn++;
                String inp = new String();
                String limit = "-1";
                String q="Q 0 0";
                char c = 'C';
                while((inp=br.readLine())!= limit)
                {
                    if(inp.equals(q))
                    {
                        obj.findEvenComm();
                    }
                    else if(inp.charAt(z)==c)
                    {
                        String str[] = inp.split(" ");
                        int i = Integer.parseInt(str[1]);
                        int j = Integer.parseInt(str[2]);
                        if(i>=lb && i<=n && j>=lb && j<=n)
                        {
                            obj.insertIntoComm(i,j);
                        }
                    }
                }
                return;
            }
        }
        catch(Exception ex)
        {}
    }

    public void findEvenComm()
    {
        int count=0;
        for (int k=0; k<loutn; k++)
        {
            List<Integer> l1 = (List<Integer>) lout[k];
            int div=2;
            int z=0;
            if((l1.size())%div==z && !l1.isEmpty())
                count++;
        }    
        System.out.println(count);

    }

    public void insertIntoComm(int n1,int n2)
    {
        List<Integer> l1;
        Boolean flagi=false, flagj=false;
        int i=0,j=0;
        int z=0;
        if(((List<Integer>)lout[z]).isEmpty())
            ((List<Integer>)lout[z]).add(n1);
        for(int k=0; k<loutn; k++)
        {
            l1 = (List<Integer>) lout[k];
            if(l1.contains(n1))
            {
                flagi=true;
                break;
            }
            i++;
        }
        for(int k=0; k<loutn; k++)
        {
            l1 = (List<Integer>) lout[k];
            if(l1.contains(n2))
            {    
                flagj=true;
                break;
            }
            j++;
        }
        if(!flagi && !flagj)
        {
            List<Integer> templ = new ArrayList<Integer>();
            templ.add(n1);
            templ.add(n2);
            lout[loutn] = templ;
            loutn++;
        }
        else if(flagi && flagj && i!=j)
        {            
            ((List<Integer>) lout[i]).addAll((List<Integer>) lout[j]);
            lout[j] = lout[loutn-1];
            loutn--;

        }
        else if(flagi && !flagj)
        {
            ((List<Integer>) lout[i]).add(n2);
        }
        else if(!flagi && flagj)
        {
            ((List<Integer>) lout[j]).add(n1);
        }
        return;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Please provide attribution to the originator of the challenge question. \$\endgroup\$ – 200_success Aug 13 '14 at 16:10
4
\$\begingroup\$

Okay I understand this is a programming challenge so I won't comment on programming style or variable naming as one does not usually care in this case. But it would be nice if you'd tidy it up enough for us to see what you're doing. I can't quite make out what lout is supposed to be for example.

In any case I'd bet your performance issue comes from these two for loops:

    for(int k=0; k<loutn; k++)
    {
        l1 = (List<Integer>) lout[k];
        if(l1.contains(n1))
        {
            flagi=true;
            break;
        }
        i++;
    }
    for(int k=0; k<loutn; k++)
    {
        l1 = (List<Integer>) lout[k];
        if(l1.contains(n2))
        {    
            flagj=true;
            break;
        }
        j++;
    }

The time complexity of List.contains() is linear in the number of elements. As the test progresses you'll end up with at least quadratic time. You need to swap your Lists for something with a quicker .contains(). I would suggest HashSet which has amortized constant time in look-up.

\$\endgroup\$
0
\$\begingroup\$

The problem is a variation on the classic Quick-Find/Quick-Union problem. I highly recommend to study a standard implementation first.

Another speedup is in getting rid of findEvenComm. The challenge only asks for a count of even-populated groups, so there is no need to keep a list of them. A simple counter will do. Each group should know if it is odd- or even-populated. When two groups are joined, the counter increments if both groups are odd, and decrements otherwise.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.