## Yahoo Interview Question for Software Engineer / Developers

• 2

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

I believe it could be done in O(n) as below:

``````//pseudo code
pivot1 points to start of subsequence
pivot2 moves forward accumulating elements
vector sequences to store sequences that match S and P
int maxLength=size(array);

initially pivot1 = pivot2 = 0, sum = array[0], product = array[0].
while(pivot2<size)
++pivot2,
sum = sum+array[pivot2]; product = product*array[pivot2];
while((sum>S || product>P)){ //move pivot1 if sum or product exceeded
sum=sum-array[pivot1]; product = product/array[pivot1]; ++pivot1;
if(pivot1<size) break;
}
add pivot1 and pivot2 to sequences, //i.e. elements between pivot1 and pivot2 satisfy
if(pivot2-pivot1 < maxLength) maxLength = pivot2-pivot1;``````

pivot1 moves n and pivot2 moves n => total is 2n => O(n)

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

This wouldn't work for negative numbers.
For example, a[0] till a[i] may exceed the target in sum and product, but a[i+1] may be negative, so a[0] till a[i+1] may be the solution.

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

``````//!Complexity O(2n+1) = O(n).
//The code is written to demonstrate the algorithm and might fail for certain inputs
#include <iostream>
using namespace std;
int numcomputs = 0;
int main(){
int array[] = {2,3,4,5,4,1,2,3,1,1,1,2,2,4,6,2,2,4,5,1,2,3,8,8};
int S = 21, P = 384,pivot1, pivot2,size = sizeof(array)/sizeof(int);
long sum = 0, product = 0;
int minLength=size,minLenP1 = 0,minLenP2=0;
pivot1 =0; pivot2 = 0; sum = array[0]; product = array[0];

while(pivot2<size){
++pivot2;
sum = sum+array[pivot2]; product = product*array[pivot2];
++numcomputs;
while((sum>S || product>P)){ //move pivot1 if sum or product exceeded
sum=sum-array[pivot1]; product = product/array[pivot1]; ++pivot1;
++numcomputs;
if(pivot1>size) break;
}
if(sum==S && product==P && ((pivot2-pivot1) < minLength)){
if((pivot2-pivot1) < minLength){
minLength = pivot2-pivot1;
minLenP1 = pivot1,minLenP2=pivot2;
}
}
}
if(minLength==size && minLenP1==0 && minLenP2==0)
cout<<"No string found!!"<<endl;
else{
cout<<"Length of sequence: "<<minLength;
cout<<".    array["<<minLenP1<<"] to array["<<minLenP2<<"]"<<endl;
for(;minLenP1<=minLenP2;++minLenP1)
cout<<array[minLenP1]<<" ,";
cout<<endl<<"size of array: "<<size<<", Total number of loopings: "<<numcomputs<<" .";
}

}``````

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

Looks like it has O(n^2) complexity because of inner cycle. Bruteforce has O(n^3) complexity and I haven't found anything better O(n^2).

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

No... There is no worst case for this. There's only one case. O(2n+1) = O(n)
pivot1 and pivot2 can move only forward. pivot1 cannot move beyond pivot2. At a point of time either pivot1 or pivot2 moves. in the inner loop we are not setting pivot1 to 0 every time, pivot1 only increments.

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

Yes, you're right.
It doesn't work for arrays containing 0 and negative numbers, but most likely this is what they meant.

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

@chennavarri
check for this input;
A[]={8,8,16}
S=16;
P=1;
your code is giving wrong answer if there is no such suibarray

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

and there is NO: have to find both SUM and PRODUCT, not only one of them

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

YES. The algorithm checks for both. Please check the code carefully.
The code is written with a purpose of demonstrating a linear algorithm. The code fails for inputs such as empty array and may be other inputs. The code demonstrates that the algorithm gives correct output for a valid input.
Anyways " no string found" case is added

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

Hi, I believe the updated code fails for the following input:

array[] = { 9, 1, 1 };
S = 9;
P = 9;

In fact, it fails whenever the solution involves the first element of the array.

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

gud work chennavarri

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

