머신러닝 인터뷰 준비

Contents

컴공
수학
통계
머신러닝
알고리즘
퀴즈

[ 컴공 ]

# f(x) = O(g(x))

iff there exists positive constant c, and k such that f(x) <= cg(x) for all x>= k. The value of c and k must be fixed for the function f and must not depend on x.

It means f(x) is less than some constant multiple of g(x) and a method used to find asymptotic(점근선) upper bound.

f(x) = O(g(x)) if there are positive c and k that f(x) <= c * g(x) where x >= k. c and k should be fixed for function f and should not be depend on x

# Linked List

Advantage:

Dynamic data structure (can grow and prune)
Insert and deletion is easy

Disadvantage:

Use more memory than array because of pointers
read in order from the beginning

# Hash table, dealing with collision

Advantage:

search O(1) (worst O(n))
Insert and deletion is easy

Disadvantage:

collision
worst addition O(n)
When key dict size is small, space overhead of the next pointer is significant

# Binary Search Tree

It is a tree data structure where left and right child nodes are bigger or lesser than parent node.

sorting: build tree for arr[:i] from i=1 to n

advantage: insert, search average O(log n), worst O(n)

disadvantage: worst insert (sort) O(n^2) if inputs are sorted as 1,2,3,4,5,.. or 5,4,3,2,1

implementation: array (index means position)

insertion: recursion (from top to bottom)

deletion: move one of leftmost or rightmost of child tree

# Unbalanced tree : Red-Black tree = BST + color change + rotation

Several constraints enforces “root <-> farthest leaf is no more than twice as long as root <-> nearest leaf ”

# Heap (worst sort: O(log n) : because insertion is always to the end)

It is a tree data structure where parent node always have bigger or lesser value than all child nodes.

sorting: build max heap and pop (One of the best sorting methods, no quadratic worst-case scenarios)

advantage: insert, remove average O(1), worst O(log n)

disadvantage: search O(n)

implementation: array (index means position)

add: add the last, swap if larger than parent (upward)

remove: move the last to the position, swap if smaller (down)

# Heap vs Stack (in RAM memory)

a special region of memory that stores temporary variables.

Data: static, global variable. Stay until the program ends.

Heap: dynamic memory allocation. Stay until free or terminal. Size is decided during the runtime.

void main() {

int i = 10;

int arr[i];

}

Stack: static memory allocation. Only live in a scope of function. Size is decided during the compiler time.

# Depth first search (stack, 왔던 곳 체크하기)

Depth First Search is an algorithm for traversing or search tree data structure.

implementation: stack and mark visited. Can get path from root to target by saving meta info.

# BFS (queue, 왔던 곳 체크하기)

Breadth First Search is another algorithm for traversing or search tree data structure.
implementation: queue and mark visited. Can get path from root to target by saving meta info.

# Memory leak

Type of a resource leak where a program incorrectly manage memory allocation

Memory no longer needed is not released. When object is stored but cannot be accessed.

# Compiler

a software transform code of one language into another, mostly to high-level to low-level (machine code).

advantage: check syntax error. optimized to be faster.

disadvantage: compilation time.

# Interpreter

a software directly execute instruction written in program language.

advantage: no compilation time. partial execution. find error before complete a program. productivity. disadvantage: program is not verified. runtime error. slow execution.

# JIT (Just In Time compilation)

A type of compilation. Involve compilation during execution rather than before execution.

Only required code will be converted into machine code.

ex. JVM (Java Virtual Machine)

# GPL = General Public License

# GNU = GNU's Not Unix!

# OOP

Polymorphism : a single interface (function, class) support different types
string = number.StringValue();
string = date.StringValue();
Encapsulation (public, private) : bundling of data with the methods that operate on that data
Prevent mistake by restricting direct access
Inheritance : when an object or class is based on another object

# Refactoring

Renaing
Encapsulate fields: getter and setter
Extract class
Extract common codes
Introduce assertion

# Lambda function (= Anonymous function)

a function definition that is not bound to an identifier

# Garbage collection

A way of automatic memory management.

Collector attempts to reclaim gar bage, or memory occupied by objects that are no longer in use

# Functional programming <-> Procedural programming

Treats computation as the evaluation of functions and avoids changing-state and mutable data

Always returns the same output for a given input
Order of evaluation is usually undefined
Must be stateless. i.e. No side effects
Good fit for parallel execution
Increased readability and maintainability

# Process : An instance of a computer program that is being executed.

# Thread : the smallest sequence of programmed instructions which share code and the values of variables

# Lock
A way that limits on access to a resource where there are many threads of execution

# Deadlock

Each thread is waiting for the other thread to relinquish a lock, they both remain waiting forever.

