The Computer Science Handbook By: Michael Young

The Computer Science Handbook Michael Young May 8, 2015

i

Thanks to: Dr. Yuli Ye, for teaching me Gord Ridout, for encouraging me to make this book

Contents 1

Getting Started 1.1 Getting Started . . . . . . . . . . . . . . . . . . . 1.1.1 Format . . . . . . . . . . . . . . . . . . . .

9 9 10

2

Interviews 2.1 Interviews . . . . . . . . . . 2.1.1 Interview Preparation 2.1.2 Resume . . . . . . . . 2.1.3 Before the Interview . 2.1.4 During the Interview 2.1.5 During the Interview 2.1.6 End Interview . . . . .

11 11 11 12 12 13 14 15

I 3

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Part 1: Behavioural Part 2: Technical . . . . . . . . . . . . . .

Fundamentals

17

Fundamentals 3.1 Runtime and Memory . . . . . . . . 3.1.1 Limits . . . . . . . . . . . . . . 3.1.2 Big O Notation . . . . . . . . . 3.1.3 Runtime and Memory Analysis 3.1.4 Exercises . . . . . . . . . . . .

1

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

18 18 19 19 21 26

CONTENTS

II 4

III 5

6

2

Recursion

27

Recursion 4.1 Recursion . . . . . . . . . . . 4.1.1 Factorial . . . . . . . . . 4.1.2 Sum of digits of a string 4.1.3 Count . . . . . . . . . . 4.1.4 Calculate Exponential . 4.1.5 Exercises . . . . . . . . 4.2 Advanced Recursion . . . . . 4.2.1 Number of paths . . . . 4.2.2 Towers of Hanoi . . . . 4.2.3 Permutations . . . . . . 4.2.4 Exercises . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

28 28 29 31 33 35 37 37 37 40 47 51

Data Structures

52

Stack 5.1 Stack . . . . . . . . . 5.2 Vector . . . . . . . . 5.2.1 Class . . . . . . 5.2.2 Resize . . . . . 5.2.3 Add Element . 5.2.4 Pop . . . . . . 5.2.5 Remove . . . . 5.2.6 Get Element . 5.2.7 Insert Element 5.2.8 Exercises . . . 5.3 Exercises . . . . . . .

55 55 57 57 58 58 59 60 60 61 62 63

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

Queue 64 6.1 Queue . . . . . . . . . . . . . . . . . . . . . . . . 64 6.2 Linked List . . . . . . . . . . . . . . . . . . . . . 66 6.2.1 Link Class . . . . . . . . . . . . . . . . . . . 67

CONTENTS

6.3 7

8

3

6.2.2 LinkedList Class 6.2.3 Push . . . . . . . 6.2.4 Pop . . . . . . . 6.2.5 Get . . . . . . . 6.2.6 Delete . . . . . . 6.2.7 Exercises . . . . Exercises . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .