airekans / algohacks

Some algorithm hacks I collected over the internet

Algohacks

Some algorithm hacks I collected over the internet

algohacks's Issues

Hacking Spot Vol.2 Issue 2: Nth element

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).

Hacking Spot Vol.2 Issue 1: Square

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.

Hacking Spot Vol.1 Issue 3: Weights and Balance

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

Hacking Spot Vol.1 Issue 5: Least positive number

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

Possible Ways To Transform

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']}

Hacking Spot Vol.1 Issue 6: Max Rectangle in Histogram

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

Hacking Spot Vol.1 Issue 4: Min-stack

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

Largest Set of Consecutive Number

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.

Rotate an array

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]

Merge Array Inplace

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