Can prevent by breaking the symmetry of the locks.

# Semaphore
A variable that is used for controlling access, by multiple processes, to a common resource.
Useful tool in the prevention of race conditions

# Race condition

When two or more threads can access shared data and they try to change it at the same time.

Execution are random. Root 권한의 setuid가 걸려있는 프로그램으로 악용 가능

# Context Switch
The process of storing and restoring the state (more specifically, the execution context) of a process or thread so that execution can be resumed from the same point at a later time.

[ 수학 ]

# Draw log(x+10)

# Draw sin(x^2)

# Draw cos(x^2)

# Derivative of ln x = 1/x

# Derivative sin(x^2) = 2x cos(x^2)

# (sinx)^2 + (cosx)^2 = 1

# Integration by parts

# Integral log(x) (integration by parts)

# integral 1/x = ln |x| + C

# integral 1/(1-x) = - ln |1 - x| + C

# integral x sin x (integration by parts) = -x cos x + sin x + C

# integral x cos x (integration by parts) = x sin x + cos x + C

sin x 미분 : cos x cos x 미분 : - sin x

cos x 적분 : sin x sin x 적분 : - cos x

# (ε, δ)-definition of limit (epsilon–delta)

[[ 엡실론이 양 끝 ]]

# Derivative (f: R->R) dx/dy = derivative of x “with respect to” y

the sensitivity to change of the function value

# Partial derivative (f: R^M->R)

of a function of several variables f(x,y,...,z) is its derivative with respect to one of those variables

# Gradient (f: R^M->R)

a multi-variable generalization of the derivative.

# Jacobbian (f: R^M->R^N)

Generalizes the gradient of a scalar-valued function of multiple variables

# Hessian (f: R^M->R)

Second-order derivatives of a scalar-valued function

# Inner product x • y = <x, y>

# Outer product (벡터곱)

# Orthogonal vectors

inner product x • y = <x, y> = 0

# Orthogonal matrix

(E: identity matrix)

# Orthonormal

inner product x • y = <x, y>=0
||x|| = 1, ||y|| = 1 (L2 norm)

# Linearly independence

A set of vectors is said to be linearly independent, if one of the vectors in the set can’t be defined as a linear combination of the others

# Determinant (det(A) = 0 <-> A^-1 not exists)

A useful value that can be computed from the elements of a square matrix.

# Properties of det

Identity : det(I) = 1
Transpose: det(A^T) = det(A)
Inverse: det(A^-1) = 1 / det(A)
Multiplication: det(AB) = det(A)det(B)

# Eigenvector of a linear transformation

(v: eigenvector, lambda: eigenvalue)

a non-zero vector that only changes by an scale (eigenvalue)

(선형변환 A에 의한 변환 결과가 자기 자신의 상수배가 되는 0이 아닌 벡터)

# How to calculate Eigenvector?

Eigenvectors u should not be zero-vector => there should be no inverse matrix

Therefore, (characteristic equation)

# Eigendecomposition (Only diagonalizable square matrix can be factorized )

조건 : “A” should have n linearly independent eigenvectors

왜 중요한가? Easy to calculate det(A), A^2, A^-1, ...

<= det(inv(A)) = 1/det(A)

# Singular Value Decomposition (SVD)

generalization of eigendecomposition to m x n matrix

# Matrix inversion

A is invertible if there exists B such that

# Pseudoinverse A+

a generalization of the inverse matrix to m x n matrix

Use to compute a 'best fit' (least squares |Ax-b|=0) solution to a system of linear equations

# (대부분의 경우) 역행렬이 존재하는 않을 때 (m x n matrix) 해를 구하는 방법

=> det(A) != 0, det(A) = 0,

# Norm of one thing

a function that assigns a strictly positive length or size to each vector:

Scalar : p(av) = |a| p(v)
Sum : p(u + v) ≤ p(u) + p(v)
Positive : p(v) ≥ 0
Zero-vector : If p(v) = 0 then v = 0

# L1 norm

# L2 norm (Euclidean norm)

# Metric of two thing (distance function)

A function that defines a distance between each pair of elements of a set.

Symmetry : d(x, y) = d(y, x)
Sum : d(x, z) ≤ p(x, y) + p(y, z)
Positive : p(x, y) ≥ 0
Zero-equality : If p(x, y) = 0 then x = y

# Discrete metric

if x = y, d(x,y) = 0. Otherwise, d(x,y) = 1.

# Euclidean distance

# Newton Method (뉴턴 메소드)

finding repeatedly better approximations to the roots (or where f(x) = 0) of a real-valued function.

until |x_n+1 - x_n| (change) is small

Should be continuous and differentiable
Can only find one among multiple answers (dependent on initial x_0)
When gradient is zero

