Algorithms

It gains the name "exclusive or" because the meaning of "or" is ambiguous when both operands are true; the exclusive or operator excludes that case. This is sometimes thought of as "one or the other but not both". This could be written as "A or B, but not, A and B".

More generally, XOR is true only when an odd number of inputs are true.

A chain of XORs—

a XOR b XOR c XOR d (and so on)

—is true whenever an odd number of the inputs are true and is false whenever an even number of inputs are true.

Queue : enQueue + deQueue

Priority queue = Queue + deleteMin or deleteMax in const time

https://habrahabr.ru/post/268261/ Sorting

http://www.geeksforgeeks.org/fundamentals-of-algorithms/

https://www.codementor.io/learn-programming/graph-algorithms-interview-questions

https://blog.clevertap.com/how-to-remove-duplicates-in-large-datasets/

http://www.grokit.ca/cnt/KnapsackProblem/

https://tekmarathon.com/

http://ticki.github.io/blog/skip-lists-done-right/

Time complexity Cheat Sheet

Advantages of BST over Hash Table

Hash Table supports following operations in Θ(1) time.

1) Search

2) Insert

3) Delete

The time complexity of above operations in a self-balancing Binary Search Tree (BST) (like Red-Black Tree, AVL Tree, Splay Tree, etc) is O(Logn).

So Hash Table seems to beating BST in all common operations. When should we prefer BST over Hash Tables, what are advantages. Following are some important points in favor of BSTs.

1. We can get all keys in sorted order by just doing Inorder Traversal of BST. This is not a natural operation in Hash Tables and requires extra efforts.
2. Doing order statistics, finding closest lower and greater elements, doing range queries are easy to do with BSTs. Like sorting, these operations are not a natural operation with Hash Tables.
3. BSTs are easy to implement compared to hashing, we can easily implement our own customized BST. To implement Hashing, we generally rely on libraries provided by programming languages.
4. With BSTs, all operations are guaranteed to work in O(Logn) time. But with Hashing, Θ(1) is average time and some particular operations may be costly, especially when table resizing happens.

https://github.com/thundergolfer/interview-with-python Python

https://github.com/thejameskyle/itsy-bitsy-data-structures JavaScript

https://www.youtube.com/results?search_query=cube+drone

https://codevillage.wordpress.com/

https://sites.google.com/site/indy256/

http://www.programming-algorithms.net/

https://github.com/MauriceGit/Advanced_Algorithms

http://www.programcreek.com/2012/12/leetcode-solution-for-binary-tree-preorder-traversal-in-java/

https://github.com/ramswaroop/Algorithms-and-Data-Structures-in-Java

https://sites.google.com/site/indy256/algo/kth_order_statistics

https://www.quora.com/What-data-structures-support-insertion-deletion-and-selection-of-a-random-element-with-a-math-O-1-math-time-complexity-bound

http://www.drdobbs.com/architecture-and-design/the-rete-matching-algorithm/184405218

http://www.cs.jhu.edu/~langmea/resources/lecture_notes/tries_and_suffix_tries.pdf

https://en.wikipedia.org/wiki/External_sorting

For sorting 900 megabytes of data using only 100 megabytes of RAM:

1. Read 100 MB of the data in main memory and sort by some conventional method, like quicksort.
2. Write the sorted data to disk.
3. Repeat steps 1 and 2 until all of the data is in sorted 100 MB chunks (there are 900MB / 100MB = 9 chunks), which now need to be merged into one single output file.
4. Read the first 10 MB (= 100MB / (9 chunks + 1)) of each sorted chunk into input buffers in main memory and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)
5. Perform a 9-way merge and store the result in the output buffer. Whenever the output buffer fills, write it to the final sorted file and empty it. Whenever any of the 9 input buffers empties, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available. This is the key step that makes external merge sort work externally -- because the merge algorithm only makes one pass sequentially through each of the chunks, each chunk does not have to be loaded completely; rather, sequential parts of the chunk can be loaded as needed.

External Sort

http://preshing.com/20121025/heres-some-working-code-to-sort-one-million-8-digit-numbers-in-1mb-of-ram

http://preshing.com/20121026/1mb-sorting-explained

http://preshing.com/20121105/arithmetic-coding-and-the-1mb-sorting-problem

