## Yahoo Interview Question for Software Engineers

Country: United States

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

``````package com.algorithm.yahoo;

import java.util.Arrays;

public class Pmean {

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr1 = { 20, 30, 10 };
System.out.println("Pmean1 :- " + Pmeans(arr1));
}

private static int Pmeans(int[] arr1) {
// TODO Auto-generated method stub
Arrays.sort(arr1);
int j = 1;
int result = 0;
for (int i : arr1) {
result += i * j;
j++;
}
return result;
}

}``````

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

Its mentioned that "every rotation of the array". So, sorting the array and calculating PEMAN will not give the correct result. Correct me if I am wrong.

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

It is mentioned "for every rotation of the array", so sorting the array and calculating PMEAN should not give correct result always. correct me if I am wrong.

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

It is mentioned "for every rotation of the array", so sorting the array and calculating PMEAN should not give correct result always. correct me if I am wrong.

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

Suppose that an array(Arr) has 'N' elements {a, b, c, d, e, ....}.
Array indexing starts at 1.

Define S=a+b+c+d+e+.....

We will have
PMEAN1 = a + 2b + 3c + 4d + 5e + .....
PMEAN2 = b + 2c + 3d + 4e + .....+Na
..
..
PMEAN(k)=PMEAN(k-1) - S + N*Arr[k-1]

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

Solution in C++:

``````#include <vector>

int pmean(const std::vector<int> &V)
{
int n = V.size();
int i;
int sum = 0;
int pmean = 0;
int best = 0;

for (i = 0; i < n; ++i) {
sum += V[i];
}

for (i = 0; i < n; ++i) {
pmean += V[i] * (i+1);
}
best = pmean;

for (i = 0; i < (n-1); ++i) {
pmean -= sum;
pmean += V[i] * n;
if (pmean > best) {
best = pmean;
}
}

return best;
}``````

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

Awesome!!

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

can you explain the logic please?

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

PMean[i+1] = PMean[i] - TS + n*A[i]

TS = Total sum of array
A[i] = ith element in the array A

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

sort the array first then apply the calculation.

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

def pmean(array):
sum = 0
for n in range(len(array)):
sum += array[n] * n+1
return sum

def max_pmean(array):
if len(array) == []:
return 0
elif len(array) == 1:
return array[0]
else:
max_p = pmean(array)
for i in range(len(array)):
missing_i_array = array[0:i] + array[i+1:]
p_mean_missing_i_array = max_pmean(missing_i_array)
temp_pmean = p_mean_missing_i_array + len(array)*array[i]
if temp_pmean > max_p:
max_p = temp_pmean
last_number = array[i]
return max_p

print max_pmean([10,20,30])

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

Use Pmean1 and then use the fact that as you rotate left
each value moves to one smaller location.

This means you are multiplying that
number with one less than prev location.
For eg
for PMEAN1 : 10 was multiplied by 3
for PMEAN2 : 10 is multiplied by 2
for PMEAN3 : 10 is multiplied by 1

This means for each successive rotation: you subtract PMEAN by 10.

you do the same for all entries except for the first. As the first moves to the last location
so you multiply that by (index).

Illustratively:

PMEAN1 = 0 + 1*20 + 2*30 + 3*10 = 110
PMEAN2 = 110 + (3-1)*20 - 30 - 10 = 110
and so on...

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

Can you please add two more examples, before so on..? I want to see how you get 140..

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

C++ implementation

``````#include <vector>

size_t MaxSumOfElementsTimeIndicesViaRotation(const std::vector<size_t> input)
{
size_t fPrev = 0;
size_t sum = 0;
size_t index = 1;
for (auto x : input) {
fPrev += x*index;
sum += x;
++index;
}

size_t maxVal = fPrev;
const size_t SizeOfInput = input.size();
size_t fCur;
for (index = 1; index < SizeOfInput; ++index) {
fCur = fPrev + input[index - 1] * SizeOfInput - sum;
if (fCur > maxVal) {
maxVal = fCur;
}
fPrev = fCur;
}

return maxVal;
}``````

See the sub-problem deduction:cpluspluslearning-petert.blogspot.co.uk/2015/02/data-structure-and-algorithm-max-sum-of.html

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

Test:

``````#include <cassert>
void TestCases()
{
{
std::vector<size_t> input = { 1, 2, 3, 4, 5, 6, 7 };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}

{
std::vector<size_t> input = { 2, 3, 4, 5, 6, 7, 1 };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}

{
std::vector<size_t> input = { 3, 4, 5, 6, 7, 1, 2 };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}

{
std::vector<size_t> input = { 4, 5, 6, 7, 1, 2, 3 };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}

{
std::vector<size_t> input = { 5, 6, 7, 1, 2, 3, 4 };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}

{
std::vector<size_t> input = { 6, 7, 1, 2, 3, 4, 5 };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}

{
std::vector<size_t> input = { 7, 1, 2, 3, 4, 5, 6, };
assert(MaxSumOfElementsTimeIndicesViaRotation(input) ==
(1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5 + 6 * 6 + 7 * 7));
}
}``````

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

``````def pMean():
pass
arrayItems = [10,30,20]
sum = 0
arrayItems.insert(0, 0)
arrayItems.sort()
for i in range(len(arrayItems)):
sum += i* arrayItems[i]
print sum

if __name__ == '__main__':
pass

pMean()``````

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

def pMean():
pass
arrayItems = [10,30,20]
sum = 0
arrayItems.insert(0, 0)
arrayItems.sort()
for i in range(len(arrayItems)):
sum += i* arrayItems[i]
print sum

if __name__ == '__main__':
pass

pMean()

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

Pmean max is when the largest value has the largest weight and the next largest has the next largest weight.

By weight I mean index value.

Apply Quicksort to sort the numbers
-Calculate the PMEAN formula

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

``````def pmeans_alt(array_test):

loops  = len(array_test)
pnt = 0;
means = []
while pnt < loops:
total = 0
for i,x in enumerate(array_test):

total += (i+1)*x

means.append(total)
print array_test
##now pop and insert at the beginning
final_element = array_test[loops-1]
array_test.pop()
array_test.insert(0,final_element);
pnt += 1

max_mean = 0
for x in means:
print x
if x > max_mean:
max_mean = x

print "max mean: ",max_mean``````

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

``````def pmeans_alt(array_test):

loops  = len(array_test)
pnt = 0;
means = []
while pnt < loops:
total = 0
for i,x in enumerate(array_test):

total += (i+1)*x

means.append(total)
print array_test
##now pop and insert at the beginning
final_element = array_test[loops-1]
array_test.pop()
array_test.insert(0,final_element);
pnt += 1

max_mean = 0
for x in means:
print x
if x > max_mean:
max_mean = x

print "max mean: ",max_mean``````

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

``````public static int getPMean(int nums[]){
int maxPMeanValue = Integer.MIN_VALUE;
for(int i =0; i<nums.length;i++){
int pmean = calcuateMean(nums, i);
if(pmean > maxPMeanValue){
maxPMeanValue = pmean;
}
}
return maxPMeanValue;
}

private static int calcuateMean(int nums[], int startIndex){
int sum = 0;
int n = nums.length;
for(int i =0; i<nums.length;i++){
sum = sum + (nums[startIndex] *(i+1));
startIndex = (startIndex+1)%n;
}
return sum;
}``````

}

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.