c++ specific

sort

sorted vector : use set
reverse sort

std::sort(begin, end, std::greater<int>())

sort custom struct

// 
bool myCompare(const int a, const int b){
    return gDelay[a] < gDelay[b];
}
sort(gSortedDelay, gSortedDelay+gN, myCompare);

struct Meeting{
    int start, end;
    int nth;
};
bool operator < (const Meeting& a, const Meeting& b){
    if (a.end != b.end) {
        return a.end < b.end;
    }    
    return a.start < a.start;
}

priority_queue

#include <queue>

priority_queue<int> pq;
priority_queue<int, vector<int>, greater<int>> pq_min_heap;

// pq with custom class pointer
class Comparator {
public:
    bool operator()(const Node* a, const Node* b)
    {
        return (a->distance > b->distance);
    }
};
priority_queue<Node*, vector<Node*>, Comparator > queue;

pair

priority_queue<pair<int,int>> pq;
pq.push(make_pair(3,4));

algorithm

max heap

properties: A[p]>=A[i], left = 2*i+1(0-based idx), right=2*i+2, parent = (i-1)/2

maxHeapify(A, len, i) : LEFT(i) & RIGHT(i) already max heap. float down.
buildMaxHeap :
heapSort :

priorityqueue using max heap

heapMaximum
heapExtractMax
heapIncreaseKey :
maxHeapInsert

// assume under i, already maxheap
void maxHeapify(int[] a, int i, int size){
    int largest = i;
    int left = 2*i +1;
    int right = left +1;

    if (left < size && a[left] > a[largest]){
        largest = left;
    }
    if (right < size && a[right] > a[largest]){
        largest = right;
    }
    if (largest!=i){
        swap(a[i], a[largest]);
        maxHeapify(a, largest, size);
    }
}

void buildMaxHeap(int[] a){
    for (int i = a.length/2; i >=0 ; i--){
        maxHeapify(a, i, a.length);
    }
}

void heapSort(int[] a){
    buildMaxHeap();
    int len = a.length -1;
    for (int i = len; i >0; i--){
        swap(a[i], a[0]);
        maxHeapify(a, 0, i);
    }
}

void heapExtractMax(int[] a){
    if (a.heap_size < 1)
        error "heap underflow";
    int max = a[0];
    a[0] = a[heap_size-1];
    a.heap_size --;
    maxHeapify(a, 0, a.heap_size);
    return max;
}

void heapIncreaseKey(int[] a, int i, int key){
    if (key < a[i])
        error "new key is smaller than current key";
    a[i] = key;
    while(i>1 && a[PARENT(i)] <a[i]){
        swap(a[i], a[PARENT(i)]);
        i=PARENT(i);
    }            
}

greedy

activity selection problem

graph

shortest path, Dijstra

struct Node{
    int x,y,v;
};
Node q[10000]; // when you can't use priority_queue<Node>
#define H_MAX 987654321

void findMin(int x, int y){
    int dx = 100;
    int dy = 100;

    q[0].x = x;
    q[0].y = y;
    q[0].v = H_MAX;
    int top=1;
    
    while (top>0){
        Node cur = q[top-1];
        top--;
        // optimize; pop min value form q[0] ~ q[top-1]

        for (int i = 0; i <N; i++){
            int nx, ny, nv;
            // calc nx, ny, nv
            q[top].x = nx;
            q[top].y = ny;
            q[top].v = nv;
            top++;
        }
    }
}

dfs

topological sort : DAG(no cycle), see dictionary

void toposort(){    
  Stack<Integer> s;
  Stack<Integer> path;
  s.push(start);  

  while(1){
      int cur = s.peek();

      s.
  }



}

floyd

shortest path of all vertex

for (int k = 0; k < N; k++){
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            gMat[i][j] = min(gMat[i][j], gMat[i][k] + gMat[k][j]);
        }
    }
}

basic : see workConversion

stochastic

simulated annealing : http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6
genetic algorithm

implementation

matrix rotation

shift clockwise
1.6 NxN matrix, rotate 90 degree clockwise in-place

linked list

reverse linked list, reverse every K nodes

sort

selection sort : O(n^2), swap O(n)
insertion sort : O(n^2) very effective when sorting already sorted data
quick sort : O(n log(n)), worst case O(n^2)
merge sort : O(n long(n)), used when data size is very large
stable sort : add index to each object, when compare use index with the primary data.
given an array of integers arrange them such that alternate elements are large and small.(2,5,3,6,…) ; find median and split, and arrange

void insertionSort(int[] a){
    int key;
    for (int j = 2; j < a.length; j++){
        key = a[j];
        i = j-1;
        while(i>0 && a[i]>key){
            a[i+1] = a[i];
            i=i-1;
        }
        a[i+1] = key;            
    }
}

