[Powered by Google Translate] [세미나 : 기술 인터뷰] [케니 유, 하버드 대학교] [이 CS50 수 있습니다.] [CS50.TV] 안녕 모두, 내가 케니입니다. 저는 현재 중학교 공부 컴퓨터 과학입니다. 전 전 CS TF, 그리고 나는 underclassman 때이이 있었으면 좋겠다 내가이 세미나를주지 이유 죠. 그래서 당신이 즐기시기 바랍니다. 본 세미나는, 기술 면접에 대해 얘기입니다 그리고 모든 자원은이 링크에서 찾을 수 있습니다 여기이 링크 자원의 몇. 그래서 꽤 몇 가지 문제가, 사실은, 문제의 목록을 만들었어요. 우리가 조언을 찾을 수 있습니다 또한 일반 리소스 페이지 인터뷰를 준비하는 방법에 대한, 당신이 실제 인터뷰하는 동안 무엇을해야하는지에 대한 도움말을, 뿐만 아니라 나중에 참조 할 수 있도록 문제와 자원을 접근하는 방법. 그것은 모든 온라인입니다. 그리고 이번 세미나 면책 조항을 시작해 to 이렇게 안돼 - 인터뷰 준비를 이 목록에 제한되어서는 안됩니다. 이은, 안내하기위한 것입니다 당신은 확실히, 나는 소금 입자로 말을 전부를해야합니다 뿐만 아니라 당신의 면접 준비를하는 데 도움이 모든 것을 사용합니다. 

나는 다음 슬라이드를 통해 빠르게거야 그래서 우리는 실제 사례 연구로 이동할 수 있습니다. 소프트웨어 엔지니어링 postion에 대한 인터뷰의 구조, 일반적으로는 30-45분 것은, 회사에 따라 여러 발. 종종 당신은 화이트 보드에 코딩됩니다. 따라서이 같은 있지만, 종종 작은 규모의 화이트 보드. 당신이 전화 인터뷰를 문제가있는 경우, 당신은 아마 사용할 것 collabedit하거나 Google 문서 중 하나 그래서 그들은 당신이 코딩 살고 볼 수 있습니다 당신은 전화로 인터뷰하는 동안. 인터뷰 자체는 일반적으로 2 ~ 3 문제입니다 컴퓨터 과학 지식을 테스트합니다. 그리고 거의 확실히 코딩 포함됩니다. 당신이 볼 수있는 질문의 종류는 일반적으로 데이터 구조 및 알고리즘입니다. 그리고 문제가 이러한 종류의 일을에 사람들이 좋아하는 당신을 물어볼 것입니다, 어떻게 시간과 공간의 복잡성, 큰 O입니까? 종종 그들은 또한 높은 수준의 질문을 따라서, 시스템을 설계 어떻게 코드를 배치까요? 어떤 인터페이스, 어떤 클래스, 귀하의 시스템에 어떤 모듈이있어, 이러한이 어떻게 함께 상호 작용합니까? 따라서 데이터 구조 및 알고리즘뿐만 아니라 설계 시스템. 

우리는 사례 연구에 뛰어 들기 전에 몇 가지 일반적인 도움말을 제공하고 있습니다. 나는 가장 중요한 규칙은 항상 큰 소리로 생각을 할 수있다 생각합니다. 인터뷰는 사고 과정을 보여줄 수 있어야합니다. 면접관은 측정하기 위해 인터뷰의 요점은 당신이 어떻게 생각하고 어떻게 문제를 통해 이동합니다. 당신이 할 수있는 최악의 일은 전체 인터뷰 내내 수 조용입니다. 그건 그냥 안 좋네요. 당신은 질문을 제공하는 경우, 당신은 또한 질문을 이해하고 있는지 확인하려고. 따라서 자신의 단어에 다시 질문을 반복 그리고 시도는 철저하게 몇 가지 간단한 테스트 케이스를 일을하는 당신이 질문을 이해했는지 확인합니다. 몇 가지 테스트 케이스를 통해 작업하면 당신에게이 문제를 해결하는 방법에 대한 직관을 제공합니다. 당신은 몇 패턴이 문제를 해결하기 위해 발견 할 수 있습니다. 그들의 큰 팁은 좌절하지하는 것입니다. 좌절하지 마십시오. 인터뷰는 도전하지만, 당신이 할 수있는 최악의 일, 침묵 할뿐만 아니라, visibly 좌절하는 것입니다. 당신은 인터뷰에 해당 인상을주고 싶지 않아. 한가지 당신 - 그래서, 많은 사람들이, 그들이 인터뷰로 이동, 그들은 먼저 최선의 해결책을 찾기 위해 노력을 시도 때 정말 눈부시게 명백한 해결책는 없습니다. 그것은 느려질 수 있습니다, 그것은 비효율적 일 수도 있지만, 그냥 명시해야합니다 그냥 좀 더 일을하기에 시작 지점이 있습니다. 또한 솔루션을 지적하는 측면에서, 느린 큰 O 시간 복잡도 나 공간의 복잡성, 당신이 이해하는 면접관 to 보여줍니다 이러한 문제 코드를 작성할 때. 그래서 일단 가장 간단한 알고리즘을 마련 걸 두려워하지 말라고 그리고 거기에서 더 나은 작동합니다. 질문까지? 좋아,. 

