저는 이번 가을에 업계 전역의 다양한 장소에서 인터뷰하는 데 시간을 보냈습니다. 이 일을 계획하고있는 거의 모든 사람들이 알고 있듯이,모든 회사는 기본적으로 동일한 맛의 질문을 던집니다. 그러나,그들은 어려움과 범위에서 변화 하는 경향이. 인터뷰 경험의 핵심은 알고리즘 및 데이터 구조,즉 표준,1 학년,학부생입니다. 우리는 하루 종일 프로그래머 능력의 좋은 측정 여부를 결정 보낼 수 있지만(그것은 거의 확실 하지 않습니다,특히 누구의 주요 사업 아주 간단한 아이폰 애플 리 케이 션을 구축 하는 기업에 대 한),거래는 게임을 학습 하는 것은 그것을 피하는 것 보다 더 나은(그리고 확실히 더 유리한).
대부분의 인터뷰 준비 자료는 주로 그들의 편재성뿐만 아니라 그들이”너무 많이하지 않는다”는 사실,즉 대부분의 추상화가 꽤 얇기 때문에 자바 또는 씨++로 보인다. 그러나 루비스트가 우리의 선택 도구와의 인터뷰를 통해 자신의 방식으로 일할 수없는 이유는 없습니다. 이 글에서,우리는 루비를 사용하여 몇 가지 합리적으로 쉽게 평균 어려움 인터뷰 문제를 통해 갈 수 있습니다. 그들은 정말 복잡한 코드를 포함하기 때문에 대부분의 시간,열심히 면접 질문은 어렵지 않다;대신,그들은 단지 더 많은 생각과 통찰력을 필요로. 그래서,루비에서 쉽게 물건을 수행하는 방법을 파악함으로써,당신도 어려운 문제를 해결하기 위해 설정해야합니다.
스타일에 대한 참고 사항
이 기사는 가능한 가장 영리한 루비를 작성하는 방법에 관한 것이 아닙니다. 이 아이디어는 이해하기 쉬운 명확한 코드를 작성하는 것입니다.이 코드는 루비 문법에서 사용할 수있는 모든 트릭을 사용하는 것보다(특히 인터뷰 설정에서)더 중요합니다. 따라서 제시된 코드는 가능한 한 단순하고 간단하도록 만들어졌습니다.
링크 된 목록
링크 된 목록은 아마도 인터뷰에서 테스트 된 가장 일반적인 구조 일 것입니다(해시 테이블에서 첫 번째 장소에 대한 경쟁이 심합니다. 따라서 연결된 목록에 친밀하게 익숙해지는 것이 좋습니다. 링크 된 목록 뒤에 개념을 설명하는 다른 많은 소스가 있지만 기본 아이디어는 링크 된 목록이 여러 노드(즉,데이터 조각)로 구성되고 각 노드가 다음 노드에 대한 링크를 포함한다는 것입니다. 때로는 각 노드가 이전 노드뿐만 아니라 다음 노드에 대한 링크를 포함하는 이중 연결 목록을 사용해야합니다.
첫 번째 문제를 해결하기 전에 링크 목록 데이터 구조를 구현하는 방법을 알아 보겠습니다. 그것은 꽤 간단합니다:
class Node attr_accessor :value, :next_node def initialize(value, next_node) @value = value @next_node = next_node endend우리가하고있는 모든 각 노드의 값과 다음 노드에 대한 참조를 유지하고있다. 우리가 먼저 할 수있는 가장 간단한 일을 해결합시다:
Given a node, print the linked list that begins with that node.이것은 매우 쉽다. 우리는 우리에게 주어진 노드에서 현재 노드를 시작하고 값을 인쇄(또는 문자열에 추가)한 다음 현재 노드를 해당 노드의@next_node속성으로 이동합니다. 여기 루비에 있습니다:
class Node ... def to_s curr_node = self res = "" ... end가장 아름다운 코드는 아니지만 작동합니다. 우리는 그것을 테스트 할 수 있습니다:
head = Node.new 8, nil snd = Node.new 7, nil head.next_node = snd puts head.는 리를 공니다.:
Reverse a linked list given its head.이것은 거의 아무도 더 이상 그것을 사용 하 여 너무 인기 있는 문제입니다. 이 솔루션은 즉시 명확하지 않다,하지만 당신은 그것을 백만 번 들었어요 일단 그렇게된다. 기본적으로 우리는이 문제를 재귀 적으로 해결합니다. 노드가 주어지면 먼저 노드가 목록의 마지막인지 여부를 확인합니다. 이 경우 즉시 반환합니다(즉,의 반대는입니다). 그렇지 않은 경우 다음 노드를 역 함수로 전달하십시오. 이 목록을 반전하고 우리가 반전 목록의 끝에 전달 된 노드를 배치합니다. 그런 다음 현재 노드를 이 목록의”다음”에 붙입니다. 이 때문에 현재 노드의 다음 실제로 반전 목록의 끝에서 끝나는 트릭 조금 혼란 그래서 현재 노드의 다음의 다음은 우리가 현재 노드를 넣을 위치입니다. 코드에서 체크 아웃:
def reverse_list(curr) return curr if curr == nil or curr.next_node == nil next_node = curr.next_node new_head = reverse_list(curr.next_node) next_node.next_node = curr curr.next_node = nil return new_headend이 코드는 매우 간단합니다. “속임수”는next_node.next_node = curr에서 나옵니다. 우리는curr의 다음 노드가 반전 된 목록의 끝에있을 것이라는 것을 알고 있기 때문에curr의 다음 노드 끝에curr를 붙입니다. 의 다른 문제를 살펴 보자.
Implement a stack using a linked list.우선,스택이 무엇을 의미하는지 명확히 해 봅시다. 기본적으로,그것은 당신의 책상에 앉아 책의 스택처럼. 당신은 상단에 물건을 넣을 수 있습니다(이 호출됩니다push)당신은 당신이 거기에 넣어 마지막 책을 벗을 수 있습니다(이 호출됩니다pop). 연결된 목록으로 스택을 구현하는 방법에는 여러 가지가 있으며 그 중 하나를 선택합니다.
우리는 링크 된 목록의 머리로 스택의 상단을 추적합니다. 그런 다음,우리는 스택의 상단에 물건을 밀어하려면,우리는 단순히 목록의 머리를 변경하고 이전 머리에 새로운 머리의 다음 노드를 가리 킵니다. 우리는 물건을 팝업 할 경우,우리는 단지 머리를 이동(우리는 오래된 머리의 가비지 수집기 핸들 할당 해제를 드리겠습니다). 의 살펴 보자:
class Stack attr_reader :head def initialize @head = nil end def push(value) new_head = Node.new value, @head @head = new_head end def pop @head = @head.next_node endend당신이 볼 수 있듯이,우리가하고있는 모든 푸시에 머리를 만들고 팝의 다음 노드에 머리를 이동합니다. 우리는 그것을 테스트 할 수 있습니다:
stack = Stack.newstack.push 3stack.push 5stack.push 7stack.popstack.push 8print stack.head우리가 비록 여기에 생략 한 몇 가지 중요한 물건이있다. 빈 스택에서pop를 호출하면 어떻게됩니까? 너는 너의 탐방기자에 이것 가장자리 케이스를 토론하,그들을 취급하는 방법에 올라야 한다(예를들면 예외를 던지십시요).
해시 테이블
해시 테이블은 이러한 인터뷰를 에이스하기 위해 아래로 두드려야하는 또 다른 데이터 구조입니다. 루비에서 해시 테이블은Hash의 인스턴스입니다. 해시 테이블의 내부(예:범용 해싱,체인 등)에 대한 약한 이해로 벗어날 수 있습니다.),그 물건을 이해하는 것은 어떤 시점에서 유용 할 수 있습니다. 거의 모든 알고리즘 교과서는 당신에게이 정보를 제공 할 것입니다.
링크된 목록과 달리 해시 테이블은 루비 라이브러리의 일부이기 때문에 해시 테이블을 직접 구현할 필요가 없으며 해시 테이블을 처음부터 구현할 수 있는지 걱정하는 사람도 거의 없습니다. 의 쉬운 문제를 살펴 보자:
Remove duplicates in an array of numbers.여기에 우리가 무엇을. 우리는 해시 테이블의 각 숫자를 키로 넣은 다음 맨 끝에 키를 반환합니다. 우리는 우리가 이미 본 적이 번호를 발생하는 경우 즉,우리가 이미 해시 테이블에 배치 한 의미하기 때문에,그것은 더 비기 없습니다.
def remove_duplicates(list) set = {} list.each do |el| set = 1 end set.keysend여기서 해시 테이블을 사용하는 요점은 무엇입니까? 이 표는 우리가 이미 전에 요소를 본 적이 있는지 여부를 일정한 시간에 확인할 수 있습니다. 즉,이 코드는 선형 시간에 실행할 수 있습니다. 좋아,조금 더 관련된 것:
두 문자열은 다른 순서 일 수 있지만 동일한 문자(각 문자의 동일한 빈도로)로 구성된 경우 아나그램으로 간주됩니다. 문자열이 다른 철자 바꾸기인지 확인하는 함수를 작성합니다.
이 질문을 구성하는 또 다른 방법은 두 문자열의 각 문자의 빈도가 동일한지 확인하려는 것입니다. 해시 테이블로 주파수를 아주 쉽게 계산할 수 있습니다. 우리는 단지 문자열을 반복 하 고 각 문자에 대 한 값에 추가. 그런 다음,우리는 비교하고 두 주파수가 같은 경우 참조. 여기 루비에 있습니다:
def get_freq(str) freq = Hash.new(0) str.each_char do |chr| freq += 1 end freqenddef check_anagram(str1, str2) return get_freq(str1) == get_freq(str2)end여기서 유일한 특이한 점은Hash.new(0)입니다. 그러면 모든 키의”기본값”값이0인 해시가 생성됩니다. 이것은 약간 사소하고 중요하지 않은 것처럼 보일 수 있지만 주파수를 계산하기 위해 해시 테이블을 자주 사용하기 때문에 거의 모든 해시 테이블 관련 인터뷰 문제에 매우 유용합니다.
마무리
루비와의 인터뷰에서이 짧은 조각에 대한 것입니다. 우리가 지금까지 논의한 물건은 매우 간단하지만,그것은 당신이 당신의 목 아래로 호흡 면접관이있을 때 가장 기본적인 물건을 망치는 것이 얼마나 쉬운 꽤 놀라운 일이다. 다음 부금에서는,우리는 이원 나무 및 루루 캐시의 실시를 다룰 것입니다.