Ch 09 Recursion and Dynamic Programming


재귀적 방법

  • 상향식과 하향식으로 나눠 진다.

동적 프로그래밍의 예: 피보나치 수
중간과정을 저장하면 그게 동적 프로그래밍이다.

$n^2$ 복잡도의 일반 코드

int fibonacci(int i){
	if(i==0) return 0;
	if(i==1) return 1;
	return fibonacci(i-1) + fibonacci(i-2);
}

Time complexity를 $O(n)$으로 줄이는 코드

int[] fib = new int[max];
int fibonacci(int i){
	if (i==0) return 0;
	if (i==1) return 1;
	if (fib[i] != 0) return fib[i]; // 캐시된 결과 반환
	fib[i] = fibonacci(i-1) + fibonacci(i-2); // 계산 결과 캐시
	return fib[i];
}

동적 프로그래밍을 구현 할 때의 전략은 다음과 같다.

  • 재귀함수를 먼저 구현
  • 캐쉬 부분을 구현


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch02 LinkedList  (0) 2017.08.11
Ch01 Array and Strings  (0) 2017.08.10
Sorting  (0) 2017.08.06
Graph Search  (0) 2017.08.06
String  (0) 2017.07.31

Ch02 LinkedList


2.1 정렬되지 않은 linkedList에서 중복된 값을 삭제하는 코드를 작성 한다.

해법1
set자료 구조에 하나씩 저장하면서 순회하는 방식을 사용한다.
단 한번의 순회로 모두 처리 할 수 있다.
복잡도는 O(n)이다.

def remove_dups(ll):
    if ll.head is None:
        return

    current = ll.head
    seen = set([current.value])
    while current.next:
        if current.next.value in seen:
            current.next = current.next.next
        else:
            seen.add(current.next.value)
            current = current.next

    return ll

실행결과

# 제거 전
1 -> 6 -> 1 -> 4 -> 3 -> 2 -> 4 -> 2 -> 2 -> 5 -> 5 -> 4 -> 2 -> 3 -> 8 -> 6 -> 2 -> 0 -> 1 -> 6 -> 3 -> 6 -> 2 -> 2 -> 6 -> 2 -> 1 -> 6 -> 2 -> 4 -> 2 -> 4 -> 7 -> 8 -> 4 -> 4 -> 3 -> 8 -> 5 -> 5 -> 0 -> 7 -> 7 -> 4 -> 1 -> 1 -> 1 -> 8 -> 5 -> 0 -> 7 -> 5 -> 9 -> 3 -> 0 -> 9 -> 2 -> 0 -> 4 -> 0 -> 0 -> 3 -> 1 -> 3 -> 5 -> 1 -> 0 -> 0 -> 5 -> 9 -> 7 -> 7 -> 0 -> 3 -> 3 -> 1 -> 7 -> 5 -> 5 -> 9 -> 7 -> 4 -> 2 -> 4 -> 6 -> 5 -> 3 -> 2 -> 9 -> 9 -> 8 -> 5 -> 1 -> 7 -> 4 -> 1 -> 8 -> 4 -> 3 -> 9

# 제거 후
1 -> 6 -> 4 -> 3 -> 2 -> 5 -> 8 -> 0 -> 7 -> 9

제약사항

  • temporary buffer를 허용하지 않는다.

해법
버퍼를 사용할 수 없다면 두 개의 포인터를 사용해 순회하여 문제를 해결할 수 있다. current라는 포인터로는 연결 리스트를 순회하고, runner로는 그 뒤에 중복이 있는지 확인 하는 것이다.

하지만 하나의 current node에 대해서 반복을 수행을 계속 해야 하므로 공간 복잡도는 O(1)이 되지만, 시간 복잡도는 O(N^2)이 된다.

def remove_dups_followup(ll):
    if ll.head is None:
        return

    current = ll.head
    while current:
        runner = current
        while runner.next:
            if runner.next.value == current.value:
                runner.next = runner.next.next
            else:
                runner = runner.next
        current = current.next

    return ll.head

실행결과

# 제거 전
1 -> 7 -> 8 -> 1 -> 5 -> 7 -> 8 -> 4 -> 9 -> 6 -> 5 -> 9 -> 0 -> 3 -> 8 -> 8 -> 9 -> 3 -> 2 -> 8 -> 7 -> 6 -> 7 -> 9 -> 9 -> 8 -> 5 -> 8 -> 9 -> 5 -> 1 -> 2 -> 6 -> 5 -> 6 -> 9 -> 2 -> 9 -> 2 -> 4 -> 4 -> 0 -> 8 -> 1 -> 5 -> 9 -> 9 -> 5 -> 0 -> 2 -> 9 -> 8 -> 0 -> 6 -> 1 -> 2 -> 1 -> 3 -> 0 -> 7 -> 6 -> 8 -> 1 -> 4 -> 5 -> 0 -> 2 -> 4 -> 9 -> 9 -> 9 -> 5 -> 3 -> 8 -> 0 -> 5 -> 7 -> 2 -> 8 -> 0 -> 3 -> 2 -> 8 -> 0 -> 0 -> 8 -> 2 -> 9 -> 0 -> 5 -> 3 -> 6 -> 8 -> 2 -> 1 -> 7 -> 8 -> 3 -> 7 -> 6

# 제거 후
1 -> 7 -> 8 -> 5 -> 4 -> 9 -> 6 -> 0 -> 3 -> 2

2.2 단방향 Linked List에서 k번째 요소를 찾는 코드를 구현 해야 한다.

해법1
재귀함수를 이용하는 방법

순회하고 매번 index를 저장하기 때문에 O(n)의 복잡도를 가지게 된다. 해당 위치에서 값을 출력하고 index는 return하는 방법으로 구현 했다.

def recursive_kth_to_last(ll, k):
    if ll is None:
        return 0
    i = recursive_kth_to_last(ll.next, k) + 1

    if i is k:
        print(ll.value)
    return i

실행결과

# 생성된 linked list
71 -> 83 -> 3 -> 2 -> 59 -> 25 -> 33 -> 40 -> 21 -> 93

# 뒤에서 3번 째 index라고 하면
40 #

해법2
순환적(iterarive) 방법으로 해결할 수 있다.
직관적이지는 않지만 좀 더 최적인 방법은, 순환적으로 푸는 것이다. 두 개의 포인터 p1과 p2를 사용한다. p1이 리스트 시작 노드를 가리키게 한 다음, p2를 k 노드만큼 움직여서 p1과 p2가 k 노드만큼 떨어져 있도록 만든다. 그런 다음, p1과 p2를 보조를 맞춰 같이 이동시킨다. p2는 LENGTH-k번 후에 연결 리스트의 맨 마지막 노드에 도달할 것이다. 바로 그 시점에, p1은 LENGTH-k번 노드, 그러니까 뒤에서부터 k번째 노드를 가리키게 된다.

코드

def kth_to_last(ll, k):
    runner = current = ll.head
    for i in range(k):
        if runner is None:
            return None
        runner = runner.next

    while runner:
        current = current.next
        runner = runner.next

    return current

실행결과

11 -> 11 -> 83 -> 92 -> 74 -> 2 -> 80 -> 97 -> 76 -> 88
97

2.3 Delete Middle Node

중간 노드를 삭제하는 알고리즘을 구현 한다. 즉 head나 tail을 제외한 아무 노드나 삭제 할 수 있어야 한다.

그렇다고 정확히 middle일 필요도 없다.

example
input: the node c from the linked list a->b->c->d->e->f
result: nothing is returned, but the new linked list looks like a->b->d->e->f

python에서는 쉽게 구현이 가능하다.

