algo calisthenics

알고리즘 및 데이터 구조

나는이 저장소를 연습 놀이터 (Kata)로 사용하고 일반적이고 단순하지만 강력한 알고리즘을 상기시켜줍니다. 우아한 경우 Clojure 트랜스 듀서를 사용하여 시퀀스를 처리 할 수있는 훌륭한 전동 공구입니다. 이 문서는 철저한 것처럼 보일 수 있지만 공부해야 할 때 언제든지 돌아올 수있는 목록으로 사용하려고합니다. 여기에 나열된 모든 것을 구현하지 않았습니다.

글쓰기 스타일

여기서 코드는 전문 코딩에 사용할 스타일로 형성되지 않습니다. 모든 팀에는 코드 스타일에 대한 문화와 의견이 있으며 이러한 일반적인 지침을 고수하는 것이 좋습니다. 또한 코드는 주로 다른 사람들이 읽을 수 있도록 작성되거나 기계 독자 만 목표로하는 경우 최대 성능을 위해 어셈블리로 코드를 코드로 작성합니다. 코드 팀의 일원으로 작성하는 코드는이 팀의 다른 사람이 작성했을 수 있습니다.

여기에 코드는 EMAC 및 ORG 모드 덕분에 쓰레기 프로그래밍으로 작성되었습니다. 이는 Clojure로 작성된 코드가 그 배후의 추론을 설명하는 텍스트 파일에서 파생된다는 것을 의미합니다. 읽기가 더 쉬워지기를 바랍니다.

파이썬

새로운 문제를 준비하는 것

./dev-resources/new-problem.sh 
  --problem-path neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups

--help 참조.

초기화 스크립트가 완료되면 테스트에 대한 제안 된 명령이 마지막에 나타납니다.

poetry run ptw -- -- 
  src/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups.py 
  tests/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups_test.py

시와 피 테스트와 상호 작용합니다

예를 들어, 개발 중에 테스트를 시청합니다.

poetry run ptw
poetry run ptw -- -- --memray
poetry run ptw -- -- --benchmark-only
poetry run ptw -- -- --benchmark-skip

주위의 작은 춤 -- -- 아마도 피할 수는 있지만, 나는 무엇이 달리는 지에 대해 매우 명백한 것을 선호하기 때문에 poetry 왼쪽의 전면 논쟁으로 유지합니다.

메모리 Flamegraph를 얻으려면 :

poetry run memray run -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4 "
poetry run python -m memray flamegraph memray-neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate.554244.bin

CPU flamegraph (또는 기타 그래프)를 얻으려면 :

poetry run python -m cProfile -o program.prof -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4, 4 "
poetry run snakeviz program.prof

벤치 마크를 실행하고 그래픽 요약을 얻으려면 :

poetry run pytest --benchmark-only --benchmark-histogram

연구 목록

정렬 알고리즘

• 처음부터 구현 : 버블 정렬, 병합 정렬, 빠른 정렬, 힙 정렬.
• 정수 배열이 주어지면 빠른 선택 알고리즘을 사용하여 Kth 가장 작은 요소를 찾으십시오.
• 카운팅 정렬 알고리즘을 구현하여 알려진 범위의 값으로 정수 배열을 정렬하십시오.
• 빠른 정렬을 사용하여 "3 방향 파티션"문제를 해결하여 중복 값의 배열을 효율적으로 정렬하십시오.

알고리즘 검색

• 처음부터 구현 : 이진 검색 (정렬 된 배열), 선형 검색.
• 회전 된 정렬 배열이 주어지면 수정 된 이진 검색을 사용하여 대상 요소를 찾으십시오.

그 트래버스의 그래프, 트리 및 알고리즘

• 처음부터 구현 : BFS (Bradth-Firt Search), DFS (Depth-First Search), Dijkstra 알고리즘, Bellman-Ford 알고리즘.
• 다른 표현을 구현하십시오 : 인접 행렬, 인접력 목록.
• Dijkstra의 알고리즘을 사용하여 가중 그래프에서 두 노드 사이의 가장 짧은 경로를 찾으십시오.
• 이진 검색 트리를 구현하고 삽입, 삭제 및 검색과 같은 기본 작업을 수행하십시오.
• 지시 된 그래프가 주어지면 두 노드 사이에 경로가 있는지 확인하십시오.
• 방향이없는 그래프에서 연결된 구성 요소의 수를 찾으십시오.
• DAG (Directed Acyclic Graph)에 대한 토폴로지 분류를 구현합니다.
• 이진 트리에서 두 노드의 가장 낮은 공통 조상 (LCA)을 찾으십시오.
• 이진 트리가 주어지면 유효한 이진 검색 트리 (BST)인지 확인하십시오.
• 그래프가 주어지면 Kosaraju의 알고리즘 또는 Tarjan의 알고리즘을 사용하여 강력하게 연결된 모든 구성 요소 (SCC)를 찾으십시오.
• Floyd-Warshall 알고리즘을 구현하여 가중 그래프에서 All-Pairs 최단 경로를 찾으십시오.
• n-ary 트리가 주어지면 레벨 주문 트래버스 또는 깊이 우선 순관 (예 : 선주문, 우편 주문)을 수행하십시오.

동적 프로그래밍

• 문제를 더 작은 중첩 하위 문제로 나누는 개념을 이해하고 메모 화 또는 표를 사용합니다.
• 재귀 적 및 역동적 인 프로그래밍 방식을 사용하여 클래식 "Fibonacci"문제를 해결하십시오.
• 가중치와 값이있는 항목 세트가 주어지면 0-1 knapsack 문제를 사용하여 주어진 최대 무게로 얻을 수있는 최대 값을 찾으십시오.

욕심 많은 알고리즘

