The fruits in basket problem

The fruits in basket problem

Malus_Tulpenapfel_4165

You have a list of integers which are fruits.

Each int value is a fruit type

You have two baskets

Each baskets can ONLY contain ONE type of fruit.

What is the max fruits you can collect?

You can only go left to right on the list.

e.g [strawberry, apple, mango, apple] -> answer is 3.

[pear, apple, orange, orange, apple, pear, apple, orange, mango, pear ] -> answer is 4

Solution:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Stack;

public class Solution {
    HashMap<Integer, Integer> basket1 = new HashMap();
    HashMap<Integer, Integer> basket2 = new HashMap();
    Stack<HashMap> lastbucket = new Stack();
    int maxFruits = 0;
    public int totalFruit(int[] tree) {
        for(int i=0;i<tree.length;i++){
            int f = tree[i];
            if(basket1.containsKey(f)||
                    (basket1.size()==0&&!basket2.containsKey(f))){
                Integer count = basket1.get(f);
                if(count==null){count=0;}
                basket1.put(f,count+1);
                lastbucket.push(basket1);
            }else if(basket2.containsKey(f)||
                    (basket2.size()==0&&!basket1.containsKey(f))){
                Integer count = basket2.get(f);
                if(count==null){count=0;}
                basket2.put(f,count+1);
                lastbucket.push(basket2);
            }else{
                if(fruitCount(basket1)+fruitCount(basket2)>maxFruits){
                    maxFruits = fruitCount(basket1)+fruitCount(basket2);
                }
                if(lastbucket.peek()==basket1){
                    HashMap tmp = lastbucket.pop();
                    int ct=0;
                    while(tmp==basket1){
                        ct = ct+1;
                        basket1.put(basket1.keySet().iterator().next(),ct);
                        if(lastbucket.size()>0){
                            tmp = lastbucket.pop();
                        }else{
                            break;
                        }
                    }
                    lastbucket.push(basket1);
                    basket2.clear();
                    basket2.put(f,1);
                    lastbucket.push(basket2);
                }else{
                    HashMap tmp = lastbucket.pop();
                    int ct=0;
                    while(tmp==basket2){
                        ct = ct+1;
                        basket2.put(basket2.keySet().iterator().next(),ct);
                        if(lastbucket.size()>0){
                            tmp = lastbucket.pop();
                        }else{
                            break;
                        }
                    }
                    lastbucket.push(basket2);
                    basket1.clear();
                    basket1.put(f,1);
                    lastbucket.push(basket1);
                }
            }

        }
        if(fruitCount(basket1)+fruitCount(basket2)>maxFruits){
            maxFruits = fruitCount(basket1)+fruitCount(basket2);
        }

        return maxFruits;
    }
    private int fruitCount(HashMap<Integer,Integer> basket){
        Iterator<Integer> it = basket.keySet().iterator();
        while(it.hasNext()){
            Integer key = it.next();
            return basket.get(key);
        }
        return 0;
    }
}
Advertisements
READ  Script to git clone all repositories of a user from bitbucket

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Terms of Use | Privacy Policy 
2018-2019 © eXitDiscount