http://preshing.com/20121105/arithmetic-encoding-using-fixed-point-math/

http://alex.dzyoba.com/programming/external-sort.html

How to merge k sorted input lists

Using heap:

- Build a min-heap h of the k lists, using the first element as the key.
- While any of the lists is non-empty:

- - - Let i = find-min(h). <--- O(logK)
    - Output the first element of list i and remove it from its list.
    - Re-heapify h. <-- O(logK)

All together the complexity is O(n*logK)

merge arrays in O(nk*Logk) time using Min Heap.

1. Create an output array of size n*k.

2. Create a min heap of size k and insert 1st element in all the arrays into a the heap

3. Repeat following steps n*k times.

a) Get minimum element from heap (minimum is always at root) and store it in output array.

b) Replace heap root with next element from the array from which the element is extracted. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.

Merge 2 sorted arrays

https://www.youtube.com/watch?v=zYrlYlwkbLo

http://www.programcreek.com/2012/12/leetcode-merge-sorted-array-java/

https://tekmarathon.com/2013/03/23/arrays-algos-algorithm-to-merge-two-sorted-arrays-without-additional-array/

https://changhaz.wordpress.com/2014/04/16/merge-k-sorted-lists-multiple-solutions/

http://www.programcreek.com/2014/05/merge-k-sorted-arrays-in-java/

Heap

http://algosaur.us/data-structures-basics/ heap

http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf

http://habrahabr.ru/post/263765/ heap in python

def insert(elem): global currSize index = len(heap) heap.append(elem) currSize += 1 par = parent(index) flag = 0 while flag != 1: if index == 1: #we have reached the root of the heap flag = 1 elif heap[par] > elem: #if parent index is larger than index of elem, then elem has now been inserted into the right place flag = 1 else: #swaps the parent and the index itself swap(par, index) index = par par = parent(index) print heap

http://habrahabr.ru/post/246105/

http://paratey.com/posts/binary-heaps-and-priority-queues/

http://en.wikipedia.org/wiki/Binary_heap HEAP

http://www.cs.cmu.edu/~adamchik/15-121/lectures/Binary%20Heaps/heaps.html

Heapsort runs in two steps. Given an array of data, first, we build a heap and then turn it into a sorted list by calling deleteMin. The running time of the algorithm is O(n log n).

A complete binary tree can be uniquely represented by storing its level order traversal in an array.

Find largest 1 million numbers in 1 billion numbers

http://en.wikipedia.org/wiki/Partial_sorting

https://tproger.ru/problems/find-the-smallest-one-million-numbers-in-one-billion-numbers/

http://stackoverflow.com/questions/2933758/priority-queue-with-limited-space-looking-for-a-good-algorithm

1) Sort and take 1st million O(n log n)

2) Create Min Heap with first million

For each remaining number insert into mean heap and delete the minimum value from heap

O(n log m) where m = 1 million

3) Selection rank algo: O(n) https://en.wikipedia.org/wiki/Quickselect

Pick a random element in the array and use it as a ‘pivot’. Move all elements smaller than that element to one side of the array, and all elements larger to the other side.

If there are exactly i elements on the right, then you just find the smallest element on that side.

Otherwise, if the right side is bigger than i, repeat the algorithm on the right.

If the right side is smaller than i, repeat the algorithm on the left for i – right.size().

TOP K elements in stream

http://en.wikipedia.org/wiki/Partial_sorting

https://www.reddit.com/r/algorithms/comments/3vxysb/when_we_partition_an_array_like_in_quickselect/

Heap-based solution

Heaps admit a simple single-pass partial sort when k is fixed: insert the first k elements of the input into a max-heap. Then make one pass over the remaining elements, add each to the heap in turn, and remove the largest element. Each insertion operation takes O(log k) time, resulting inO(n log k) time overall; this algorithm is practical for small values of k and in online settings.^[1]

Solution by partitioning selection

A further relaxation requiring only a list of the k smallest elements, but without requiring that these be ordered, makes the problem equivalent to partition-based selection; the original partial sorting problem can be solved by such a selection algorithm to obtain an array where the first k elements are the k smallest, and sorting these, at a total cost of O(n + k log k) operations. A popular choice to implement this algorithm scheme is to combine quickselect and quicksort; the result is sometimes called "quickselsort".^[1]

