Mock Interview: Apple

911. Online Election

class TopVotedCandidate {
    public int[] leadingCand;
    public TopVotedCandidate(int[] persons, int[] times) {
        
        Map<Integer, Integer> votingCount = new HashMap<Integer, Integer>();
        
        int howLong = times[times.length - 1];
        
        leadingCand = new int[howLong+1];
        
        int prev = times[0];
        
        int curlead = persons[0];
        
//         for (int k = 0; k < times[0]; k++) {
//             leadingCand[k] = -1;
//         }
        
//         votingCount.put(curlead, 1);
        
        for (int i = 0; i < persons.length; i++) {
            votingCount.put(persons[i], votingCount.getOrDefault(persons[i], 0) + 1);
            
            curlead = (votingCount.get(curlead) > votingCount.get(persons[i])) ? curlead : persons[i];
            
            int end = Math.min(i+1, times.length - 1);
            for (int j = times[i]; j < times[end]; j++) {
                leadingCand[j] = curlead;
            }
            
        }
        
        
    }
    
    public int q(int t) {
        if (t >= this.leadingCand.length) {
            return this.leadingCand[this.leadingCand.length - 1];
        }

        return this.leadingCand[t];
    }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);
 */

19 / 97 test cases passed.

쉬맵이: 각 candidate의 투표수를 기록
시작부터 time의 끝에있는 수까지의 array인 leadingCand를 만들고
persons를 하나하나 보면서 쉬맵이에다가 투표수를 넣어주면서 time에 있는 동안의 가장 큰 candidate을 leadingCand에다가 넣어줬읍니다

class TopVotedCandidate {
    List<Vote> A;
    public TopVotedCandidate(int[] persons, int[] times) {
        A = new ArrayList();
        Map<Integer, Integer> count = new HashMap();
        int leader = -1;  // current leader
        int m = 0;  // current number of votes for leader

        for (int i = 0; i < persons.length; ++i) {
            int p = persons[i], t = times[i];
            int c = count.getOrDefault(p, 0) + 1;
            count.put(p, c);

            if (c >= m) {
                if (p != leader) {  // lead change
                    leader = p;
                    A.add(new Vote(leader, t));
                }

                if (c > m) m = c;
            }
        }
    }

    public int q(int t) {
        int lo = 1, hi = A.size();
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (A.get(mi).time <= t)
                lo = mi + 1;
            else
                hi = mi;
        }

        return A.get(lo - 1).person;
    }
}

class Vote {
    int person, time;
    Vote(int p, int t) {
        person = p;
        time = t;
    }
}

Runtime: 72 ms, faster than 71.94% of Java online submissions for Online Election.
Memory Usage: 48 MB, less than 95.79% of Java online submissions for Online Election.

1094. Car Pooling

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int drive = 0; 
        for (int[] t : trips) {
            drive = Math.max(drive, t[2]);
        }
        int[] possible = new int[drive];
        
        for (int[] t : trips) {
            int passenger = t[0];
            
            for (int i = t[1]; i < t[2]; i++) {
                possible[i] += passenger;
                if (possible[i] > capacity) {
                    return false; 
                }
            }
        }
        
//        for (int j = 0; j < possible.length; j++) {
//            if (possible[j] > capacity) {
//                return false;
//            }
//        }
        return true;
    }
}

Runtime: 3 ms, faster than 70.33% of Java online submissions for Car Pooling.
Memory Usage: 38.6 MB, less than 83.92% of Java online submissions for Car Pooling.

일단 가장 멀리 가는데가 어딘지 for loop을 한번 돌려서 알아내고
그 사이즈만큼의 array인 possible을 만들어줬읍니다
그 다음에 모든 trip을 보면서 시작부터 끝까지 passenger 수 만큼 넣어주고
넣었는데 capacity를 넘었으면 바로 false 리턴해줬읍니다