## Interview Question for SDE1s

• 1
of 1 vote

Country: United States
Interview Type: Written Test

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

I redid the solution... now the O(n^3)
Optimizations
1 like that of @hrabryi found the limits for c, b, d dynamically (improvement in best case Ω and average case Θ, but not in worst case O, still O(n^4))
2 did away with looping a from 0 to 10000 since we can assume that a from calculating

``a = s-(b^2 + c^3 + d^4)``

and we can check if for given b, c, d inferred a is in 0 to 10000
this gives us O(n^3) the solution is as follows

``````public static void main(String[] args) {
System.out.print("Enter the value s (0<=s<=10^15) : ");
long s = (new Scanner(System.in)).nextLong();
System.out.println("The count of integrals is " + countOfIntegrals(s));
}

private static long countOfIntegrals(long s) {
long count = 0;
long lb, lc, ld, cp3, dp4;
ld = Math.min(root(s, 4), 10000);
for (int d = 0; d <= ld; d++) {
dp4 = pow(d, 4);
lc = Math.min(root(s - dp4, 3), 10000);
for (int c = 0; c <= lc; c++) {
cp3 = pow(c, 3);
lb = Math.min(root(s - dp4 - cp3, 2), 10000);
for (int b = 0; b <= lb; b++) {
long a = s - (pow(b, 2) + cp3 + dp4);
if (a < 10001 && a > -1) {
System.out.println(a + " " + b + " " + c + " " + d);
count++;
}
}
}
}
return count;
}

private static long pow(int n, int p) {
return p > 1 ? n * pow(n, p - 1) : n;
}

private static long root(long s, int pow) {
return (long) Math.floor(Math.exp(Math.log(s) / pow)) + 1;
}``````

other smaller optimizations only to adjust working code for java

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

@Peyar : I have edited the question and provided sample input. Can you share your view how can we achieve that.Actually all the solutions with sum less than S can be included

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

if we need to include for all solutions in 0 to s then we need to add not just 1 per a we find, we need to add 1 for each 0 to a for every a we find i.e. a+1 to count.

the only place were this might be false is when a>10000 in that case we need to add 10001 to count
the modified code will be this

``````if (a > -1) {
System.out.println("a=0to" + a + " b=" + b + " c=" + c + " d=" + d);
count += Math.min(a + 1, 10001);
}``````

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

Thanks Peyar! It worked.
One more question,for ranges of the loop of b,c,d, can't we directly do like @hrabryi has done or like you did in your previous answer of O(n^4)? I am not able to understand the use of root function here

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

the root function does the same as s**1/2or3or4(python) in java there is no direct function to do so had to implement it in code

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

something like this should work but note that the time complexity is O(n^4)

``````public static void main(String[] args) {
System.out.print("Enter the value s (0<=s<=10^15) : ");
long s = (new Scanner(System.in)).nextLong();
System.out.println("The count of integrals is " + countOfIntegrals(s));
}

private static long countOfIntegrals(long s) {
long count = 0, pb2, pc3;
int a, b, c, d;
for (a = 0; a <= s && a < 10001; a++)
for (b = 0, pb2 = a + pow(b, 2); pb2 <= s && b < 10001; pb2 = a + pow(++b, 2))
for (c = 0, pc3 = pb2 + pow(c, 3); pc3 <= s && c < 10001; pc3 = pb2 + pow(++c, 3))
for (d = 0; d < 10001; d++)
if (pc3 + pow(d, 4) == s) {
System.out.println(a + " " + b + " " + c + " " + d);
count++;
break;
}
return count;
}

private static long pow(int n, int p) {
return p > 1 ? n * pow(n, p - 1) : n;
}``````

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

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

Python solution. You can limit the numbers, so the solution will be better than O(N^3)

{{def find_nums(S):
max_a = min(S, 10000)
max_b = min(S**(1/2), 10000)
max_c = min(S**(1/3), 10000)
max_d = min(S ** (1/4), 10000)
for a in range(max_a):
for b in range(int(max_b)+1):
for c in range(int(max_c)+1):
for d in range(int(max_d)+1):
if a + b ** 2 + c ** 3 + d ** 4 <= S:
print(a, b, c, d)}}

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

Python solution. You can limit the numbers, so the solution will be better than O(N^3)

``````def find_nums(S):
max_a = min(S, 10000)
max_b = min(S**(1/2), 10000)
max_c = min(S**(1/3), 10000)
max_d = min(S ** (1/4), 10000)
for a in range(max_a):
for b in range(int(max_b)+1):
for c in range(int(max_c)+1):
for d in range(int(max_d)+1):
if a + b ** 2 + c ** 3 + d ** 4 <= S:
print(a, b, c, d)``````

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

four for loops is being used and so the complexity is still O(n^4)...

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

Can be done in O(n^2 log (n^2)) time, O(n^2) space by meet in the middle.

I would be shocked if this was a real phone interview question so I am not going to provide code.

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

It was a written test...sorry i did not check that while posting the question.
Can you please explain you algo in steps or give pseudo-code ?
Thanks

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

Find and sort all combinations of a + b^2 (including duplicates).

For combinations of N = c^3 + d^4 where N<= S, binary search this sorted list for S-N, and the index is the number of solutions. Sum these indexes.

thank u, next

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.