Cover image for Apple
Logo
See All Photos

Apple

Engaged Employer

Apple

Add an Interview

Interview Question

Senior Software Engineer Interview

-

Apple

In a stream of integers from 1 to n, only one number will be repeated. How can you tell what that number is?

Interview Answers

11 Answers

21

You know n. S = n*(n+1)/2 is the sum of 1st n numbers. P = sum of the n+1 numbers you are provided with. Finding P given an array of n+1 integers can be done in O(n). P - S is the repeated integer.

Anonymous on

1

If you're writing it in ruby def find_repeat(numbers) numbers.length.times{|n| return numbers[n] if numbers[n] != n } end

Anonymous on

0

Mat, try 1,2,2,3: 1+2+2+3= 8 1^2^2^3= 2 (8-2)/2=3?2

OZone on

0

Add to HashSet. It will return true if it exists.

Anonymous on

0

Add each integer to the map if it doesn’t already exist as key if it’s exists then it is a repeated number.

Anonymous on

1

lmao, ok everyone getting a little craycray, why not just simply this.... int prev << stream; while (stream) { int curr << stream; if curr == prev return else prev = curr; }

notorious on

0

(sum_of_numbers - (n*(n-1)/2))

Anonymous on

0

A hash table would resolve the question with O(n)

Jobhunter on

3

int sum = 0; int xorSum = 0; for(int i =0 ; i < n; i++) { sum += input[i]; xorSum ^= input[i] } return (sum - xorSum)/2;

Mat on

1

This felt like a brain teaser question to me, and since I hadn't heard it before it took me a little while to come up with a solution that involved using a factorial function.

Anonymous on

2

Heres an explanation, http://www.techinterview.org/post/526329049/sum-it-up

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.

Apple Careers

Cover image for Apple

An open invitation to open minds. Come to Apple, where thousands of individual imaginations gather together to pave the way to...More

  • Life at Apple
  • Areas of Work
  • Apple Retail
  • Students
This is the employer's chance to tell you why you should work for them. The information provided is from their perspective.