-1
\$\begingroup\$

I need some assistance in reviewing the following code. I just need to understand what can be done to improve the code with an understanding that logic will be used to create the function that generates the 4 largest integers from a list of integers. The function that returns the 4 largest integers should not included library functions, but pure logic.

package largestFourNumbers;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class largestFNumbers {
/**
 * Assignment
   Write a function that takes a list of integers and returns the 4 highest in O(n) time. 
   We'd like to see how you think about algorithms and data structures. 
   So please use your own logic instead of calling out to libraries.
 * @param arrayofintegers
 * @return
 */
public static int[] highIntegers(int[] arrayofintegers ) {
    int[] temparray = new int[4];                               // Array to contain the return list of the 4 largest 
                                                            // integers in the list
    int arrayofintegerslength = arrayofintegers.length;         // The value that contains the length of the array
if ( arrayofintegerslength <= 4 ) return arrayofintegers;   // If the array is empty or size of array is less than 5
                                                            // then there are no values to provided or the array already 
                                                            // has 4 largest integers. An empty is returned if the size is 0.
temparray[0] = arrayofintegers[0];                          // The following is assigned, since by default the 
                                                            // array is set to all zeros. This will cause an 
                                                            // issue when negative integers. Assigning the first 
                                                            // value from the array will ensure that the 
                                                            // comparison is completed with the remaining elements
                                                            // in the array. 

for(int x = 1; x < arrayofintegerslength; x++ ) {
    if ( arrayofintegers[x] > temparray[0] ) {
        temparray[3] = temparray[2];
        temparray[2] = temparray[1];
        temparray[1] = temparray[0];
        temparray[0] = arrayofintegers[x];          
    }
    if ( arrayofintegers[x] < temparray[0] && arrayofintegers[x] > temparray[1] ) {
        temparray[3] = temparray[2];
        temparray[2] = temparray[1];
        temparray[1] = arrayofintegers[x];
    }
    if ( arrayofintegers[x] < temparray[1] && arrayofintegers[x] > temparray[2] ) {
        temparray[3] = temparray[2];
        temparray[2] = arrayofintegers[x];
    }
    if ( arrayofintegers[x] < temparray[2] && arrayofintegers[x] > temparray[3] ) {
        temparray[3] = arrayofintegers[x];
    }
}
return temparray;
}
/**
 * The following is the main program that executes different test cases for the defined requested function
 * The main program will call the function and execute against multiple array lists.
 * The program has also been designed to capture a list of integers from the console and execute the 
 * same function. A list of comma separated integers must be enter at the console for the program to work as 
 * required. To implement the test portion of the code, please pass debug as a parameter to the main program 
 * via command line to execute debugging. 
 * @param args
 */
public static void main(String[] args) {
    // The originalset contains the integer set of integers that will be tested to ensure the function 
    // executes the task as requested 
   boolean debug = false;
   if ( args.length > 0) debug = (args[0].contains("debug")) ? true : false;
   if ( debug ) {
       int[][] originalset = {{-17,1,2,3,4,5,-6},{-17,1,2,3,-4,5,-6},{-1,1,2,3,4,5,-6},
                               {1,1,2,3,4,5},{6,8,0,10},{0,0,0,0,5},{},{0},
                               {11,14,23,33,-10,24,54,66}, {100,124,4302,232,324,2442,-1,224434,4353,234}, 
                               {-17,-23,-45,-9,-8,-11}, 
                               {-1,-3,5,78,20,300,40,-50,1000,21000,100,124,4302,232,324,2442,-1,224434,4353,234}};
       for (int[] testcase : originalset ) {
           System.out.println("The following is the largest 4 numbers");
           for(int valueinarray : highIntegers(testcase))  System.out.print(valueinarray + " ");
           System.out.println();
       }
  }else {
  System.out.println("Please enter a list of integers separated by commas to determine the 4 largest values?");
  System.out.println(" ");

  try( BufferedReader br = new BufferedReader(new InputStreamReader(System.in)) ) {
          String[] myIntegers = br.readLine().replace(" ","").split(",");
          int myIntegersLength = myIntegers.length;
          int[] myIntegersForFunction  = new int[myIntegersLength];           
          for(int x = 0; x < myIntegersLength; x++ ){
             myIntegersForFunction[x] = Integer.parseInt(myIntegers[x]);
          }
         for(int valueinarray : highIntegers(myIntegersForFunction))          
System.out.print(valueinarray + " ");
  } catch (IOException e) {
       System.out.println("Something is wrong with the values entered. Please check the integer(s) and try again.");
  } catch (NumberFormatException e) { 
       System.out.println("The values entered are not all integers separated by commas. Please try again.");
      }
  }
}
}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Your program does not work correctly for arrays with negative elements. As an example, for {-1,-2,-3,-4,-5,-6} the output is -1 0 0 0. \$\endgroup\$
    – Martin R
    Dec 21, 2019 at 3:51
  • \$\begingroup\$ By this: should not included library functions, but pure logic. do you mean that you must write all the code yourself? \$\endgroup\$
    – markspace
    Dec 21, 2019 at 3:57
  • 2
    \$\begingroup\$ Please try and fix the indentation of the presentation of your code above: Use blanks only for indent, enclose code block in lines containing just ~~~. \$\endgroup\$
    – greybeard
    Dec 21, 2019 at 6:23
  • 2
    \$\begingroup\$ Can you clarify how repeated elements should be handled? As an example, what are the four largest integers in {1, 1, 2, 2, 3, 3, 4, 4}? Should the result be 4, 3, 2, 1 or 4, 4, 3, 3? \$\endgroup\$
    – Martin R
    Dec 21, 2019 at 12:02