but YAHOO needs that this problem must run for all cases negative, zero as well as positive numbers too :( :(

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

Can anyone suggest solving this by divide and conquer approach? I mean recursion. THat should do it with more efficiency.

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

Create two more arrays Sum[] and Product[] such that
Sum[i] = a[0]+a[1]+...+a[i]
Product[i] = a[0]*a[1]*...*a[i]

Now for every element in Sum[i] check if Sum[i]-S is present in the sub-array from 0 to i-1. If it is present check if the product also matches using the Product array.

We can decide on how to perform this repetitive search in Sum[i] to be better.

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

guys i think Kadane's algorithm would work just fine for this problem....

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

looks like there are 2 conditions
- A[i] should be a perfect divisor of P
- |curr_product| < |P| every iteration

If any of the above is not true you cannot take that chunk and need to reset curr_start and curr_end = i+1

This is only assuming u have +- integers

If u have array of real numbers then u would need a brute force and then optimization by DP for getting the product or sum

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

assuming positive values

``````int sub_array_with_sum(int s[], int n, int sum, int product)
{
int currentSum, currentProduct;
int i, j;

currentSum = 0;
i = j = 0;
currentProduct = 1;

while(j < n)
{
currentSum += s[j];

if(currentSum < sum)
{
currentProduct *= s[j];
j++;
}
else if(currentSum > sum)
{
if(i == j)
{
i++;
j++;
currentSum = 0;
currentProduct = 1;
}
else
{
currentSum = currentSum - s[i] - s[j];
currentProduct /= s[i];
i++;
}
}
else
{
currentProduct *= s[j];
if(currentProduct == product)
return j-i+1;

currentSum -= s[i];
currentProduct /= s[i];
i++;
j++;
}
}

return -1;
}``````

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

It can be done in O(nlogn)
consider the array {2,-1,3,-4,5,1}
A=cumulative-sum,index = {(2,0),(1,1),(4,0),(0,3),(5,4),(6,5)}
P=cumulative product {2,-2,6,24,120,120}
sort A array on the basis of sum
take two pointers p1=0,p2=0;
and proceed .....

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

There is pretty straight forward solution and goes like what is written below.
1) find sum and product of all contigious elements.
2) Check trivially if any contigious sum, product is same.
3) check for all ranges, j, i such that sum(i - j) = product (i/j). where 0 > j < i & 0 < i < |A|

public void printEqualSumMul(int [] arr) {
int len = arr.length;
int [] sum = new int[len];
int [] mul = new int[len];

for(int i = 1; i < len; i++) {
sum[i] = sum[i-1] + arr[i];
}
for(int i = 1; i < len; i++) {
mul[i] = mul[i-1]*arr[i];
}
//Check if there is any contigious sequence which has same sum and mul
for(int i = 1; i < len; i++) {
if (mul[i] == sum[i]){
System.out.print("Elements with equal sum and mul :" + i + " " + i);
}
}
//Check for any range is having same sum and mul
for(int i = 1; i < len; i++) {
for(int j = 0; j < i; j++) {
if (i == j) continue;
int s = sum[i] - sum [j];
int m = mul[i]/mul[j];
if (s == m) {
System.out.print("Elements with equal sum and mul :" + i + " " + j);
}
}
}
return;
}

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

#include<stdio.h>
#include<conio.h>

int main()
{
int i,j,pro,sum,s=0,num=100000,p1,p2;
int arr[24];
int n=24;
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
scanf("%d%d",&pro,&sum);
int p;
j=0;p=1;
for(i=0;i<24;i++)
{
p=p*arr[i];
if(pro%p==0)
{
s=s+arr[i];
if(pro==p)
if(s==sum)
if(num>(i-j+1))
{ p1=j;p2=i;p=1;s=0;j=i+1; }
else
{
j=i+1;
p=1;
s=0;
}
}
else
{
p=1;s=0;
j=i+1;
}
}
for(i=p1;i<=p2;i++)
printf("%d",arr[i]);
return 0;
getch();
}

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

using Kadane's algorithm , we can find a contiguous sub-array whose sum = S.
Now check if product of sub-array =P.
If yes , then update the variable min_length;
(min_length--> stores the requisite minimum length)

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.