CareerCup

C# Solution

/* Test Cases:
         * (0,5) (2,4)
         * (2,4) (0,5)
         * (1,5) (3, 7)
         * (7,9) (3,8)
         * (0,3) (7,9)
         * (0,5) (0,5)
         */ 
        public  struct range
        {
            internal int start;
            internal int end;
        }

        public static void FindDifference(range a, range b)
        {
            //if B is contained in A
            if (a.start <= b.start && b.end <= a.end)
            {
                for (int i = a.start; i <= a.end; i++)
                {
                    if (i < b.start || i > b.end)
                        Console.Write(i + " ");
                }
            }
                //if A is contained in B
            else if ( b.start <= a.start && a.end <= b.end)
            {
                for (int i = b.start; i <= b.end; i++)
                {
                    if (i < a.start || i > a.end)
                        Console.Write(i + " ");
                }
            }
                //A is before B but they overlap 
            else if (a.start <= b.start && a.end >= b.start && a.end <= b.end)
            {
                for (int i = a.start; i < b.start; i++)
                    Console.Write(i + " ");
                for (int i = a.end + 1; i <= b.end; i++)
                    Console.Write(i + " ");
            }
                //B is before A but they overlap
            else if (b.start <= a.start && b.end >= a.end && b.end <= a.end)
            {
                for (int i = b.start; i < a.start; i++)
                    Console.Write(i + " ");
                for (int i = b.end + 1; i <= a.end; i++)
                    Console.Write(i + " ");
            }
                //A and B are completely detached. 
            else
            {
                for (int i = a.start; i <= a.end; i++)
                    Console.Write(i + " ");
                for (int i = b.start; i <= b.end; i++)
                    Console.Write(i + " ");
            }
            Console.WriteLine();
        }

let A=(a,b) and B=(c,d)
if B is contained in A i.e. a=<c, b>=d return (a,c)U(d,b) equality is only for either or b
if A is contained in B return empty set
if a>=c and b>=d return (d,b)
if a<=c and b<=d return (a,c)
else return (a,b)

Let A and B be two ranges which are limited by [Alow,Ahigh] [Blow,Bhigh]
Now there can be total 7 cases
1. both ranges matches
2. A is contained in B
3. B is contained in A
4. they intersect but A is on right of B
5. they intersect but B is on right of A
6. they dont intersect and B is on right of A
7. they dont intersect and A is on right of B

which have been handled in python code as following

def findDiffAB(Alow,Ahigh,Blow,Bhigh):
    #negetive test case
    if (Alow>Ahigh or Blow>Bhigh):
        return list()
    if(Alow==Blow and Ahigh==Bhigh):
        return list()
    if (Alow>Blow and Ahigh<Bhigh):
        return list()
    if (Alow<Blow and Ahigh>Bhigh):
        return range(Alow,Blow)+range(Bhigh,Ahigh)
    if (Alow>Blow and Ahigh>Bhigh and Alow<Bhigh):
        return range(Bhigh,Ahigh)
    if (Alow<Blow and Ahigh<Bhigh and Blow<Ahigh):
        return range(Alow,Blow)
    if (Ahigh<=Blow):
        return range(Alow,Ahigh)
    if (Alow>=Bhigh):
        return range(Alow,Ahigh)

Obviously 4 cases can be merged two 2 here but i didnt for sake of clarity

Few test cases:
print findDiffAB(2,5,2,5)
print findDiffAB(3,5,2,7)
print findDiffAB(2,15,7,9)
print findDiffAB(12,25,2,5)
print findDiffAB(2,5,12,25)
print findDiffAB(2,5,13,15)
print findDiffAB(12,25,2,5)

can u give an example?

void PrintRange(int start,int end)
{
	if(end<start) return;
	for(int i=start;i<=end;start++)
		cout<<i<<endl;	
}
void Minus(int start1,int end1,int start2,int end2)
{
	if((start1<start2 && end1<start2) || (start1>end2 && end1>end2))
		PrintRange(start1,end1);
	else
	{
		PrintRange(start1,start2-1);
		PrintRange(end2+1,end1);		
	}
}

testcases:
[0,1][2,5] -> [0,1]
[3,5][0,1] -> [3,5]
[1,8][2,5] -> [1,6,7,8]

import java.util.HashSet;
import java.util.Set;


public class SetDiff {

    public void diff(int minA, int maxA, int minB, int maxB) {
        Set<Integer> s = new HashSet<Integer>();

        for (int i = minA; i <= maxA; i++) {
            s.add(i);
        }

        for (int i = minB; i <= maxB; i++) {
            s.remove(i);
        }
        System.out.println(s);
    }

    public static void main(String... args) {
        SetDiff diff = new SetDiff();

        diff.diff(0,1,2,5);   // [0, 1]
        diff.diff(3,5,0,1);   // [3, 4, 5]
        diff.diff(1,8,2,5);   // [1, 6, 7, 8]
        diff.diff(0,5,2,8);   // [0, 1]
        diff.diff(2,6,4,5);   // [2, 3, 6]
    }
}

This should cover all the cases :

void findDiff(int a1,int a2, int a3, int a4)
{
   cout<<"("<<a1<<","<<a2<<") - ("<<a3<<","<<a4<<") = \n";

   if(a1 < a3) 
   {
         int end = (a2<a3) ? a2: a3-1;
         for(int i=a1; i<=end; i++) cout<<i<<"\t";
   }

   if(a4 < a2) 
   {
         int start = (a1>a4) ? a1 : (a4+1);
         for(int i=start; i<=a2; i++) cout<<i<<"\t";
   }
   cout<<"\n";
}

Complexity of O(m+n). Please let me know if something is wrong with this code.

import java.util.HashSet;

public class Test 
{
	public static void main(String[] args) 
	{
		int low1 = 0;
		int high1 = 5;
		int low2 = 2;
		int high2 = 4;
		
		HashSet hashSet = new HashSet();
		
		for(int i = low1; i<=high1; i++)
		{
			hashSet.add(i);
		}
		
		for(int i=low2; i<=high2; i++)
		{
			if(hashSet.contains(i))
			{
				hashSet.remove(i);
			}
		}		
		System.out.println(hashSet);
	}
}

Store B in hash table. Iterate over A and print only those elements that doesn't satisfy hash lookup.

let A=(low,high) and B(low,high)

if(A.low > B.high || A.high < B.low)
    return A.low and A.high 
Else 
       if(A.Low < B.Low)
              return A.low and B.low -1
       if(A[1].high > B.high)
              return B.high+1 and A.high

Do not need to consider so many cases
suppose a1<a2 , b1<b2

void findDiff(int a1, int a2, int b1, int b2)
{
if(a1<b1)
{
while(a1!=b1)
{
cout<<a1<<endl;
a1++;
}
}
if(b2<a2)
{
while(b2!=a2)
{
cout<<a2<<endl;
a2--;
}
}

}