3 Answers 3

6
\$\begingroup\$

Your code looks pretty decent already asside from a minor bug. I only have a few remarks for improvement.


Don't use comments to explain the code. Either the code is clear by itself, or you should change it. The only exception is explaining WHY code is written a certain way. In your case, explaining why you do temparray[0] = arrayofintegers[0]; first helps understanding the reasoning behind your solution. It also points out why it doesn't work for an input like {-1,-2,-3,-4,-5,-6}.

The comment explaining what your temparray means shouldn't be required. Instead of that comment it's better to give the variable a more meaningful name like largestNumbers.

The comment explaining result when input is less or equal to 4 numbers long can just be ommitted entirely. The line of code is perfectly clear to understand this immediatly without the distracting comment.


Just nitpicking here but the int[] temparray = new int[4]; isn't needed when the input is too small. Put it after the if ( arrayofintegerslength <= 4 ) return arrayofintegers; instead.


Your logic to insert elements into the largest 4 list is slightly confusing because it's 4 separate if statements that always get checked. It would be better to use else which makes it obvious that if a previous case was handled, we can skip the following insertion checks.

Added bonus is that you can simplify the checks for the next if statements because you know the current item is smaller than the previous checked elements already.

for (int x = 1; x < arrayofintegerslength; x++) {
    if (arrayofintegers[x] > largestNumbers[0]) {
        largestNumbers[3] = largestNumbers[2];
        largestNumbers[2] = largestNumbers[1];
        largestNumbers[1] = largestNumbers[0];
        largestNumbers[0] = arrayofintegers[x];
    } else if (arrayofintegers[x] > largestNumbers[1]) {
        largestNumbers[3] = largestNumbers[2];
        largestNumbers[2] = largestNumbers[1];
        largestNumbers[1] = arrayofintegers[x];
    } else if (arrayofintegers[x] > largestNumbers[2]) {
        largestNumbers[3] = largestNumbers[2];
        largestNumbers[2] = arrayofintegers[x];
    } else if (arrayofintegers[x] > largestNumbers[3]) {
        largestNumbers[3] = arrayofintegers[x];
    }
}

What would happen if your next assignment is to modify your current algorithm to search for the largest n integers instead of a fixed 4? You'll have to rethink how your if statements should be handled. Given my last suggestion helps a bit already. The logic then needs to be to find the index in the largestNumbers array where the current element needs to be inserted, then use a loop to move all elements up to that index down a spot and finally put in the current element in it's place.

A slighly different algorithm makes it easier to generalise to any n largest numbers. The idea is to check the element against the current smallest of the n largestNumbers and put it in at that spot. Then move it up in the array by swapping places until it's in the right spot. This looks something like this:

for (int x = 1; x < arrayofintegerslength; x++) {
    if (arrayofintegers[x] > largestNumbers[3]) {
        largestNumbers[3] = arrayofintegers[x];
    }
    if (arrayofintegers[x] > largestNumbers[2]) {
        largestNumbers[3] = largestNumbers[2];
        largestNumbers[2] = arrayofintegers[x];
    }
    if (arrayofintegers[x] > largestNumbers[1]) {
        largestNumbers[2] = largestNumbers[1];
        largestNumbers[1] = arrayofintegers[x];
    }
    if (arrayofintegers[x] > largestNumbers[0]) {
        largestNumbers[1] = largestNumbers[0];
        largestNumbers[0] = arrayofintegers[x];
    }
}