그럼 시작하자 첫 번째 문제에 뛰어. "N의 정수의 배열을 감안할 때, 배열을 shuffles 함수를 작성합니다 N 개의 정수의 모든 순열이 동등하게 가능성이있는 것으로 같은 장소에서. " 그리고 당신이 사용할 수있는 임의의 정수 생성기가 가정 그 반은 범위, 0 ~ 전까지 범위의 정수를 생성합니다. 모든 사람들이이 질문을 이해합니까? 내가 N 개의 정수의 배열을 제공, 그리고 당신이 셔플을 원하는. 내 디렉토리에 나는 무슨 뜻인지 설명 할 수있는 몇 가지 프로그램을 썼습니다. 나는 셔플 20 요소의 배열을 갈거야 -10에서 9까지, 그리고 당신은 같은 목록을 출력하고 싶습니다. 그래서 내 정렬 입력 배열이며, 당신이 셔플을 원하는. 우리는 또 할거야. 모두가 질문을 이해합니까? 좋아,. 그럼 당신에게 달려 있습니다. 몇 가지 아이디어는 무엇입니까? 당신은 N ^ 2, N 로그 N, N으로 할 수 있습니까? 제안을 엽니 다. 좋아,. 에미가 제안한 따라서 하나의 생각, 첫번째 0에서 20 임의의 숫자, 임의의 정수, 범위를 계산합니다. 따라서 우리의 배열이 20의 길이가 가정합니다. 20 요소의 다이어그램에서, 이곳은 우리의 입력 배열입니다. 그리고 지금, 그녀의 제안은 새로운 배열을 만드는 것입니다 그래서이 출력 배열 될 것입니다. 그리고 내가 란드에 의해 반환 된에 따라 - 난다면,, 17, 보자 첫 번째 위치에 17 요소를 복사합니다. 이제 우리는 삭제할 필요가 - 우리는 여기에 모든 요소를​​ 이동해야합니다 이상 우리가 말에 격차와 중간에 구멍이 있는지. 그리고 지금 우리는 과정을 반복합니다. 이제 우리는 0과 19 사이의 새로운 임의의 정수를 선택하십시오. 우리는 여기에서 새 I를 가지고 있고, 우리는이 위치에이 요소를 복사합니다. 그럼 우리가 위에 항목을 이동하고 우리는 완전히 새로운 배열을 가지고 때까지이 과정을 반복합니다. 이 알고리즘의 실행 시간은 무엇입니까? 음,이 미치는 영향을 생각해 보자. 우리는 모든 요소를​​ 이동합니다. 우리가이 있는데 난을 제거하면, 우리는 왼쪽으로 한 후 모든 요소를​​ 이동합니다. 그래서 O (n)이 비용이다 때문에 우리가 첫 번째 요소를 제거하면? 따라서 각 제거, 우리는 제거 - 각 제거는 O (n)이 작업을 부과 우리가 삭제를 향한이 때문에,이 O (N ^ 2) 셔플로 연결됩니다. 좋아,. 그럼 좋은 시작. 좋은 시작. 

