0
\$\begingroup\$

Given a int optimumMemory and int[] array with list of available memories find the pair of indexes of memories whose sum of the values will be equal to the optimumMemory?

If there exists more than one such pair whose sum of values are equal to the optimumMemory then filter out the indexes for the below conditions

condition1: find the pair of indices which has maximumMemory

condition2: If there exists 2 pairs with same maximumMemory then select the pair with lowest index

Example: int optimumMemory = 10MB int[] availableMemories= [6,3,8,1,1,4,9,2,9,7]

The pair of indices whose sum is equal to 10MB ={(0,5),(1,9),(2,7),(3,6),(3,8),(4,6),(4,8)};

applying condition1 to the above list ={(3,6),(3,8),(4,6),(4,8)};

applying condition2 to the above list will result in only one order pair = {(3,6)}

import com.sun.tools.javac.util.Pair;

public class Test(){

public static void main(String[] args){
         int optimumMemory = 10;
         int[] list = new int[]{6,3,8,1,1,4,9,2,9,7};       
         Pair<Integer,Integer> result = new Pair<>(Integer.MIN_VALUE,Integer.MIN_VALUE);
         //2 pointer approach
         for(int i=0;i<list.length;i++){
            for(int j=i+1;j<list.length;j++){
                //checking if the sum of memory is equal to optimumMemory
                if(list[i]+list[j] == optimumMemory){
                    Pair<Integer,Integer> pair = new Pair<>(i,j);
                    //this happens only once, when the very first pair that satisfies the condition is found
                    if(result.fst==Integer.MIN_VALUE && result.snd == Integer.MIN_VALUE)
                    {
                        result = pair;
                        continue;
                    }
                    int maximumMemoryInResult = Math.max(list[result.fst],list[result.snd]);
                    int maximumMemoryInPair = Math.max(list[pair.fst],list[pair.snd]);
                    //applying **condition1**
                    if(maximumMemoryInResult < maximumMemoryInPair){
                        result = pair;
                        continue;
                    }//end of condition1
                    //applying **condition2**
                    else if(maximumMemoryInResult == maximumMemoryInPair){
                        int minIndexInResult = Math.min(result.fst,result.snd);
                        int minIndexInPair = Math.min(pair.fst,pair.snd);
                        if(minIndexInPair<minIndexInResult){
                            result = pair;
                            continue;
                        }
                    }//end of condition2
                }
            }//end of j loop
        }// end of i loop
   }// end of main method
}

Is there any way to improve the code I posted?

\$\endgroup\$
7
  • 1
    \$\begingroup\$ You can at least try and indent correctly, introduce some methods and make it runnable code, right? \$\endgroup\$ Jan 23, 2021 at 23:06
  • \$\begingroup\$ Where is your "Pair" implementation? \$\endgroup\$ Jan 23, 2021 at 23:13
  • \$\begingroup\$ I used Pair class that is available in the core Java libraries \$\endgroup\$
    – teja sri
    Jan 23, 2021 at 23:24
  • 2
    \$\begingroup\$ Alright. Maybe you can change the title of your question though, as asking for a better coding practice is way too generic for Code Review :) \$\endgroup\$ Jan 24, 2021 at 2:19
  • 1
    \$\begingroup\$ The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How do I ask a good question?. \$\endgroup\$
    – BCdotWEB
    Jan 24, 2021 at 12:14

1 Answer 1

1
\$\begingroup\$

First, lets show how I'd solve this. Of course, I've got a bit more experience with classes and such.

Note that I have left out quite a few checks, e.g. of negative sizes, invalid references and MemoryReferences without references.

package com.stackexchange.codereview;

import java.util.Optional;

public class Memories {

    public static class MemoryReferences implements Comparable<MemoryReferences> {
        
        private int[] memorySizes;
        private int[] refs;

        public MemoryReferences(int[] list, int ... refs) {
            this.memorySizes = list;
            this.refs = refs;
        }
        
        public int totalMemory() {
            int total = 0;
            for (int ref : refs) {
                total += memorySizes[ref];
            }
            return total;
        }
        
        private int refWithMax() {
            int refWithMax = refs[0];
            int max = memorySizes[refWithMax];
            for (int refIndex = 1; refIndex < refs.length; refIndex++) {
                int curRef = refs[refIndex];
                int curValue = memorySizes[curRef]; 
                if (curValue > max) {
                    refWithMax = curRef;
                    max = curValue;
                }
            }
            return refWithMax;
        }