# Root of a function

# Cartesian coordinate system (x, y)

# Polar coordinate system (r, ϕ)

Cartesian -> Polar

# Find n prime numbers => 에라토스테네스의 체(sieve of Eratosthenes)

# Metric (distance function)

Defines a distance between each pair of elements of a set

ex) Euclidean, Discrete, Levenshtein distance (but no KL-divergence b/c not symmetric)

# NP (Nondeterministic Polynomial Time)

Sudoku is in NP (quickly checkable) but does not seem to be in P (quickly solvable)
NP is the set of all decision problems where the 'yes'-answers can be verified in polynomial time O(n^k) by a deterministic Turing machine, or solvable by a non-deterministic Turing machine
(polynomial time안에 그 solution이 맞는 solution인지 아닌지 구분할 수 있는지)

# P (Nondeterministic Polynomial Time)
P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. Since they can be solved in polynomial time, they can also be verified in polynomial time. P is a subset of NP.

# NP-hard (at least as hard as the hardest problems in NP)
H is NP-hard when for every problem L in NP, there is a polynomial-time reduction from L (easy) to H (hard), that is given a solution for L we can verify it is a solution for H in polynomial time.
Solve any NP-hard problem in polynomial time would solve all NP problem

# NP-hard but not NP-complete :

given a program and its input, will it run forever? : undecidable because of infinite run

# NP-complete

Both in NP and NP-hard. Any NP problem can be reduced into NP-complete.

# Turing machine

a mathematical model of computation with tape

Tape (memory)
Head
State register : A or B or C
Table of instruction : action table

# Turing completeness

A system (like programming language) is said to be Turing complete if it can simulate any Turing machine.

It could be used to solve any computation problem.

# Finite-state machine

A mathematical model of computation without memory (tape)

State : description of the status of a system
Transition : a set of actions to be executed

[ 통계 ]

# Probability

A likelihood of an event of random variable to be occurred. Sum of p for all possible disjoint events are 1.

# Random variable

a function that maps outcomes to numerical quantities

a variable whose values are numerical outcomes of a random phenomenon. (ex. Coin front/back)

# PDF (Probability Density Function)

A relative likelihood that the value of the random variable would equal that sample

(the absolute likelihood of continuous random variable on any particular value is 0. 0.0231을 뽑을 확률은 0)

# PDF condition :

f(x) > 0

# How PDF > 1 ?

Uniform distribution defined in 0 < x < 1/2

# Variance

Expectation of the squared deviation of a random variable from its mean

(how far the values are spread out from mean)

# Covariance

# Bernoulli distribution

special case of the Binomial distribution where a single experiment/trial is conducted (n=1)

# Binomial : n for # of trial, p

the discrete probability distribution of the # of successes in a sequence of n independent experiments

where (combination w/o considering order)

# Multinomial: n for # of trials, p_1, p_2, .., p_k (sum p_j=1)

# Gaussian: mean, variance

PDF :

# Multivariate Normal distribution:

generalization of the one-dimension to higher dimension

# Moment

A quantitative measure of the shape of a set of points.

Mean :
Variance :
Skewness : ( a measure of the asymmetry )
Kurtosis

# i.i.d (Independent and Identically Distributed)

Independent : not related to previous result
Identically Distributed : probability distribution is identical over time

To simplify the underlying mathematics of many statistical methods (not Markov chain P(x_t|x_t-1))

# Bayesian probability <-> Frequentist

Bayesian interpretation of probability is a degree-of-belief interpretation.

Take into account of prior distribution (can say there was life on Mars a billion years ago is 1/2)

Advantage:
1. Prior : easy to apply domain knowledge
2. Uncertainty: can predict uncertainty. Can detect anomaly

Disadvantage :
1. Choice of prior
2. Computationally intensive : if it is required to sample lots of variables

# Frequentist probability

limiting value of the number of successes in a sequence of trials

(p of life on Mars a billion years ago is can’t be assigned)

# Mean, Median and Mode

Mean : Expected value in probability distribution. ,
Median : the value separating the higher half.
Mode : Most frequent value in a data set

# Joint probability distribution

Join probability P(X=x, Y=y,...) is probability that each of X, Y, ... falls in any particular values.

# Conditional probability distribution

P(Y|X) is probability of Y when X is known to be a particular value

# Independence

Two events are called independent if and only if P(A∩B) = P(A)P(B)

# Marginal distribution

Marginal distribution of subset of a collection of random variables is the probability distribution of the variables contained in the subset

# Bayes rule

Likelihood: how probable is the [evidence] given the hypothesis
Prior: how probable was [hypothesis] before observing evidence
Posterior: how probable is [hypothesis] given the observed evidence
Priori (Marginal): how probable is the new [evidence] under all hypothesis