def delete_middle_node(node):
    node.value = node.next.value
    node.next = node.next.next

ll = LinkedList()
ll.add_multiple([1, 2, 3, 4])
middle_node = ll.add(5)
ll.add_multiple([7, 8, 9])

print(ll)
delete_middle_node(middle_node)
print(ll)

실행결과

1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9
1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9

2.4 x값을 갖는 노드를 기준으로 연결 리스트를 나누는 코드를 작성하라. x 보다 작은 값을 갖는 노드가 x와 같거나 더 큰 값을 갖는 노드들보다 앞쪽에 오도록 하면 된다.

연결리스트를 사용하면 쉽게 해결 된다.
x를 기준으로 작은 값을 저장하는 것과 그렇지 않은것을 저장 하는 것으로 나누면 된다.

index를 1개만 이용해서 앞에서 부터 채우게 하면 좀 더 메모리를 절약할 수 있다.

def partition(ll, x):
    current = ll.tail = ll.head

    while current:
        nextNode = current.next
        current.next = None
        if current.value < x:
            current.next = ll.head
            ll.head = current
        else:
            ll.tail.next = current
            ll.tail = current
        current = nextNode
        
    # Error check in case all nodes are less than x
    if ll.tail.next is not None:
        ll.tail.next = None


ll = LinkedList()
ll.generate(10, 0, 99)
print(ll)
partition(ll, ll.head.value)
print(ll)

실행결과
partition 46으로 선택했을 때의 결과이다.

46 -> 53 -> 52 -> 69 -> 48 -> 3 -> 23 -> 59 -> 2 -> 91
2 -> 23 -> 3 -> 46 -> 53 -> 52 -> 69 -> 48 -> 59 -> 91

2.5 Sum Lists

  • 2개의 연결 리스트가 있고 각각은 싱글 digit을 포함하고 있다. 그리고 이 숫자는 역순으로 정렬되어 있다. 즉 1의 자리숫자가 맨 앞에 있다는 뜻이 된다. 이 두개의 연결 리스트를 더해서 그 결과를 반환하는 코드를 작성하라.

Example
Input: (7->1->6) + (5->9->2). That is, 617 + 295
Output: 2->1->9. That is 912.

코드

def sum_lists(ll_a, ll_b):
    n1, n2 = ll_a.head, ll_b.head
    ll = LinkedList()
    carry = 0
    while n1 or n2:
        result = carry
        if n1:
            result += n1.value
            n1 = n1.next
        if n2:
            result += n2.value
            n2 = n2.next

        ll.add(result % 10)
        carry = result // 10

    if carry:
        ll.add(carry)

    return ll

실행 결과

5 -> 3 -> 7 -> 7
8 -> 6 -> 8
3 -> 0 -> 6 -> 8

Follow up problem

  • 길이가 맞지 않는 경우
  • 계산결과를 head에 붙여서 처리하는 방식으로 구현

코드

def sum_lists_followup(ll_a, ll_b):
    # Pad the shorter list with zeros
    if len(ll_a) < len(ll_b):
        for i in range(len(ll_b) - len(ll_a)):
            ll_a.add_to_beginning(0)
    else:
        for i in range(len(ll_a) - len(ll_b)):
            ll_b.add_to_beginning(0)

    # Find sum
    n1, n2 = ll_a.head, ll_b.head
    result = 0
    while n1 and n2:
        result = (result * 10) + n1.value + n2.value
        n1 = n1.next
        n2 = n2.next

    # Create new linked list
    ll = LinkedList()
    ll.add_multiple([int(i) for i in str(result)])

    return ll

실행결과

뒤에서 부터 1의 자리로 생각 하기 때문에 결과가 다르다.

5 -> 3 -> 7 -> 7
8 -> 6 -> 8
6 -> 2 -> 4 -> 5

2.6 주어진 연결 리스트가 회문(palindrome)인지 검사하는 함수를 작성하라

palindrome이라 함은 앞에서 보다 뒤에서 보다 같은 구조를 뜻한다.

0->1->2->1->0

해법1: 뒤집어 비교한다.

  • 포인트는 절반만 비교한다는 것이다.

해법2: 순환적(iterative) 접근법

  • 리스트 앞 절반을 뒤집는 것을 스택을 사용해서 구현 한다.
  • 연결리스트의 길이를 알 경우 절반만 push 하면 된다 (홀수인 경우에도 올바르게 처리 해줘야 한다).
  • 길이를 모를 경우 fast runner slow runner를 적절히 조합해서 사용 한다.

해법3: 재귀적 접근법

코드

def is_palindrome(ll):
    fast = slow = ll.head
    stack = []

    while fast and fast.next:
        stack.append(slow.value)
        slow = slow.next
        fast = fast.next.next

    if fast:
        slow = slow.next

    while slow:
        top = stack.pop()

        if top != slow.value:
            return False

        slow = slow.next

    return True


ll_true = LinkedList([1, 2, 3, 4, 5, 4, 3, 2, 1])
print(is_palindrome(ll_true))
ll_false = LinkedList([1, 2, 3, 4, 5, 6, 7, 8, 9])
print(is_palindrome(ll_false))

실행 결과

True
False


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch 09 Recursion and Dynamic Programming  (0) 2017.08.23
Ch01 Array and Strings  (0) 2017.08.10
Sorting  (0) 2017.08.06
Graph Search  (0) 2017.08.06
String  (0) 2017.07.31

Ch01 Array and Strings


1.1 문자열에 포함된 다른 문자들이 전부 유일한지를 검사하는 알고리즘 구현. 다른 자료구조를 사용할 수 없는 상황에서의

문자가 a~z로 총 26개라면 int 변수 1개로 count해서 이를 판별할 수 있다.

Code

public class QuestionB {

	/* Assumes only letters a through z. */
	public static boolean isUniqueChars(String str) {
		if (str.length() > 26) { // Only 26 characters
			return false;
		}
		int checker = 0;
		for (int i = 0; i < str.length(); i++) {
			int val = str.charAt(i) - 'a';
			if ((checker & (1 << val)) > 0) return false;
			checker |= (1 << val);
		}
		return true;
	}
	
	public static void main(String[] args) {
		String[] words = {"abcde", "hello", "apple", "kite", "padle"};
		for (String word : words) {
			System.out.println(word + ": " + isUniqueChars(word));
		}
		String a = "abcde";
	}
}

1.2 Permuation을 확인 하는 방법, Anagram 이랑 동일

정렬된 Algorihtm을 가지고 비교 한다.

Sroting을 해서 비교하는 방법이다.

public class QuestionA {	
	public static String sort(String s) {
		char[] content = s.toCharArray();
		java.util.Arrays.sort(content);
		return new String(content);
	}
	
	public static boolean permutation(String s, String t) {
		return sort(s).equals(sort(t));
	}	
	
	public static void main(String[] args) {
		String[][] pairs = {{"apple", "papel"}, {"carrot", "tarroc"}, {"hello", "llloh"}};
		for (String[] pair : pairs) {
			String word1 = pair[0];
			String word2 = pair[1];
			boolean anagram = permutation(word1, word2);
			System.out.println(word1 + ", " + word2 + ": " + anagram);
		}
	}
}

Ascii 코드를 이용한 방법이다.

public class QuestionB {	
	public static boolean permutation(String s, String t) {
		if (s.length() != t.length()) return false; // Permutations must be same length
		
		int[] letters = new int[128]; // Assumption: ASCII
		for (int i = 0; i < s.length(); i++) {
			letters[s.charAt(i)]++;
		}
		  
		for (int i = 0; i < t.length(); i++) {
			letters[t.charAt(i)]--;
		    if (letters[t.charAt(i)] < 0) {
		    	return false;
		    }
		}
		  
		return true; // letters array has no negative values, and therefore no positive values either
	}
	
