Apple Interview Question: The accent of the interviewer... | Glassdoor

Interview Question

Software Engineer Interview(Student Candidate)

The accent of the interviewer was very hard to understand

 . Given an array with N - 2 elements (two missing) from 1 to N, find the two missing elements in linear time and constant memory usage.
Answer

Interview Answer

12 Answers

6

You sweep through the array once and updating 2 variables. The first sums all the numbers in the array. The second multiply them. Now it's just a matter of solving 2 equation with 2 unknowns.
x + y = SUM[1..N] - t1 ; x * y = factorial[1..N] / t2.

outline of the answer on Sep 12, 2014
1

Why would you make it so complicated? Why would you compute factorial. If there's a million elements in the array, your algorithm just cried.

Algorithm: sweep through the entire array. If the first element is equal to one, print zero. If the first element is equal to two, print one and zero. Now generalize that. There is a special case to consider it it's the last two elements that are missing, which falls into the same category of having an array of size N = 1.

It's O(n), which I believe means linear time? And it actually doens't use any additional memory.

fzivkovi on Oct 11, 2014
1

The array of integers isn't sorted so your approach doesn't really work fzivkovi.

j on Oct 15, 2014
2

1. Create a new array of size N, the values of all members are zero.
2. Loop through the input array
- Suppose the value of the current member is X
- Put 1 to the X-th member of the new array
3. Loop through the new array
- If the value of a member is zero, print out the member.

It takes O(n) time and O(n) space.

Vee on Oct 26, 2014
4

Vee - your answer does not use constant space. It uses linear space.

Anonymous on Dec 21, 2014
2

Since array is from 1...n, we know that all numbers between 1 and N must be represented. so if n = 5, then array should be 1, 2, 3, 4, 5. Therefore:

for( i = 0, i < array.length, i++){

    if( array[ i ] != i+1){
          // this element is missing
     }

}

asdf on Feb 20, 2015

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.

0

This will be a little confusing since I don't want to write the algorithm for this here.

Sort the array in O(N). Start from the first element. If it is not in the right place, set it to 0 and move it to the right place. Do the same to the next element (otherwise you will overwrite it). Do this until your element is in the right place or is equal to 0. Now repeat to all elements in the array. At the end, scan the array and find which elements in the array are equal to 0. This algorithm assumes the array size is N and not N-2, but can be modified to use two variables for the last two elements.

Carlos on Apr 18, 2015
0

list
=> [3, 1, 2, 5, 7, 8]
   prod = reduce(lambda x,y: x*y, [x for x in range(1,9)])
   product = reduce (lambda x, y : x * y, list)
   prod/product
=> 24
   product = prod/product
   product
=> 24
   sum
=> 10
   100 - 24*4
=> 4
   x = sum/2.0 + math.sqrt(sum*sum - 4*product)/2.0
   x
=> 6.0
   y = sum/2.0 - math.sqrt(sum*sum - 4*product)/2.0
   y
=> 4.0
   int(x)
=> 6
   int(y)
=> 4

Anonymous on Jun 2, 2015
0

// assume array is in A, size to N with two BLANK element.

#define BLANK N+1

for(int i =0; i<N; i++)
{
  int x = A[i];
  swap(A, x, i);
}

// A is sorted with blanks in the middle

for(int i=0; i< N; i++)
{
  if( A[i] == BLANK)
  {
    std::cout << i << std::endl;
   }
}

Jack on Jul 27, 2015
0

We know that array has elements from 1 to N. Just traverse an array, for every element

if( array[ i ] = 4 )
   make array[4] negative

once entire array has traversed and changed values to negative using above statements, traverse it again and the 2 places whose values are NOT negative, are nothing but missing values.

Anonymous on Jul 22, 2016
0

int main(){

    int arr[] = {1,2,4,5,6,7,9,10}; //3 and 8 missed

    int n = sizeof(arr)/sizeof(arr[0]);
    vector b(n+3);

    int t = 0, tt, nn = n + 2;

    if ((nn)%2 == 0)
        tt = (nn/2) * (nn+1);
    else
        tt = ((nn+1)/2) * nn;

    for (int i = 0; i < n; i++){
        t = t + arr[i];
        b[arr[i]] = true;
    }

    int diff = tt - t;

    int i;
    for (i = 1; i < diff; i++){
        if (!b[i])
            break;
    }

    cout << i << " & "<< diff - i;
    return 0;
}

ektormelendez on Jan 25, 2017

Add Answers or Comments

To comment on this, Sign In or Sign Up.