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

- Ricky January 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why cubarrsize=size/3+1?

- aka January 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about N = 0
a = -b
there are infinite pairs

- Anonymous February 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n) is funny.

- Anonymous February 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

its O(nlogn) not O(n)

- desicoder May 31, 2014 | Flag
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;
}

- Felipe Cerqueira January 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 14, 2014 | Flag
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++;
				
			}		
			
		}	

	}

}

- careeradmirer January 31, 2014 | Flag Reply
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

- Nino Tokuda January 31, 2014 | Flag Reply
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);
}

- aka January 31, 2014 | Flag Reply
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.

- Nascent January 31, 2014 | Flag Reply
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;
  }
}

- Alex February 01, 2014 | Flag Reply
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;
}

- overload119 February 02, 2014 | Flag Reply
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);	
}

- Kuber Saini February 12, 2014 | Flag Reply
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);	
}

- kuber February 12, 2014 | Flag Reply
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;
}
}
}

- Xiaoyu August 19, 2014 | Flag Reply
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);
    }

}

- Karthik Thamatam January 30, 2014 | Flag Reply
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);
    }

}

}

- Anonymous January 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- dilkash.rocks May 04, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More