	public static void main(String[] args) {
		String[][] pairs = {{"apple", "papel"}, {"carrot", "tarroc"}, {"hello", "llloh"}};
		for (String[] pair : pairs) {
			String word1 = pair[0];
			String word2 = pair[1];
			boolean anagram = permutation(word1, word2);
			System.out.println(word1 + ", " + word2 + ": " + anagram);
		}
	}
}

1.3 URLify 모든 빈 공간을 %20으로 채워라

예제
input: "Mr John Smith "
Output: "Mr%20John%20Smith"

뒷 쪽에 충분한 Margin이 있으므로 뒤에서 부터 앞으로 작업하는 것이 일반적인 방법이다.

two scan approach를 채택 한다.

  • 첫 번째에서는 number of spaces를 카운트 한다. 그 다음 3배를 해서 최종적으로 얼마나 많은 추가 character가 필요한지 알 수 있다.
  • 두 번째에서는 실제 string의 순서를 조절하게 된다. 즉 space가 있으면 %20을 채우고 no space면 orignal character를 채운다.
# O(N)
import unittest

def urlify(string, length):
    '''function replaces single spaces with %20 and removes trailing spaces'''
    new_index = len(string)

    for i in reversed(range(length)):
        if string[i] == ' ':
            # Replace spaces
            string[new_index - 3:new_index] = '%20'
            new_index -= 3
        else:
            # Move characters
            string[new_index - 1] = string[i]
            new_index -= 1

    return string

class Test(unittest.TestCase):
    '''Test Cases'''
    # Using lists because Python strings are immutable
    data = [
        (list('much ado about nothing      '), 22,
         list('much%20ado%20about%20nothing')),
        (list('Mr John Smith    '), 13, list('Mr%20John%20Smith'))]

    def test_urlify(self):
        for [test_string, length, expected] in self.data:
            actual = urlify(test_string, length)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()

문자열 압축 (String Compression)

# O(N)
import unittest

def string_compression(string):
    compressed = []
    counter = 0

    for i in range(len(string)):
        if i != 0 and string[i] != string[i - 1]:
            compressed.append(string[i - 1] + str(counter))
            counter = 0
        counter += 1

    # add last repeated character
    compressed.append(string[-1] + str(counter))

    # returns original string if compressed string isn't smaller
    return min(string, ''.join(compressed), key=len)


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ('aabcccccaaa', 'a2b1c5a3'),
        ('abcdef', 'abcdef')
    ]

    def test_string_compression(self):
        for [test_string, expected] in self.data:
            actual = string_compression(test_string)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()

Rotate Matrix

Matrix를 Rotation 하게 된다. 외부에서 안으로 진행하는 방식으로 처리 한다.

# O(NxN)
import unittest


def rotate_matrix(matrix):
    '''rotates a matrix 90 degrees clockwise'''
    n = len(matrix)
    for layer in range(n // 2):
        first, last = layer, n - layer - 1
        for i in range(first, last):
            # save top
            top = matrix[layer][i]

            # left -> top
            matrix[layer][i] = matrix[-i - 1][layer]

            # bottom -> left
            matrix[-i - 1][layer] = matrix[-layer - 1][-i - 1]

            # right -> bottom
            matrix[-layer - 1][-i - 1] = matrix[i][- layer - 1]

            # top -> right
            matrix[i][- layer - 1] = top
    return matrix


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ([
            [1, 2, 3, 4, 5],
            [6, 7, 8, 9, 10],
            [11, 12, 13, 14, 15],
            [16, 17, 18, 19, 20],
            [21, 22, 23, 24, 25]
        ], [
            [21, 16, 11, 6, 1],
            [22, 17, 12, 7, 2],
            [23, 18, 13, 8, 3],
            [24, 19, 14, 9, 4],
            [25, 20, 15, 10, 5]
        ])
    ]

    def test_rotate_matrix(self):
        for [test_matrix, expected] in self.data:
            actual = rotate_matrix(test_matrix)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()

1.7 M x N 행렬의 한 원소가 0일 경우 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성

생각1
단순히 발견하는 0의 행과 열을 0으로 변경하면서 진행하면 금방 전부다 0이 되어 버린다.

생각2
추가적인 공간 O(MN)에 0의 위치를 기록하고 그 다음 해당 열과 행을 0으로 초기화 하는 방법이 있다.

생각3
그런데 정말로 O(MN) 만큼의 공간이 필요한가? 그렇지 않다. 같은 행과 열의 모든 원소의 값을 0으로 만들 것이므로, 0인 원소가 정확히 몇 번째 행에 몇 번째 열의 원소였는지 알 필요는 없다. 우리는 그저 어떤 행 안에 0 값을 갖는 원소가 있다는 사실만 기록하면 되고, 어떤 열 안에 0값을 갖는 원소가 있다는 사실만 기록하면 된다. 어차피 그 행과 열의 모든 원소를 0으로 만들 것인데, 왜 정확한 위치를 기록해야 하는가.

코드는 아래와 같다. 0이 있는 행과 열을 추적하기 위한 배열을 두 개 사용 했다. 그런 다음, 이 배열의 갑에 따라서 행과 열을 전부 0으로 만들도록 했다.

코드

# O(MxN)
import unittest


def zero_matrix(matrix):
    m = len(matrix)
    n = len(matrix[0])
    rows = []
    cols = []

    for x in range(m):
        for y in range(n):
            if matrix[x][y] == 0:
                rows.append(x)
                cols.append(y)

    for row in rows:
        nullify_row(matrix, row)

    for col in cols:
        nullify_col(matrix, col)

    return matrix


def nullify_row(matrix, row):
    for i in range(len(matrix[0])):
        matrix[row][i] = 0


def nullify_col(matrix, col):
    for i in range(len(matrix)):
        matrix[i][col] = 0


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ([
            [1, 2, 3, 4, 0],
            [6, 0, 8, 9, 10],
            [11, 12, 13, 14, 15],
            [16, 0, 18, 19, 20],
            [21, 22, 23, 24, 25]
        ], [
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [11, 0, 13, 14, 0],
            [0, 0, 0, 0, 0],
            [21, 0, 23, 24, 0]
        ])
    ]

    def test_zero_matrix(self):
        for [test_matrix, expected] in self.data:
            actual = zero_matrix(test_matrix)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()

1.8 한 단어가 다른 단어에 포함된 문자열인지 판별하는 isSubstring이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌을 때, s2가 s1을 회전시킨 결과인지 판별하는 코드를 isSubstring을 한 번만 호출하도록 하여 작성하라.

s2가 s1을 회전시켜 얻은 문자열이라면, 회전된 지점이 어딘지를 알아봐야 한다.
가령 waterbottle을 회전시켜 erbbottlewat을 얻어다고 해보자.
회전시킬 때, s1을 x와 y의 두 부분으로 나눈 다음 다시 배열하여 s2를 얻었을 것이다.

s1 = xy = waterbottle
x = wat
y = erbottle
s2 = yx = erbottlewat

하지만 중요한점은 x와 y를 나눈 지점이 어디인가 상관없이, yx는 언제나 xyxy의 부분 문자열이다. 다시 말해서, s2는 언제나 s1s1의 부분 문자열이란 이야기이다.

즉, isSubstring(s1s1,s2)인지 알아보면 된다는 것이다.

# O(N)
import unittest


def is_substring(string, sub):
    return string.find(sub) != -1


