Alcatel Lucent Interview Question


Country: United States
Interview Type: In-Person




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

O(n) time complexity and O(1) time complexity.

public int[] findTwo(int[] a, int[] b) {
		int sumA = 0, squareSumA = 0;
		for (int i = 0; i < a.length; i++) {
			sumA += a[i];
			squareSumA += a[i] * a[i];
		}
		int sumB = 0, squareSumB = 0;
		for (int i = 0; i < b.length; i++) {
			sumB += b[i];
			squareSumB += b[i] * b[i];
		}
		int twosum = sumB - sumA;
		int squareSum = squareSumB - squareSumA;
		int param1 = 2;
		int param2 = 2 * twosum;
		int param3 = twosum * twosum - squareSum;
		int[] res = new int[2];
		int sqrtdiff = (int) Math.sqrt(param2 * param2 - 4 * param1 * param3);
		res[0] = (param2 - sqrtdiff) / (2 * param1);
		res[1] = (param2 + sqrtdiff) / (2 * param1);
		return res;
	}

- jack December 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

typo. O(1) Space complexity.
For quadratic equation ax^2 + bx + c = 0, the answer x = (b +/- sqrt(b * b - 4 * a * c)) / 2a;

- jack December 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I tested this and it works.

Can you explain how you came up with a solution like this?

- rizhang December 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n) space complexity since you have to store the arrays

- Anonymous December 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

algorithm is not O(1) as it involves two for loops!! O(n2) is the time complexity

- Jacker December 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code isn't O(n2) the for loops only cycle through each array once and only touching each element once. The for loops would need to be nested to be O(n2). Although, depending on the language using ".length" can be frowned upon because rather than storing the value it is retrieving it every iteration. Well done on the solution.

- Noah December 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public List<Integer> findDiff (int [] A , int [] B){
		if (B.length > A.length) return findDiff (B,A);
		HashSet<Integer> set = new HashSet<Integer> ();
		List<Integer> result = new ArrayList<Integer> ();
		for (int a : A) set.add(a);
		for (int b : B) {
			if (!set.contains(b)) result.add(b) ;
		}	
		return result ;

}

- Scott December 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Tell me will your solution work if:
A = {2, 3}
B = {2, 3, 3, 3}

- mikkysati December 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if (B.length > A.length) return findDiff (B,A);

- Anonymous December 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

mikkysati is correct, using contains will not work (swapping the arrays does nothing either)

A = { 1, 2 }
B = { 1, 2, 2, 3 }

Also, this algo is adding the wrong array to the hashset. You want to add the smaller array.

- Anonymous December 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The logic to the solution given by Jack,
Since we know that we are looking at 2 additional values
diff A - B will give the sum of 2 additional numbers ( x + y)
diff of A^2- B^2 will give x^2 + y^2

we also know that (x+y)^2 = x^2 + y^2 + 2*x*y, so x*y can be computed
We are trying to find x-y , using the property (x-y)^2 = (x+y)^2 - 4x*y

Then we can solve (x+y) and (x-y) to get x and y.

I hope this helps.

- maverick December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do you mean (x-y)^2 = (x+y)^2 - 2x*y? I'm still confused about where the quad formula came from

- rizhang December 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

var arrA =[1, 4, 2, 6, 3];
var arrB =[4, 0, 7, 6, 3, 2, 1];

arrA = arrA.sort();
arrB = arrB.sort();

exe();

function exe(){
    var i = 0;
    var j = 0;
   for(number in arrB){

        if(arrA[i] != arrB[j]){
            j++;
            console.log(arrB[number]);
        }else{
            i++;
            j++;
        }
    }

}

- Quick Hack December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I edited my code incase arrayA out of bounds and also break when we have gotten the two unknown numbers instead of going through the whole thing:

var arrA =[1, 4, 2, 6, 3];
var arrB =[4, 0, 7, 6, 3, 2, 1];

arrA = arrA.sort();
arrB = arrB.sort();

exe();

function exe(){
    var i = 0;
    var j = 0;
    var count = 0;
   for(number in arrB){
        if(arrA[i] != arrB[j]){
            
            j++;
            count++;
            console.log(arrB[number]);
            
        }else{

            i != arrA.length ? i++ : i;
            
            j++;
        }
        
        if (count == 2){
            break;
        }
    }

}

