## Alcatel Lucent Interview Question

• 0
of 0 votes

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;
int sqrtdiff = (int) Math.sqrt(param2 * param2 - 4 * param1 * param3);
res = (param2 - sqrtdiff) / (2 * param1);
res = (param2 + sqrtdiff) / (2 * param1);
return res;
}``````

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;

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?

Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

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.

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 ;``````

}

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}

Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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.

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.

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

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++;
}
}

}``````

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;
}
}

}``````

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``````

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+...arrB[n+2]) - (arrA+...arrA[n])
a*b=(arrB*...*arrB[n+2]) / (arrA*...*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.

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();

}``````

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.

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);
}
}``````

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);
}

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain the logic.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain the logic.

Comment hidden because of low score. Click to expand.
0
of 0 votes

pls explain ur logic.....

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