Note the lack of else statements here.

We can then generalise this with a simple for loop. Adding in a few extra optimisations results in this solution:

// TODO initialize array to a certain value that prevents your current 0 issue.

for (int currentInt : arrayofintegers) {
    if (currentInt <= largestNumbers[largestNumbers.length - 1]) {
        continue;
    }
    largestNumbers[largestNumbers.length - 1] = currentInt;
    for (int index = largestNumbers.length - 2; index >= 0; index--) {
        if (currentInt <= largestNumbers[index]) {
            break;
        }

        largestNumbers[index + 1] = largestNumbers[index];
        largestNumbers[index] = currentInt;
    }
}

I do want to point out that your solution (given my other remarks) works so if you don't expect that you might need to generalise to any n largest numbers there isn't really a good reason to prefer this solution over yours.

\$\endgroup\$
6
  • \$\begingroup\$ Your suggested code behaves different from the original code for arrays with repeated elements, e.g {1, 1, 2, 2, 3, 3, 4, 4}. Also it does not work correctly for {-1, -2, -3, -4, -5} either. \$\endgroup\$
    – Martin R
    Dec 21, 2019 at 11:39
  • \$\begingroup\$ @MartinR I see what you mean. I'm going to assume that it's another bug in OP's code. Especially given that {1, 2, 4, 4} returns "4 4 2 1" but {1, 2, 4, 4,4} returns "4 2 1 0" ... \$\endgroup\$
    – Imus
    Dec 21, 2019 at 18:47
  • \$\begingroup\$ @MartinR what would you suggest to resolve the issue with negative numbers? My thought would be to initial the largestNumbers array with values to ensure the values are adjusted for example : temparray[0] = arrayofintegers[0]; temparray[1] = arrayofintegers[1]; temparray[2] = arrayofintegers[2]; temparray[3] = arrayofintegers[3]; before the for loop in the function. What do you think about this as a solution ? \$\endgroup\$ Dec 21, 2019 at 23:59
  • \$\begingroup\$ @ClarenceLLeslie that might work but you need to make sure those 4 are sorted too to let the algorithm(s) work correctly. Take a look at the constant Integer.MIN_VALUE inside the integer class. If you know that no int can be smaller than that value, it becomes rather clear what you can use as initial values for your temorary array :) \$\endgroup\$
    – Imus
    Dec 23, 2019 at 21:00
  • \$\begingroup\$ @Imus. Thanks Imus, that solved the issue and allows the program to work for all integers. Since I can't use Integer.MIN_VALUE, but set the values to -2147483648, which is the smallest integer, then any number added will be greater unless -2147483648 is used in the array. \$\endgroup\$ Dec 30, 2019 at 22:19
0
\$\begingroup\$

When I look at the problem statement in your code, it doesn't seem to specifically mention keeping everything in one function. I think here a simple swap function, still keeps with the directive to not make any library calls, but neatens the the highIntegers function up greatly.

Treating the first 3 integers as special cases, allows you make fewer swaps. This also makes it easy to get the first 4 sorted and stays within the bounds of being O(n) complexity.

With the temparray filled and sorted, the code inside the loop is simplified by working from the smallest and swapping until it's in sorted place.

A side note I forgot to add before. This solution will correct the bug that doesn't deal with the array having all negative numbers.

It could look something like this:

  public static int[] highIntegers(int[] arrayOfIntegers) {
    int[] tempArray = new int[4];
    int arrayOfIntegersLength = arrayOfIntegers.length;
    if (arrayOfIntegersLength <= 4) {
      return arrayOfIntegers;
    }
    tempArray[0] = arrayOfIntegers[0];
    tempArray[1] = arrayOfIntegers[1];
    if (tempArray[1] > tempArray[0]) {
      swap(tempArray, 0, 1);
    }
    tempArray[2] = arrayOfIntegers[2];
    if (tempArray[2] > tempArray[1]) {
      swap(tempArray, 1, 2);
      if (tempArray[1] > tempArray[0]) {
        swap(tempArray, 0, 1);
      }
    }
    tempArray[3] = Integer.MIN_VALUE;

    for (int i = 3; i < arrayOfIntegers.length; i++) {

      if (arrayOfIntegers[i] > tempArray[3]) {
        tempArray[3] = arrayOfIntegers[i];
        if (tempArray[3] > tempArray[2]) {
          swap(tempArray, 2, 3);
          if (tempArray[2] > tempArray[1]) {
            swap(tempArray, 1, 2);
            if (tempArray[1] > tempArray[0]) {
              swap(tempArray, 0, 1);
            }
          }
        }
      }
    }
    return tempArray;
  }