[ 머신러닝 ]

# Maximum Likelihood Estimation

finding the parameter that maximize the likelihood of making the observations given the parameters

# ((all) Batch) Gradient descent

w := w - lr * dL/dw

compute on ALL training set

# Stochastic gradient descent

compute on a SAMPLE of training set. "stochastic approximation" of the "true" cost gradient.

Faster matrix operations (computation)
Parallelization
Convergence is slower than second-order gradient methods (Newton’s method)

But benefit of computational efficient is greater
Can converge faster if learning rate is adjusted

# Regression

Predict continuous valued output

(linear regression, k-nearest neighbors, nonlinear regression, polynomial regression)

# Linear regression

Pros: easy to compute

Cons: Sensitive to Outliers, limited to Linear Relationships, Data should be Independent,

Update: gradient descent with least square (+ L2 regularization)

: least square error + l2-regularizer

# Classification

Predict a category (probability for each) of new data

(logistic regression, decision tree, k-nearest neighbors, boosting ...)

# Logistic regression (a generalized linear model)

Pros: easy to compute

Cons: scalability, Data should be Independent

Update: gradient descent with (sigmoid) cross entropy loss.

(maximize log likelihood)

# Sigmoid cross entropy loss:

loss = z * -log(sigmoid(x)) + (1 - z) * -log(1 - sigmoid(x))

# Ensemble : use multiple learning algorithms to obtain better performance

Bootstrap aggregating (bagging) : ensemble vote with equal weight
Boosting : a set of weak learners -> strong learner (reduce bias)
Stacking : train additional merger model (theoretically represent any of the ensemble techniques)

# Supervised

labeled training data

# Unsupervised

Unlabeled training data

# Semi-supervised

Only part of the training data is labeled

# Why semi-supervised is important

Overcoming the problem of lack of data by adding cheap and abundant unlabeled data

# Clustering

task of grouping where objects in the same group (called a cluster) are more similar

(k-means, hierarchical clustering)

# k-means - Centroid-based clustering (NP-hard)

Pros: Simple, No training-time. Always converge

Cons: can’t distinguish all distribution (평행한 두 데이터), NP-hard (local minimum), wrong k

Update:

Random initialize centroids
Repeat {Assignment, Update}

Finding k : Elbow method

Sum of the squared distance between each member of the cluster and its centroid

k=6 at which the SSE decreases abruptly

# Hierarchical clustering

Agglomerative (bottom up) : starts with N cluster. Merge two successively.
Divisive (top down) : starts with one cluster. Splits successively.

# Overfitting

best model : where the validation error is global minimum.

test error increases while training error decreases

# Cross validation

Validation method to generalizability on an test set.

Independent round training prevent to be optimistically biased.

One round : split a data train/validate/test and train and validate
Repeat multiple rounds with different partitions and average the validation results.

# k-fold cross validation

Partitioned into k equal sized subsamples. Repeated k times (the folds) and the k results are averaged

Pros: when test set is too small, performance estimate is less sensitive to the partitioning of the data

# Reinforcement learning

RL is modeled as a Markov Decision Process.

<reward, state, action, policy, state transition>

# Markov Chain (Markov process)

a stochastic model describing a sequence of possible events

=> 이전 state에만 conditioning하는 sequential한 stochastic 모델

# Hidden Markov model

a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved (i.e. hidden) states.

#####################

# Monte Carlo Method <-> Deterministic Algorithm

#####################

Use repeated random sampling to obtain numerical results (overall distribution)

###################################
# MCMC (Markov chain Monte Carlo)

###################################

Posterior mean 계산이 어렵기 때문에 i.i.d. 가정을 하고 샘플링 (approximation), Sampling algorithms based on constructing a Markov chain.

Gibbs Sampling
Metropolis–Hastings algorithm

1. Gibbs Sampling (\in MCMC)

A MCMC algorithm for obtaining a sequence of observations which are approximated from a specified multivariate probability distribution, when direct sampling is difficult.

쉽게 이해하자면 처음 하나의 초기 샘플 X_0을 랜덤하기 정한다음, 그 샘플에서 차원 1개씩 순차적으로 정하는 방법이다. n번째의 값을 정할 경우, 그 이외의 차원들은 고정된 값으로 본다. MCMC는 N차원의 점에서 바로 N차원의 점으로 모든 차원을 한번에 이동하면서 샘플링을 한 것인 반면, 깁스 샘플링은 한개의 차원을 제외한 나머지는 고정을 시킨다음, 한 차원 씩 샘플링을 해서 총 N번의 이동을 하고 난 다음 진짜 새로운 데이터를 샘플링하는 것이다.

