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 returnください.
一度も小さくならなかったとき、一度も大きくならなかったときのedge caseを捕まえてあげました.

939. Minimum Area Rectangle

3号は少しふわふわして3号に集中して全然解けなかった

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.
各線が引かれているかどうかを比較し、前の結合と求めた幅を求め、全体の幅を求める3次方程式を作成しました.最小値で比較し、最高値のみを格納します.

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勝メモリを作ろうとしたが、メモリが制限を超えた。 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. だから私は許三二に戻った。 今回は時間制限を超えました^^ 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. 私との差は多くないが、shmapの代わりにTreemapで通過した。ほほほ と思ったら、本当にTreemapを使っていたら、前につかまっていたのに・・・もっと速くしてこそ話になる。