def string_rotation(s1, s2):
    if len(s1) == len(s2) != 0:
        return is_substring(s1 + s1, s2)
    return False


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ('waterbottle', 'erbottlewat', True),
        ('foo', 'bar', False),
        ('foo', 'foofoo', False)
    ]

    def test_string_rotation(self):
        for [s1, s2, expected] in self.data:
            actual = string_rotation(s1, s2)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch 09 Recursion and Dynamic Programming  (0) 2017.08.23
Ch02 LinkedList  (0) 2017.08.11
Sorting  (0) 2017.08.06
Graph Search  (0) 2017.08.06
String  (0) 2017.07.31

Sorting


Bubble

시간복잡도는 $O(N^2)$이다.
공간복잡도는 $O(1)$

def bubbleSort(n, a):
    cumulatedNumSwap = 0
    for i in range(0, n):
        numSwap = 0
        for j in range(0, n-1):
            if a[j] > a[j+1]:
                temp = a[j]
                a[j] = a[j+1]
                a[j+1] = temp
                numSwap += 1
        cumulatedNumSwap += numSwap
        if numSwap == 0:
            break
    return cumulatedNumSwap, a

if __name__ == "__main__":
    a = [2, 1, 3, 1, 2]
    numSwap, sortedA = bubbleSort(len(a), a)

    print("Array is sorted in %d swaps."%numSwap)
    print("First Element: %d"%sortedA[0])
    print("Last Element: %d"%sortedA[-1])

Insertion

Time Complexity:

  • best: $O(n)$
  • worst: $O(n^2)$
    Space Complexity: $O(1)$

간단한 삽입정렬

def InsertionSort(input):
    for i in range(len(input)-1):
        for j in range(i+1,len(input)):
            if(input[j] < input[i]):
                input[i], input[j] = input[j], input[i]
    return input
import random

def InsertionSort(input):

    for idx, valueToInsert in enumerate(input):
        # select the hole position where number is to be inserted
        holePosition = idx

        # check if previous no. is larger than value to be inserted
        while holePosition > 0 and input[holePosition-1] > valueToInsert:
            input[holePosition - 1], input[holePosition] = input[holePosition], input[holePosition-1]
            holePosition = holePosition - 1

    return input

if __name__ == "__main__":
    A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
    print(A)
    InsertionSort(A)
    print(A)

실행결과

[84, 59, 97, 41, 6, 93, 80, 62, 19, 37, 83, 24, 86, 95, 46]
[6, 19, 24, 37, 41, 46, 59, 62, 80, 83, 84, 86, 93, 95, 97]

Selection

Time complexity: $O(n^2)$
Space complexity: $O(1)$

import random
def selectionSort(input):
    for i in range(len(input) - 1):
        # assume the min is the first element
        idx_min = i
        j = i + 1

        # test against elements after i to find the smallest
        while j < len(input):
            if(input[j] < input[idx_min]):
                # found new minimum; remember its index
                idx_min = j
            j = j + 1

        if idx_min is not i:
            # swap
            input[idx_min], input[i] = input[i], input[idx_min]

    return input

if __name__ == "__main__":
    A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
    print(A)
    selectionSort(A)
    print(A)

실행결과

[72, 10, 31, 7, 51, 11, 97, 9, 45, 54, 35, 26, 61, 55, 13]
[7, 9, 10, 11, 13, 26, 31, 35, 45, 51, 54, 55, 61, 72, 97]

Merge

worst와 average모두 $O(n \log n)$인 엄청나게 좋은 알고리즘이다.
하지만 공간 복잡도는 $O(n)$을 메모리는 많이 사용 합니다.
그래도 기본적인 Dvide and Conquer를 적용한 알고리즘이기에 확실히 알고 넘어가면 좋다.

위키피디아에 나온 그림으로 나타낸 동작 방법은 아래와 같다.

$T(n)=2T\left(\frac{n}{2}\right)+n$
$\begin{aligned}
T(n)&=2\left(2T\left(\frac{n}{4}\right)+\frac{n}{2}\right)+n \newline
&=4T\left(\frac{n}{4}\right)+n+n\newline
&=…\newline
&\approx O(\underbrace{n+n+…+n}_{\log n})\newline
&=O(n\log n)
\end{aligned}$

코드는 아래와 같다.

import random

# Time Complexity O(nLogn)
# Space Complexity O(n)

def mergeSort(A):
    ### Base case ###

    if len(A) <= 1:
        return A

    ### A를 반으로 쪼개서 recursive call을 해 주고 정렬된 반쪽짜리들을 받아옵니다.
    left = mergeSort(A[:int(len(A)/2)])
    right = mergeSort(A[int(len(A)/2):])

    ### 여기서부터 두 개의 쪼개졌던 list를 합치는 Merge 부분입니다.
    ### 여기서 포인트는 정렬된 상태로 돌아왔기 때문에 앞에서부터 순차적으로 한번만 돌면 정렬시킬 수 있다는 것입니다.
    i, j, k = 0, 0, 0
    while i<len(left) and j<len(right):
        if left[i] < right[j]:
            A[k] = left[i]
            i += 1
        else:
            A[k] = right[j]
            j += 1
        k += 1
    if i == len(left): #만약 left의 원소를 모두 채웠고, right가 남아있을 때.
        while j<len(right):
            A[k] = right[j]
            j += 1
            k += 1
    elif j == len(right): #만약 right의 원소를 모두 채웠고, left가 남아있을 때.
        while i<len(left):
            A[k] = left[i]
            i += 1
            k += 1
    return A #마지막으로 정렬된 list를 리턴합니다.

if __name__ == "__main__":

    A=[random.randint(1,100) for _ in range(10)]
    print("unsorted List:")
    print(A)
    print("Sorted List:")
    print(mergeSort(A))

실행결과

unsorted List:
[94, 22, 47, 26, 28, 29, 33, 53, 5, 54]
Sorted List:
[5, 22, 26, 28, 29, 33, 47, 53, 54, 94]

참고자료
https://smlee729.github.io/python/algorithm/2015/03/03/1-merge-sort.html

Quick

분할 정복 알고리즘으로 Sorting한다.
Merge Sort와 다르게 분할 할 때 복잡하고 병합할 때는 복잡하지 않다.

평균 시간 복잡도는 $O(nlogn)$이다. 메모리 측면에서 좀 더 효율 적이다. 따라서 실제로 동작하는 속도가 좀 더 빠르다.
$$T(n)\approx n+2T(\frac{n}{2})$$

하지만, 최악의 상황인 이미 정렬이 완료된 List를 정렬할 경우 $T(n)=n+T(n-1)$으로 분할 된다.
왜냐하면 pivot이 가장 큰 값이라면 left side n-1개가 존재하고 이 부분을 계속 quick sort로 recursive하게 호출이 발생하기 때문이다. 결국 $O(n^2)$의 복잡도를 가진다.

Pivot이 Median값이라면 merge sort와 같은 복잡도를 가진다. 최악의 경우를 피하는 방법은 통상 random choice를 이용한다.

import random

# 아까 말씀드렸다시피, pivot을 선택한 후에(parition 함수의 결과값으로 pivot의 최종 index가 나옵니다.) recursive call로 쪼갭니다.
def quicksort(A, start, end):
    if start < end:
        p = partition(A, start, end)
        quicksort(A, start, p - 1)
        quicksort(A, p + 1, end)


# 이제 pivot을 뽑는 과정을 알아봅시다.
def partition(A, start, end):
    pivot = end
    wall = start
    # 나머지 원소들은 A[hi]와 비교하면서 재정렬합니다.
    for i in range(start, end):
        if A[i] < A[pivot]:
            #swap
            A[i], A[wall] = A[wall], A[i]
            wall += 1
    A[pivot], A[wall] = A[wall], A[pivot] # 마지막으로 pivot을 자신보다 큰 원소들의 첫번째 원소와 바꿔줍니다. (전반부, 후반부를 나누기 위해서)
    return wall