또 다른 제안은 누스 셔플로 알려진 무언가를 사용하는 것입니다 또는 피셔 - 예이츠 셔플. 그리고 실제로 선형 시간 셔플입니다. 그리고 아이디어는 매우 비슷합니다. 다시 말하지만, 우리는 우리의 입력 배열을 가지고 대신 우리의 입 / 출력을 위해 두 배열을 사용, 우리는 우리의 질질 부분을 추적하기 위해 배열의 첫 번째 부분을 사용 우리는 추적하고 우리는 unshuffled 부분에 대한 우리의 배열의 나머지 부분을 두십시오. 그래서 여기 내 말 무슨 뜻인지입니다. 우리는로 시작 - 우리는 i를 선택 0에서 20 배열입니다. 현재 포인터는 첫 번째 인덱스를 가리키고 있습니다. 우리는 내가 여기를 선택 지금 우리는 스왑. 이 5 살이 4 게 아니라면 결과 배열은 여기 오 여기 4해야합니다. 그리고 지금 우리는 여기에 마커를 확인합니다. 왼쪽에있는 모든, 질질 is 그리고 오른쪽에있는 모든이 unshuffled 있습니다. 그리고 지금 우리는이 과정을 반복 할 수 있습니다. 우리는 지금 1 20 사이의 임의의 인덱스를 선택합니다. 그래서 여기에 우리의 새로운 가정 해 보겠습니다. 이제 우리는 여기에 현재 새로운 위치로이 전을 교환. 그래서 우리는 이런 식으로 앞뒤로 교환 않습니다. 내가 더 구체적인 할 수있는 코드를 가져 보자. 우리는 내가 우리의 선택 시작 - 내가가 0으로 우리가 시작, 우리는 임의의 위치 제이를 선택 배열의 unshuffled 부분에, 내가 N-1. 내가 여기 온 경우, 여기 배열의 나머지 부분 사이의 임의의 색인을 선택 우리는 스왑. 이 셔플 귀하의 배열을하는 데 필요한 모든 코드입니다. 질문? 

음, 하나는 질문을 필요로하는 것은, 왜이 정확합니까? 왜 모든 순열은 동일 가능성이 높습니다? 그리고, 이것의 증명을 통과하지 않습니다 하지만 컴퓨터 과학의 많은 문제는 유도를 통해 입증 할 수 있습니다. 어떻게 많은 것은 유도에 대해 잘 알고있는? 좋아,. 좋아. 그럼 당신은 간단 유도하여이 알고리즘의 정확성을 입증 할 수 귀하의 유도 가설이있는 곳, 그 가정 제 셔플은 모든 순열 동등하게 가능성을 반환 최대 우선 요소에. 지금은, + 1을 고려하십시오. 그리고 우리가 Google 색인 제이가 바꿔 치기를 선택하는 방식으로, 다음은 세부 사항을 해결 -이로 연결 이 알고리즘은 반환 이유를 적어도 전체 증명 동등하게 가능성이 확률로 모든 순열. 

좋아요, 그럼 다음 문제가 발생했습니다. 따라서 ", 제외, 제로, postive 정수의 배열을 제공 최대 합계를 계산하는 함수를 작성합니다 입력 배열의 continueous subarray의. " 여기 예를 들어, 모든 숫자가 긍정적 인 경우,이 그리고 현재 최선의 선택은 전체 배열을하는 것입니다. 1, 2, 3, 4, 10과 같습니다. 거기에 일부 제외가있는 경우 이 경우에 우리는 처음 두 필요 -1 및 / 또는 -3를 선택하는 것은 우리의 합계를 나타납니다 때문입니다. 때때로 우리는 배열의 중간에 시작해야 할 수도 있습니다. 때때로 우리 모두의 아무것도 선택하고 싶지, 그것은 아무것도 안하는 것이 좋습니다. 그리고 가끔은 물러나야하는 것이 좋습니다 그 후 점은 슈퍼 큰 때문입니다. 모든 아이디어는 그래서? (학생, 이해할 수없는) >> 그래. 나는 -1하지 말아요 가정 해 보겠습니다. 그런 다음 나는 1,000 20,000 선택 아니면 3 억 선택합니다. 음, 가장 좋은 선택은 모든 숫자를하는 것입니다. 이 -1, 제외 임에도 불구하고, 전체 합계는 내가 -1을하지 못한 것이 좋습니다. 그래서 앞서 언급 한 방법 중 하나는 분명 당연한 것이 었습니다 첫 번째와 폭력 솔루션입니다. 이 문제의 폭력 솔루션은 무엇입니까? 응? [제인] 글쎄, 난 폭력 솔루션 것 같아요 가능한 모든 조합을 (이해할 수없는)를 추가하는 것이다. [유] 좋아. 그럼, 제인의 아이디어는 가능한 모든을하는 것입니다 - 나는 paraphrasing 해요 - 가능한 모든 연속 subarray을하고, 의 합계를 계산하고 가능한 모든 연속 subarrays의 최대보십시오. 어떻게 고유 내 입력 배열에 subarray를 식별? 내가 뭘 두 가지 필요 하죠처럼? 응? (학생, 이해할 수없는) >> 맞아. 낮은 색인과 상단 바운드 인덱스에 행 고유 연속 subarray를 결정합니다. [여자 학생] 우리는 고유 한 숫자의 배열 추정 있습니까? [유] 아니, 그녀의 질문에 그래서, 우리는 배열을 가정 아르 수 있습니다 - 우리 어레이는 고유 번호입니다, 그리고 대답은 '노'입니다. 

