0

Java 7 doesn't support lambda expressions. How can I optimize two similar methods 'GetMinOfList' and 'GetMaxOfList'?

package com.example; import java.util.ArrayList; import java.util.List; public class MinMax<T extends Comparable<T>> { private List<T> lst = null; public MinMax(List<T> com) { this.lst = com; } public Pair<T, T> GetMinMaxOfList() { return GetMinMaxOfList(this.lst); } private Pair<T, T> GetMinMaxOfList(List<T> list) { if(list == null || list.size() == 1) return null; //Pair<T, T> minMax = new Pair<T, T>(); T min, max; if(list.size() == 2) { if(list.get(0).compareTo(list.get(1)) < 0) { min = list.get(0); max = list.get(1); return new Pair<T,T>(min, max); } } //T sentry = list.get(0); min = GetMinOfList(list); max = GetMaxOfList(list); return new Pair<T, T>(min, max); } private T GetMinOfList(List<T> littleList) { T sentry = littleList.get(0); if(littleList.size() == 1) return sentry; List<T> nextLittle = new ArrayList<T>(1); for(T t: littleList) { if(t.compareTo(sentry) < 0) nextLittle.add(t); } if(nextLittle.size() == 0) return sentry; return GetMinOfList(nextLittle); } private T GetMaxOfList(List<T> lagerList) { T sentry = lagerList.get(0); if(lagerList.size() == 1) return sentry; List<T> nextLarge = new ArrayList<T>(1); for(T t: lagerList) { if(t.compareTo(sentry) > 0) nextLarge.add(t); } if(nextLarge.size() == 0) return sentry; return GetMaxOfList(nextLarge); } }
Improve this question
4
  • 2
    What do you mean by optimize: better performance or less code? Commented Sep 26, 2013 at 3:31
  • 4
    Wow . . . I never though I'd see a O(n^2) recursive min or max function . . . Commented Sep 26, 2013 at 3:36
  • possible duplicate of best way for get min and max value from a list of Comparables in java Commented Sep 26, 2013 at 3:38
  • @Aurand Never done an interview before? I've seen O(n^3) array reverse algorithms from interview candidates. Commented Sep 26, 2013 at 3:39

3 Answers 3

Reset to default
4

Less code? You can replace those methods with these:

 min = Collections.min(list); max = Collections.max(list);

Though that assumes T implements Comparable. As Luiggi Mendoza points out: you can also implement a comparator and use it via the other form of min/max, if it doesn't:

 min = Collections.min(list, comparator); max = Collections.max(list, comparator);
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Probably you need to implement an anonymous Comparator<YourClass> as well. Still, this is the lesser code that accomplish the task.
1

I Think your use of Recursion is not very efficient. This type of recursion and use up alot of stack memory. Also every iteration will trigger an additional ArrayList creation. Try simply looping through the given list and setting a local variable if the next element is greater than / less than depending on which function you're in

private T GetMaxOfList(List<T> littleList){ T smallest = null; for(T element : littleList){ if(smallest == null){ smallest = element; } else if (smallest.compareTo(element) > 0) { smallest = element; } } return smallest }

and vice versa.

Improve this answer

Comments

1

Java provide Collections.min(Comparables) and Collections.max(Comparables) which you can implement as follows.

private Pair<T, T> GetMinMaxOfList(List<T> list) { return new Pair<T, T>(getMinOfList(list), getMaxOfList(list)); } private T getMinOfList(List<T> list) { return Collections.min(list) } private T getMaxOfList(List<T> list) { return Collections.max(list) }
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.