장점 : break the curse of dimensionality

단점 : doesn't allow the variables to evolve jointly

2. Metropolis–Hastings algorithm (\in MCMC)

???

# Markov Decision Process <S, A, R, T, discount>

Framework for modeling decision making with Markov process.

Algorithm :

Dynamic programming

and is updated alternatively
(policy가 있기 때문에 max가 없음)

Value iteration

is calculated within
(policy가 없기 때문에 max)

If assignment became equal, it’s Bellman equation

(R에 randomness만 뺀것)

Policy iteration (Policy evaluation + Policy improvement)

# Reinforcement Learning

Policy:

Return:

Value:

Q-value:

Monte Carlo in RL

Importance Sampling

Objective function in RL

Policy Gradient

Cons : using Q is low variance but biased

REINFORCE (Monte-Carlo Policy Gradient)

Return = unbiased (but high variance) estimation of Q(a, s)

## To deal with high variance of REINFORCE

Baseline (or Advantageous function)

Sum pi = 1

Actor critic

# Q-learning (Value iteration update, off policy)

+ epsilon greedy

a simple value iteration update, using the weighted average of the old value and the new information

epsilon greedy :

# SARSA (on-policy)

# Parametric

a finite number of parameters which does not depend on data

(linear regression, logistic regression)

# Nonparametric learning

Models become more complex with an increasing amount of data.

(K-nearest neighbor, Decision Trees, Histogram)

# Sequential data

Markov (decision) process : P depends only on the state attained in “one-step” before event
RNN

# Neural Network

computing systems inspired by the biological neural networks composed of neurons

# SVM loss

score of the correct class to be higher than all other scores by at least a margin of delta.

(delta and regularizer coefficient works as same so only need one of them)

# Softmax loss

Information theory : minimizing cross-entropy between softmaxed probability and true distribution
Maximum Likelihood Estimation: minimizing the negative log likelihood of the correct class

f -= np.max(f) ← Stablize softmax

p = np.exp(f) / np.sum(np.exp(f))

# Sigmoid loss

Minimizing cross-entropy between sigmoided probability and true distribution

# RNN
h_t = tanh(W [x_t; h_t-1] + b)

o = softmax(W h_t + b)

# LSTM
f, i, c’, o = f(W [x_t; h_t-1] + b). f, i, o : sigmoid, c’ : tanh

c_t = f * c_t-1 + i * c’

h_t = o * tanh(c_t)

지금 x과 h를 바탕으로 할 것 예측
이전 c를 지우고 씀 => c 끝
다음 x와의 계산에 중요한 것만 남김 => h끝

# Vanishing & Exploding gradient

0<= 0 d sigmoid x <= 1/4
0<= 0 d tanh x <= 1

Gradient contributions from “far away” steps become zero by chain rule

Proper initialization
ReLU instead of tanh or sigmoid
LSTM : if f gate is 1 : no vanishing gradient => long term dependencies can be learned

# Backpropagation

Forward pass
Compute error
Backward pass
Repeat

# Backpropagation Through Time

A weight is updated with sum of gradient for each time step (because weights are shared)

# Black box model vs White box model

Advantage:

Performance
End-to-End optimization

Disadvantage:

Interpretability

Can this network tell a Husky from a Poodle?
Which objects are easy to classify for the algorithm, which are difficult?
Which part of a dog is the most important for being able to classify it correctly? The tail or the foot?
If I photoshop a cats head on a dog, what happens, and why?

# Curse of dimensionality

With classical non-parametric learning algorithms (e.g. nearest-neighbor, SVM, etc.), the learner will need to see at least one example for each of these many configurations.

# of data is exponentially increasing so solution in low dim can’t be applied to higher dim

# VAE vs GAN

VAE: maximum likelihood

assign high p to any point that occurs frequently (also blurry images).

where the latent is important

GAN: GAN loss {D_real + D_fake} + {G_fake} is highly dependent on how D is optimal

avoid assigning high p to points that the discriminator recognizes as fake (such as blurry images)

GAN convergence does not guarantee the performance convergence
Mode collapsing

Solving MiniMax problem:
But train D, G alternatively makes NN undistinguishable between minimax and maximin
In maximin, G could just generate single image that can fake the D (non optimal)
<->
No quantitative loss:
Fake or not is subjective based on D (unlike autoencoder loss in VAE)
Even when G does not cover all modes, it’s still fine with GAN loss

Blurry image : VAE high p, GAN low p

# Softmax = exp(x_i) / sum_j exp(x_j) 가 불안전한 이유

0 or infinite division. Can avoid with - max(x_i) to all terms.

# REINFORCE = E[ R d log(p) ]를 안정되게 하려면