http://habrahabr.ru/post/167177/ Поиск часто встречающихся элементов в массиве

Kth element in linear time quickSelect

http://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html linear time

http://functionspace.com/articles/19/Median-of-Medians

http://austinrochford.com/posts/2013-10-28-median-of-medians.html

http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/

http://avva.livejournal.com/2819992.html

select top 10 or median or .. http://en.wikipedia.org/wiki/Selection_algorithm

In quicksort, there is a subprocedure called partition that can, in linear time, group a list (ranging from indices left to right) into two parts, those less than a certain element, and those greater than or equal to the element. Here is pseudocode that performs a partition about the element list[pivotIndex]:

function partition(list, left, right, pivotIndex)

pivotValue := list[pivotIndex]

swap list[pivotIndex] and list[right] // Move pivot to end

storeIndex := left

for i from left to right-1

if list[i] < pivotValue swap list[storeIndex] and list[i]

increment storeIndex swap list[right] and list[storeIndex]

// Move pivot to its final place

return storeIndex

function select(list, left, right, n) loop if left = right return list[left] pivotIndex := ... // select pivotIndex between left and right pivotIndex := partition(list, left, right, pivotIndex) if n = pivotIndex return list[n] else if n < pivotIndex right := pivotIndex - 1 else left := pivotIndex + 1

it's basically a quicksort in which one only recurses down one side of the partition.

-- Find the kth element of array A FIND(A, k) = pivot = find_median(A) -- O(n) operation index = partition(A, pivot) -- O(n) partition into lower/higher than pivot, return the new index of the pivot if k < index: FIND(A[:index], k) -- Approx. n/2 sized else if k > index: FIND(A[index:], k - index) -- Approx. n/2 sized else: return pivot

Where find_median and partition are linear operations across the array, each iteration is θ(n) time, and recurses on one problem of approx. n/2 size:

T(n) = T(n/2) + θ(n) Case 3 Master Theorem: a = 1, b = 2, log_2 1 = 0, f(n) = n θ(n) = Ω(n^0 = 1) Show regularity: af(n/b) <= kf(n), k < 1 n/2 <= kn, k <= 0.5, condition satisfied T(n) = θ(n)

The distinction between the deterministic and random cases are whether you select the median, or a random index. The worst case analysis is indeed θ(n^2), but the average case is so overwhelmingly common that one should observe the worst case is, for a reasonably large n, less likely to occur than a cosmic ray striking the computer system performing the algorithm and corrupting a bit in memory; you can consider random-select pivot quicksorts to be effectively θ(n) too.

http://me.dt.in.th/page/Quicksort/ - visualization

http://www.reddit.com/r/Python/comments/yymys/finding_the_top_k_items_in_a_list_efficiently/

Finding the top K items can be done in O(nlogk) time, which is much faster than O(nlogn), using a heap (wikipedia) or a priority queue.

The strategy is to go through the list once, and as you go, keep a list of the top k elements that you found so far. To do this efficiently, you have to always know the smallest element in this top-k, so you can possibly replace it with one that is larger - heap structure

http://stackoverflow.com/questions/3260653/algorithm-to-find-top-10-search-terms TOP10

http://stackoverflow.com/questions/3532556/fixed-size-collection-that-keeps-top-n-values

http://stackoverflow.com/questions/1151015/please-identify-this-algorithm-probabilistic-top-k-elements-in-a-data-stream

http://www.notjustrandom.com/2009/11/13/finding-frequent-items-in-a-data-stream/

http://stackoverflow.com/questions/4084495/find-top-n-elements-in-an-array

http://en.wikipedia.org/wiki/Selection_algorithm k-th element in array O(n)

http://stevehanov.ca/blog/index.php?id=122

http://stackoverflow.com/questions/3260653/algorithm-to-find-top-10-search-terms/

http://efreedom.com/Question/1-185697/Efficient-Way-Find-Top-Frequent-Words-Big-Word-Sequence

http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=799