- Quick Hack December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findTwo(A, B):
    difference = sum(B) - sum(A)
    differenceSqrs = sum(x ** 2 for x in B) - sum(x ** 2 for x in A)
    a1 = int((difference + (2 * differenceSqrs - difference ** 2) ** 0.5) / 2)
    a2 = int((difference + (2 * differenceSqrs - difference ** 2) ** 0.5) / 2)
    if sum(1 for x in A if x == a1) != sum(1 for x in B if x == a1):
        return a1, difference - a1
    return a2, difference - a2

- Alisa December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm in O(N) time complexity and O(1) space complexity.

Let 2 numbers be a,b
Find addition and multiplication of each numbers from 2 arrays.
a+b=(arrB[0]+...arrB[n+2]) - (arrA[0]+...arrA[n])
a*b=(arrB[0]*...*arrB[n+2]) / (arrA[0]*...*arrA[n])

Given a+b and a*b, finding a and b is one step.

Assumption-values are integers and result of multiplication is within range.

- Anonymous December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The shortest way, I suppose.

static void Main(string[] args)
        {
            int[] a = new int[] { 1, 4, 2, 6, 3 };
            int[] b = new int[] { 4, 0, 7, 6, 3, 2, 1 };
            
            var ans = a.Concat(b).GroupBy(x => x).Where(y => y.Count() == 1).Select(z => z.Key).ToList();

            foreach (int item in ans)
            {
                Console.WriteLine(item);
            }
            Console.ReadLine();


        }

- Eugene Mmmmm December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose you are told that two numbers, x and y, have a certain sum x+y=S, and a certain product xy=P. How to find S and P?

We can use the fact that we know how to solve quadratic equations. Notice that
(t−x)(t−y) = t^2 −(x+y)t + xy= t^2−St+P.

That means that x and y are precisely the solutions to
t^2 − St + P = 0.

So what we can do is:

public static void main(String[] args) {
		
		int[] A = { 1, 4, 2, 6, 3 };
		int[] B = {4, 0, 7, 6, 3, 2, 1};

		int S = 0, P = 1;
		int a = 0, b = 0;
		
		for(int i: A) {
			S += i;
			P *= (i==0)?1:i; //Avoid zeroing the product
		}
		
		for(int j: B) {
			S -= j;
			P /= (j==0)?1:j; //avoid division by zero
		}

		S = Math.abs(S);
		
		//Solve t^2 - St + P = 0
		a = (int) ( S + Math.sqrt(S*S - 4*P) ) / 2;
		b = (int) ( S - Math.sqrt(S*S - 4*P) ) / 2;
		
		System.out.println("The different numbers are: " + a + ", " + b);
		
	}

That was a way that seemed clear to me... There could be easier ways for other people. But that`s the way I would go with.

Time complexity O(n) iterates only once through each array, and Space complexity O(1) because the only additional storage needed are the variables a,b,S and P.

Hope this helps somebody.

- Arthur December 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	
	public static void findUnCommonNumbers(int[] a,int[] b)
	{
		HashMap<Integer,Integer> input = new HashMap<Integer,Integer>();
		
		for(int i:a)
		{
			input.put(i,i);
		}
		
		for(int j:b)
		{
			if(!input.containsKey(j))
			{
				System.out.print(" "+j);
			}
		}
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		int a[] ={1, 4, 2, 6, 3} ;
		int b[]={4, 0,7, 6, 3, 2, 1};
		
		
		findUnCommonNumbers(a,b);
	}
}

- Himanshu Jain December 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class UncommonData {
static int ar1[] = {1,4,2,6,3};
static int ar2[] = {4,0,7,6,3,2,1};
static void getUncommonData(int ar1[],int ar2[])
{
for(int i : ar2)
{
int count = 0;
for(int j: ar1)
{
if(i==j)
break;
else
count++;


}
if(count==5)
System.out.println(i);
}

}
public static void main(String[] args) {
getUncommonData(ar1,ar2);
}

- ganesh January 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Haven't tried, but I guess the following algo should work.

for (i=0; i< a.length; i++) A1 = a[i] ^ b[i];
A1 = A1 ^ b[a.length] ^ b[a.length + 1];

for (i=0; i<b.length; i++)
{
	if (A1 ^ b[i]) continue;
	else cout << b[i] << endl;
}

- Varun December 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain the logic.

- mikkysati December 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain the logic.

- mikkysati December 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

pls explain ur logic.....

- Anonymous December 15, 2014 | Flag


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