Mock Interview: Google

941. Valid Mountain Array

class Solution {
    public boolean validMountainArray(int[] arr) {
        if (arr.length < 3) {
            return false;
        }
        
        boolean decreasing = false;
        int prev = arr[0];
        
        if (arr[0] > arr[1]) {
            return false; 
        }
        
        for (int i = 1; i < arr.length; i++) {
            if (! decreasing) {
                if (arr[i] < prev) {
                    decreasing = true;
                } else if (arr[i] == prev) {
                    return false; 
                }
                prev = arr[i];
            } else {
                if (arr[i] >= prev) {
                    return false; 
                }
                prev = arr[i];
            }
        }
        
        if (! decreasing) {
            return false;
        } else {
            return true; 
        }
    }
}

Runtime: 1 ms, faster than 100.00% of Java online submissions for Valid Mountain Array.
Memory Usage: 40.3 MB, less than 36.52% of Java online submissions for Valid Mountain Array.

한번이라도 줄어들면 그 이후로 커지면 false 리턴해주고
한번도 안줄어들었을 때, 한번도 안커졌을때를 위한 edge case를 잡아줬읍니다

939. Minimum Area Rectangle

3번이 풀릴랑말랑 해서 3번에 집중하느라 2번은 아예 못풀었읍니다..

class Solution {
    public int minAreaRect(int[][] points) {
        Set<String> hs = new HashSet<>();
        for(int[] p: points)
            hs.add(p[0] + "#" + p[1]);
        
        int min = Integer.MAX_VALUE;
        for(int i=0; i<points.length; i++)
        {
            for(int j= i+1; j<points.length; j++)
            {
                if(points[i][0]==points[j][0]||points[i][1]==points[j][1]) continue;
                String p1 = points[i][0] + "#" + points[j][1]; 
                String p2 = points[j][0] + "#" + points[i][1]; 
                if(hs.contains(p1)&&hs.contains(p2))
                {
                    int area = Math.abs((points[i][0]-points[j][0])*(points[i][1]-points[j][1]));
                    min = Math.min(min, area);
                }
            }
        }
        return min==Integer.MAX_VALUE?0:min;   
    }
}

Runtime: 584 ms, faster than 19.31% of Java online submissions for Minimum Area Rectangle.
Memory Usage: 39.6 MB, less than 32.52% of Java online submissions for Minimum Area Rectangle.

쉬셋이를 만들어줘서 하나하나 선이 그어지는지 비교해서 전에 있는 것들과 합쳐서 구해지는 넓이를 구하고 전체 넓이를 Math.min로 비교해줘서 최솟값만 저장하는 방식

class MyCalendarTwo {
    int[] schedule;
    public MyCalendarTwo() {
        schedule = new int[1000000000];
    }
    
    public boolean book(int start, int end) {
        boolean booked = true; 
        for (int i = start; i < end; i++) {
            if (this.schedule[i] < 3) {
                this.schedule[i]++;
            } else {
                booked = false;
            }
        }
        return booked;
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(start,end);
 */

Memory Limit Exceeded

처음에는 10^9승 메모리를 만드려고 했는데 memory limit exceeded 걸렸읍니다

class MyCalendarTwo {
    Map<Integer, Integer> schedule;
    public MyCalendarTwo() {
        schedule = new HashMap<Integer, Integer>();
    }
    
    public boolean book(int start, int end) {
        boolean booked = true; 
        for (int i = start; i < end; i++) {
            schedule.put(i, schedule.getOrDefault(i, 0) + 1);
            if (schedule.get(i) >= 3) {
                booked = false; 
            }
        }
        
        if (!booked) {
            for (int j = start; j < end; j++) {
                schedule.put(j, schedule.get(j) - 1);
            }
        }
        return booked;
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(start,end);
 */

Time Limit Exceeded

67 / 97 test cases passed.

그래서 쉬셋이로 돌아왔는데..
이번에는 time limit exceeded^^

class MyCalendarTwo {
    Map<int[], Integer> schedule;
    public MyCalendarTwo() {
        schedule = new HashMap<int[], Integer>();
    }
    
    public boolean book(int start, int end) {
        for (int i = start; i < end; i++) {
            int prev = 0; 
            for (int[] times : schedule.keySet()) {
                if (i < times[1] && i >= times[0]) {
                    prev += schedule.get(times);
                }
                if (prev >= 2) {
                    return false; 
                }
            }
        }
        int[] cur = new int[2];
        cur[0] = start; 
        cur[1] = end;
        
        schedule.put(cur, schedule.getOrDefault(cur, 0) + 1);
        
        return true; 
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(start,end);
 */

60 / 97 test cases passed.

이게 더 빠르길 바랬는데 더 느리네요..ㅠ
이건 쉬맵이

class MyCalendarTwo {
    TreeMap<Integer, Integer> delta;

    public MyCalendarTwo() {
        delta = new TreeMap();
    }

    public boolean book(int start, int end) {
        delta.put(start, delta.getOrDefault(start, 0) + 1);
        delta.put(end, delta.getOrDefault(end, 0) - 1);

        int active = 0;
        for (int d: delta.values()) {
            active += d;
            if (active >= 3) {
                delta.put(start, delta.get(start) - 1);
                delta.put(end, delta.get(end) + 1);
                if (delta.get(start) == 0)
                    delta.remove(start);
                return false;
            }
        }
        return true;
    }
}

Runtime: 213 ms, faster than 38.23% of Java online submissions for My Calendar II.
Memory Usage: 39.8 MB, less than 50.23% of Java online submissions for My Calendar II.

제꺼와 걍 거의 동일한데 쉬맵이 대신에 treemap을 쓰니깐 통과됐어요......ㅎ
생각해보니깐 진짜 treemap을 쓰면 더 앞에서 잡히니깐... 더 빠른게 말이 되네요