Hello backEnd

캐시 스탬피드(Stempede) 막는 방법 관련 고민

캐시 스탬피드(Cache Stampede)특정 데이터의 캐시가 만료되었을 때 여러 요청이 한꺼번에 오면서 과부화가 생기는 현상해결법뮤텍스 / 잠금백그라운드 갱신확률적 조기 만료 (PER)이전 데이터 보여주면서 갱신 (Stale-While-Revalidate)뮤텍스 / 잠금가장 기본적인 잠금 방식캐시 미스되었을 때 최초 요청만 락을 획득하고 DB 조회나머지 요청들은 락 걸려서 대기장점구현이 간단함(하나 오면 나머지는 락걸면 됨)과거 데이터를 볼 일은 없음 (최신 데이터 아니면 못봄)단점트래픽이 많으면 OOM이 되거나 커넥션 풀이 고갈되거나 락 확인 때문에 레디스가 죽을수도 있다.트래픽이 아주 많지 않을 때 사용백그라운드 갱신캐시 미스 시 DB 조회 로직을 아예 제외그냥 스케쥴러나 워커를 통해 DB 최신 데..

굉장히 오래 헤맨 문제Node 로 푸는건가 PQ로 푸는건가 했는데 PQ 로 풀면 구할 수 있었다. 리밸런싱과 값 처리만 할줄 알면 된다. 이걸 근데 코테중에 떠올릴 수 있을지는 모르겠다. class MedianFinder { // PQ 두개 PriorityQueue lower; // 작은 값들을 가지고 있을 큐 -> 내림차순 PriorityQueue upper; // 큰 값들을 가지고 있을 큐 // 둘의 크기가 일정하게 유지되면 된다. // 크기를 맞춰서 안맞으면 하나 뺴서 하나 넣고 구하면 가운데를 구할 수 있음 public MedianFinder() { lower = new PriorityQueue(Comparator.reverseOrder()); ..

이거는 굉장히 쉽다. timestamp 는 무조건 증가하니까(이분탐색)들고와서(HashMap)이하를 return 해주면 된다. class Store { int timestamp; String value;}class TimeMap { // key - value 와 timestamp 를 저장한다. // get이 핵심 // get 할 때 key 와 timestamp 를 쓰면, 그 timestamp 이하의 key 에 대한 value 가 return 된다. // 풀이 방법 // get // key 로 찾으면 timestamp 를 찾는다. // 저장을 순서대로 한다면? // 결국 key 가져와서 거기서 이분탐색으로 timestamp ..

class SeatManager { // 예약 / 해지 // 낮은 순으로 예약 가능 // 해지는 원하는 숫자에 가능 // Set 이랑 PQ 쓰면 되지 않나? // 낮은 숫자로 만드는건 PQ // 예약 되었는지는 Set PriorityQueue pq; // 여기 있는 것들은 남은 자리 Set set; // 여기 있는 것들은 이미 누군가 앉은 자리 // 자리를 뺄 때에는 set 에 있는지 파악해서 있으면 set 에서 지우고 pq 에 넣어주면 된다. // pq 에 있는건 무조건 빈자리 // 그럼 set 의 용도는? 뺄 수 있는지 확인을 위함 int size; public SeatManager(int n) { this.si..

쉬운 풀이class NumMatrix { // y1 x1 y2 x2 // int[][] matrix; public NumMatrix(int[][] matrix) { this.matrix = matrix; } public int sumRegion(int row1, int col1, int row2, int col2) { int sum = 0; int x1 = Math.max(row1, row2); int x2 = Math.min(row1, row2); int y2 = Math.min(col1, col2); int y1 = Math.max(col1, col2); for(int i=x..

이게 왜 미디엄..? 이라는 생각이 들정도로 다른 것들이랑 차이가 많이 나는 문제이다.솔직히 풀이랄것도 없다. 그냥 맨 위 값을 캐싱하면 해결된다. // Java Iterator interface reference:// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.htmlclass PeekingIterator implements Iterator { Iterator iterator; Integer cache; public PeekingIterator(Iterator iterator) { this.iterator = iterator; cache = iterator.next(); } // Returns ..

이거는 앞의 문제 https://hello-backend.tistory.com/423 이거를 풀었으면 매우 쉽다.그냥 저장은 똑같고, DFS 찾을 때에 . 이면 거기 싹다 찾으면 된다. class Word { boolean isEnd; Word[] word = new Word[26];}class WordDictionary { Word root; public WordDictionary() { root = new Word(); } // 객체가 객체를 저장하는 형태 // 결국 특정 알파뱃에 대하여 그 아래에 객체가 존재하고 ... -> 반복 시 모든 문자열의 형태가 저장된다. // 그렇다면 어떻게 확인할 수 있을까? // DFS 를 통..

대체 뭐 어떻게 하는건지 감도 안왔었다.결국 중요한건 1. 단어를 만들 때 각 알파뱃까지로 만들어진 객체가 있는지를 보고2. 그 아래로 쭉쭉 만들어가면서 만들고 확인할 때에는 1. DFS 를 써서 확인할 단어로 보다가2. 정확히 일치하면 맞는거3. prefix 인 경우는 그거만 확인하면 됨 으로 진행하면 된다.뭔가 지금까지 하면서 느낀게, 이런 구현들은 객체를 어떻게 만들지를 보는 것 같다.요구조건에 따라 객체를 잘 만들면 해결 자체는 수월해 보임. class Word { boolean isEnd; Word[] cha = new Word[26]; // a ~ z 까지, 그리고 그 내부로 들어가면 그것 또한 트리의 형태.}class Trie { // 처음부터 확인한다. // 노드로 ..

푸는 방법을 생각해 내는게 어려운 문제.방법을 알면 푸는건 간단한데 생각하기가 참 어렵다. 중요한건 노드 기준으로 볼 때 현재 노드의 왼쪽 아래 : 이것보다 작음왼쪽의 왼쪽 아래 : 더 작음현재 노드의 오른쪽 아래 : 이것보다 큼현재 노드의 오른쪽 아래 : 내 위보다는 작음 이거를 기억하면 된다. 스택에 노드에서 왼쪽으로 가면서 쭉 넣어주고next 할 때에는 노드에서 값을 꺼내서 보여주고, 현재 기준 오른쪽 노드를 기준으로도 쭉 확인해보기hasNext 는 스택이 비어있지 않으면 가능/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; *..

내가 이런 구현에 재능이 없었다.참 오래 공부를 안했다.강의를 대충 보고 풀었는데도 1시간 정도 소요되었다. 문제를 보고 풀이를 할 때 좀 더 확실히 보고 풀어야겠다는 생각이 든다. import java.util.*;// 이중 LinkedList 를 구현할 Classclass CacheItem { CacheItem prev; CacheItem next; int key; int value; public CacheItem(int key, int value) { this.key = key; this.value = value; }}class LRUCache { // 맨 앞, 맨 뒤에 접근해야 한다. // Double Linked Lis..