## Adobe Interview Question for Member Technical Staffs

Country: India
Interview Type: In-Person

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

O(n)

1. Find the cube of each number starting from 1 to (n-3) and store in an array.
2. Search the combination of numbers which can sum to n ( I used binary search to do so)

// Use binary search to find the element.
int getIndex(int* data, int start, int end, int num)
{
if ( start < end )
{
if ( data[(start + end)/2] == num )
{
return ((start + end)/2);
}
else if ( data[(start + end)/2] > num )
{
return getIndex(data,start,(start + end)/2, num);
}
else
{
return getIndex(data,(start + end)/2 + 1, end, num);
}
}
else if ( start == end)
{
return data[start] == num ? start : -1;
}
return -1;
}

void printAllCombination(const int num)
{
//std::map<int,int> cube;
const int cubeArrsize = (num/3) + 1;
int *cubeArr = new int[num + 1];

//  Find the cube of each number and store in array.
for ( int i = 1; i< cubeArrsize; i++)
{
cubeArr[i] = i*i*i;
}

// Do a binary search for the remaining number from the given position.
for ( int i = 1; i< cubeArrsize; i++)
{
int j = getIndex(cubeArr, i+1, cubeArrsize,num - cubeArr[i]);
if ( j > 0 )
{
std::cout<<"\n"<<i<<" , "<<j;
}
}
delete[] cubeArr;
}

int main()
{
printAllCombination(224);
std::cout<<std::endl;
getch();
}

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

Why cubarrsize=size/3+1?

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

a = -b
there are infinite pairs

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

O(n) is funny.

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

its O(nlogn) not O(n)

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

O(n) solution using a set

#include <iostream>
#include <set>
#include <cmath>

int main() {
int N = 91;
std::set<long> cubics_set;

// Generating all cubic values between 1 and N
for(int i = 1; i < N; i++) {
cubics_set.insert(std::pow(i, 3));
}

for(auto it = cubics_set.begin(); it != cubics_set.end(); ++it) {
if(*it > N)
break;

long required = N - *it;

if(cubics_set.find(required) != cubics_set.end())
std::cout << "a:" << *it << " "
<< "b:" << required << std::endl;

}

return 0;
}

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

am i loosing it. how come this s "O(n)"!?

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

The Solution is O(n) -- Still can be reduced

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class cubeN {

public static void main(String[] args) {

int sum = 0,l = 1;
HashMap<Integer,Integer> hm  = new HashMap<Integer,Integer>();

System.out.println("Enter the Value of N :");
Scanner s = new Scanner(System.in);

int n = s.nextInt();

for(int j = 0; j < n; j++){

sum = j*j*j;
hm.put(sum,j);
}

Set set = hm.entrySet();
Iterator i = set.iterator();

while(i.hasNext()){

Map.Entry me = (Map.Entry)i.next();
int Value = n - (Integer) me.getKey();
int num1 = (Integer)me.getValue();

if(hm.containsKey(Value)){
int num2 = hm.get(Value);
System.out.println("Combination -"+l+" "+num1+","+num2);
l++;

}

}

}

}

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

solution in python

import math

def find_sol(a, b, N):