우리는 우리의 폭력 솔루션, 시작 / 끝 인덱스를 사용하는 경우 고유 지속적으로 subarray를 결정합니다. 우리는 가능한 모든 시작 항목을 반복하면, 모든 최종 항목에> 또는 =, 시작하고 <N에게 당신은 합계를 계산 한 후 우리는 우리가 지금까지 본 적이있는 최대 금액을. 이 들었나? 이 솔루션의 가장 큰 O는 무엇입니까? Timewise. 매우 ^ 2를 향한 없습니다. 우리는 0에서 N으로 반복합니다 그래서 그 루프 하나. 우리는 루프를 들어, 거의 처음부터 끝까지 다시 다른 반복합니다. 그리고, 그 안에, 우리는 모든 항목을 요약해야 그래서 그 루프에 다른입니다. 그래서 우리는 세 루프에 대한 중첩, N ^ 3을 갖추고 있습니다. 좋아,. 이 시작 지점으로갑니다. 우리 솔루션은 N ^ 3보다 더 나빠하지 않습니다. 모두가 폭력 솔루션을 이해합니까? 

좋아,. 더 나은 솔루션은 동적 프로그래밍이라는 개념을 사용하고 있습니다. 당신은 CS124을하면되는데,이, 알고리즘 및 데이터 구조입니다 이 기술을 잘 알고 될 것입니다. 그리고 아이디어는 먼저 작은 문제에 대한 해결책을 구축하려고합니다. 시작과 끝 :이 사람이 내 말 무슨 뜻인지, 우리는 현재 두 가지 걱정해야합니다. 그리고 짜증나니까. 우리가 그 매개 변수 중 하나를 제거 할 수 있다면 무엇입니까? 우린 우리의 원래 문제가 주어 - 하나의 아이디어에서 가깝습니다 범위에서 subarray의 최대 합계 [O, N-1]를 찾습니다. 그리고 지금 우리는, 우리의 현재 색인 내가, 우리가 알고있는 새로운 subproblem을 가지고 우리는 우리가 결론을해야합니다 알아요. 우리 subarray은 현재 색인에서 끝나야합니다. 남은 문제는 그래서, 어디 우리 subarray을 시작해야하나요? 이 말이 돼? 좋아,. 그래서이 일을 코딩 한 결과, 무슨 뜻인지 살펴합시다. codirectory에서 subarray라는 프로그램이있어 그리고, 항목의 수를 소요 그리고 내 질질 목록에서 최대 subarray 합을 반환합니다. 따라서이 경우에, 우리의 최대 subarray은 3입니다. 그리고 그건 그냥 2 1을 사용하여 갔죠. 의 다시 실행할 수 있습니다. 또한 세입니다. 하지만 이번에는 우리는 3를 얻었는지 확인합니다. 우리는했다 - 우리가 3 자체를 그것은 양쪽에 제외로 둘러싸여 있기 때문에, 합에게 <3을 가져집니다. 의 10 항목을 실행할 수 있습니다. 가 7로이 시간, 우리는 선도적 인 3, 4를. 이 시간은 8이고, 우리는 1, 4, 3를 취하여 것을을 구하십시오. 그럼 당신에게 방법에 대한 직관을주고 우리는이 transformed 문제를 해결할 수 있습니다, 의이 subarray를 살펴 보자. 우리는이 입력 배열을 제공, 우리는 답은 8 알하고 있습니다. 우리는 1, 4, 3을. 그러나의 우리가 실제로 그 답을 얻었는지 살펴 보도록하겠습니다. 의 이러한 인덱스의 각에 마감 된 최대 subarray 살펴 보도록하겠습니다. 첫 번째 위치에 종료하는 최대 subarray은 무엇입니까? [학생] 제로. >> 제로. 그냥 -5도 취하지 않습니다. 여기뿐만 아니라 영거야. 응? (학생, 이해할 수없는) [유] 아, 죄송 해요, 그것은 -3입니다. 이 2 그래서이 -3입니다. 좋아,. 그럼 -4 그 위치를 종료 할 수있는 최대 subarray이 뭐죠 -4은 어디 있는거야? 제로. 하나? 1, 5, 8. 자, -2가에있는 위치에서 끝나야합니다. 따라서 6, 5, 7, 그리고 마지막 하나는 4입니다. 이 내 항목임을 알고 난이 인덱스의 각에 종​​료해야합니다 변환 문제에 대한, 그리고 마지막 대답은 단지이다,에서 스윕을 및 최대 개수를. 따라서이 경우는 8입니다. 이것은 최대 subarray이 색인에 끝을 의미 그리고 전에 어딘가에 시작했다. 모든 사람은이 변형 subarray을 이해합니까? 

