Google Interview Question
Software DevelopersCountry: United States
long long approx_cubth_root( long long n) {
long long min = 1, max = n;
long long mid;
while( min < max ) {
mid = min + ( max - min) / 2;
if( mid * mid * mid == n) return mid;
else if( mid * mid * mid < n ) min = mid + 1;
else max = mid - 1;
}
if(min * min * min < n ) return min;
else return max;
}
void print_good_numbers(long long n) {
long long cubth = approx_cubth_root(n);
unordered_set<long long> level1;
set<long long> level2;
for(long long i = 1; i <= cubth + 1; i++) {
for( long long j = i; j <= cubth + 1; j++ ) {
long long cur = i * i * i + j * j * j;
if( cur <= n ) {
if( level1.find( cur) == level1.end()){
level1.insert( cur );
} else{
level1.erase(cur);
level2.insert(cur);
}
}
}
}
for(auto itr = level2.begin(); itr != level2.end(); itr++) {
cout << *itr << " ";
}
cout << "\n";
}
import java.util.*;
public class GoodNumber {
public GoodNumber() {}
public List<Integer> getAllCubes(int n) {
List<Integer> allCubes = new ArrayList<Integer>();
int nextNumber = 1;
int nextCube = 1;
while (nextCube <= n) {
allCubes.add(nextCube);
nextNumber++;
nextCube = nextNumber * nextNumber;
}
return allCubes;
}
public boolean isAGoodNumber(int n) {
List<Integer> allCubes = getAllCubes(n);
int distinctWays = 0;
for(Integer i: allCubes) {
for(Integer j: allCubes){
if ((i+j) == n) {
distinctWays++;
}
if (distinctWays >= 4) return true;
}
}
return false;
}
public List<Integer> getAllGoodNumbers(int n){
List<Integer> allGoodNumbers = new ArrayList<Integer>();
for (int i=1; i<=n; i++){
if(isAGoodNumber(i)) allGoodNumbers.add(i);
}
return allGoodNumbers;
}
public static void main(String a[]) {
GoodNumber gn = new GoodNumber();
List<Integer> inputArr = gn.getAllGoodNumbers(100);
for(int i:inputArr){
System.out.print(i);
System.out.print(" ");
}
}
}
public void getGoodNumbers(int limit) {
List<String> output = new ArrayList<>();
int i = 1;
int jMax = (int) Math.cbrt(limit);
while (i < jMax - 3) {
int j = i + 3;
while (j <= jMax) {
long iCube = i * i * i;
long jCube = j * j * j;
long n = iCube + jCube;
if (n > limit) {
break;
}
// System.out.println("****i,j******");
// System.out.println(i + "\t" + j);
int start = i + 1;
int end = j - 1;
while (start < end) {
// System.out.println("****start,end******");
// System.out.println(start + "\t" + end);
long res = (start * start * start) + (end * end * end);
if (res == n) {
output.add(start + " & " + end + " AND " + i + " & " + j);
break;
} else if (res < n) {
start++;
} else {
end--;
}
}
j++;
}
i++;
}
System.out.println(output);
}
Dynamic answer:
countArray[1 to n] = 0
sumsArray[0 to n] = 0..n
loop ii = 2 to cube root of n
cube = ii^2
loop jj = cube to n
numberSums = 1 + sumsArray[jj-cube+1]
if numberSums == 2
countArray[jj]++
end
if numberSums < table[jj]
table[jj] = numberSums
end
endLoop
endLoop
for ii = 1 to n
if countArray[ii] == 2
display ii
end
end loop
public class Solution {
public static void main(String [] args) {
printGoodNumbers(1000000);
}
public static boolean isGoodNumber(int number, List<Integer> cubes) {
int ways = 0;
for (int i = 0; i < cubes.size(); i++) {
for (int j = i+1; j < cubes.size(); j++) {
if (cubes.get(i) + cubes.get(j) == number) {
ways++;
if (ways == 2) {
return true;
}
}
if (cubes.get(i) + cubes.get(j) > number) {
break;
}
}
}
return false;
}
public static void printGoodNumbers(int limit) {
List<Integer> cubes = new ArrayList<>();
int i = 1;
int cube = 1;
while (cube <= limit) {
cubes.add(cube);
i++;
cube = i * i * i;
}
for (int l = 1; l < limit; l++) {
if (isGoodNumber(l, cubes)) {
System.out.println(l);
}
}
}
}
from itertools import combinations
from collections import defaultdict
def find_good_number(n):
upper_bound = int(n**(1./3.))
cubes = [i**3 for i in xrange(upper_bound + 1)]
sums = defaultdict(list)
for i in combinations(cubes, 2):
sums[sum(i)].append(i)
result = [k for k,v in sums.items() if len(v) > 1 and k <= n]
return result
print find_good_number(5000)
- Roger June 22, 2016