CareerCup

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

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;
}

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)}}

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)

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.