Yahoo Interview Question
Software EngineersCountry: United States
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.
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.
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;
}
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])
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...
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
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));
}
}
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
print "total means added",len(means)
max_mean = 0
for x in means:
print x
if x > max_mean:
max_mean = x
print "max mean: ",max_mean
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
print "total means added",len(means)
max_mean = 0
for x in means:
print x
if x > max_mean:
max_mean = x
print "max mean: ",max_mean
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;
}
}
- Vir Pratap Uttam April 12, 2015