        @Override
        public int compareTo(MemoryReferences that) {
            int totalCompared = Integer.compare(this.totalMemory(), that.totalMemory());
            if (totalCompared != 0) {
                return totalCompared;
            }
            
            return Integer.compare(memorySizes[this.refWithMax()], memorySizes[that.refWithMax()]);
        }
        
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int ref : refs) {
                if (sb.length() != 0) {
                    sb.append(", ");
                }
                sb.append(Integer.toString(ref));
            }
            
            return sb.toString();
        }
    }
    
    public static Optional<MemoryReferences> getLocationsWithOptimumMemory(int[] memorySizes, int optimumMemory) {
        Optional<MemoryReferences> optMem = Optional.empty();
        
        for (int i = 0; i < memorySizes.length; i++) {
            for (int j = i + 1; j < memorySizes.length; j++) {
                MemoryReferences curMem = new MemoryReferences(memorySizes, i, j);
                
                if (curMem.totalMemory() == optimumMemory) {
                    if (optMem.isEmpty()) {
                        optMem = Optional.of(curMem);
                    } else if (curMem.compareTo(optMem.get()) > 0) {
                        optMem = Optional.of(curMem);
                    }
                }
            } 
        }
        return optMem;
    }

    public static void main(String[] args) {
        {
            int optimumMemory = 10;
            int[] memorySizes = new int[] { 6, 3, 8, 1, 1, 4, 9, 2, 9, 7 };

            Optional<MemoryReferences> optMem = getLocationsWithOptimumMemory(memorySizes, optimumMemory);
            
            if (optMem.isPresent()) {
                System.out.println(optMem.get());
            }            
        }
    }
}

The main idea of this class is to get rid of the overly complex code within the loops and if statements.

It uses a little trick by referencing memorySizes (previously list). As it is a reference, it won't actually consume any additional memory. Instead of making it a pair I allowed any number of references as it was actually easier to program it that way.

It's slightly slow because it always calculates the total and such but hey, maybe memorySizes changes dynamically, right? It implements Comparable to look for the best option out there.


Great, that out of the way, let's do the review:

First of all, there is way too little white-space in the code, compare your code with mine, e.g. put spaces between the memory sizes in list.

import com.sun.tools.javac.util.Pair;

That's a Java implementation class. You should never use any classes within com.sun packages unless they have explicitly been indicated as being a public API.

int[] list = new int[]{6,3,8,1,1,4,9,2,9,7};

Please don't call an array list. And always name containers after the elements they contain.

Pair<Integer,Integer> result = new Pair<>(Integer.MIN_VALUE,Integer.MIN_VALUE);

Never use magics to indicate a bad result. Use null if you have to. But now the result will be set to this result if there isn't an optimalMemory. That's not correct, how are you going to check this?

Pair<Integer,Integer> pair = new Pair<>(i,j);

Again with the naming, what does pair mean, and a pair of what? At least call it pairOfReferences or curPairOfReferences. Don't be afraid of longer names, as long as they are functional.

 //this happens only once, when the very first pair that satisfies the condition is found

Great comment, very helpful. However it would be even better if you can code in such a way that such comments are not needed at all (hence my use of Optional in the code above).

int maximumMemoryInResult = Math.max(list[result.fst],list[result.snd]);
int maximumMemoryInPair = Math.max(list[pair.fst],list[pair.snd]);

Here you show a much better control over variable names, great!

else if(maximumMemoryInResult == maximumMemoryInPair){

Do you really need the confusing else if you just did a continue on the previous line?

int minIndexInResult = Math.min(result.fst,result.snd);
int minIndexInPair = Math.min(pair.fst,pair.snd);

Think about this: when will result.snd ever be smaller than result.fst? Same for pair?

        continue;
    }
}//end of condition2

Yeah, that continue is a bit wasted on me, we're at the end anyway.

}// end of main method

I personally dislike end of line comments with a passion. But besides that, loops and if statements should not need them to indicate where they end. You can do that by moving code out of the loop.

\$\endgroup\$
3
  • \$\begingroup\$ Thank-you for the reply \$\endgroup\$
    – teja sri
    Jan 24, 2021 at 3:42
  • \$\begingroup\$ "At least call it pairOfReferences or curPairOfReferences" For many cases I'd even go further: Pairs are often horrible to understand (not only in Java) when re-reading even own code. If not quite closely located and used to according semantic types like maps, you often have to think about them at least twice again and again. Self-explaining classes/structs are often the better alternative here I think. \$\endgroup\$
    – Secundi
    Jan 24, 2021 at 13:32
  • \$\begingroup\$ Yeah, that's kind of why I created just such a thing. They don't scale either. \$\endgroup\$ Jan 24, 2021 at 15:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.