좋아,. 음,이에 대한 재발을 찾아 보자. 그냥 처음 몇 항목을 생각해 보자. 그래서 여기가, 8 0, 0, 0, 1, 5했습니다. 그리고 거기에 여기 -2이었고, 그 6 내려 왔어. 나는 위치에서 항목을 전화면 내가 subproblem은 (i), 어떻게 이전 subproblem에 대한 답변을 사용할 수 있습니다 이 subproblem 대답? 제가 보면이 항목이 있다고 가정합니다. 어떻게 보면 답 6 계산할 수 이 배열이 배열의 이전 subproblems에 대한 답변의 조합? 그래? [여자 학생] 당신은 금액의 배열을 위치에 바로 전, 8 있으므로 그리고 당신은 현재 subproblem을 추가합니다. [유]는 그녀의 제안이 두 숫자 보는 것입니다 그래서 이 번호와 번호입니다. 그래서 8 subproblem에 대한 답변 (- 1 I)을 의미합니다. 그리고의 내 입력 배열 A. 전화 할게 위치 i를에 끝나는 최대 subarray을 찾으려면하면, 나는 두 가지 선택이 있습니다 나도 subarray를 계속할 수 그 이전의 색인에 종료하거나 새 배열을 시작합니다. 나는 이전 색인에서 시작 subarray를 계속한다면 그럼 내가 달성 할 수있는 최대 금액은 이전 subproblem에 답 플러스 현재 배열 항목. 그러나, 나는 또한, 새로운 subarray을 시작 선택할 수 있습니다 이 경우의 합계는 0입니다. 1, 플러스 현재 배열 항목 - 그래서 답은 0 최대, subproblem 전입니다. 이 재발하지 않니? 우리 재발는 우리가 발견 한 것처럼 subproblem 전입니다 , 이전 subproblem의 최대 더불어 현재 배열의 항목과 동일 이는, 이전 subarray을 계속 의미 또는 0, 현재 인덱스에서 새 subarray를 시작합니다. 그리고 일단 우리가 우리의 마지막 대답은 다음 솔루션이 테이블을 구축 한 단지 subproblem 배열에서 선형 스윕을 및 최대 개수를. 이건 내가 무슨 말을하는지의 정확한 구현 한 것입니다. 그래서 우리는 새로운 subproblem 배열, subproblems을 만듭니다. 첫 번째 항목은 0 또는 첫 번째 항목, 두의 최대 중입니다. 그리고 subproblems의 나머지 부분에 대한 우리는 우리가 발견 한 정확한 재발을 사용합니다. 이제 우리는 우리의 subproblems 배열의 최대 계산, 그건 최종 답변입니다. 

따라서 공간이 얼마나 우리는이 알고리즘에 사용하고 있습니까? 만 CS50를 취했다면, 당신은 매우 많은 공간을 논의하지 수 있습니다. 음, 한가지 유의할 사항은 제가 크기 N과 함께 malloc이라는 것입니다. 그건 당신에게 무슨 제안합니까? 이 알고리즘은 선형 공간을 사용합니다. 우리는 더 나은 작업을 수행 할 수 있습니까? 당신이 최종 답을 계산 필요는 것을 알 것이 있나요? 내 생각에 더 좋은 질문이되고, 어떤 정보 우리는 마지막까지 모든 방법을 수행 할 필요가 없습니다합니까? 이제, 우리는이 두 행을 보면, 우리는, 이전 subproblem에 관심 그리고 우리는 우리가 지금까지 본 적이 최대 관심. 최종 답변을 계산하기 위해, 우리는 전체 배열을 필요하지 않습니다. 우리는 마지막 번호 마지막 두 숫자 만 필요합니다. 최대의 subproblem 배열, 마지막 번호 마지막 번호입니다. 그래서, 사실, 우리가 함께 이러한 루프를 융합 할 수 및 선형 공간에서 일정한 공간으로 이동합니다. 현재 합 지금까지, 여기 subproblem 우리 subproblem 배열의 역할을 대체합니다. 따라서 현재의 합계는, 지금까지 이전 subproblem에 대한 답입니다. 그리고 그 합계는, 지금까지 우리의 최대의 이루어집니다. 우리도 진행하는데로 우리는 최대를 계산합니다. 그래서 우리는, 일정한 공간을 선형 공간에서 이동 우리는 또한 subarray 문제에 대한 선형 해결책을 가지고 있습니다. 

