Some algorithm hacks I collected over the internet
airekans / algohacks Goto Github PK
View Code? Open in Web Editor NEWSome algorithm hacks I collected over the internet
Some algorithm hacks I collected over the internet
Given a unsorted array of numbers, how can you find out the nth largest element in the array?
Here's an example session:
In[1]: [4, 5, 1, 7, 0, 9], 3
Out[1]: 5
C++ STL has implemented std::nth_element
, you can check its implementation. std::nth_element
has expected time cost of O(lg n).
Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?
Here's an example session:
In[1]: 1 1 1 1
Out[1]: Yes
In[2]: 10 20 30 40 50
Out[2]: No
In[3]: 1 7 2 6 4 4 3 5
Out[3]: Yes
You can check my answer in this gist.
You have a balance and a number of weights, and each is a certain power of three grams, e.g. 1g, 3g, 9g, 27g, etc. Note that you have only one for each of them. Given a thing with x grams, how can you place it and make the balance balanced. For example, given a book with 55 grams, how can you achieve it?
Sample:
Input: 55
Output: 55 + 3^3 = 3^4 + 3^0
Given a unsorted array of integers, including negatives, zero, and positives, can you design an algorithm to find out the least positive integer that is not in the array?
In: [-2, 0, 3, 1, 9]
Out: 2
Answer:
If the original array is permitted to change, then we can use an O(n) algorithm with O(1) space cost.
The algorithm is as follow:
def least_positive(nums):
length = len(nums)
is_valid = lambda e: 0 < e <= length
def swap(i, j):
nums[i], nums[j] = nums[j], nums[i]
i = 0
while i < length:
e = nums[i]
if is_valid(e) and nums[e - 1] != e:
swap(i, e - 1)
else:
i += 1
print nums
for i, e in enumerate(nums):
if not is_valid(e) or i != e - 1:
return i + 1
return length + 1
Given strings a, b and a set of strings, which are of equal size, find all possible ways to transform a to b. Every step in the transformation should be from s1 to s2, where s1 and s2 are almost the same except only one character difference.
For example,
In[1]: a = 'abc', b = 'afg', ['afc', 'bfg', 'cfc', 'cfg']
Out[1]: {['afc', 'cfc', 'cfg'], ['afc', 'cfc', 'cfg', 'bfg']}
Given a histogram, can you can find the max rectangle in it?
For example, given the following histogram:
[1, 2, 4, 2, 1]
#
#
###
#####
-----
The max rectangle is the one starting from 2, whose height is 2 and width is 3.
Note that each number in the input list is non-negative.
This problem has many solutions, please refer here
Here's the Python code that solve the problem with a stack. Its time cost is O(n).
def max_rect(histogram):
rect_stack = []
result = {"max_area": 0, "range": (-1, -1)}
for i, h in enumerate(histogram + [0]):
if len(rect_stack) == 0 or rect_stack[-1][0] < h:
rect_stack.append((h, i))
elif rect_stack[-1][0] > h:
while len(rect_stack) > 0 and rect_stack[-1][0] > h:
(last_h, last_i) = rect_stack.pop()
area = (i - last_i) * last_h
if result["max_area"] < area:
result["max_area"] = area
result["range"] = (last_i, i)
rect_stack.append((h, i))
return result
Design a min-stack, which can push, pop elements and get the minimal element in the stack all in O(1) time.
For example,
class MinStack:
def push(self, e):
pass
def pop(self):
pass
def min(self):
pass
stack = MinStack()
stack.push(1) # O(1) time
stack.pop(2) # O(1) time
print stack.min() # O(1) time
Given an array of integers, find out the largest set of consecutive numbers, O(n) time complexity.
For example,
In[1]: [6, 2, 4, 9, 3, 7]
Out[2]: [2, 3, 4]
Note that the result is a set, which means elements in it do not need to be in order.
Given an array a of certain type and 3 indexes i, j, k, where i <= j <= k
, can you rotate the array with less time and space cost, so that elements in [i, j)
are now after [j, k)
?
For example,
In[1]: [1, 2, 3, 4, 5], 0, 3, 5
Out[1]: [4, 5, 1, 2, 3]
In[2]: [4, 5, 6, 7, 8, 1], 0, 2, 6
Out[2]: [6, 7, 8, 1, 4, 5]
Given an array with n elements whose elements in [0, k) and [k, n) are sorted, try to write a program to merge the array back inplace with less memory.
For example,
In[1]: [1, 3, 6, 7, 2, 5, 8, 9], 4
Out[1]: [1, 2, 3, 5, 6, 7, 8, 9] # this is the same array as the input
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.