if __name__ == "__main__":
    A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
    print(A)
    quicksort(A, 0, len(A)-1)
    print(A)


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch02 LinkedList  (0) 2017.08.11
Ch01 Array and Strings  (0) 2017.08.10
Graph Search  (0) 2017.08.06
String  (0) 2017.07.31
HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31

Graph Search


아래와 같은 Graph가 있다고 가정한다.

Depth Frist Search (DFS)

  • 임의의 노드n을 선택
  • n을 방문했다고 표시
  • n의 방문하지 않은 인접 vertex를 방문한다.

Breadth First Search (BFS)

  • 노드 n부터 시작하고, 방문했다고 표시하면서 큐에 삽입
  • 큐가 empty일때까지 계속 반복하면서,
  • 큐에서 첫번째 원소를 뽑는다. 그리고 뽑은 원소의 방문하지 않은 이웃들을 방문했다고 표시 후에 큐의 끝에 지어넣는다.
class graph:
    def __init__(self, vertexList, edgeList):
        self.vertexList = vertexList
        self.edgeList = edgeList
        self.adjacentList = [[] for id in range(len(vertexList))]
        for edge in edgeList:
            self.adjacentList[edge[0]].append(edge[1])

def recursiveDFS(graph,node, visited=[]):
    visited.append(node)
    for neighbor in graph.adjacentList[node]:
        if neighbor not in visited:
            recursiveDFS(graph, neighbor, visited)
    return visited

# queue에 insert 할 때 넣는 방법
def BFS(graph,node, visited=[]):
    queue = [node] # 맨 처음 버텍스를 삽입 한다.
    visited.append(node) # 방문한 리스트에 맨 처음 버텍스를 넣는다.
    while queue: # 큐가 비었는지 확인 한다
        current = queue.pop() # 큐에서 데이터를 꺼내온다.
        for neighbor in graph.adjacentList[current]: # 인접 vertex에서 값을 하나 가져온다.
            if not neighbor in visited: # 현재 인접 노드의 값이 방문한 것이 아닌지 확인 한다.
                queue.insert(0,neighbor)
                visited.append(neighbor)
    return visited

# queue에 pop할 때 visit 하는 방법
def BFS2(graph,node, visited=[]):
    queue = [node]
    #visited.append(node)

    while queue:
        current = queue.pop()
        for vertex in graph.adjacentList[current]:
            if vertex not in visited:
                queue.insert(0, vertex)
        visited.append(current)
    return visited



if __name__ == "__main__":

    # Depth First Search (DFS)
    vertexList = ['0', '1', '2', '3', '4', '5', '6']
    edgeList = [(0, 1), (0, 2), (1, 0), (1, 3), (2, 0), (2, 4), (2, 5), (3, 1), (4, 2), (4, 6), (5, 2), (6, 4)]

    graphObj = graph(vertexList, edgeList)
    print("vertex list")
    print(graphObj.vertexList)
    print("edge list")
    print(graphObj.edgeList)
    print("adjacent list")
    print(graphObj.adjacentList)

    print("DFS Traverse:")
    print(recursiveDFS(graphObj,0))
    print("BFS Traverse:")
    print(BFS(graphObj,0))

실행결과

vertex list
['0', '1', '2', '3', '4', '5', '6']
edge list
[(0, 1), (0, 2), (1, 0), (1, 3), (2, 0), (2, 4), (2, 5), (3, 1), (4, 2), (4, 6), (5, 2), (6, 4)]
adjacent list
[[1, 2], [0, 3], [0, 4, 5], [1], [2, 6], [2], [4]]
DFS Traverse:
[0, 1, 3, 2, 4, 6, 5]
BFS Traverse:
[0, 1, 2, 3, 4, 5, 6]

참고자료
https://smlee729.github.io/python/network%20analysis/2015/04/09/1-networkx-dfs-bfs.html


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch01 Array and Strings  (0) 2017.08.10
Sorting  (0) 2017.08.06
String  (0) 2017.07.31
HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31
Binary Search Tree  (0) 2017.07.31

String


Reverse

input = list("abcdefg")

mid = int(len(input)/2)
left = 0
right = len(input)-1

while left < right:
    input[left], input[right] = input[right], input[left]
    left += 1
    right -= 1

print(input)

Super Reduced String

  • pair string을 줄이는 작업을 수행 한다.
def super_reduced_string(S):
    LS = list(S)
    i = 0
    while i < len(LS)-1:
        if LS[i]==LS[i+1]:
            del LS[i]
            del LS[i]
            i = 0
            if len(LS) == 0:
                return 'Empty String'
        else:
            i+=1
    return ''.join(LS)

CamelCase

eBay, iPhone처럼 중간에 띄어쓰기 없이 대소문자로만 단어를 구분하는 것을 말한다.

이렇게 표시된 unique한 단어가 몇개인지 찾아서 출력 해야 한다.

#!/bin/python3

import sys
import string

s = input().strip()

sl = list(s)

i = 0
count = 1
while i < len(sl):
    if sl[i].isupper():
        count += 1
    i += 1

print(count)

한줄 코드

print(sum(map(str.isupper, input())) + 1)

Sliding Window

https://scipher.wordpress.com/2010/12/02/simple-sliding-window-iterator-in-python/

Two Characters

번갈아 가면서 두개의 서로다른 character를 배열 해야 한다.

  • (o) xyxyx or yxyxy
  • (x) xxyy or xyyx

들어온 입력에 대해서 가능한한 가장 긴 두개의 charater로만 생성 가능한 그리고 번갈아 가면서(alternating)으로 만들 수 있는 string을 반환하는게 목적이다.

불가능 하다면 0을 리턴 한다.

예제

10
beabeefeab

해설

  • If we delete e and f, the resulting string is babab. This is a valid as there are only two distinct characters (a and b), and they are alternating within the string.
  • If we delete a and f, the resulting string is bebeeeb. This is not a valid string because there are three consecutive e's present.
  • If we delete only e, the resulting string is babfab. This is not a valid string because it contains three distinct characters.
  • Thus, we print the length of babab, which is , as our answer.
import sys

def validate(inp):
    for i in range(len(inp)-1):
        if inp[i+1]==inp[i]:
            return False
    return True    
    

s_len = int(input().strip())
s = input().strip()

ans = 0
chtoindex = []
for ch in set(s):
    chtoindex.append((ch, len([j for j, x in enumerate(s) if x == ch])))
    

for i, pack in enumerate(chtoindex[:-1]):
    char_i, lenchar_i = pack[0], pack[1]
    for j, otherpack in enumerate(chtoindex[i+1:]):
        char_j, lenchar_j = otherpack[0], otherpack[1]
        if abs(lenchar_i-lenchar_j)<2:
            c = [cha for cha in s if cha is char_i or cha is char_j]
            if validate(c):
                ans = max(ans, lenchar_j+lenchar_i)
print(ans)

참고자료

문자열관련 Python 유용함수 모음 블로그


'Computer Science > Coding Interview' 카테고리의 다른 글

Sorting  (0) 2017.08.06
Graph Search  (0) 2017.08.06
HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31
Binary Search Tree  (0) 2017.07.31
HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30

HackerRank- Trees: Is This a Binary Search Tree


해당 트리가 이진 탐색 트리인지 확인 하는 문제이다.

단순히 특정 노드의 자식들 값이 부모보다 작은지 큰지를 가지고 판단할 경우 아래의 경우에 문제가 발생 한다.

