Time complexity notations

Sometimes complexed about the exact meaning of the Big-O, theta, and omega notations. I found a great and beautiful summary table of them.

For more details, check out the wikipedia pages below.

Useful

Algorithm Time complexity : Family of Bachman Landau notations

Master theorem

recursive algorithm을 구현할 때, 점화식으로부터 시간 복잡도를 구할 때 사용되는 theorem이다.

기본적으로 점화식이 다음과 같이 나올 경우에 대해서,

다음 세 가지 usecase 로 나누어서 해당 algorithm의 time complexity를 측정하는 것이 가능하다.

Example

유명하게 알려져 있는 recursive algorithm에 Master theorem을 대입하면 다음과 같다.

further questions

• 각각 다음과 같은 식으로 점화식이 분리가 되어서 나올 때는 어떻게 식을 적용해야 하는 지는 좀 헷갈린다.

T(n) = T(0.4n) + T(0.6n) + O(n)

T(n) = T(0.4n) + T(0.2n) + O(n^2)

Userful links

Master theorem, Wikipedia

Tips on tech interviews by Gayle Mac

1. how companies evaluate tech interviews

• you gotta focus on communications
  1. Talk a lot loud to express thought process
  2. At least, try to summarize what you try to do
  3. little mumbles are better than staying silent

2. how to approach behavioral questions

• short intro

  1. quick shows of success
  2. key strories (let the interview ask for details)
  3. hobbies (tech / non-tech)

• prepare to dicuss at least 2-3 projects in detail

  1. techinial role
  2. soft skills
  3. about the bad stuff
• mistakes
• failures

3. 7 steps to solve algorithm problems

1. listen
2. example
3. brute force
4. optimize
5. walk through your algorithm
6. code on a writeboard or on a paper
   • coding style matters
   • consistnet braces
   • descriptive variables
   • modulize
7. test
   • analyse
   • use test cases

4. 3 algorithm strategies

1. BUD

   • Bottlenecks
     • what details make the algorithm slow?
     • how can we improve that?
   • Unneccessary work
     • is there any unneccessary work to make the algo faster?
   • Duplicated work
     • same with the above

2. Space / Time trade-offs

   • Hashtable : good example of space/time trade-offs

3. DIY

   • Use your brain to find a shortcut algorithm
   • Try a large & generic example

Useful Links

How companies evaluate tech interviews - Gayle Mc

How to approach behavioral questions - Gayle Mc

7 Step to solve algorithm problems - Gayle Mc

3 Algorithm Strategies - Gayle Mc

Tips using linux

Upload & download files using SCP