# solution
if (pow(a, 3)  + pow(b, 3) == N):
return 1
# over solution
elif (pow(a, 3)  + pow(b, 3) > N):
return 0
# under solution
else:
return (find_sol(a + 1, b, N) + find_sol(a, b + 1, N)

if __name__ == '__main__':
N = 2 # or some other value
num_sol = find_sol(0,0,N)
num_sol/=2

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

Can we use binary search in this?
max value for this a^3 + b^3 will be N and mininum value will be 0.
I am sure the below code is not going to work for some cases but right now not able to figure out.
So search will be like this:

#include <math.h>
int power(int no, int power)
{
int sum = 1;int i;
for(i=0;i<power;i++) {
sum = sum*no;
}
return sum;
}

void bsearch(int low, int high, int no) {
printf("low %d high %d\n", low, high);
/* base cases */
if(low < 0 || high > no || high < 0 || low > no)
return;
if(power(low, 3) + power(high, 3) == no) {
printf("%d %d\n", low, high);
return;
} else if(power(low, 3) + power(high, 3) >= no) {
bsearch(low, high-1, no);
} else
bsearch(low+1, high, no);
}

int main()
{
bsearch(0, 9/2, 9);
}

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

initialize i =1 and j=N-1

put loop condition while(i<j)
{
if(i^3 + j^3 >N)
--j;
elseif(i^3 + j^3 <N)
++i;
else
cout<<i<<j;
++i;--j;

thats all
O(N) time.

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

Could be done in O(N^(1/3)) (cubic root).

for (int a = 0; a * a * a <= N; ++a) {
int b3 = N - a * a * a;
int b = (int)pow((double)b3, 1. / 3.); // That could be done manually with binary search or something else.
/* Here we can check close ints to be sure with precision errors */
bool is_cubic_root = false;
int mem = -1;
for (int delta = -2; delta <= 2; ++delta) if (pow3(b + delta) == b3) is_cubic_root = true, mem = b + delta;
if (is_cubic_root) {
cout << a << ' ' << mem << endl;
}
}

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

function findCubedPairs(n) { // assume n > 0
var powers = {};
var result = [];
for (var i = 0; i < n; i++) {
powers[i * i * i] = i;
}

for (var i = 0; i < n; i++) {
var a = i;
var aCubed = i*i*i;
var bCubed = n - aCubed;
var b;
var neg = 1;

if (bCubed < 0) {
neg = -1;
}

var b = powers[bCubed * neg];

if (powers[bCubed * neg]) {
if (neg === -1) {
result.push([a, -b]);
result.push([-a, b]);
} else {
result.push([a, b]);
}
}
}

return result;
}

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

void PrintAllCombination(int iNumber)
{
//To reduce the number of iterations.....
int iMaxLimit = pow((double)iNumber, (double)1/3.) + 0.5 ;

int iA, iB;

int iLoopCounter = 0;
int iFirstVal;

//If the cube of the value is equal to number then again we are adding some value in to it, that will be waste of iteration & time.
for( iA = 0; iA <= iMaxLimit; iA ++ )
{
//Calculating to reduce the multiplication process again & again.
iFirstVal = iA * iA * iA;
for( iB = 0; iB <= iMaxLimit; iB ++ )
{
if( iFirstVal + iB * iB * iB == iNumber )
printf("A := %d B := %d\n", iA, iB);

iLoopCounter ++;
}
}

printf("Total Iteration:%d", iLoopCounter);
}

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

Here is the optimized code that will take less time to compute the combination... please comment if I missed anything..
void PrintAllCombination(int iNumber)
{
//To reduce the number of iterations.....
int iMaxLimit = pow((double)iNumber, (double)1/3.) + 0.5 ;

int iA, iB;

int iLoopCounter = 0;
int iFirstVal;

//If the cube of the value is equal to number then again we are adding some value in to it, that will be waste of iteration & time.
for( iA = 0; iA <= iMaxLimit; iA ++ )
{
//Calculating to reduce the multiplication process again & again.
iFirstVal = iA * iA * iA;
for( iB = 0; iB <= iMaxLimit; iB ++ )
{
if( iFirstVal + iB * iB * iB == iNumber )
printf("A := %d B := %d\n", iA, iB);

iLoopCounter ++;
}
}

printf("Total Iteration:%d", iLoopCounter);
}

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

#include<iostream>
#include<string>
#include<math.h>
#include<stdlib.h>
using namespace std;
int main()
{
double N,t;
cin >> N;
int i;
for(i=0;i<N/2;i++)
{
t=(double)(cbrt(N-pow(i,3)));
if(t-ceil(t)==0)
{
cout<<"a is : "<<t<<" b is : " << i << endl;
}
}
}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

import static java.lang.System.exit;
import java.util.Scanner;

public class Number {

int a, b;

Number() {
a = 0;
b = 0;

}

public int[] findAB(int n) {
int sum = 0;
int i;
int j;

for (i = 0; i < 1000; i++) {
for (j = 0; j < 1000; j++) {
sum = i * i * i + j * j * j;
if(sum==n){
System.out.println(i+" , "+j);

}
}
}
return null;

}

public static void main(String args[]) {
int n;
Number num = new Number();
Scanner in = new Scanner(System.in);
n = in.nextInt();
num.findAB(n);
}

}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

import static java.lang.System.exit;
import java.util.Scanner;

public class Number {

int a, b;

Number() {
a = 0;
b = 0;

}

public int[] findAB(int n) {
int sum = 0;
int i;
int j;

for (a = 0; a < 1000; a++) {
for (b = 0; b < 1000; b++) {
sum = a * a * a + b * b * b;
if(sum==n){
System.out.println(a+" , "+b);

}
}
}
return null;

}

public static void main(String args[]) {
int n;
Number num = new Number();
Scanner in = new Scanner(System.in);
n = in.nextInt();
num.findAB(n);
}

}

}

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

#include <stdio.h>

main()
{
int a,b,i,j,k=0;
printf("enter no.");
scanf("%d",&N);

for(a=0;a<N;a++)
{
if((a*a*a)>N)
{
a--;
break;
}
k++;
}

for(i=a;i>=0;i--)
{
for(j=0;j<=a;j++)
{
if(((i*i*i)+(j*j*j))==N)
printf("%d,%d\n",i,j);
if(((i*i*i)+(j*j*j))>N)
break;
}
k++;
}
printf("\nnumber of comparison %d\n",k);
}

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.