Amazon Interview Question SDE1s
Country: United States
Interview Type: Phone Interview
As long as a > b, there is no optimization
as the sequence goes down there is a symmetric behaviour
EX: a = 7 b =6
EX: a = 7 b =6
(7 6)
(7 5)
(7 4)
(7 3)
(7 2)
(7 1)
-----------
(6 5) (5 6)
(6 4) (4 6)
(6 1) (1 6)
-----------
(5 6) = > Already listed No need to compute in line 9
(5 4) (4 5)
(5 3) (3 5)
(5 2) (2 5)
(5 1) (1 5)
-----------
(4 6) = > Already listed No need to compute in line 10
(4 5) = > Already listed No need to compute in line 14
(4 3) (3 4)
(4 1) (1 4)
-----------
(3 5) = > Already listed No need to compute in line 15
(3 4) = > Already listed No need to compute in line 21
(3 2) (2 3)
(3 1) (1 3)
-----------
(2 5) = > Already listed No need to compute in line 16
(2 3) = > Already listed No need to compute in line 26
(2 1) (1 2)
-----------
(1 6) = > Already listed No need to compute in line 11
(1 5) = > Already listed No need to compute in line 17
(1 4) = > Already listed No need to compute in line 22
(1 3) = > Already listed No need to compute in line 27
(1 2) = > Already listed No need to compute in line 31
(1 1)
So if you think of a 2D array of a x b element
let T indicates valid pair and F indicates not valid
all A[1,i] {i = 0 to b-1} is 'T'
all A[i, 1] {i = 0 to a-1} is 'T'
all A[i,j] {i = j} is 'F'
Now compute all T & F for a > b
when a becomes b, its symmetric. ie A[i,j] = A[j,i] so compute only for the upper or lower triangle.
Why not, if you use the list of all primes less than a, and list of all primes less than b.
Then you iterate to generate all factorizations of number less than a.
The next step, harder is for each factorization of number less than a you find all factorizations of number less than b with no common prime as in the candidate from a. You can brute force this with increasing or decreasing trial value.
This will optimize a lot because the stepping in the tree is no longer just 1 like your matrix. There is no duplication, because your trial goes in order (increase or decrease(
Do they allow us to have a list of all primes under 10^5
- Anonymous June 02, 2014