질문 이러한 종류의 당신은 인터뷰하는 동안 얻을 것이다. 시간 복잡도는 무엇입니까, 공간 복잡도는 무엇인가? 당신은 좀 더 할 수 있습니까? 주위에 유지하는 데 필요되는 부분이 있습니까? 난 당신이 직접 수행 할 분석을 강조하기 위해 이런 짓을 당신은 이러한 문제를 통해 최선을 다하고 있습니다. 항상 "내가 더 잘 할 수 있습니까?"자신을 요청해야 사실, 우리는이보다 더 할 수 있습니까? 트릭 질문의 정렬. 당신이 필요하기 때문에, 안 돼 최소한 문제에 대한 입력을 읽습니다. 당신이해야 할 사실은 적어도이 문제에 대해 입력을 읽었다 당신이 선형 시간보다 더 잘할 수 있다는 것을 의미 당신은 일정한 공간보다 더 잘할 수 없습니다. 그래서이 사실,이 문제에 대한 가장 좋은 솔루션입니다. 질문이 있으십니까? 좋아,. 

주식 시장 문제 : "긍정적, 제로, 또는 부정적인 N 개의 정수의 배열 감안할 때, 즉, N 일 동안 주식의 가격을 나타냅니다 당신이 할 수있는 최대 이익을 계산하는 함수를 작성 당신이 N 일 이내에 정확하게 한 주식을 사고 팔 것을 고려. " 기본적으로, 우리는 낮은 구입 높은 판매하고 싶습니다. 그리고 우리는 우리가 할 수있는 최선의 이익을 파악하고 싶습니다. 내 팁으로 돌아 간다, 어떻게 즉시 명확하고 간단한 대답은하지만 속도가 느린거야? 그래? (학생, 이해할 수없는) >> 예. >> 그래서 당신은하지만 가서 주식 가격을 살펴볼 수 에서 시간에 각 점 (이해할 수없는). [유] 그래, 그럼 그녀 솔루션 - 컴퓨팅 그녀의 제안 최저와 최고를 계산 반드시 작동하지 않습니다 가장 높은이 가장 낮은 전에 발생할 때문입니다. 따라서이 문제에 대한 폭력 솔루션은 무엇입니까? 나는 고유 제가 만든 이익을 결정하는 데 필요한 두 가지 사항은 무엇입니까? 맞아. 폭력 솔루션입니다 - 그럼, 조지의 제안은 우리가 이틀 필요가있어 독특한 두 일 이익을 결정합니다. 그래서 우리는, 구입 / 판매 좋아, 모든 쌍을 계산 음수 또는 양수 또는 0이 될 수있는 이익을 계산합니다. 우리가 일의 모든 쌍으로 반복 한 후 확인하는 최대 이익을 계산합니다. 그래서 최종 답변이 될 것입니다. 그리고 그 해결책이 있기 때문에, O (N ^ 2)로 N 이쌍를 선택합니다 - 당신이 마지막 일 중에서 선택할 수 있습니다 일. 좋아, 내가 여기 폭력 솔루션으로 가지 않을거야. 나는 N 로그 N 솔루션은이 말을거야. 현재 N 로그 N입니다 어떤 알고리즘을 알 수 있습니까? 속임수의 질문이 아니 란다. 

