Brute force with memory in case of your interviewer forbid tricky solution


  • 8

    This is an Amazon interview question that could be solved in a very tricky way. Since a lot of people have already posted their solutions, I just post a brute force solution in case of the interviewer want a normal way.

    I use recursion. For each recursion, I find the maximum result and also the minimum result. For example, if you want to know the maximum result of A/B, where A and B are also some expressions, then you only need to know the maximum result of A and the minimum result of B. However, if you want to know the maximum result of C/(A/B), then you also need to know the minimum result of A/B. That's why both maximum and minimum should be stored.

    // by fallcreek
    public class Solution {
    
        public String optimalDivision(int[] nums) {
            Map<String, pair> memory = new HashMap<>();
            pair sol = divid(nums,0,nums.length-1, memory);
            return sol.maxS;
        }
        
        public pair divid(int[] nums, int start, int end, Map<String, pair> memory){
            String key = start + " " + end;
            if(memory.containsKey(key)) return memory.get(key);
            if(start == end)    return new pair(nums[start], "" + nums[start],nums[start], "" + nums[start]);
            
            pair sol = new pair(0,"",0,"");
            
            for(int i = start; i < end; i++){
                pair left = divid(nums, start, i, memory);
                pair right = divid(nums, i + 1, end, memory);
                
                double min = left.min / right.max;
                String minS = left.minS + "/" + (i + 1 == end ? right.maxS : "(" + right.maxS + ")"); 
                double max = left.max / right.min;
                String maxS = left.maxS + "/" + (i + 1 == end ? right.minS : "(" + right.minS + ")"); 
                if(sol.min == 0 || min < sol.min){
                    sol.min = min;
                    sol.minS = minS;
                }
                if(max > sol.max){
                    sol.max = max;
                    sol.maxS = maxS;
                }
            }
            memory.put(key, sol);
            return sol;
        }
    }
    
    class pair{
        double min;
        String minS;
        double max;
        String maxS;
        
        public pair(double min, String minS, double max, String maxS){
            this.min = min;
            this.minS = minS;
            this.max = max;
            this.maxS = maxS;
        }
    }
    

  • 0
    Z

    This is very helpful! Thanks for sharing.


  • 0
    A

    can you explain a little bit on when to choose to add parentheses? thanks


  • 0

    Love this solution. Now we are at least learning something.


  • 0
    J

    Thanks, it's a good solution


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.