• 지역적으로 최적의 선택을 만드는 문제 이해는 전 세계적으로 최적의 솔루션으로 이어집니다.
• 겹치지 않는 최대 활동 수를 선택 해야하는 "활동 선택 문제"에 대한 솔루션을 구현하십시오.
• 교단과 양이 다른 동전 세트가 주어지면 탐욕스러운 접근법을 사용하여 그 양을 만드는 데 필요한 최소 동전 수를 찾으십시오.

역 추적 알고리즘

• "n-queens"문제를 해결하여 N Queens를 서로 공격하지 않고 n × n 체스 보드에 배치하십시오.
• 스도쿠 솔버를 구현하여 부분적으로 채워진 스도쿠 퍼즐을 해결하십시오.

문자열 조작 알고리즘

• 문자열 일치
• 문자열 반전
• Palindrome 확인
• 두 줄이 주어지면 하나가 다른 문자열인지 확인하십시오.
• "Rabin-Karp"알고리즘을 구현하여 주어진 텍스트에서 패턴을 찾으십시오.

비트 조작 알고리즘

• 배열에서 단일 고유 한 요소를 찾는 비트 타이어 작업.
• 하나의 숫자를 제외하고 모든 숫자가 두 번 발생하는 배열이 주어지면 단일 고유 번호를 찾으십시오.
• 정수에서 1으로 설정된 비트 수를 계산하는 함수를 구현하십시오.

알고리즘을 나누고 정복합니다

• 이진 검색, 최대 서브 어패레이 합계 찾기.
• 큰 정수의 빠른 곱셈을 위해 Karatsuba 알고리즘을 구현하십시오.
• 분할 및 정복 접근법을 사용하여 2D 공간의 점 중 가장 가까운 점을 찾으십시오.

무작위 알고리즘

• 배열을 무작위로 셔플하십시오.
• "무작위 선택 선택"알고리즘을 구현하여 어레이에서 KTH 가장 작은 요소를 찾으십시오.

슬라이딩 윈도우 기술

• 정수 배열이 주어지면 크기 k의 연속 서브 어레이의 최대 합을 찾으십시오.
• 주어진 문자열에서 최대 k 별개의 문자로 가장 긴 하위 문자를 찾으십시오.

간격 문제

• 간격 목록이 주어지면 중첩 간격을 병합하십시오.
• 간격 목록을 예약하는 데 필요한 최소 회의실 수를 찾으십시오.

시도합니다

• 효율적인 문자열 검색 및 검색을위한 트리 데이터 구조를 구현하십시오.
• 단어 목록이 주어지면 트리를 사용하여 가장 긴 일반적인 접두사를 찾으십시오.
• 주어진 단어 세트에 대한 트리를 사용하여 자동 완성 기능을 구현하십시오.
• 단어 목록이 주어지면 연결이 팔린 드롬을 형성하도록 모든 단어 쌍을 찾으십시오.

해싱

• 해시 기능, 충돌 해상도 기술 및 사용 사례 구현.
• 충돌 해상도 (예 : 체인 또는 오픈 주소 지정)가있는 해시 테이블을 구현하십시오.
• 해시 맵을 사용하여 문자열에서 첫 번째 비 반복 된 문자를 찾으십시오.
• 문자열과 여러 패턴과 일치하는 Rabin-Karp 알고리즘을 구현하십시오.
• 문자 주파수에 대한 해시 맵을 사용하여 캐릭터를 반복하지 않고 가장 긴 부분 문자열을 찾으십시오.

힙

• Min-Heaps 및 Max-Heaps 및 해당 응용 프로그램 (예 : 우선 순위 대기열)을 구현합니다.
• 처음부터 Minheap 또는 Max-Heap을 구현하십시오.
• 다양한 요소가 주어지면 힙 기반 접근법을 사용하여 KTH 가장 큰 요소를 찾으십시오.

매트릭스 조작

• M × N 매트릭스가 주어지면 90도에서 회전하십시오.
• 0과 1의 매트릭스가 주어지면 1 초 (최대 크기의 제곱 서브 매트릭스)의 가장 큰 제곱을 찾아서 그 면적을 반환하십시오.

붉은 검은 나무 또는 AVL 나무

• 빨간색 블랙 트리 또는 AVL 트리의 삽입 및 삭제 작업을 구현하십시오.
• 불균형 바이너리 검색 트리의 균형을 맞추기 위해 회전을 수행하십시오.

데이터 구조 구현

• 배열 및 목록 : 배열, 링크 된 목록 및 작업 구현.
• 스택 및 대기열 : 스택 및 큐 데이터 구조 및 응용 프로그램 구현.
• 해시 맵 : 해시 맵 구현 및 시간 복잡성을 이해합니다.

도구

알고리즘 및 데이터 구조는보다 현실적인 설정과보다 강력한 테스트를 위해 간단한 편안한 API에 의해 노출됩니다.

• 성능

  • API 부하 : Gatling, Jmeter, Locust;

  • 마이크로 벤치 마크 : JMH, Criterium;

  • 자원 : htop , top , vmstat ;

  • 기억 : objgraph, jamm;

• 행동

  • 테스트 : UnitTest, Mockito, 생성 또는 속성 기반 테스트, 표준 테스트 라이브러리 및 관행;

  • 정적 분석 : Sonarqube;

  • 프로파일 링 : 프레임 그래프, cprofile, visualVM, Spring Boot Actuator, Jstack;

• 코드 스타일

  • 돌연변이 테스트 : Lein-Mutant, Pitest, Cosmic Ray;

  • 코드 적용 범위 : Cloverage, Coverage.py, Jacoco;

  • 코드 메트릭 : Radon, Checkstyle, JQassistant;

• 관찰 가능성 : Prometheus, Grafana;

(여기에 나열된 도구는 일부 언어에만 해당 될 수 있습니다)