정렬을 병합합니다. 병합 정렬은 N 로그 N입니다 그리고 사실,이 문제를 해결하는 한 가지 방법은 사용하는 것입니다 라는 아이디어 병합 정렬 종류는 일반적으로 나눠서 맡을. 다음과 같이 그리고 아이디어입니다. 당신은 최고 거래를 계산 / 왼쪽 반으로 쌍을 판매하고 싶습니다. 당신은 두 일 동안의 첫 번째 N과 함께 할 수있는 최선의 이익을 찾아보세요. 그럼 당신은 최고의 거래를 oompute / 오른쪽 절반에 쌍을 판매 할 2 일간 그래서 마지막 n. 이제 문제는 어떻게 우리가 다시 함께 이러한 솔루션을 병합 않습니다인가요? 그래? (학생, 이해할 수없는) 좋아요 >>. 그럼 내가 그림을 그려 보자. 그래? (조지, 이해할 수없는) 정확히 >>. 조지의 솔루션은 정확히 맞아. 그의 제안은 그래서 먼저, 가장 구매 / 판매 쌍을 계산 그리고 왼쪽 반으로 발생합니다 그러니, 왼쪽, 왼쪽 것을이라고 불러. 최선의 오른쪽 절반에서 발생하는 쌍을 구입 / 판매하고 있습니다. 우리는이 두 숫자를 비교한다면, 우리는 사건을 누락 여기 구입하고 오른쪽 절반 어딘가에 팔. 우리는 왼쪽 반으로 구입, 오른쪽 반으로 판매하고 있습니다. 그리고 두 반쪽에 걸쳐 최고의 구매 / 판매 쌍을 계산하는 가장 좋은 방법은 여기에 최소 계산하고 여기에 최대를 계산하는 것입니다 과의 차이를. 구매 / 판매 쌍은 여기가 발생하여 두 경우를 따라서 여기뿐 또는 두 가지 모두 절반에이 세 숫자에 의해 정의됩니다. 다시 우리의 솔루션을 병합에 대한 우리의 알고리즘은 자 우리는 최고의 구매 / 판매 쌍을 계산하려면 우리가 왼쪽 부분에 구입하여 오른쪽 절반에 팔. 그리고 할 수있는 가장 좋은 방법은, 최초의 반으로 최저 가격을 계산하는 것입니다 가장 오른쪽 반 가격과의 차이를. 그 결과 세 이윤은이 세 숫자는, 당신은 세 가지의 최대를 그리고 그 말은 당신이 첫 번째와 마지막 일 동안 만들 수있는 최선의 이익입니다. 다음은 중요한 선은 빨간색입니다. 이 왼쪽 반으로 답을 계산하는 재귀 호출입니다. 이것은 오른쪽 절반에 답을 계산하는 재귀 호출입니다. 이 두 루프에 각각 왼쪽과 오른쪽 절반에 분, 최대 계산합니다. 지금은 모두 절반에 걸쳐 이익을 계산 그리고 최종 답은이 세의 최대입니다. 좋아,. 

그럼, 물론, 우리는 알고리즘을 가지고 있지만 더 큰 문제는 이 시간 복잡도는 무엇인가? 그리고 병합 정렬을 언급하는 이유는이 양식에 대한 답변을 나눌 것입니다 두 개로하고 다시 우리의 솔루션을 통합 정확히 병합 정렬의 형태입니다. 그래서 나는이 기간을 통해 가자. 우리는 단계의 수를 될 수있는 기능을 t (N)을 정의하는 경우 N 일 경우, 두 재귀 호출 각 t (N / 2), 비용 거예요 그리고 이러한 호출의 두 종류가 있습니다. 지금은, 왼쪽 반 이상을 계산해야합니다 난 상 / 2 시간, 플러스 오른쪽 절반의 최대에 수행 할 수있는. 그래서 막 습니됩니다. 그리고 어떤 일정한 일을 플러스. 그리고이 재발 방정식 정확히 병합 정렬의 재발 방정식입니다. 그리고 우리는 병합 정렬 N 로그 N 시간 것을 알고있다. 따라서, 우리의 알고리즘은 로그 N 시간 습니하고 있습니다. 이 반복 않니? 이 아주 간단한 뉴스 레터를 살펴 : T (N)은 최대 이익을 계산하는 단계의 수입니다 N 일의 과정 동안. 우리는 재귀 호출을 분할하는 방법 , 첫 번째 N / 2 일에 우리의 솔루션을 호출하는 것입니다 그래서 한 통화가 ... 그리고 우리는 후반에 다시 전화하십시오. 그럼 두 통화입니다. 그리고 우리는, 우리가 선형 시간에 수행 할 수있는, 왼쪽 부분에 최소를 찾을 수 우리가 선형 시간에 할 수있는 오른쪽 절반의 최대를 찾습니다. 따라서 N / 2 + N / 2는 N입니다. 그럼 우리가 연산을하는 것입니다 어떤 일정한 작업을 수 있습니다. 이 반복 방정식은 정확히 병합 정렬의 재발 방정식입니다. 따라서, 우리 셔플 알고리즘은 또한 N N를 기록합니다. 따라서 공간이 얼마나 우리를 사용하고 있습니까? 가 코드로 돌아가 보자. 

더 나은 질문은 얼마나 많은 스택 프레임을 우리는 어느 특정 순간에해야합니까 무엇입니까? 우리는 재귀를 사용하고 있기 때문에, 스택 프레임의 수는 우리의 공간 사용을 결정합니다. 가 N = 8을 고려하자. 우리는 8 일 셔플 전화 처음 네 항목에 셔플를 호출됩니다, 이는 처음 두 항목에 대한 셔플를​​ 호출합니다. 그럼 우리 스택입니다 - 이건 우리의 스택입니다. 그리고 우리는 1 일에 다시 셔플 전화 그리고 우리의 기본 케이스가 뭔지, 그래서 우리는 즉시 반환합니다. 우리가 이렇게 많은 스택 프레임 이상이 있습니까? 아니, 우리는 호출을 할 때마다 때문에, 셔플에 재귀 호출, 우리는 절반으로 크기를 나눕니다. 우리는 어느 특정 순간에이 스택 프레임의 최대 수 있도록 로그 N 스택 프레임의 순서에 있습니다. 각 스택 프레임은 일정한 공간이 공간의 따라서 총 금액 우리가 사용하는 공간의 최대 금액은 O (로그 n)이 공간입니다 여기서 n은 일 수 있습니다. 

