4

Say there is a vector of int. Now we want to merge such that , we select 2 adjacent element v[I] and v[I+1] ( for each valid I ) and do v[I] = v[I+1] + v[I] . And erase v[I+1]. Keep on doing this until you're just left with one element in the vector.(Note I=0 & I=v.size()-1 are also considered as adjacent ). so we need to try all such possible combination(i.e which pair we took first and merged matters if further clarification required please let me know in the comment)

where every time we merge we do cost+= v[I] + v[I+1].Goal is to minimise cost.Take an example say vector is 1 2 3. merging [1 2 3]-> [3,3] & cost=3 -> [6] & cost=9 another way [1 2 3]-> [1,5] & cost=5 -> [6] & cost=11 . So is their any algorithm to generate all permutation with given constrain ?

#include<bits/stdc++.h>
using namespace std;
int mn =INT_MAX;
void r(vector<int > v, int sum)
{
    if(v.size()==1){if( mn >sum) mn=sum; return ;}

    for(int i=0;i<v.size();i++)
    {
        sum+=v[i]+v[(i+1)%v.size()];
        v[i]=v[i]+v[(i+1)%v.size()];
        v.erase(v.begin()+(i+1)%v.size());
        r(v,sum);
    }
}
int main()
{
   vector<int> v;//suppose we gave some input to our vector 

   r(v,0);
   cout<<mn;
return 0;

}
#if you have a better solution, do state it, thankyou!
Ram Prabodh Induri
  • 95
  • 1
  • 11
  • Are you looking for any algorithm to determine minimum cost, including brute force? Or is this about optimisation? – Yunnosch Jul 13 '19 at 06:37
  • Showing code is very appreciated, but what purpose does showing serve? Is it one solution? Does it have a problem? Which one? – Yunnosch Jul 13 '19 at 06:39
  • You seem to use the global `mn` to return the result from the recursive function `r`. Why don't you use a return value? – Yunnosch Jul 13 '19 at 06:41
  • Using speaking, self-explaining names for variables and funcitons usually helps with understanding code, including your own code. – Yunnosch Jul 13 '19 at 06:42
  • 1
    https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h – Yunnosch Jul 13 '19 at 06:43
  • Yes, I'm trying to know if there's a way to come up with the best solution efficiently, i.e an algorithm with best time and space complexity. I've shown the code so that people might come up with ways I can make that code more efficient. – Ram Prabodh Induri Jul 13 '19 at 06:45
  • Please state whether this is a homework assignment or an exam question. If it is please have a look at the compromise described here: https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions – Yunnosch Jul 13 '19 at 06:45
  • Please [edit] your question to explain that it is a solution and needs optimisation. Also explain what you want to achieve by optimising it. What requirement needs to be achieved by the optimisaiton? Higher speed? Lower memory consumption? For which cases? Long input vector? Short input vector? Random nput vector? Input vector sorted by size (as in your example)? Making a teacher give a better grade for the homework? – Yunnosch Jul 13 '19 at 06:49
  • This is a practice question on one of the coding websites. – Ram Prabodh Induri Jul 13 '19 at 06:51
  • So why optimise? – Yunnosch Jul 13 '19 at 06:51
  • The thing is, I'm preparing for intern interviews, so I'm trying to find ways to optimize my code.Just trying to know if there are ways to write better functioning code. – Ram Prabodh Induri Jul 13 '19 at 06:54
  • You need to optimise for a certain cost. Trying to optimise for duration AND size is usually hard to impossible. The only possibility is when you have wasted both to begin with. Please read this, because I think your question might fit better there https://codereview.meta.stackexchange.com/questions/5777/a-guide-to-code-review-for-stack-overflow-users – Yunnosch Jul 13 '19 at 06:58
  • For impressing interviewers, who most likely are looking for people who can write easily readable code, you might have best success with the first comments I wrote. I.e. explain better what your code does. Stop using global variables. Improve naming of identifiers, stop questionable habits and become aware of when to optimise and for what purpose. – Yunnosch Jul 13 '19 at 07:02
  • Please excuse me if this sounds cynical, but consider changing your title to "How to impress interviewers with my coding?". I think it is what you are actually asking and it is an interesting question. (Might be a duplicate though, let's see what others think.) – Yunnosch Jul 13 '19 at 07:09
  • Do not leave quotation marks dangling. Find descriptive short titles. – greybeard Jul 13 '19 at 11:24

1 Answers1

5

Your goal is to impress interviewers.
They are looking for people who can work in teams and can make reusable code, which can be handed over to colleagues when needing to be switched to a different topic to work on.

For that, learn to

  • get into the habit of explaing your code, i.e. write useful comments
    • write comments according to "if code and comment do not match, both are probably in error"
    • write comments according to "my comments help me to understand my own code after I return from a three month vacation on an island without computers"
  • stop using global variables, at least instead of return values
  • use self-explaining identifiers for variables and functions
  • have a look through StackOverflow questions for questionable habits to abolish (e.g. Why should I not #include <bits/stdc++.h>? )
  • learn when to optimise, it usually does not pay to optimise when not needed
  • learn to optimise for a certain purpose
Yunnosch
  • 26,130
  • 9
  • 42
  • 54