Reducing Variance Using a Baseline : E[ (R - mu) d log(p) ]. Gradient 가 같기 때문에 update 가 똑같음.
The advantage function has lower variance since the baseline compensates for the variance introduced by being in different states.

# Policy-Based RL

장점 : learn stochastic policies, continuous action spaces

단점 : Evaluating a policy is typically inefficient and high variance

(may receive very different rewards for similar or even identical behavior)

[ Problem solving ]

http://ronniej.sfuh.tk/array-pair-sum/

# Anagram O(2n) = O(n)

def anagram(a, b):

if len(a) != len(b):

return False

counter = {}

for c in a:

c = c.lower()

if c not in counter:

counter[c] = 1

else:

counter[c] += 1

for c in b:

c = c.lower()

if c not in counter:

return False

counter[c] -= 1

if counter[c] < 0:

return False

return True

print(anagram('Eleven plus two', 'Twelve plus onn'))

# Max contiguous sum

def max_cont_sum(array):

max_sum = -9999

max_sum_sofar = array[0]

for num in array[1:]:

max_sum_sofar = max(num, max_sum_sofar+num)

max_sum = max(max_sum, max_sum_sofar)

return max_sum

print(max_cont_sum([1,2,3,-100,1,2,1]))

# Kth Largest Element in Array

def find_k(array, k):

for k_i in range(k):

for idx in range(k_i+1, len(array)):

if array[idx] >= array[k_i]:

array[idx], array[k_i] = array[k_i], array[idx]

print(array)

return array[k]

print(find_k([0,-1,5,4,2,1,3], 3))

# Powerset (permutation)

# f([3, 1, 5])

# = { [3] + x in f([1, 5]) }

# + { x in f([1, 5]) }

def powerset(x):

answers = []

if len(x) <= 1:

return [x, []]

else:

for item in powerset(x[1:]):

answers.append([x[0]] + item) # [1] + ([2], [])

answers.append(item) # [2], []

return answers

# reverse string and omit multiple space

def reverse(string):

split_string = []

tmp = ""

for char in string:

if char == " ":

if tmp != "":

split_string.append(tmp)

tmp = ""

else:

tmp += char

split_string.append(tmp)

return " ".join(reversed(split_string))

def reverse(string):

return " ".join([word[::-1] for word in string[::-1].split()])

def reverse(string):

return " ".join(reversed(string.split()))

# Return pairs where sum is k

def array_pair_sum(array, k): # O(n^2)

answers = []

array.sort() # O(n logn)

for idx, num in enumerate(array):

if k - num in array[idx+1:]: # O(n^2)

answers.append([num, k-num])

return answers

def array_pair_sum(array, k): # O(nlogn)

answers = []

array.sort() # O(n logn)

left, right = 0, len(array) - 1

while left < right:

tmp = array[left] + array[right]

if tmp == k:

answers.append([array[left], array[right]])

elif tmp < k:

left += 1

else:

right += 1

return answers

def array_pair_sum(array, k): # O(n)

answers = []

table = {}

for idx, num in enumerate(array):

if k - num in table:

answers.append([num, k-num])

else:

table[num] = True

return answers

# check combined two string

def check(a, b, merge):

if len(a) + len(b) != len(merge):

return False

if not a or not b or not merge:

if a + b == merge:

return True

else:

return False

if a[0] != merge[0] and b[0] != merge[0]:

return False

elif a[0] == merge[0] and check(a[1:], b, merge[1:]):

return True

elif b[0] == merge[0] and check(a, b[1:], merge[1:]):

return True

return False

print(check("abc", "def", "dabcef"))

# Check binary tree

def isBT(tree, min_val=-999 max_val=999):

if tree is None:

return True

if not min_val <= tree.val <= max_val:

return False

return isBT(tree.left, min_val, tree.val) and \

isBT(tree.right, tree.val, max_Val)

# Convert array in-place using constant extra space.

def get_index(idx, N):

return (idx % 3) * N + idx // 3

def convert_array(array):

N = len(array) // 3

for idx in range(len(array)):

swap_idx = get_index(idx, N)

while swap_idx < idx:

swap_idx = get_index(swap_idx, N)

array[idx], array[swap_idx] = array[swap_idx], array[idx]

return array

array = list("1234abcdzxyw")

print(convert_array(array))

#############

# Quicksort

def partition(array, start, end):

if start >= end:

return start

else:

pivot = start

for idx in range(start+1, end+1):

if array[idx] <= array[start]:

pivot += 1

array[idx], array[pivot] = array[pivot], array[idx]

array[start], array[pivot] = array[pivot], array[start]

print(array[start:pivot], array[pivot], array[pivot+1:end+1])

return pivot

