Amazon Interview Question: given an integer, output all ... | Glassdoor

Interview Question

Software Engineer Intern Interview(Student Candidate) Pittsburgh, PA

given an integer, output all the prime factors of that

  integer, ex: input: 6, output: 2,3 input 25, output: 5, 5 given an integer array, output all the numbers that appear odd number of times, ex: input: 1,2,1,3,3,4 output: 2, 4

Interview Answer

2 Answers


First one is fairly simple. Here's my code in Python.

    p = []
    for i in range(2,x+1):
    if(x % i == 0):
        while(x % i == 0):
            x = x/i

Runs in linear time.

Anonymous on Feb 21, 2015

There is a solution to the second one in linear time, but that works only if you there is only one element that appears odd number of times.

If there are multiple such elements, you can create a hash table storing frequencies of each element in the array.
Linear time to create hash table
Linear time to traverse it.
Linear space complexity.

Anonymous on Feb 21, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.