int partition(int[] a, int s, int e){
    p = a[e];
    i = s-1;
    for (int j = s; j <= e-1; j++){
        if (a[j]<=p){
            i++;
            swap(a[j], a[i]);
        }
    }
    swap(a[i+1], a[e]);
    return i+1;
}
// s,e : inclusive
void qsort(int[] a, int s, int e){
    if (s<e){
        int m = partition(a, s, e);
        qsort(a, s, m-1);
        qsort(a, m+1, e);
    }
}

// a& b inclusive
static void mergeSort(int[] a, int[] b, int start, int end) {
    if (start == end) {
        return;
    }
        
    int m = (start+end)/2;
    mergeSort(a, b, start, m);
    mergeSort(a, b, m+1, end);
    // copy sorted a to b
    int l = start;
    int r = m + 1;
    for (int i = start; i <= end; i++) {
        if (l > m) {
            b[i] = a[r++];
            continue;
        }
        if (r > end) {
            b[i] = a[l++];
            continue;
        }

        if (a[l] > a[r]) {
            b[i] = a[r++];
        } else {
            b[i] = a[l++];
        }
    }
        
    // copy b back to a
    for (int i = start; i <= end; i++) {
        a[i] = b[i];
    }
}
// sort custom object
Arrays.sort(strings, new Comparator<String>(){
        int compare(String o1, String o2) {
            // return >0 , if o1 is greater than o2,
            // return 0, when equals
        }
    });

return the number of non-empty contiguous subarray whose sum is in range[a,b]

http://www.careercup.com/question?id=5200686994161664 idea : sort prefix sum. and choose

3sum

3sum : https://leetcode.com/problems/3sum/ 3sum closest :

dp

lis (longest increasing subsequence)

see lis(java) http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/ http://www.geeksforgeeks.org/dynamic-programming-set-14-variations-of-lis/ hackerrank, https://www.hackerrank.com/challenges/subsequence-weighting http://www.programminglogic.com/codesprint-2-problem-subsequence-weighting/

binary search

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/ see BinarySearch(java)

static int binarySearch(int[] a, int s, int e, int key) {
    while (s <= e) {
        int m = (s + e) / 2;
        if (a[m] > key) {
            e = m - 1;
        } else if (a[m] < key) {
            s = m + 1;
        } else
            return m;
    }
    return -1;
}

questions

http://www.glassdoor.com/Interview/Google-Interview-Questions-E9079.htm http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Practice_Questions_Person_B.pdf

bigo notation : http://bigocheatsheet.com/ http://www.reddit.com/search?q=google+interview+phone&restrict_sr=off&sort=relevance&t=all

kth largest element

quickselect

QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))
  else
    # it's equal to the pivot
    return pivot

pemutation, combination

see combination

stack, queue

// queue
LinkedList<Integer> l = new LinkedList<Integer>();
l.poll();
l.peek();
l.add();

// stack
Stack<Integer> stack = new Stack<Intege>();
stack.push(1);
stack.pop();

tree

# nodes of having values between 2 given integers. each node has # left children and #right children.

int getMaxDepth(Node n){
    if(node==null)
        return 0;
    return 1 + Math.max(getMaxDepth(n.left), getMaxDepth(n.right));
}

Node getTreeMinRecursive(Node n){
    if (n==null){
        return null;
    }
    if (n.left!=null){
        return getTreeMinRecusive(n.left);
    }
    return n;
}

Node getTreeMinIterative(Node n){
    if (n==null){
        return null;
    }
    Node cur = n;
    while(cur.left!=null)
        cur = cur.left;
    return cur;
}

Node getTreeMax(Node n){
    if (node==null){
        return null;
    }
    Node cur=n;
    while (cur.right!=null){
        cur = cur.right;
    }
    return cur;
}

Node getTreePredecessor(Node n){
    if (node==null){
        return null;
    }

    if (node.left!=null){
        return getTreeMax(node.right);
    }

    Node cur = n;
    while (cur.getParent()!=null && cur==cur.getParent().left){
        cur = cur.getParent();
    }
    return cur.getParent();
}

Node getTreeSuccessor(Node n){
    if (n==null){
        return null;
    }

    if (n.right!=null){
        return getTreeMin(Node n);
    }

    Node cur = n;
    while (cur.getParent()!=null && cur==cur.getParent().right){
        cur = cur.getParent();
    }

    return cur.getParent();    
}

void transPlant(Tree t, Node u, Node v){
    if (u.parent==null){
        t.root = v;
        return;
    }

    if (u==u.parent.left){
        u.parent.left =v;
    }else
        u.parent.right=v;
    if (v!=null){
        v.parent = u.parent;        
    }
}

segment tree

trie

insert/search O(M)

math

gcd

gcd(a,a) = a gcd(a,b) = gcd(a - b,b), if a > b gcd(a,b) = gcd(a, b-a)d, if b > a

bit

big endian; store from MSB, little endian, store from LSB. x86 : little, arm: bi-endianness
>> : append 1 when negative. called 부호확장. use >>> to append 0 always
remove specific bit : bit &= ~(1<<p)
toggle specific bit : bit ^= (1<<p)
Integer.bitCount(toppings)
5.3 next smallest number/ previous largest number that have same number of 1 bits in their binary representation

