## Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

I am sorry. One correction. k^2 ranges from 1 - 10^10.

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

Is there a condition like a != b != k

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

As the question asked for different ordered set, so a!=b. But no condition on k.

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

brute force: a start from 1 to k. Find all a's, we'll automatically get corresponding b's as k2/a. Time complexity is O(k).

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

Time complexity is not O(k). Its O(k^2). you will need to run this loop within another loop which will reach to k itself. Try it.

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

if at all, we could decompose k into its primefactors, say a1^b1,a2^b2....an^bn, then k2 will be a1^2b1,a2^2b2....an^2bn. Now, we need to place n distinct numbers (a1...an) in 2b1+2b2+....+2bn bins ...it's a permutations problem. Someone good in math, pls solve and explain the steps in detail.

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

10^10 is 10 billion! How do you find the prime factors of a number that big AND generate all ordered pairs within 2 seconds?

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

You can definitely factor a number up to 10 billion into prime factors very quickly. Even using a relatively naive method (standard loop to try all factors up to sqrt(n) <= 10^5), you should be able to get all the prime factors in a few milliseconds or so.

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

unsigned long long result = 0;
unsigned long i;
for (i = 1; i<=TEN_OF_FIVE; i++) {
result += TEN_OF_TEN / i;
}
for (i = 1; i<TEN_OF_FIVE; i++) {
result += i * (TEN_OF_TEN/i - TEN_OF_TEN/(i+1));
}

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

Comment:
The problem is same as: count the number of (a, k) that a | k where 1<= k <= N.
The complexity is O(sqrt(N)).

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

can you clarify the problem? k is not given? it is asking for a k which has most sets?

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

I wonder if one thing we're supposed to notice is that if you square 10^10, you exceed the maximum value of even a 64 bit long integer. So, therefore, you should compare sqrt(a*b) to k, as opposed to comparing a*b to k^2. And then you get into floating point math, not integer math, so you should allow for some small difference in the comparison.

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

Let S_k = { (a, b) | a * b = k^2 },

and if k = p_1^r_1 ... p_t^r_t(pow of different primes), then

#S_k = (2 * r_1 + 1) * ... * (2 * r_t + 1).

Just find max (#S_k for all k in 1, ...10^5).

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

O(1) space
O(n) time complexity;

``````void func(int *arr, int n, unsigned int k)
{
long long req = (long long)k * (long long)k;
int i = 0, j = n -1;
bool found = false;
while (i < j) {
long long mul = (long long)arr[i] * (long long)arr[j];
if (mul < req) {
i++;
} else if (mul > req) {
j--;
} else {

found = true;
break;
}
}

if (found == true) {
printf("%d %d\n", arr[i], arr[j]);
} else {
}
}``````

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.

### 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.