메모 03 스택과 큐 스택 말 그대로 데이터를 쌓아 올린다(stack)는 의미 LIFO(Last-In-First-Out)으로 자료를 배열함. pop() : 스택에서 가장 위에 있는 항목을 제거 push(item) : item 하나를 스택의 가장 윗 부분에 추가 peek() : 스택의 가장 위에 있는 항목을 반환 isEmpty() : 스택이 비어있을 경우 true 반환 i 번째 항목에 상수 시간 접근이 불가능 단, 데이터 추가, 삭제는 상수 시간에 가능 배열처럼 원소를 하나씩 옆으로 밀어줄 필요가 없음. 같은 방향에서 아이템을 추가하고 삭제한다는 조건하에 연결리스트로 구현할 수 있음. public class MyStack { private static class StackNode { private T da..
면접 문제 2.3 중간 노드 삭제 단방향 연결리스트가 주어졌을 때 중간(정확히 가운데 노드일 필요는 없고 처음과 끝 노드만 아니면 된다.)에 있는 노드 하나를 삭제하는 알고리즘을 구현하라. 단, 삭제할 노드에만 접근할 수 있다. 예제 입력 : 연결리스트 a → b → c → d → e 에서 노드 c 결과 : 아무것도 반환할 필요는 없지만, 결과로 연결리스트 a → b → d → e가 되어 있어야 한다. 힌트 리스트 1 → 5 → 9 → 12를 그려보자. 9를 지우면 1 → 5 → 12가 된다. 9 노드에만 접근할 수 있다. 정답처럼 보이게 만들 수 있겠는가? public class Solution { public static boolean deleteNode(LinkedListNode n) { if (n..
메모 02 연결리스트 차례로 연결된 노드를 표현해주는 자료구조임. 단방향, 양방향이 있음. 연결리스트는 배열과 달리 특정 인덱스를 상수 시간에 접근할 수 없음. 연결리스트의 장점은 시작 지점에 아이템을 추가하거나, 삭제하는 연산을 상수 시간에 할 수 있음. 연결리스트 만들기 class Node { Node next = null; int data; public Node(int d) { data = d; } void appendToTail(int d) { Node end = new Node(d); Node n = this; while (n.next != null) { n = n.next; } n.next = end; } } 이 코드는 LinkedList 자료구조를 사용하지 않음. 연결리스트에 접근할 때 he..
메모 면접 문제 1.4 회문 순열 주어진 문자열이 회문(palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은구절을 의미하며, 순열이란 문자열을 재배치하는 것을 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다. public class Solution { public static void main(String[] args) { String pali = "Rats live on no evil star"; System.out.println(isPermutationPalindrome(pali)); } public static boolean isPermutationPalindrome(String s) { Map characterInteg..
요약 면접 문제 배열과 문자열 해시 테이블 구현을 위해 연결리스트와 해시 코드 함수가 필요함. 충돌을 고려해야 함. ArrayList와 가변 크기 배열 적 가변 크기 기능이 내재되어있는 배열과 비슷한 자료구조를 원할 때 보통 ArrayList 를 사용함. 상환 입력 시간은 왜 O(1)이 되는가 배열 복제가 자주 일어나지 않기 때문 StringBuilder 필요한 경우에만 문자열을 복제함. 면접 문제 메모 9. 면접 문제 www.CrackingTheCodingInterview.com 에서 전체 해법을 다운 받을 수 있음. 01. 배열과 문자열 배열이나 문자열에 대한 문제들은 서로 대체 가능함. 해시 테이블 효율적인 탐색을 위한 자료구조로서 키를 값에 대응시킴. 간단한 해시테이블을 구현하기 위해선 연결리스트..
요약 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)) 오답에 대한 대처법 알고 있던 문제가 면접에 나왔을 때 면접용으로 ‘완벽한’ 언어 널리 사용되는 언어 언어 가독성 잠재적인 문제점 언어가 얼마나 장황한지 사용하기 쉬운 언어 어떤 코드가 좋아 보이나 포기하지 말라 합격한 뒤에 합격 또는 거절 통지에 대처하는 요령 입사 결정 기한과 연장 입사 제안 거절 탈락 통보 대처 입사 제안 평가 재정 관련 사항 경력 개발 회사의 안전성 행복의 척도 연봉 협상 입사 후 튼튼한 관계 수립 원하는 것을 요구하라 꾸준히 면접을 보라 메모 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)) 어떤 문제를 푸는 데 상상할 수 있는 모든 해법 중 수행 시간이 가장 빠른..
요약 기술적 문제 준비하기 알고 있어야 할 것들 핵심 자료구조, 알고리즘, 기본 개념 2의 승수(power of 2) 표 실제 문제 살펴보기 원하는 것이 무엇인가. 최적화 및 문제풀이 기술 #1: BUD를 찾으라 최적화 및 문제풀이 기술 #2: 스스로 풀어보라 DIY(Do Iy Yourself) 최적화 및 문제풀이 기술 #3: 단순화 일반화하라 최적화 및 문제풀이 기술 #4: 초기 사례(base case)로부터 확장하기(build) 최적화 및 문제풀이 기술 #5: 자료구조 브레인스토밍 메모 7. 기술적 문제 준비하기 이 책에 실린 문제를 만날 때마다 다음과 같이 하라 직접 풀도록 노력하라 답을 보지 않고 직접 풀려고 노력하라 공간과 시간 효율에 대해서 반드시 생각하라 코드를 종이에 적으라 코드를 작성하고..
요약 big-O 시간 복잡도 점근적 실행 시간을 의미 최선의 경우, 최악의 경우, 평균적인 경우 알고리즘에서는 최선의 경우를 고려하지 않는 경우가 많음. 공간 복잡도 알고리즘에서는 시간뿐 아니라 메모리 또한 신경 써야 함. 상수항은 무시하라 특수한 입력에 대한 시간 차이를 무시함 지배적이지 않은 항은 무시하라 여러 부분으로 이루어진 알고리즘 : 덧셈 vs. 곱셈 ex) for 문을 끊어서 하는가 중첩에서 하는가 상환 시간 전체 수행 시간이 일정하지 않을 때 분할 상환 개념을 이용 ex) ArrayList 삽입 시간 log N 수행 시간 ex) 원소의 개수가 절반씩 줄어든다. 재귀적으로 수행 시간 구하기 O(분기^깊이) 메모 6. big-O big-O : 알고리즘의 효율성을 나타내는 지표 혹은 언어 시간 ..
요약 면접 전에 탄탄 이력서 작성 필요 적절한 이력서 길이 고용 이력 프로젝트 주요 프로젝트 2~4개 정리 프로그래밍 언어와 소프트웨어 소프트웨어 회사에 적합한 소프트웨어를 신중히 선택 프로그래밍 언어 능숙한 언어가 2개혹은 그 이상은 있어야 함 낙인의 가능성에 대해 알고 있기 행동 문제 여러분의 단점은 무엇인가 진짜 단점 얘기하기 면접관에게는 어떤 질문을 해야 하나 순수한 질문 통찰력을 보여줄 수 있는 질문 열정을 보여줄 수 있는 질문 기술적 프로젝트에 대한 이해 행동 질문에 대한 대처 요령 구체적으로 답하고, 오만한 태도를 보이지 말라 세부사항은 최소한만 언급하라 팀이 아닌 여러분 자신에 초점을 맞춰라 구조적인 답변을 내놓으라 취했던 행동에 대해 논하라 여러분의 이야기를 되짚어 보자 그러니까, 당신에..
요약 특별한 상황에서의 면접 경력자 시스템 디자인은 경력 수준에 비추어 매겨짐. 테스터 혹은 SDET 명시적으로 테스트를 요구하지 않는다고 하더라도 “어떻게 테스트할까” 고민해봐야 함 PM 개발 책임자, 관리자 스타트업 면접관의 입장 여기에 있는 문제를 그대로 사용하지 말라 중간 이상의 어려운 문제를 출제하라 겁을 주는 문제는 피하라 지원자를 긍정적으로 대하라 행동 질문을 철저히 하라 지원자에게 조언하라 그들이 생각할 시간을 원한다면 생각할 시간을 주라 방식을 정하라 : 새너티 테스트, 수준, 전문가, 프락시 메모 3. 특별한 상황에서의 면접 경력자 어떤 회사가 신입 지원자에게 알고리즘을 물어 본다면 그 회사는 경력자에게도 알고리즘 문제를 물어 볼 가능성이 큼. 회사마다 다름 시스템 디자인은 경력 수준에..
요약 면접 과정 분석, 코딩, 기술적 지식, 컴퓨터 과학 기본, 경험, 문화, 의사소통 능력을 봄. 부정 오류는 괜찮다. 실력이 좋은 사람을 원한다. 몇 명을 놓치는 것은 괜찮다. 실력이 좋지 않은 사람을 뽑는 것을 두려워 함. 문제풀이 능력이 좋은 사람을 원함 머리가 뛰어남 → 회사에 가치있는 인재 기초적인 자료구조 알고리즘 지식은 유용함 지원자를 판단할 수 있는 척도가 됨. 회사별 면접 과정 마이크로 소프트 똑똑하고 기술에 열정적인 사람을 원함 아마존 규모 확장성을 고민하는 사람을 원함 구글 규모 확장성을 고민하는 사람을 원함 애플 자신의 생각을 명료하게 전달하는 사람을 원함 페이스북 기업가 정신을 가진 개발자를 원함 어떤 언어든 확장 가능한 시스템을 만들어나갈 개발자를 원함 팰런티어 뛰어난 사람을 ..
책너두 6기에 참여했다. 이번에는 코딩 인터뷰 완전분석이라는 책을 선택했다. 실무에 필수적인 내용이 아니었기에 미루거나 초반 부만 시도하다가 그만둔 책인데 이번 기회에 이 책을 다 읽어서 코딩 인터뷰에 대한 인사이트를 얻고, 문제에 대한 유연한 사고를 해보고자 이 책을 선택했다. 전반적인 내용 초반부는 면접, 인터뷰에 대한 요령 및 예시를 설명한다. 중반부는 면접 문제에 등장하는 자료구조, 알고리즘에 대한 내용이 주를 이룬다. 후반부는 지식 기반문제에 대한 내용으로 C, C++, JAVA 언어에 대한 내용, 데이터베이스, 스레드와 락에 대한 내용을 설명한다. 독서 전략 기존에 읽어 왔던 책과 확실히 다른 독서 전략이 필요하다. 코딩 인터뷰에 대한 내용이기 때문에, 단순히 책을 읽는 것을 넘어서서 문제를 ..