이유는 4의 경우 root 보다 큰대도 불구하고 자식 노드의 자식으로 분류되어 있다.
즉, 더 윗 부분의 부모 노드에서 판단하는 부분이 제외 되기 때문에 문제가 발생 한다.

방법1

  • 재귀적으로 최소 최대 값을 확인하며 루프를 도는 방법
  • 일단 데이터에 음수가 없다는 가정에서 출발 한다.
def checkBST(root):
    return(check_in_order(root,[-1]))
    
def check_in_order(root,prev):
    result = True
    if root.left is not None:
        result &= check_in_order(root.left,prev)
    if prev[0] >= root.data:
        return False
    prev[0] = root.data
    if root.right is not None:
        result &= check_in_order(root.right,prev)
    return result

방법2

  • Inorder traversal을 해서 확인하는 방법.
  • 올바른 Binary Search라면 출력이 순차적이게 된다.
  • 해당 문제에서 보면 중독된 노드는 이진탐색트리로 허용하지 않으니 그 문제에 대한 해결을 필요로 한다.
""" Node is defined as
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
"""

def checkBST(root):
    # traversal by inOrder 
    resList = []
    resList = inOrder(root,resList)
    sortedList = sorted(resList)
    
    if len(set(resList)) != len(resList):
        return False
    
    if len([i for i, j in zip(resList, sortedList) if i == j]) == len(resList):
        return True
    else:
        return False
    
def inOrder(node,resList):
    if node.left is not None:
        resList = inOrder(node.left, resList)
    resList.append(node.data)
    if node.right is not None:
        resList = inOrder(node.right, resList)
    return resList


'Computer Science > Coding Interview' 카테고리의 다른 글

Graph Search  (0) 2017.08.06
String  (0) 2017.07.31
Binary Search Tree  (0) 2017.07.31
HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30

Binary Search Tree

Traverse 방식

pre order traverse (depth-first traverse라고도함.)

  • visit the root
  • traverse the left subtree
  • traverse the right subtree

사용처는 byte-stream으로 tree 정보를 다른 곳으로 전송 할 때 사용 한다.

in-order traverse (symmetric traverse)

  • visit left
  • visit parent
  • visit right

순차적으로 데이터를 출력 할 때 사용 한다.

post order traverse

  • visit left
  • visit right
  • visit root

노드를 지워야 할 때 사용한다.

구현 코드

생성한 트리의 모습은 아래와 같다.

class Node:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, value):
        if value <= self.data:
            if self.left is None:
                self.left = Node(value)
            else:
                self.left.insert(value)
        elif value > self.data:
            if self.right is None:
                self.right = Node(value)
            else:
                self.right.insert(value)
        else:
            self.data = value

    def inOrder(self):
        if self.left is not None:
            self.left.inOrder()
        print(self.data)
        if self.right is not None:
            self.right.inOrder()

    def preOrder(self):
        print(self.data)
        if self.left is not None:
            self.left.preOrder()
        if self.right is not None:
            self.right.preOrder()

    def postOrder(self):
        if self.left is not None:
            self.left.postOrder()
        if self.right is not None:
            self.right.postOrder()
        print(self.data)

if __name__ == "__main__":
    char = None
    root = Node(4)
    root.insert(3)
    root.insert(6)
    root.insert(2)
    root.insert(1)
    root.insert(5)
    root.insert(7)
    root.insert(8)

    print("inOrder traversal:")
    root.inOrder()
    print("preOrder traversal:")
    root.preOrder()
    print("PostOrder traversal:")
    root.postOrder()

참고문헌

한글로 설명된 깔끔한 블로그
설명 잘 되어 있는 외국 사이트


'Computer Science > Coding Interview' 카테고리의 다른 글

String  (0) 2017.07.31
HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31
HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30

HackerRank Queues: A Tale of Two Stacks


입력

  • q, 쿼리의 숫자
  • 쿼리 타입, 1만 뒤에 추가적인 값이 따라온다.

쿼리 타입

  • 1: x를 enqueue 한다.
  • 2: dequeue
  • 3: print 1개만

이 challenge에서는 반드시 queue를 두개의 stack을 이용해서 구현하라고 한다.
이게 front에서 팝이랑 삽입이 모두 이뤄져야 하기 때문에 통상의queue랑은 다르다.

List를 이용한 직접 작성한 Queue

class MyQueue(object):
    def __init__(self):
        self.q = [] 
        self.right = 0
        
    def peek(self):
        if self.q:
            return self.q[0]
        
    def pop(self):
        if self.q:
            self.q.pop()
            self.right -= 1
                
    def put(self, value):        
        self.q.insert(self.right,value)
        self.right += 1

새로운 queue

Class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        self.items.pop()

    def print_queue(self):
        print(self.items)

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)

어려운 Test Case

10
1 76
1 33
2
1 23
1 97
1 21
3
3
1 74
3

정답

33
33
33

정답

class MyQueue(object):
    def __init__(self):
        self.old_to_new = []
        self.new_to_old = []
   
    def peek(self):
        if not self.new_to_old:
            while self.old_to_new:
                self.new_to_old.append(self.old_to_new.pop())
        val = self.new_to_old.pop()
        self.new_to_old.append(val)
        return val
       
    def pop(self):
        if not self.new_to_old:
            while self.old_to_new:
                self.new_to_old.append(self.old_to_new.pop())
        return self.new_to_old.pop()
       
    def put(self, value):
        self.old_to_new.append(value)


        
queue = MyQueue()
t = int(input())
for line in range(t):
    values = map(int, input().split())
    values = list(values)
    if values[0] == 1:
        queue.put(values[1])        
    elif values[0] == 2:
        queue.pop()
    else:
        print(queue.peek())


'Computer Science > Coding Interview' 카테고리의 다른 글

HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31
Binary Search Tree  (0) 2017.07.31
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30
HackerRank MergeSort Counting Inversions  (0) 2017.07.29

Stacks: Balanced Brackets


bracket은 (), {}, [] 이 세가지를 모두 포함한다.
이것을 매칭하는 문제이다.

구현코드

def is_matched(expression):
    stack = []
    for bracket in expression:
        if bracket in ['[', '{', "("]:
            stack.append(bracket)
        else:
            if stack:
                if bracket == ']':
                    leftBracket = stack.pop()
                    if leftBracket != '[':
                        return False
                elif bracket == '}':
                    leftBracket = stack.pop()
                    if leftBracket != '{':
                        return False
                elif bracket == ')':
                    leftBracket = stack.pop()
                    if leftBracket != '(':
                        return False
            else:
                return False
    return True

t = int(input().strip())
for a0 in range(t):
    expression = list(input().strip())
    if is_matched(expression) == True:
        print("YES")
    else:
        print("NO")

실행결과

# Input
3
{[()]}
{[(])}
{{[[(())]]}}

# Output
YES
NO
YES
  • 하지만 이 방법은 runtime issue를 발생 시킨다.

새로운 솔루션

def is_matched(expression):
    stack = []
    for bracket in expression:
        if bracket == '{':
            stack.append('}')
        elif bracket == '[':
            stack.append(']')
        elif bracket == '(':
            stack.append(')')
        else:
            if len(stack) == 0 or bracket != stack[-1]:
                return False
            stack.pop()
    return len(stack) == 0

t = int(input().strip())
for a0 in range(t):
    expression = input().strip()
    if is_matched(expression) == True:
        print("YES")
    else:
        print("NO")

Dictionary를 이용한 방법

Advantage

  • 다른 bracket을 필요로 하다면 쉽게 확장이 가능하다.
  • if-else 또는 switch case를 다중으로 작성할 필요가 없다.
  • O(1) call time을 가진다 (hash table이니 당연한 말이긴 하다).