• local sever -> remote server

  1	scp abc@111.222.333.444:/home/abc/* /home/me/

• remote sever -> local server

  1	scp /home/me/ abc@111.222.333.444:/home/abc/*

• in case of using other port as SSH

  1	scp -P 2222 abc@1.2.3.4:/home/abc/* /home/me/

List all files

• including folders

  1

  find .

• excluding folders

  1	find . -type f

다른 계정으로 bash 명령 실행하기

1. 계정 이름, host 주소만 필요할 경우

   1	ssh [id]@[host] [command]

2. password도 필요한 경우

   1	sshpass -p [password] ssh [id]@[host] [command]

bash error handling

• error 발생시 스크립트 종료하기

  1	[bash_command] || [error_handling_function]

• example

  1 2 3 4 5 6 7 8

  function error_exit { echo "$1" 1>&2 exit 1 } # [bash_command] || error_exit [error_message] cd $some_directory || error_exit "Cannot change directory! Aborting."

Using bash script on python

1. simple way without a return value

   1 2	import os, sys os.system("ls -al")

2. the way with a return value (printed value)

   1 2 3 4 5 6

   import subprocess def bashcmd (cmd, isPrint=True): result = subprocess.check_output(cmd, shell=True) print result.decode("utf-8") bashcmd ('ls -al')

3. in case of python < 2.7

import subprocess
if "check_output" not in dir( subprocess ): # duck punch it in!
    def f(*popenargs, **kwargs):
        if 'stdout' in kwargs:
            raise ValueError('stdout argument not allowed, it will be overridden.')
        process = subprocess.Popen(stdout=subprocess.PIPE, *popenargs, **kwargs)
        output, unused_err = process.communicate()
        retcode = process.poll()
        if retcode:
            cmd = kwargs.get("args")
            if cmd is None:
                cmd = popenargs[0]
            raise subprocess.CalledProcessError(retcode, cmd)
        return output
    subprocess.check_output = f

def bashcmd (cmd, isPrint=True):
    result = subprocess.check_output(cmd, shell=True)
    print result.decode("utf-8")

bashcmd ('ls -al')

Useful Links

file upload & download between Linux machines using scp

python 사용하여 bash shell 사용

how to use subprocess.check_output() in python 2.6

다른 계정으로 명령 실행하기

using ssh with password

error handling with bash

Install R & Rstudio in CLI on Mac

Install homebrew

Homebrew is awesome, since you can just install things wtih your terminal, like yum, apt-get in Ubuntu.

First, turn on your terminal. If you didn’t install homebrew yet, just copy & paste the following script.

1

ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

or you already installed homebrew, just update it.

1

brew update && brew upgrade

Install R & Rstudio

You gotta extend the respositories by installing Cask. Just don’t be cared, follow the steps of each line.

1
2
3
4
5
6
7
8
9
10

brew tap caskroom/cask
brew install brew-cask
brew install Caskroom/cask/xquartz
brew cask install java
brew tap homebrew/science
brew install R
brew install Caskroom/cask/rstudio

Then, you can get this.

• note
  • While you got into several steps, it would bootstrap. It could take more than an hour sometimes. Don’t be panic, and take a cup of coffee reading some posts in Facebook or some.

Useful links

R for Mac

Rstudio for Mac

How to install R & Rstudio

Shiny in Rstudio

Important Data Structure

• array & string
• linked Lists
• stack & queue
• tree & graph

Important algorithms & concepts

• bit manipulations
• probabilities
• OOP
• Recursive & Dynamic Programming
• Sort & Search
• Scalability & memory issues
• Testing

Knowledge

• C++
• database
• thread & lock

Data Structure terms

Tree

Tree = acyclic graph

Binary tree = tree that consists of 2-children nodes

Binary Search Tree = binary tree with the relationship between all parent(p) and left child(l), right child(r), such that l.val <= p.val < r.val

Depth

Min : logn // Max : n

Search

Best : O(logn) // Wost : O(n)

Traverse

pre-order : parent -> left subtree -> right subtree

in-order : left subtree -> parent -> right subtree

post-order : left subtree -> right subtree -> parent

Balanced BST

Red-Black Tree

AVL Tree

Treap : tree + heap, randomized binary search tree

implementation

node implementation

Array vs Dynamic memory

Useful Links

Tree Data structure

Binary Tree

BST

Huklee’s Vim cheet sheet

1. Using bash shell commands

1

:! [bash_cmd]

• run a shell

  1

  :sh

2. Auto-indent

• all lines

  1

  gg=G

• for selected lines

  1 2	[selected mode] =

3.

Useful Links

Vim tips working external commands

vim cheat sheet

1. Bianry Search for closest number problem

• Input : ordred list of integers, a given number

• Ouptut : find the the closest number to the given number

• solution in python

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  # recursion solution def solve(arr, num, start=0): # 01. base case : size() <= 3 if len(arr) <= 3: minVal = min([abs(x - num) for x in arr]) for i in range(len(arr)): if minVal == abs(arr[i] - num): return start + i # 02. check the mid value then exclude the wrong side mid = int(len(arr)/2) if arr[mid] < num: return solve(arr[mid + 1:], num, start + mid + 1) else: return solve(arr[:mid + 1], num, start)

• solution in C++

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  // recursive solution int solve(vector<int> arr, int num, int start, int end){ // 01. base case : size() <= 3 if (end - start <= 2){ int min_val = abs(num - arr[start]); for (int i=start; i <= end; i++) min_val = min(abs(num - arr[i]), min_val); for (int i=start; i <= end; i++) if min_val == abs(num - arr[i]) return i; } // 02. check the mid value then exclude the wrong side int mid = (end - start)/2; if (arr[mid] < num) return solve(arr, num, mid + 1, end); else return solve(arr, num, start, mid); }

SQL : Structured Query Language

SQL tutorials

DB를 다루는 데 기본적인 query를 배우기 위해서는 SQL을 알아야 한다. 어느 정도 사용법을 익숙해 지기 위해서는 다음 튜토리얼을 따라가면 금방 익힐 수 있다.

SQL Tutorials

사이트에서는 간단한 SQL Testbed를 제공하는데, 훌륭한 예제 database가 들어가 있어서, 왠만한 기본 기능을 익히고 테스트 하는 데 괜찮다. crate table & insert into를 사용하면 데이터를 넣는 것도 가능하지 때문에, 이것저것 스스로 예제를 만들어서 간단히 테스트하는 것도 가능하다.

SQL try testbed

Advanced

다음은 개인적으로 사용법이 좀 헷갈리는 것들을 정리해 놓은 것

Group By

1
2
3
4
5
6
7
8
9
10

SELECT orderid,
  SUM(total) as total_price,
  AVG(total)/SUM(quantity) as average_price_of_items,
  SUM(quantity) as Items
FROM(
  SELECT *, quantity*price as total
  FROM [orderdetails] as o
      LEFT JOIN [products] as p
  WHERE o.productID = p.productID)
GROUP BY orderid;

=> orderid 별로 total_price, average_price_of item, num_items를 구하는 SQL Query

Useful Links

mysql installation on Mac

Using database indexes

SQL cheet Sheet

All kinds of SQL Queries

Type 1: INNER JOIN - only where both tables match

1.) INNER JOIN aka JOIN

1
2
3

SELECT *
FROM table1 as a (INNER) JOIN table2 as b
ON a.id = b.id;

Type 2: OUTER JOINS where either one or both tables match

1.) LEFT OUTER JOIN aka LEFT JOIN

1
2
3

SELECT *
FROM table1 as a LEFT (OUTER) JOIN table2 as b
ON a.id = b.id;

2.) RIGHT OUTER JOIN aka RIGHT JOIN

1
2
3

SELECT *
FROM table1 as a RIGHT (OUTER) JOIN table2 as b
ON a.id = b.id;

3.) FULL OUTER JOIN aka FULL JOIN
(supported depending on what database program)

1
2
3

SELECT *
FROM table1 as a FULL OUTER JOIN table2 as b
ON a.id = b.id;

Type 3: CROSS JOIN - Cartesian product(all possible combos of each table)

(supported depending on what database program)

1
2

SELECT *
FROM table1 as a CROSS JOIN table2 as b;

Useful Links

stackoverflow on SQL

Cross Join & Self Join