public static <T extends Comparable<T>> List<T> leastN(Collection<T> input, int n) {

assert n > 0; PriorityQueue<T> pq = new PriorityQueue<>(Collections.reverseOrder());

for (T t : input) {

if (pq.size() < n) {

pq.add(t);

} else if (pq.peek().compareTo(t) > 0) {

pq.poll();

pq.add(t);

}

List<T> list = new ArrayList<>(pq);

Collections.sort(list);

return list;

}

https://vimeo.com/171927600 Alexandresku

http://web.engr.illinois.edu/~jeffe/teaching/algorithms/

https://www.khanacademy.org/computing/computer-science/algorithms

https://habrahabr.ru/company/wunderfund/blog/277143/

http://courses.csail.mit.edu/6.006/spring11/notes.shtml

http://algorithmsjs.org/

https://github.com/aalhour/C-Sharp-Algorithms

http://e-maxx.ru/index.php

http://www.sonarlearning.co.uk/coursepage.php?topic=university&course=uni-mit-advanced-data-structures

transducers are composable and efficient data transformation functions which doesn’t create intermediate collections.

http://algs4.cs.princeton.edu/home/ Book "Algorithms" by Robert Sedgewick and Kevin Wayne

http://cstheory.stackexchange.com/questions/19759/core-algorithms-deployed/19773#19773

http://habrahabr.ru/hub/algorithms/

https://news.ycombinator.com/item?id=9637046 metropolis hasting

http://www.quora.com/Which-is-the-best-algorithm-to-merge-k-ordered-lists/

http://blog.notdot.net/tag/damn-cool-algorithms

Print matrix in spiral order

http://www.technicalinterviewquestions.net/2009/03/print-2d-array-matrix-spiral-order.html

// prints the top and right shells of the matrix void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2){ int i = 0, j = 0; // print the row for(i = x1; i<=x2; i++) { printf("%d,", a[y1][i]); } //print the column for(j = y1 + 1; j <= y2; j++) { printf("%d,", a[j][x2]); } // see if we have more cells left if(x2-x1 > 0) { // 'recursively' call the function to print the bottom-left layer print_layer_bottom_left(a, x1, y1 + 1, x2-1, y2); } } // prints the bottom and left shells of the matrix void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2){ int i = 0, j = 0; //print the row of the matrix in reverse for(i = x2; i>=x1; i--){ printf("%d,", a[y2][i]); } // print the last column of the matrix in reverse for(j = y2 - 1; j >= y1; j--) { printf("%d,", a[j][x1]); } if(x2-x1 > 0) { // 'recursively' call the function to print the top-right layer print_layer_top_right(a, x1+1, y1, x2, y2-1); } }

Find peak elements in array

public static int findPeak(int[] array, int start, int end) { int index = start + (end - start) / 2; if (index - 1 >= 0 && array[index] < array[index - 1]) { return findPeak(array, start, index - 1); } else if (index + 1 <= array.length - 1 && array[index] < array[index + 1]) { return findPeak(array, index + 1, end); } else { return array[index]; }}

static int findPeakUtil(int arr[], int low, int high, int n)

{

int mid = low + (high - low)/2; /* (low + high)/2 */

// Compare middle element with its neighbours

if ((mid == 0 || arr[mid-1] <= arr[mid]) && (mid == n-1 || arr[mid+1] <= arr[mid]))

return mid;

// If middle element is not peak and its left neighbor is

// greater than it,then left half must have a peak element

else if (mid > 0 && arr[mid-1] > arr[mid])

return findPeakUtil(arr, low, (mid -1), n);

// If middle element is not peak and its right neighbor

// is greater than it, then right half must have a peak element

else return findPeakUtil(arr, (mid + 1), high, n);

}

// A wrapper over recursive function findPeakUtil()

static int findPeak(int arr[], int n)

{

return findPeakUtil(arr, 0, n-1, n);

}

Most frequent element in array:

Solution #1: sort + scan ; time complexity: nlog(n) space complexity: o(1)

Solution #2: extra hash time complexity: O(n) space complexity: o(n)

Find majority element (which exist at least in half of array) in linear time

import random items = [1, 2, 3, 4, 5, 5, 5, 5, 5 ] # shuffle the items random.shuffle(items) print("shuffled items: ", items) majority_elem = items[0] count = 1 for i in range(1,len(items)): if items[i] == majority_elem: count += 1 else: count -= 1 if count == 0: majority_elem = items[i] count = 1 print("majority element : %d" % majority_elem )

public int majorityElement(int[] nums) { int result = 0, count = 0; for(int i = 0; i<nums.length; i++ ) { if(count == 0){ result = nums[ i ]; count = 1; }else if(result == nums[i]){ count++; }else{ count--; } } return result;}

For every element in A find # of elements immediately before current element j where A[j]<A[i]

Following solution is O(n*n)

func( int A[], int n){

int i,j, Answer[n]

for (i=0; i<n; i++){

j=1;

while j<i && A[i]>>A[i-j]

j = j+1

Answer[i]=j

}

return Answer;

}

O(n) solution:

calculate the closest element before current where value > current

func( int A[], int n){

stack *D=CreateStack();

int maxVal;

for (i=0; i<n; i++){

while stackInNotEmpty(D) {

if A[i] > A[top(D])

pop[D]

}

if stackIsEmpty(D) max_val=-1

else max_val=top(D)

S[i]=1-max_val

push(D,i)

}

return S;

Count the frequency of element in sorted array B in sub-linear time:

Let M be the number of unique items in array. The algorithm loops M times to count frequency for each unique item. Each loop runs in O(log N) time. Thus, the overall time complexity is O(M*logN).

printFrequency(B){ // B is sorted array

country = B[0]; // fist element in array

index = 0;

while(index < N){

freq = count_freq(B,country); //log(N) STL C++ equal_range() !

index += freq;

print country + " "+ freq;

};

http://datagenetics.com/blog/january42016/index.html Hamming codes

http://jasonpark.me/AlgorithmVisualizer/

How many ways from left-down corner to right-up corner on chessboard?

The number of ways to get to cell (x, y) is the sum of the ways to get to the cell (x-1, y) and the cell (x, y-1). However, the number of ways to reach the cell (x-1, y) is the sum of the number of ways to the cell (x-2, y) and (x-1, y-1). As we can see, we are solving a reduced version of the same problem! Thus we have a recurrence relation.

The base case is any cell on the left border or bottom border. There is only one way to reach the cell by either going only up or only going right.

int paths(int n,int m){

if (n == 1 || m == 1) {

return 1;

}

return paths(n - 1, m) + paths(n, m - 1);

}

http://opendatastructures.org/

http://www.thecshandbook.com/

http://bigocheatsheet.com/

https://oj.leetcode.com/problems/

http://www.geekviewpoint.com/

https://github.com/prakhar1989/Algorithms

http://bravenewgeek.com/tag/algorithms-2/

http://habrahabr.ru/company/spbau/blog/254093/

http://en.wikibooks.org/wiki/Algorithm_Implementation

http://habrahabr.ru/company/yandex/blog/208716/

http://algpedia.dcc.ufrj.br/

http://habrahabr.ru/post/243819/

https://github.com/andreis/interview

http://javarevisited.blogspot.com/2015/01/top-20-string-coding-interview-question-programming-interview.html

http://www.reddit.com/r/programming/comments/2tcan3/questions_you_should_be_asking_your_interviewers/

http://ieeeghn.org/wiki/index.php/History_of_Lossless_Data_Compression_Algorithms

http://mattmahoney.net/dc/dce.html compression

http://www.cleveralgorithms.com/nature-inspired/index.html

http://bhavin.directi.com/to-trie-or-not-to-trie-a-comparison-of-efficient-data-structures/

http://www.bfilipek.com/2014/12/top-5-beautiful-c-std-algorithms.html

Visualization

http://visualgo.net/

http://conceptviz.github.io/#/e30=

http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

http://www.algomation.com/ visualization of algo

http://rain.ifmo.ru/cat/view.php/vis

http://will.thimbleby.net/algorithms/doku.php

http://www.sorting-algorithms.com/

http://queue.acm.org/detail.cfm?ref=rss&id=2534976 Real-time Algo

image processing: http://habrahabr.ru/post/206264/ JPEG

http://bigocheatsheet.com/ Algo complexity

http://habrahabr.ru/post/188010/ Algo complexity (ru)

http://opendatastructures.org/

http://people.cs.vt.edu/~shaffer/Book/ C++ and Java version

http://cstheory.stackexchange.com/questions/19759/core-algorithms-deployed/19773#19773

http://projectmona.com/bits-of-brilliance-session-five/

http://www.cprogramming.com/algorithms-and-data-structures.html

http://bigocheatsheet.com/

http://jeremykun.com/primers/

http://habrahabr.ru/post/120343/ Greedy algorithms

https://sites.google.com/site/indy256/algo/cutpoints Java

http://igushev.com/implementations/

http://theck01.github.io/offbrand_lib/ plain C datastructures

http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book?

http://www.freetechbooks.com/

http://www.youtube.com/watch?v=jKBwGlYb13w Awesome Big Data Algorithms

http://interactivepython.org/courselib/static/pythonds/index.html

http://www.jjj.de/fxt/fxtpage.html#fxtbook

http://boso.herokuapp.com/ Best Of StackOverflow

http://www.keithschwarz.com/interesting/

http://news.ycombinator.com/item?id=4957591

http://www.infoq.com/presentations/Data-Structures

http://polycode.livejournal.com/29426.html Microsoft Interview

Linked List

Find the merging point of 2 linked lists

1) find length of both lists and calculate the diff d

2) make d steps in longest list

3) traverse both list in parallel until links to next node math