def is_matched(expression):
    stack = []
    dicty = {'(':')', '[':']', '{':'}'}
    for x in expression:
        if x in dicty:
            stack.append(dicty[x])
        elif stack and x == stack[-1]:
            stack.pop()
        else:
            return False
            
    return not stack

t = int(input().strip())
for a0 in range(t):
    expression = input().strip()
    if is_matched(expression) == True:
        print("YES")
    else:
        print("NO")


'Computer Science > Coding Interview' 카테고리의 다른 글

Binary Search Tree  (0) 2017.07.31
HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30
HackerRank MergeSort Counting Inversions  (0) 2017.07.29
Binary Search  (0) 2017.07.28

HackerRank Data Structure


Stack

class Stack:
    def __init__(self):
        self.data = []

    # for print
    def __iter__(self):
        return self

    def __str__(self):
        values = [x for x in self]
        return ' -> '.join(values)

    def push(self, data):
        self.data.append(data)

    def pop(self):
        if len(self.data) is not 0:
            return self.data.pop()
        else:
            print("stack is empty")

    def print_stack(self):
        print(self.data)

if __name__ == "__main__":

    myStack = Stack()
    myStack.push(1)
    myStack.push(2)
    myStack.push(3)
    myStack.push(4)
    myStack.print_stack()

    print(myStack.pop())
    print(myStack.pop())

    myStack.print_stack()

실행 결과

[1, 2, 3, 4]
4
3
[1, 2]

Queue

class Queue:

    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        self.items.pop()

    def print_queue(self):
        print(self.items)

if __name__ == "__main__":
    queue = Queue()
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    queue.enqueue(4)
    queue.print_queue()
    queue.dequeue()
    queue.print_queue()

실행결과

[4, 3, 2, 1]
[4, 3, 2]

LinkedList

class Node(object):
    def __init__(self, data=None, next_node=None, prev_node=None):
        self.data = data
        self.next = next_node
        self.prev = prev_node

    def __str__(self):
        return str(self.data)

class LinkedList:
    def __init__(self, data=None):
        self.head = None
        self.tail = None
        if data is not None:
            self.insert(data)

    # for print
    def __iter__(self):
        current = self.head
        while current:
            yield current
            current = current.next

    def __str__(self):
        values = [str(x) for x in self]
        return ' -> '.join(values)

    def __len__(self):
        result = 0
        node = self.head
        while node:
            result += 1
            node = node.next
        return result

    def insert(self, data):
        if self.head is None:
            self.tail = self.head = Node(data)
        else:
            self.tail.next = Node(data)
            self.tail = self.tail.next
        return self.tail

    def delete(self, data):
        if self.head is None:
            print("It is empty!")
            return
        elif self.head.data is data:
            self.head = self.head.next
        else:
            current = self.head
            while current.next is not None:
                if current.data is data:
                    print("Delete the number: %d"%(data))
                    current.data = current.next.data
                    current.next = current.next.next
                    return
                current = current.next
            print("It is not founded")


if __name__ == "__main__":
    ll = LinkedList()
    ll.insert(1)
    ll.insert(2)
    ll.insert(3)
    ll.insert(4)
    ll.insert(5)
    print(ll)
    ll.delete(3)
    ll.delete(6)
    print(ll)

실행 결과

1 -> 2 -> 3 -> 4 -> 5
Delete the number: 3
It is not founded
1 -> 2 -> 4 -> 5


'Computer Science > Coding Interview' 카테고리의 다른 글

HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank MergeSort Counting Inversions  (0) 2017.07.29
Binary Search  (0) 2017.07.28
HackerRank: Basic Problems  (0) 2017.07.25

HackerRank MergeSort Counting Inversions


스왑의 횟수를 찾아내는 것이다.

Input

  • 횟수
  • 숫자 리스트 길이
  • 실제 숫자 리스트 (공백으로 구분)

Bubble Sort 솔루션

속도 문제로 Timeout문제를 발생 시킴

def count_inversions(n,a,numSwap=0):
    cumulatedNumSwap = 0
    for i in range(0,n):
        numSwap = 0
        for j in range(0,n-1):
            if a[j] > a[j+1]:
                temp = a[j]
                a[j] = a[j+1]
                a[j+1] = temp
                numSwap += 1
        cumulatedNumSwap += numSwap
        if numSwap == 0:
            break
    return cumulatedNumSwap


t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    arr = list(map(int, input().strip().split(' ')))
    numSwap = 0
    numSwap = count_inversions(n,arr,numSwap)
    print(numSwap)
    

출력결과

#input
2
5
1 1 1 2 2
5
2 1 3 1 2

#output
0
4

MergeSort 솔루션

  • MergeSort 자체는 문제가 아니다.
  • Count를 할 때 count += mid - i + 1;이렇게 해야 한다는 점이 가장 어려운 부분이다.
  • 과도하게 문제가 꼬여 있다.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
public static long countInversions(int[] arr){
        
        return mergeSort(arr, 0, arr.length - 1);
    }
    
    public static long mergeSort(int[] arr, int start, int end){
        if(start == end)
            return 0;
        int mid = (start + end) / 2;
        long count = 0;
        count += mergeSort(arr, start, mid); //left inversions
        count += mergeSort(arr, mid + 1, end);//right inversions
        count += merge(arr, start, end); // split inversions.
        return count;
    }
    
    public static long merge(int[] arr, int start, int end){
        int mid = (start + end) / 2;
        int[] newArr = new int[end - start + 1];
        int curr = 0;
        int i = start;
        int j = mid + 1;
        long count = 0;
        while(i <= mid && j <=end) {
            if(arr[i] > arr[j]) {
                newArr[curr++] = arr[j++];
                count += mid - i + 1; // Tricky part.
            }
            else
                newArr[curr++] = arr[i++];          
        }
         // Leftover elements here.
        while(i <= mid) {
            newArr[curr++] = arr[i++];    
        }
        
        while(j <= end) {
            newArr[curr++] = arr[j++];
        }
     
        System.arraycopy(newArr, 0, arr, start, end - start + 1); // Usual stuff from merge sort algorithm with arrays.
        return count;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            int n = in.nextInt();
            int arr[] = new int[n];
            for(int arr_i=0; arr_i < n; arr_i++){
                arr[arr_i] = in.nextInt();
            }
            System.out.println(countInversions(arr));
        }
    }
}


'Computer Science > Coding Interview' 카테고리의 다른 글

HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30
Binary Search  (0) 2017.07.28
HackerRank: Basic Problems  (0) 2017.07.25

Binary Search


input = [1,2,3,4,5,6,7,8,9,10]

target = 1
index = 0

min = 0
max = len(input) -1
mid = int(len(input)/2)

step = 1
while (target != input[mid]):
    if input[mid] < target:
        min = mid +1
    else:
        max = mid -1

    mid = int((max+min)/2)
    step +=1

print("target index: %d, steps: %d"%(mid, step))

Points

  • length -1
  • min은 +1
  • max는 -1
    +를 안할 경우 mid값이 변동이 없어서 마지막 위치에 있는 target 값을 못찾는다.
    -를 안할 경우 왼쪽에 있는 값을 step 3번에 찾을 수 있는 것을 4번에 찾는다. int() 때문에 버림이 적용되우 int가 축소 되기 때문에 -를 안해도 지장이 별로 없는 것 같다.


'Computer Science > Coding Interview' 카테고리의 다른 글

HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30
HackerRank MergeSort Counting Inversions  (0) 2017.07.29
HackerRank: Basic Problems  (0) 2017.07.25

HackerRank: Basic Problems


