Good job! Whatever is written below, you wrote some good code (with a few issues). You're on the correct path, so keep trying, keep learning, keep writing code! The mentioned issues:
The general consensus is that there's no space after the opening parenthesis in a method call or declaration. Therefore, public static void main( String[] args) shoud be public static void main(String[] args).
Any time you catch yourself writing a title of a code block into a comment, you should make a method (or a test class instance) instead. For example, instead of // part 1 you should have it as an appropriately named method.
List<Integer> nums = new ArrayList<Integer>(); can be written as List<Integer> nums = new ArrayList<>(); since Java 7. It's called Diamond operator.
Since Java 7, there's a new ThreadLocalRandom class. It gives you the same results as Random, but is only safe for single-threaded usage, and the implementation therefore lacks some synchronization details and is faster. Of course, this only shows up when generating lots of numbers, but it's better to use the single-threaded classes when not dealing with multiple threads in general.
There's no need to use a ConcurrentHashMap when you're not dealing with multiple threads. Simply use a HashMap. The reason you probably went for the concurrent map was that you needed to remove from the map while iterating over it, and you were getting ConcurrentModificationExeptions. You can do it with a normal HashMap easily, too, just use iterators and their remove() method.
Your mergeEvenNumbers() works (partly due to the hack above), but does too much work for no reason. What it does:
- Goes over all entries
- Finds two even keys
- Removes the previous even entry and the current even entry
- Puts in a new entry which is the sum
- (plus some looping around that to make sure you did it enough times and nothing changes anymore)
The problem is that you don't need to do most of that. What you should do:
- Loop over the map, remove all even keys while summing their keys and values into twe local temporary variables.
- Put the sums into the map.
The final code:
private static void mergeEvenNumbers(Map<Integer, Integer> nums) { int keySum = 0; int valueSum = 0; for (Iterator<Integer> iter = nums.keySet().iterator(); iter.hasNext(); ) { int key = iter.next(); if (key % 2 == 1) { continue; } keySum += key; valueSum += nums.get(key); iter.remove(); } nums.put(keySum, valueSum); }
Much shorter, does the same thing.
Your getLastPositivePosition() ... why does it go over the whole list? It's generally easier to start at the end of the list and go backwards - once you find a positive number, you're done. The code is similarly long, but does a lot less work!
private static int getLastPositivePosition(List<Integer> nums) { for (int i = nums.size() - 1; i >= 0; i--) { if (nums.get(i) > 0) { return i; } } return -1; }
Your repeatElements(): instead of
for (int num : nums) { result.add(num); }
you could have result.addAll(nums)
Your removePositiveNumbers() and removeNegativeNumbers() are very flawed!
They iterate based on an index, and remove from the lists as they do (Oh, by the way, that's a very costly thing to do when dealing with ArrayLists. Either iterate backwards, use a Set, or at last a LinkedList. This makes a huge difference regarding speed.). Therefore, they will skip elements immediately after a remove. Consider this list:
[-1, -2, 3]
Your method would find the -1, remove it, and suddenly you'd end up with a list like this:
[-2, 3]
But the method would then look up the element on index 1 which is the 3. It would never remove the -2. The fix is to use the iterator-based removal.
removePositiveNumbers() again: Both methods return a Set which removes duplicates. Is that what you want? If yes, it's a very nasty thing to do - your method has a return value, but also changes its parameter. In general, you should do either one of these - if you change your parameters, return void. If you want to return an entirely new collection, don't change your parameter. Changes like these are called side-effects and should be avoided.
Your method's names only suggest they remove positive (negative) elements, but they also do one additional thing. Either change the name (and/or the documentation) of the methods, or move the deduplication out of the methods, into its own dedicated method removeDuplicates().
Because of the above, this code:
Set<Integer> positiveNumbers = removeNegativeNumbers(nums); Set<Integer> negativeNumbers = removePositiveNumbers(nums);
is flawed. The second line should return a list of the negative numbers from the original nums, but there are no negative numbers anymore, we removed them by calling removeNegativeNumbers(nums) on the previous line!
The final code with all of the above and something extra, too:
public class Test { private static final Random random = ThreadLocalRandom.current(); public static void main(String[] args) { List<Integer> nums = generateRandomNumberList(); long time = System.currentTimeMillis(); // part 1 int lastPositivePos = getLastPositivePosition(nums); System.out.println("lastPositivePos " + lastPositivePos + " has value " + nums.get(lastPositivePos)); List<Integer> positiveNumbers = removeNegativeNumbers(nums); List<Integer> negativeNumbers = removePositiveNumbers(nums); System.out.println(positiveNumbers.size() + " + " + negativeNumbers.size() + " should be ~100000"); // part 2 List<Integer> positiveList = repeatElements(positiveNumbers, 5); List<Integer> negativeList = repeatElements(negativeNumbers, 5); List<Integer> mergedList = mergeAndSort(negativeList, positiveList); System.out.println(mergedList.size() + " sorted elements"); // part 3 Map<Integer, Integer> nums2 = generateRandomNumberMap(); mergeEvenNumbers(nums2); System.out.println("test takes " + (System.currentTimeMillis() - time) + " ms"); } private static List<Integer> generateRandomNumberList() { // a longer Java 8 alternative // the point to ever use this would be to leave it as an IntStream and operate on that if possible (which it isn't here) // int i = 0; // random.ints(0, 100000) // .map(num -> num * ((i++ % 4 == 0) ? 1 : -1)) // .limit(100000) // .boxed() // .collect(Collectors.toList()); List<Integer> nums = new ArrayList<>(); for (int i = 0; i < 100000; i++) { nums.add(random.nextInt(100000) * ((i % 4 == 0) ? 1 : -1)); } return nums; } private static Map<Integer, Integer> generateRandomNumberMap() { Map<Integer, Integer> nums = new HashMap<>(); for (int i = 0; i < 1000; i++) { nums.put(random.nextInt(100), random.nextInt(100)); } return nums; } private static int getLastPositivePosition(List<Integer> nums) { for (int i = nums.size() - 1; i >= 0; i--) { if (nums.get(i) > 0) { return i; } } return -1; } private static List<Integer> removeNegativeNumbers(List<Integer> list) { // a Java 8 alternative // return list.stream() // .filter(num -> num > 0) // .collect(Collectors.toList()); List<Integer> result = new LinkedList<>(list); for (Iterator<Integer> iter = result.iterator(); iter.hasNext(); ) { if (iter.next() < 0) { iter.remove(); } } return result; } private static List<Integer> removePositiveNumbers(List<Integer> list) { // a Java 8 alternative // return list.stream() // .filter(num -> num < 0) // .collect(Collectors.toList()); List<Integer> result = new LinkedList<>(list); for (Iterator<Integer> iter = result.iterator(); iter.hasNext(); ) { if (iter.next() > 0) { iter.remove(); } } return result; } private static List<Integer> repeatElements(List<Integer> nums, int repeat) { List<Integer> result = new ArrayList<>(repeat * nums.size()); for (int i = 0; i < repeat; i++) { result.addAll(nums); } return result; } private static List<Integer> mergeAndSort(List<Integer> nums1, List<Integer> nums2) { List<Integer> result = new ArrayList<>(nums1.size() + nums2.size()); result.addAll(nums1); result.addAll(nums2); Collections.sort(result); return result; } /** Merges all even keys to a single entry, sum them and their values. */ private static void mergeEvenNumbers(Map<Integer, Integer> nums) { int keySum = 0; int valueSum = 0; for (Iterator<Integer> iter = nums.keySet().iterator(); iter.hasNext(); ) { int key = iter.next(); if (isOdd(key)) { continue; } keySum += key; valueSum += nums.get(key); iter.remove(); } nums.put(keySum, valueSum); } private static boolean isOdd(int key) { // return ((key & 1) == 1); // a faster alternative return ((key % 2) == 1); } }