http://en.wikipedia.org/wiki/Cycle_detection

http://en.wikipedia.org/wiki/Cycle_detection_(graph_theory)#Cycle_detection

http://twistedoakstudios.com/blog/Post3280_intersecting-linked-lists-faster

http://codingfreak.blogspot.com/2012/09/detecting-loop-in-singly-linked-list_22.html

http://news.ycombinator.com/item?id=4783301

http://www.rsdn.ru/article/alg/adt/adt.xml

http://www.youtube.com/user/A9Videos/videos?flow=grid&view=1

http://www.daemonology.net/blog/2012-10-17-software-development-final-answers-part-1.html

http://codingplayground.blogspot.co.uk/2012/08/a-collection-of-algos-and-data.html

http://en.wikipedia.org/wiki/List_of_algorithms

http://nord.org.ua/course/2009/algo/

http://www.acmsolver.org/?p=1146

http://kmike.ru/python-data-structures/

https://kunigami.wordpress.com/2012/09/25/skip-lists-in-python/

http://algoritmia.codeplex.com/ Python 3.1

http://www.cs.sunysb.edu/~algorith/video-lectures/# Sienna Algorithms

http://www.informit.com/articles/printerfriendly.aspx?p=1407357&rll=1

http://dl.dropbox.com/u/10497693/Library/index.html