지금, 항상 스스로에게 물어, "우리가 더 잘할 수 있을까?" 그리고 특히, 우리는 이미 해결 한 문제이를 줄일 수 있습니다? 힌트 : 우리는이 전에 다른 두 문제를 논의하고 셔플 않을거야. 우리는 최대 subarray 문제에이 주식 시장 문제를 변환 할 수 있습니다. 우리가 어떻게이 작업을 수행 할 수 있습니까? 둘 중 하나? 에미? (에미, 이해할 수없는) [유] 그렇지. 최대 subarray 문제 자, 우리는 지속적으로 subarray으로 합계를 찾고 있습니다. 그리고 주식의 문제에 대한 에미의 제안, 변경 또는 델타를 고려합니다. 그리고이의 사진입니다 -이 주식의 가격입니다, 하지만 각 연속 일 사이의 차이를 가져 갔다면 - 그래서 우리는 최고 가격이 최대 수익을 우리가 할 수있는 것을 볼 우리가 구매 및 여기에 판매하는 경우입니다. 그러나가 지속적으로 살펴 보자 -가 subarray 문제 살펴 보도록하겠습니다. 그래서 여기, 우리는 할 수 있습니다 - 여기에서 여기로 이동, 우리는 긍정적 인 변화를 가지고 있고, 그 다음에 여기서으로 떠날 우리는 부정적인 변화가 있습니다. 하지만, 우리가 큰 긍정적 인 변화가 여기에서 여기로 이동. 그리고 이러한 우리의 최종 이익을 얻을 요약 할 사항입니다. 그럼 우리가 더 많은 부정적인 변화 자네가 있습니다. 우리의 최대 subarray 문제로 우리의 재고 문제를 감소하기위한 핵심 일 사이의 델타를 고려하는 것입니다. 그래서 우리는, 삼각지라는 새로운 배열을 생성 , 0이 될 수있는 첫 번째 항목을 초기화 다음 각 삼각주은 (i), 차이 것을 알려 내 입력 배열은 (i), 그리고 배열 ​​(I - 1). 그럼 우리가 최대 subarray에 대한 일상적인 프로 시저를 호출 델타의 배열에 전달. 그리고 최대 subarray은 선형 시간, 때문에 이 감소,이 델타 배열을 만드는 과정, 또한 선형 시간 그리고 주식에 대한 최종 해결책은 O (n)이 작동 플러스 O (n)이 작품, 여전히 O (n)이 작품이다. 그래서 우리는 우리의 문제에 대한 선형 시간 해결책을 가지고 있습니다. 모든 사람들이 이러한 변화를 이해합니까? 

당신은 항상 가지고 있어야한다고 일반적으로 좋은 생각 당신이 보는 것을 새로운 문제를 줄이기 위해 노력하고 있습니다. 그것은 오래된 문제에 익숙 경우, 오래된 문제에를 줄여보십시오. 그리고 당신은 당신이 이전 문제에 사용한 모든 도구를 사용할 수 있는지 새로운 문제를 해결합니다. 따라서 포장을, 기술 면접은 도전하고 있습니다. 이러한 문제는 아마도 더 어려운 문제 중 일부입니다 당신은 인터뷰에서 볼 수 있다는 당신은 방금 적용하는 모든 문제를 이해하지 않는 경우, 그래서 괜찮아. 이것들은 점점 더 어려워 문제 중 일부입니다. 연습, 연습, 연습. 나는 유인물에 많은 문제를했다, 그래서 확실히 그를 확인하시기 바랍니다. 그리고 인터뷰에서 행운을 빌어 요. 내 모든 자료는이 링크에 게시되어 있습니다 내 고위 친구 중 하나는, 모의 기술 면접을 할 제공해 왔습니다 당신이 관심 있다면, 이메일이 이메일 주소 야오 윌. 당신은 몇 가지 질문이있는 경우, 당신은 날 요청할 수 있습니다. 당신들은 기술 인터뷰에 관한 특정 질문이 있습니까 또는 우리가 지금까지 본 적없는 문제가 있습니까? 좋아,. 음, 인터뷰에서 행운을 빌어 요. [CS50.TV]