def quicksort(array):

def _quicksort(array, start, end):

if start >= end:

return

else:

pivot = partition(array, start, end)

_quicksort(array, start, pivot-1)

_quicksort(array, pivot+1, end)

return _quicksort(array, 0, len(array) - 1)

# Sort

def mergesort(array):

less = []

equal = []

greater = []

if len(array) > 1:

pivot = array[0]

for x in array:

if x < pivot:

less.append(x)

elif x == pivot:

equal.append(x)

else:

greater.append(x)

return mergesort(less) + equal + mergesort(greater)

else:

return array

# Binary search

import math

def binary_search(array, find):

start = 0

end = len(array) - 1

while True:

idx = int(math.floor((start + end)/2.0))

if find == array[idx]:

return idx

elif find < array[idx]:

end = idx - 1

elif find > array[idx]:

start = idx + 1

if start >= end:

if find == array[start]:

return start

return False

def fibonacci(num):

if num == 0:

return 0

elif num == 1:

return 1

else:

return fibonaci(num-1) + fibonaci(num - 2)

def fib(n, cache={}):

if n == 1:

cache[1] = 1

return 1

elif n == 2:

cache[2] = 1

return 1

else:

if n not in cache:

cache[n] = fib(n-1, cache) + fib(n-2, cache)

return cache[n]

import numpy as np

class NQueeun(object):

def __init__(self, size):

self.size = size

self.rows = []

def place(self, start_row=0):

if len(self.rows) == self.size:

print(self.rows)

return self.rows

else:

for row in range(start_row, self.size):

if self.is_safe(row, len(self.rows)):

self.rows.append(row)

return self.place()

else:

last_row = self.rows.pop()

return self.place(last_row + 1)

def is_safe(self, row, col):

for thread_col, thread_row in enumerate(self.rows):

if row - thread_row + col - thread_col == 0:

return False

elif row - thread_row == col - thread_col:

return False

elif row == thread_row or col == thread_col:

return False

return True

def print(self):

board = np.array([[' '] * n] * n)

for q in self.rows:

board[self.rows.index(q), q] = 'Q'

print(board)

n=9

queen = NQueeun(n)

queen.place(5)

queen.print()

import heapq

import numpy as np

G = {1: {2:10, 3:12}, 2:{3:1, 4:5}, 3:{4:2}, 4:{}}

def dijkstra(G, start):

d = {}

prev = {}

for v in G.keys():

d[v] = np.inf

prev[v] = None

d[start] = 0

s = []

q = []

for v in G.keys():

heapq.heappush(q, [np.inf, v])

while len(q) != 0:

u = heapq.heappop(q)

s.append(u)

for v in G[u[1]].keys():

if d[v] > d[u[1]] + G[u[1]][v]:

d[v] = d[u[1]] + G[u[1]][v]

prev[v] = u[1]

print d

dijkstra(G, 1)

import unittest

class DijkstraTest(unittest.TestCase):

def test_dijkstra(self):

self.assertEqual(1,1)

if __name__ == '__main__':

unittest.main()

[ 퀴즈 ]

[ 컴공 ]

f(x) = O(g(x))

링크드리스트 장단점

해시테이블 장단점 콜리젼나면 어떻게 해결할래

바이너리 서치 트리 정의 장단점, 구현은 어떻게 하냐

Heap vs Stack

depth first search : stack + 왔던곳 체크

메모리릭 : is not released, not accessible

compiler, interpreter, jit 프로그래밍의 정의

compiler와 interpreter의 장단점

Encapsulation (public, private) : isolating implementation details, prevent mistake

==============> Refactoring

Lambda function

Garbage collection

Functional programming : stateless

GPL

[ 수학 ]

dx/dy = derivative of x “with respect to” y

Integration by parts

log(x+10) 그려라

sin(x^2) 그려라

sin(x^2) 미분해라

log(x) 적분

1/x 적분

==============> limit의 정의

Derivative : sensitivity to change of value
Partial derivative
Gradient
Hessian
Jacobian

Find n prime number

metric의 정의와 예시 (Euclidean 말하고 그거 식 씀)

np-complete

Turing machine : tape (memory), header, state, transition. mathematical model of computation

==============> Turing completeness : A system that can simulate any Turing machine (can solve any computation problem)

Finite state machine : state, transition

[ 통계 ]

binomial, multinomial, gaussian

==============> random variable이 뭔지 : function X: Ω→ℝ

pdf : A relative likelihood that the value of the random variable
pdf의 조건, pdf가 1 이상을 가질 수 있는 이유 (ex. uniform dist)

Variance

Covariance :

IID : previous results are not related, distribution is identical over time

==============> Bayesian statistics :