http://www.keithschwarz.com/interesting/

https://github.com/attractivechaos/klib#readme

http://attractivechaos.github.com/plb/

https://github.com/attractivechaos/benchmarks/blob/master/lock/lock_test.c

http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/

http://www.swageroo.com/wordpress/little-known-awesome-algorithms-fenwick-range-trees-rapidly-find-cumulative-frequency-sums/

http://stevehanov.ca/blog/index.php?id=120

http://dl.dropbox.com/u/10497693/Library/Computer%20Science/index.html

http://www.algorithmist.com/index.php/Main_Page

http://xlinux.nist.gov/dads/

http://stackoverflow.com/questions/500607/what-are-the-lesser-known-but-cool-data-structures

http://sharpc.livejournal.com/67583.html

http://www.cs.bell-labs.com/cm/cs/pearls/

http://habrahabr.ru/blogs/algorithm/

http://rosettacode.org/wiki/Category:Programming_Tasks

http://algowiki.net/wiki/index.php?title=Special:Allpages

http://www.dmoz.org/Computers/Algorithms/

http://www.e-booksdirectory.com/programming.php#algorithms

http://pleac.sourceforge.net/

http://rosettacode.org/wiki/Help:Similar_Sites

http://aduni.org/

http://mgccl.com/2008/04/06/aduni-videos-now-on-google-video

http://www.ihas1337code.com/

http://news.ycombinator.com/item?id=1944913

http://en.wikipedia.org/wiki/Secretary_problem

http://en.wikipedia.org/wiki/Viterbi_algorithm

http://stevehanov.ca/blog/index.php?id=130 data structures for spatial search

Cache

http://en.wikipedia.org/wiki/Cache_algorithms