int setBit(int n, int idx, boolean bset){
    if(bSet){
        return n | (1<<idx);
    }else{
        int mask = ~(1<<idx);
        return n & mask;
    }
}

design

scalability

scale up : add ram, scale out : add another machine
http://highscalability.com/google-architecture
- GFS
- MapReduce
- BigTable
url shortening service : http://www.hiredintech.com/app#the-system-design-process
load balancing
- port forwarding by loac balancer HW
- round robin DNS

image search

computer vision, machine learning image distance: compare similarity of two images in color, texture, shape

CrackCode

2.2 Implement an algorithm to find the nth to last element of a singly linked list. hint : using 2 node pointers
2.5 circular linked list. finding loop start. hint : using 2 node pointers
4.5 in-order successor
4.8 all path of tree which sum is S
11.1 stock price - system design

raw text files : hard to maintain db : dynamic query, json file for each : simple enough to display static info

find 2 numbers add up to x, with unsorted arrays; sort it, 2 pointers. one from the start, one from the end
Given a string, convert it into a palindrome with the least number of insertions possible.
Write code to determine if a given input string contains balanced parentheses. follow up: Modify the code to work for more brackets: {}, [].

etc

majority voting algorithm, http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html

If the counter is 0, we set the current candidate to e and we set the counter to 1. If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.

ing

given set of characters duplicates possible, and given dictionary (list of words). Find longest word from dictionary that can be made from given characters. How will you do it if ‘*’ (matches one wild character) is also included?
Access card system design
utf-8 byte stream verification and character extraction.

from http://www.glassdoor.com/Interview/An-array-contains-integers-with-the-property-that-a-particular-number-called-the-majority-element-appears-more-than-50-o-QTN_717526.htm Find the local minima in an array. A local minima is defined as a number whose left and right indices are greater than it in value. View Answers (4) An array contains integers with the property that a particular number, called the majority element, appears more than 50% of the time. Give an algo to find this majority number View Answers (4)

Also asked for maximum contiguous subarray problem In a given binary tree, find the number of elements that lie in a given range.

design
- online battleship game over the internet
- wearable device
- google image search

samsung strategy

useful macros

// swap
#define SWAP(a,b) do{int t=a;a=b;b=t;} while(0)

// ddebug
#define HDEBUG
#ifdef HDEBUG
#define hprint(fmt, args...) printf(fmt, ##args)
#else
#define hprint(fmt,args...)
#endif

multiple category : for small N, choose brute force, for large N choose approximation algorithm like greedy. .e.g, category 1, N<10 , category 2 N<100, category 3, N<1000
review 10/24 ToPrinter
- 500x500 dfs using recursive cause stackoverflow. plz use stack
- time is out. I was almost there. sigh!
reivew 12/5 maxModuleHeight
- find maximum height of matching grid, 30000 pieces, 4x4 grid given.
  - each grid have height, base = 1 + rand()%6, delta= base + rand()%3
review Feb PersonDogMatching
- N:5009, 10 sec time limit, dog has 4 properties(hair, age, height, weight, donation). person can adopt a dog satisfying its property range. finding max donation score by matching a dog to a person.
  - approach: 1. hash dog by weight. sort person by highest donation & lowest matcher. and from the start match a dog. if already taken, see already matching person can choose another dog. repeat!

Amazon

from http://www.workingus.com/v3/forums/topic/%EC%95%84%EB%A7%88%EC%A1%B4-%EC%84%9C%EC%9A%B8%EC%B1%84%EC%9A%A9/ Behavioral의 경우 어떻게 개인 능력을 뛰어 넘는 업무를 성공적으로 수행했는지, 가장 어려웠던 업무를 어떻게 수행했는지와 비슷한 부류의 질문을 모든 세션에서 집요하게 질문받았습니다. 그리고 처음 두 session에서는 algorithm coding 질문을 받았는데 주어진 시간 내에 코딩을 완료하고 추가 질문에 대답할 수 있을 정도의 난이도로, 그리 어려운 문제는 아니었던 것 같구요. 세번째 session에서는 object oriented design, 마지막에는 system design question을 받았는데 각 면접관의 담당 업무와 관련지어서 문제를 출제한 것 같았습니다.

Files

algorithm.org

Latest commit

History

algorithm.org

File metadata and controls

c++ specific

sort

priority_queue

pair

algorithm

max heap

greedy

graph

shortest path, Dijstra

dfs

floyd

stochastic

implementation

matrix rotation

linked list

sort

return the number of non-empty contiguous subarray whose sum is in range[a,b]

3sum

dp

lis (longest increasing subsequence)

binary search

questions

kth largest element

pemutation, combination

stack, queue

tree

segment tree

trie

math

bit

design

scalability

image search

CrackCode

etc

ing

samsung strategy

useful macros

Amazon