Solution Type

  • Approximate solution
    하나의 정답만 있지 않은 문제를 말한다.
    예를 들면, Image processing이나 computer vision이 이쪽 문제에 해당 한다.

1. Array: Left Rotation

def array_left_rotation_ext(a, n, k):
    for i in range(0,k):
        # change array
        temp = a [0]
        for j in range(0,n):
            if j+1 != n:
                a[j] = a[j+1]
        a[n-1] = temp
    return a
        
def array_left_rotation(a, n, k):
    return a[k:] + a[:k]
    

n, k = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
answer = array_left_rotation(a, n, k);
print(*answer, sep=' ')

첫 번째 함수는 시간이 너무 오래 걸려서 time-out 걸린다.

2. Strings: Making Anagrams

import string


def number_needed(a, b):
    for char in list(string.ascii_lowercase):
        al.append(a.count(char))
        bl.append(b.count(char))
    return sum(abs(x-y) for (x, y) in zip(al, bl))

a = input().strip()
b = input().strip()

al = []
bl = []

print(number_needed(a, b))

Input (stdin)

cde
abc

Your Output (stdout)

4

Expected Output

4

3. Hash Tables: Ransom Note

def ransom_note(magazine, ransom):
    d = {}
    for word in magazine:
        d.setdefault(word, 0)
        d[word] += 1
    
    for word in ransom:
        if word in d:
            d[word] -= 1
        else:
            return False
    return all([x >= 0 for x in d.values()])    

m, n = map(int, input().strip().split(' '))
magazine = input().strip().split(' ')
ransom = input().strip().split(' ')
answer = ransom_note(magazine, ransom)
if(answer):
    print("Yes")
else:
    print("No")

실행결과

6 4
give me one grand today night
give one grand today

Yes
6 5
two times three is not four
two times two is four

No

4. Linked Lists: Detect a Cycle

head point

cycle = true
no cycle = false

"""
Detect a cycle in a linked list. Note that the head pointer may be 'None' if the list is empty.

A Node is defined as: 
 
    class Node(object):
        def __init__(self, data = None, next_node = None):
            self.data = data
            self.next = next_node
"""
def has_cycle(head):
    i = 0
    if head.next == None:
        return False
    
    prev_head = head.next
    next_head = head.next
    
    while next_head != None:
        if i > 100 :
            return True      
        next_head = prev_head.next
        prev_head = next_head
        i += 1
    return False

실행 결과

0
1

5. Sorting: Bubble Sort

n = int(input().strip())
a = list(map(int, input().strip().split(' ')))

cumulatedNumSwap = 0

for i in range(0,n):
    numSwap = 0
    for j in range(0,n-1):
        if a[j] > a[j+1]:
            temp = a[j]
            a[j] = a[j+1]
            a[j+1] = temp
            numSwap += 1
    cumulatedNumSwap += numSwap
    if numSwap == 0:
        break

print("Array is sorted in %d swaps."%cumulatedNumSwap)
print("First Element: %d"%a[0])
print("Last Element: %d"%a[n-1])

In

3
3 2 1

Out

Array is sorted in 3 swaps.
First Element: 1
Last Element: 3

6. Sorting: Comparator

입력값

n // 플레이어 숫자
줄 바꾸고
공백을 두고 플레이어의 이름과 스코어

from functools import cmp_to_key

def cmp_to_key(key):
    return key

class Player:
    def __init__(self, name, score):
        self.name = name
        self.score = score
        
    def comparator(self):
        return(-self.score, self.name)

#--- reference code
n = int(input())
data = []
for i in range(n):
    name, score = input().split()
    score = int(score)
    player = Player(name, score)
    data.append(player)
    
data = sorted(data, key=cmp_to_key(Player.comparator))
for i in data:
    print(i.name, i.score)

input

5
amy 100
david 100
heraldo 50
aakansha 75
aleksa 150

output

aleksa 150
amy 100
david 100
aakansha 75
heraldo 50

7. oddNumbers (smaple test)

l과 r 사이의 숫자에서 odd number만 구해서 list로 반환

# Complete the function below.

def  oddNumbers(l, r):
    oddNumbers=[]
    i = l
    if l % 2 != 0:
        while (i <= r):
            oddNumbers.append(i)
            i+=2
    else:
        i +=1
        while (i<=r):
            oddNumbers.append(i)
            i+=2
    return oddNumbers

실행 결과

3,9
3, 5, 7, 9

8. find number (sample test)

# Complete the function below.

def  findNumber(arr, k):
    for i in arr:
        if i == int(k):
            return "YES"
        else :
            return "NO"

속도 문제가 Fail난다.

def  findNumber(arr, k):
    if k in arr :
        return "YES"
    else :
        return "NO"

속도 문제가 없다.

9. Recursion: Fibonacci Numbers

$$fibonacci(0)=0$$
$$fibonacci(1)=1$$
$$fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)$$

간단한 구현 (단, timeout 걸림)

def fibonacci(n):
    # Write your code here.
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
    
n = int(input())
print(fibonacci(n))

memory 방식: python dictionary 자료구조를 이용해서 처리한다.

memory = {}
def fibonacci(n):
    if n < 2:
        return n
    if not n in memory.keys():
        memory[n] = fibonacci(n-1) + fibonacci(n-2)
    return memory[n]
    
n = int(input())
print(fibonacci(n))

one line lambda code

fibonacci = lambda n:pow(2<<n,n+1,(4<<2*n)-(2<<n)-1)%(2<<n)

10. Bit Manipulation: Lonely Integer

하나만 Unique하게 나타나고 나머진 모두 2번 나타나게 된다.

#!/bin/python3

import sys

def lonely_integer(a):
    uniqueList = [0 for i in range(101)]
    for number in a:
        uniqueList[number] += 1
    
    return uniqueList.index(1)

n = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split(' ')]
print(lonely_integer(a))

시간 복잡도 O(3n)
공간 복잡도 O(n)

실행결과

# in
1
1
# out
1

# in
9
4 9 95 93 57 4 57 93 9
# out 
95

좀 더 좋은 방법

XOR개념을 이용해서 중복되면 0가 되는 특성을 활용한다.
시간복잡도 O(n)
공간복잡도 O(1)

def lonely_integer(a):
    result = 0
    for i in a:
        result ^= i
    return result

11. Binary Search: Ice Cream Parlor

아이스크림을 사먹는 문제이다.

  • t는 여행 횟수를 의미한다.
    그다음 가각에 대해서 인자가 3개이다.
  • n
  • 각각의 맛에 대한 가격, i 번째가 가격을 의미한다.
t = int(input().strip())
for a0 in range(t):
    m = int(input().strip())
    n = int(input().strip())
    a = list(map(int, input().strip().split(' ')))
 
    # effective cost
    costList = {}
    for i, cost in enumerate(a):
        firUser = cost
        secUser = m - cost
        if secUser in costList.keys():
            print(costList[secUser]+1,i+1)
        else:
            costList[cost] = i

output

# input
2
4
5
1 4 5 3 2
4
4
2 2 4 3


# output
1 4
1 2

해당 문제는 딱히 Binary Search를 사용할 필요가 없다. 그냥 Hash로 사용할 경우 O(n)에 복잡도로 처리가 가능하다.
그저 과거의 cost에 각각의 index를 추가하고 그것에 현재 cost 차액만큼 값이 있는지 확인하면 된다.
ID도 점점 커지므로 딱히 순서를 고려할 필요도 없다.

참고자료
TwoSum


'Computer Science > Coding Interview' 카테고리의 다른 글

HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30
HackerRank MergeSort Counting Inversions  (0) 2017.07.29
Binary Search  (0) 2017.07.28

+ Recent posts