http://habrahabr.ru/blogs/development/136758/#habracut

https://habrahabr.ru/company/surfingbird/blog/306252/

http://www.sinbadsoft.com/blog/a-lru-cache-implementation/ C#

http://www.reddit.com/r/programming/comments/1n39ld/a_lru_cache_implementation/

https://github.com/fish-shell/fish-shell/blob/master/lru.h

combination of fixed size hashmap<key,val)+linked list<keys> sorted by access time:

Then key which already present in cache is accessed it should be moved at the end of list.

How to do it fast without traversing the list O(1)? We can keep list::iterator to each list element

inside hash map hashmap<key, <Val,list::iterator>

Another approach: instead linked list have 2 maps: <key,timestamp> and <timestamp,key>

If hashmap is full then to add the new entry

a) remove first (oldest key) element from list and from hashmap

b) add new key to beginning of the list

http://stackoverflow.com/questions/2057424/lru-implementation-in-production-code

http://stackoverflow.com/questions/2504178/lru-cache-design

http://stackoverflow.com/questions/3639744/least-recently-used-cache-using-c

http://www.bottlenose.demon.co.uk/article/lru.htm

http://launchpadlibrarian.net/76289845/mct.html

http://code.google.com/p/lru-cache-cpp/ BEST

http://code.google.com/p/lruc/

http://tactothen.blogbus.com/logs/42021081.html

http://blackcat.ca/docs/lru_cache/

http://pocoproject.org/docs/

http://stackoverflow.com/questions/6398902/best-way-to-implement-lru-cache Java

Java already provides this for us in the form of a LinkedHashMap! It even provides an overridable eviction policy method (removeEldestEntry docs). The only catch is that by default the linked list order is the insertion order, not access. However one of the constructor exposes an option use the access order instead (docs).

Without further ado:

import java.util.LinkedHashMap;import java.util.Map;public LRUCache<K, V> extends LinkedHashMap<K, V> { private int cacheSize; public LRUCache(int cacheSize) { super(16, 0.75, true); this.cacheSize = cacheSize; } protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() >= cacheSize; } }

If you want a LRU cache, the simplest in Java is LinkedHashMap. The default behaviour is FIFO however you can changes it to "access order" which makes it a LRU cache.

public static <K,V> Map<K,V> lruCache(final int maxSize) { return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; } };}

Java LRU Cache implementation

October 5, 2014 Alain Defrance Algorithms and data structures, Java algorithm, data structure, LRU Cache

This one is a very known algorithm that is often taken as example for students but it’s an interesting one.

If someone ask you to implement a LRU (Least Recently Used) Cache. How would you do it?

Since it’s a cache you need to guarantee a O(1) for reading and writing. For a fast access, hash tables are very often the right data structure so we can consider it, but we need to keep the order and hash tables cannot do that.

An LRU cache is also a FIFO (First In First Out) data structure, a queue looks very adapted too but we loose the O(1) access time.

A good approach is to use both:

An hash table for the O(1) lookup time
A queue to keep the order

The only one problem is that queues are very effective for enqueue and dequeue but very slow for random access, and since each hit has to reorder the queue, those operations would lead to a O(n) lookup time for rearranging the queue every time we access the cache.

The good strategy is to keep this approach but use a double linked list instead of a queue because:

Very easy to implement a queue with it
Still slow for random access but easy to move a given node to the head and it’s all we need

Let’s focus on the implementation. We need first to define a node that contains the pair key/value:

Your LRUCache definition:

class Node {

int key;

int data;

Node previous;

Node next;

}

Same thing for the remove:

Then we write an add method that append the node as the head:

private void remove(Node node) {

// Nothing to do

if (this.head == null || null == node) {

return;

}

// The only one item

if (this.head == this.end && this.head == node) {

this.head = null;

this.end = null;

return;

}

// Remove from head

if (node == this.head) {

this.head.next.previous = null;

this.head = this.head.next;

return;

}

// Remove from end

if (node == this.end) {

this.end.previous.next = null;

this.end = this.end.previous;

return;

}

// Remove in the middle

node.previous.next = node.next;

node.next.previous = node.previous;

}