interpretation of p is degree-of-belief interpretation. Takes into account of the prior distribution

Joint probability : p when all variable falls into specific value
Conditional probability : p of Y when X is known
Independence
Marginal : In distribution with collections of variable, p of the variables contained in the subset

1st, 2nd, 3rd, 4th moment : measure of of the shape of a set of points.

==============> Mean => variance => skewness => kurtosis

==============> Bayes rule

Likelihood: how probable is the [evidence] given the hypothesis
Prior: how probable was [hypothesis] before observing evidence
Posterior: how probable is hypothesis given the observed evidence
Priori: how probable is the new [evidence] under all hypothesis

Determinant: identity, transpose, inverse, multiplication

Eigenvector: In a linear transformation, non-zero vector that only changes by an scale

Eigendecomposition: should have n linearly independent eigenvectors

Singular Value Decomposition

==============> Matrix inversion

Pseudoinverse : generalization of inverse matrix. Used in finding least squares |Ax-b|=0 solution

=> det(A) != 0, det(A) = 0,

linearly independence : a linear combination of the others

Orthogonal vector & matrix

==============> Norm : length or size : scalar, sum, positive, zero-vector

==============> Metric : distance : symmetry, sum, positive, zero-equality

Newton Method : approximation to find root of a function. x := x - f/f’

[ 머신러닝 ]

==============> Maximum Likelihood Estimation

L2 loss, l2 regularizer, l2 norm

nn 정의

gradient descent 의 정의와 식

stochastic gradient descent 정의 그리고 장점

regression의 정의와 예시 알고리즘(linear regression 말함)

linear regression의 정의와 장점 단점, 업데이트 방법, optimal을 찾는법 (least square)

classification의 정의와 예시 (logistic regression 말함)

logistic regression의 정의와 장단점

supervised, unsupervised, semi-supervised 정의

semi-supervised가 중요한 이유

clustering 정의

clustering 예시 (k means 말함)

kmeans가 뭔지 어떻게 업데이트하는지 설명, k는 어떻게 설정하는지

kmeans의 장점과 단점(단점은 구분할 수 있는 데이터 분포가 정해져있음, 클래스 2개가 일직선으로 떨어져 있으면 kmeans로 구분 못함)

cross validation이 뭔지 (k-fold cross validation이 말하고 그걸 쓰는 이유 말함 데이터가 limit 하니까)

reinforcement learning의 정의 (reward, state, action, policy, state transition)

rl 업데이트 방법 (q-function)

q-learning이 off-policy인지 on-policy인지

non bayesian과 bayesian의 차이

non parametric learnin의 정의와 예시 (원래는 binomial이라고 했는데 이거 틀림 왜냐면 p가 필요하기 때문에. 정답은 histogram). sequential data를 표현하는 모델의 예시 (hidden markov, bayes, rnn)

rnn의 정의와 식

rnn의 장점과 단점 (vanishing gradient) 해결방법 lstm.

rnn과 hidden markov의 장단점 비교 (rnn은 파라미터 쉐어해서 표현력이 떨어지지만 end-to-end 모델이라 gradeint descent해서 optimal 찾긴 찾음)

neural network 업데이트 방법 (backpropagation)

rnn의 업데이트 방법 (time delayed backpropagation)

big one black box 모델과 neural net같은 모델 (이 두 모델을 정의하는 term이 있는데 기억이 안남)을 비교했을때 nn같은 module화된 모델의 장단점 (장점은 모델 expresivity 가 훨 좋음, 단점은 각각의 모듈과 그 모듈들의 condition을 배워야 해서 오래 걸림)

curse of dimensionality

bayesian setting을 왜 잘 안쓰는지 (distribution을 정하는게 tricky하고 각각을 계산하는게 오래걸림)

prior (데이터) 샘플링 방법 : Gibbs Sampling (\in MCMC)

히든 마콥 모델이 뭔지 설명

VAE vs GAN

[ 알고리즘 ]

Permutation

N queens

Kth Largest Element in Array

2018.01.31 update

How computer represent floating number : 0.2341234123e-3

How to deal with unbalanced tree

Explain dynamic programming and give me an example

Explain quicksort. Can we do better than n log n. Radix sort

Integral of log x

Difference between process and thread

How to find A-1

Hessian, Jacobian and when these are used in practice

Jacobian is composed of column vector of gradient

What is positive definite

Why newton method has such form (x := x - f / f’)

2018.02.05 update

What is central limit theorem

The law of big number

Who can you derive mu(x) = E[x^2] - E[X]^2

How to sample from arbitrary continuous random variable with uniform distribution: A general method is the inverse transform sampling method, which uses the cumulative distribution function (CDF) of the target random variable

Recommended Lectures

carpedm20