It's never too late to learn to be a master
Given an array, there is a popular problem to search the minimum value in a range [a, b]. This is called Range Minimum Query. This post describes a method to solve the range minimum query problem using Segment Tree.
The basic idea of a Segment tree is as follows:
Given an array A with size n: the index of the array looks like this [0, 1, 2, …., n-1],
Given a weighted graph G Given a weighted graph G (V,E), =(V,E), and a source vertex s, find the minimum weighted path from s to every other vertex in G
Unweighted graph
If the graph is unweighted, we can solve this problem using Bread First Search.
|
1 2 3 4 5 |
For each vertex, keep track of Whether we have visited it ( Whether we have visited it (known) Its distance from the start vertex (dv) Its predecessor vertex along the shortest Its predecessor vertex along the shortest path from the start vertex (pv) |
Weighted Graph
For Weighted Graph, we solve this problem use Dijkstra’s algorithm.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
S: set of vertices for which the shortest path length from s is known. Invariant: for v in S, dist[v] is the length of the shortest path from s to v. Initialize S to s, dist[s] to 0, dist[v] to for all other v Repeat until S contains all vertices connected to s find e with v in S and w in S’ that minimizes dist[v] + e.weight() relax along that edge • add w to S |
shortest path between all pairs of vertices
Given G(V,E), find a shortest path between all pairs of vertices.
Solutions: (brute -force) Solve Single Source Shortest Path for each vertex as source.
[Read More...]Given an array and a value, remove all instances of that value in place and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
Example:
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.
Hint:
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note:
You may assume that you have an infinite number of each kind of coin.
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
|
1 2 3 4 |
1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 |
The solution is the Pandit’s algorithm
1 Pandit’s algorithm
The article in Wikipedia describes the algorithm invented by Narayana Pandit to changes the list in-place to generate the next permutation given a list or Array A.
Selection sort is one of the simplest sorting algorithms. This tutorial described how to implement selection sort algorithm in python.
The basic idea of selection sort is that it repeatedly select the smallest item in list A[i+1:], and exchange it with the item at A[i].
It works as follows:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
def sort(A): i = 0 j = i + 1 #find the smallest item in A[i+1:] min = i while i < len(A): print 'i= {0}, A is {1}'.format(i, A) j = i + 1 while j < len(A): if A[j] < A[i]: min = j j += 1 swap(A, i, min) print 'After {0}th round, A is {1}'.format(i, A) i += 1 def swap(A, i, j): temp = A[i] A[i] = A[j] A[j] = temp A = [2,4,6,1,3,5,7] sort(A) |
Problem:
Given an input text and an a dictionary, find all occurrences of all words in the input text.
Example:
|
1 2 3 |
dictionary {he, she, hers, his} string T: shershishers All the valid words in the string are: she, he, her, hers, she, he, her, hers |
We can solve this problem using KMP algorithm, but it is not efficient.
The solution is Aho-Corasick automation (AC automaton), which is one of the most famous string pattern match algorithms. See https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm for an introduction.
By using AC automaton, we can solve the problem in O(n + m + z), where n is the total length of the words in the dictionary, m is the length of the string T,
[Read More...]
Rss Feeds