Mock Interview: Amazon

마존남에게 까이고 온 날
마존이도 저를 까네요^^
마존이 불매합니다

541. Reverse String II

class Solution {
    public String reverseStr(String s, int k) {
//         int times = (s.length() - k) / (2 * k) + 1
//         int rev = Math.min(k, s.length() / 2);
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < s.length() / (2 * k); i++) {
            int start = i * 2 * k;
            int end = Math.min(s.length() - 1, (i * 2 * k) + k - 1);
            
            for (int j = start; j < end; j++) {
                sb.append(s.charAt(end - j - 1));
            }
        }
        
        return sb.toString();
        
    }
}

풀기 너무 귀찮아요,....ㅠㅠㅠㅠ
내일부터는 진심 열심히 해보겠읍니다

class Solution {
    public String reverseStr(String s, int k) {
        char[] a = s.toCharArray();
        for (int start = 0; start < a.length; start += 2 * k) {
            int i = start, j = Math.min(start + k - 1, a.length - 1);
            while (i < j) {
                char tmp = a[i];
                a[i++] = a[j];
                a[j--] = tmp;
            }
        }
        return new String(a);
    }
}

Runtime: 1 ms, faster than 75.60% of Java online submissions for Reverse String II.
Memory Usage: 38.8 MB, less than 89.83% of Java online submissions for Reverse String II.

뭐 특별한 방식이 있는건 아닌거 같고 걍 진짜 말그대로 2k마다 reverse 해주네요

1192. Critical Connections in a Network

class Solution {
    
    private Map<Integer, List<Integer>> graph;
    private Map<Integer, Integer> rank;
    private Map<Pair<Integer, Integer>, Boolean> connDict;
    
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
       
        this.formGraph(n, connections);
        this.dfs(0, 0);
        
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (Pair<Integer, Integer> criticalConnection : this.connDict.keySet()) {
            result.add(new ArrayList<Integer>(Arrays.asList(criticalConnection.getKey(), criticalConnection.getValue())));
        }
        
        return result;
    }
    
    private int dfs(int node, int discoveryRank) {
        
        // That means this node is already visited. We simply return the rank.
        if (this.rank.get(node) != null) {
            return this.rank.get(node);
        }
        
        // Update the rank of this node.
        this.rank.put(node, discoveryRank);
        
        // This is the max we have seen till now. So we start with this instead of INT_MAX or something.
        int minRank = discoveryRank + 1;
        
        for (Integer neighbor : this.graph.get(node)) {
            
            // Skip the parent.
            Integer neighRank = this.rank.get(neighbor);
            if (neighRank != null && neighRank == discoveryRank - 1) {
                continue;
            }
            
            // Recurse on the neighbor.
            int recursiveRank = this.dfs(neighbor, discoveryRank + 1);
            
            // Step 1, check if this edge needs to be discarded.
            if (recursiveRank <= discoveryRank) {
                int sortedU = Math.min(node, neighbor), sortedV = Math.max(node, neighbor);
                this.connDict.remove(new Pair<Integer, Integer>(sortedU, sortedV));
            }
            
            // Step 2, update the minRank if needed.
            minRank = Math.min(minRank, recursiveRank);
        }
        
        return minRank;
    }
    
    private void formGraph(int n, List<List<Integer>> connections) {
        
        this.graph = new HashMap<Integer, List<Integer>>();
        this.rank = new HashMap<Integer, Integer>();
        this.connDict = new HashMap<Pair<Integer, Integer>, Boolean>();
        
        // Default rank for unvisited nodes is "null"
        for (int i = 0; i < n; i++) {
            this.graph.put(i, new ArrayList<Integer>());
            this.rank.put(i, null);
        }
        
        for (List<Integer> edge : connections) {
            
            // Bidirectional edges
            int u = edge.get(0), v = edge.get(1);
            this.graph.get(u).add(v);
            this.graph.get(v).add(u);
            
            int sortedU = Math.min(u, v), sortedV = Math.max(u, v);
            connDict.put(new Pair<Integer, Integer>(sortedU, sortedV), true);
        }
    }
}

Runtime: 308 ms, faster than 18.94% of Java online submissions for Critical Connections in a Network.
Memory Usage: 148.1 MB, less than 31.12% of Java online submissions for Critical Connections in a Network.

우리의 사랑 cycle detection이 컴백루 햇읍니다
이건 진짜 꼭 외워두면 좋을 것 같네요