private static void swap(int[] arr, int indexA, int indexB){
    arr[indexA] += arr[indexB];
    arr[indexB]  = arr[indexA] - arr[indexB];
    arr[indexA] -= arr[indexB];
} 

If the swap function is unacceptable the simplicity of where it's used makes it a simpler matter of expanding each function call:

public static int[] highIntegers(int[] arrayOfIntegers) {
    int[] tempArray = new int[4];
    int arrayOfIntegersLength = arrayOfIntegers.length;
    if (arrayOfIntegersLength <= 4) {
        return arrayOfIntegers;
    }
    tempArray[0] = arrayOfIntegers[0];
    tempArray[1] = arrayOfIntegers[1];        
    if(tempArray[1] > tempArray[0]){
        tempArray[0] += tempArray[1];
        tempArray[1]  = tempArray[0] - tempArray[1];
        tempArray[0] -= tempArray[1];
    }
    tempArray[2] = arrayOfIntegers[2];
    if(tempArray[2] > tempArray[1]){
        tempArray[1] += tempArray[2];
        tempArray[2]  = tempArray[1] - tempArray[2];
        tempArray[1] -= tempArray[2];
        if(tempArray[1] > tempArray[0]){
            tempArray[0] += tempArray[1];
            tempArray[1]  = tempArray[0] - tempArray[1];
            tempArray[0] -= tempArray[1];
        }        
    }
    tempArray[3] = Integer.MIN_VALUE;;

    for (int i = 3; i < arrayOfIntegers.length; i++) {

        if(arrayOfIntegers[i] > tempArray[3]){
            tempArray[3] = arrayOfIntegers[i];
            if(tempArray[3] > tempArray[2]){
                tempArray[2] += tempArray[3];
                tempArray[3]  = tempArray[2] - tempArray[3];
                tempArray[2] -= tempArray[3];
                if(tempArray[2] > tempArray[1]){
                    tempArray[1] += tempArray[2];
                    tempArray[2]  = tempArray[1] - tempArray[2];
                    tempArray[1] -= tempArray[2];
                    if(tempArray[1] > tempArray[0]){
                        tempArray[0] += tempArray[1];
                        tempArray[1]  = tempArray[0] - tempArray[1];
                        tempArray[0] -= tempArray[1];
                    }
                }
            }
        }
    }
    return tempArray;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You're suggesting if-statements nested four-deep with the same code inside them copy-pasted at least three times? \$\endgroup\$ Dec 22, 2019 at 8:31
  • \$\begingroup\$ @TorbenPutkonen - I took a closer look and reduced the redundancy. \$\endgroup\$
    – user33306
    Dec 22, 2019 at 18:42
-3
\$\begingroup\$

when it comes to list of integers and comparison, use best sorting algorithm. There is one called DualPivotSorting by reverse order. The you can get easily first 4 largest number.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ Sorting entire Array just to get 4 largest elements seems a bit like overkill, especially if use of library functions Is forbidden. \$\endgroup\$
    – slepic
    Dec 21, 2019 at 9:00
  • \$\begingroup\$ If the array contains more elements, sorting and getting element is not a better approach? I didn't mean to use of Dual Piot API. I suggested to use the mechanism to get best performance. In fact, Java Sorting API uses that mechanism. \$\endgroup\$
    – parrotjack
    Dec 21, 2019 at 21:50
  • \$\begingroup\$ Sorry all, but can't use the Array.sort function as part if the limitation for the question was not to use any libraries. I could recreate the logic for that sort function, but not sure that is necessary. \$\endgroup\$ Dec 22, 2019 at 0:03
  • \$\begingroup\$ @ClarenceLLeslie I understand that in your question you can't use in the question but am suggesting that you write your own algorithm based on Pivot Algorithm. \$\endgroup\$
    – parrotjack
    Dec 22, 2019 at 4:34
  • \$\begingroup\$ @parrotjack better in what terms? Its probably less lines of code because bulk of the job Is done by the sorting algorithm. But there Is generaly no correlation between LoC and being good code. Anyway i dont think it Is good because you only need to sort 4 of N elements but your solution Always sorts N. \$\endgroup\$
    – slepic
    Dec 22, 2019 at 6:58

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