private void add(Node node) {

// Reset position

node.next = null;

node.previous = null;

// First element

if (null == this.head) {

this.head = node;

this.end = node;

return;

}

// Existing element

this.head.previous = node;

node.next = this.head;

this.head = node;

}

class LRUCache {

private int capacity;

private Map<Integer, Node> data;

private Node head;

private Node end;

public LRUCache(int capacity) {

this.capacity = capacity;

this.data = new HashMap<>();

}

Two methods that help to move a node to the head (for hits), and a remove last that cleanup the oldest item:

private void moveFirst(Node node) {

this.remove(node);

this.add(node);

}

private void removeLast() {

this.remove(this.end);

}

The linked list is partially implemented (enough for our needs).

The LRU get method simply retrieve the key and move in to the head in the list.

Last method, the set method generates an hit to move the accessed element to the head.

Like the get method, the set method deals with both hash table and linked list:

public void set(int key, int value) {

// Existing slot

if (this.data.containsKey(key)) {

Node node = this.data.get(key);

this.moveFirst(node);

node.data = value;

return;

}

// Out of capacity, cleaning the oldest slot

if (this.data.size() >= this.capacity) {

int id = this.end.key;

this.removeLast();

this.data.remove(id);

}

// New slot

Node node = new Node();

node.key = key;

node.data = value;

this.add(node);

this.data.put(key, node);

}

public int get(int key) {

// Existing key

if (this.data.containsKey(key)) {

// Move to first place

Node node = this.data.get(key);

this.moveFirst(node);

// Return the value

return node.data;

}

// Not found

return -1;

}

Data Structures

http://bhavin.directi.com/to-trie-or-not-to-trie-a-comparison-of-efficient-data-structures/

http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_skip.aspx Skip List

Memoization

http://programminggenin.blogspot.com/2013/01/memoization-in-c.html

http://slackito.com/2011/03/17/automatic-memoization-in-cplusplus0x/

Parsing, Code generation

http://softwaremaniacs.org/blog/2010/09/18/ijson/

http://spb-archlinux.ru/2009/funcparserlib/Tutorial

http://kmkeen.com/generators/

Sorting

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

http://www.umbrant.com/blog/2011/external_sorting.html

http://rosettacode.org/wiki/Sorting_algorithms

http://habrahabr.ru/blogs/algorithm/133303/ TimSort

http://kristoffer.vinther.name/academia/thesis/

http://stxxl.sourceforge.net/

http://habrahabr.ru/post/188012/ SORTING

http://stackoverflow.com/questions/7153659/find-an-integer-not-among-four-billion-given-ones

http://www.reddit.com/r/programming/comments/grrrr/efficiently_sorting_datasets_bigger_than_memory_c/

http://hackerne.ws/item?id=2621306

http://theory.stanford.edu/~amitp/rants/c++-vs-c/

Radix Sorting

http://attractivechaos.wordpress.com/2012/06/10/an-update-on-radix-sort/

http://austingwalters.com/radix-sort-in-c/

http://code.google.com/p/back40computing/wiki/RadixSorting

There are 2 sets. Find the all common elements. Find elements which only in 1st set, or only in 2nd set.

There are several ways to do it. Sort both sets: n log(n) + m log(m) Then look up using binary search: log m

You can put the numbers of one array in a hash table for O(n) and then look them up in O(1) while iterating through the other array

Sorting both lists and then traversing them in order is not the only efficient way to do it. Others are:

1. Put one of the lists (probably the smaller one) into a hash table and traverse the other list in the order given (not sorted order) and check the hash table.
2. Sort one list (probably the smaller one) and then traverse the other in its original order and do a binary search in the sorted list.
3. Same as previous, but put one list into a binary search tree or other tree data structure instead of using binary search.

These methods may actually be faster than sorting both lists.

The two lists have sizes A and B, then sorting both and merging them is O(A log A + B log B). But #2 above would be O(A log A + B log A). If B is a lot larger than A, then B log A is smaller than B log B.

Convert unfair coin to fair coin

http://www.reddit.com/r/programming/comments/lisma/how_to_turn_a_biased_coin_into_a_fair_coin/

Text search

Find all the files in a directory that contain any of the strings present in another file

while read line

for i in *

grep $line $i 1>/dev/null

if [ $? -le 0 ]

then

echo $i

done

done < checkfile