Tag Archives: Algorithm

Using bit manipulation to achieve operators

Posted on by
Reply

1）计算负数的逆元

def negative(n):
    return bit_add(~n, 1)

2）加法计算

def bit_add(a, b):
    b &= (2 ** 32 - 1)
    while b:
        tmp = a
        sum = tmp ^ b
        carry = (tmp & b) << 1
    return a

3）减法计算

def bit_sub(a, b):
    return bit_add(a, negative(b))

4）乘法计算

def bit_mul(a, b):
    result = 0

    while b:
        if b & 0x1:
            result = bit_add(result, a)
        b >>= 1
        a <<= 1

    return result

乘法模拟手工计算乘法的流程，将乘数b的二进制表示从左往右移动，当最低位为1时 (b & 0x1 == 1)，把被乘数a加到result中，同时将被乘数a向左移动一位。

5）除法计算

def bit_div(x, y):
    result = 0
    for i in range(32)[::-1]:
        if (x >> i) >= y:
            result += (1 << i)
            x -= (y << i)

    return result

考虑32位整数表示 (64位改一下 i 就可以了)。从最大的倍数开始遍历，如果被除数x >> i 大于除数y，说明该位商为1，将1<<i加到结果中，并缩小x。

Maximum XOR of Two Numbers in an Array

Posted on by
Reply

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8] 
Output: 28 
Explanation: The maximum result is 5 ^ 25 = 28.

这道题是在刷Explore的Trie tree topic里面看到的。首先一拿到题目，下意识的反应就是这道题没那么简单。最暴力的方法就是穷举遍历了，这样的话time complexity就会达到O(n^2)。

之后联想Trie tree和Binary之间的关系，可以画出上面这个图。这样问题就被转换为了找到最高的具有1节点的父节点，然后向下尽量找a^b = 1的分支 (我感觉我没有说清楚。。。)

之后看了讨论版里一位大佬的题解，真的是颇为震撼。他用了位运算的方法省去了很多不必要的步骤。 其中比较不好理解的是：

result += any(result ^ 1 ^ p in prefixes for p in prefixes)

为了理解这句话，首先我们得知道：a^b^a=b.

在这里result^1 == a^b, p = a, 所以result^1^p = b。如果在prefixes中有任意两个数a,b可以得到result^1, 而且这两个数a,b构成了previous result，那么新的result就可以是result += 1了，不然只能是result <<= 1(末位为0)。

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        result = 0
        
        for i in range(32)[::-1]:
            result <<= 1
            prefixes = {num >> i for num in nums}
            result += any(result ^ 1 ^ p in prefixes for p in prefixes)
            
        return result

Piles of Boxes

Posted on by
Reply

Several days ago, I’ve joined a Hackathon that sponsored by Facebook.

As qualifying people to this event, they hand out an easy algorithm question. Shortly, you need to calculate how less time to move a bunch of boxes in same heigh.

Here is a solution for reference:

import collections

def box(boxesInPiles):
    sortBoxes = collections.OrderedDict(sorted(collections.Counter(boxesInPiles).items()))
    count = 0
    for index, key in enumerate(sortBoxes):
        count += index * sortBoxes[key]
    return count

print(box([4, 5, 5, 2, 4]))

Haskell moment

Posted on by
Reply

Here are some Haskell code chunks, which both are simple recursion algorithms.

Quicksort is a sort of poster child for Haskell because everyone does it to showcase how elegant Haskell is.

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerSorted = quicksort [a | a <- xs, a <= x]
    biggerSoted = quicksort [a | a <- xs, a > x]
in smallerSorted ++ [x] ++ biggerSoted
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "List is empty!"
maximum' [x] = x
maximum' (x:xs) = (max x (maximum' xs))

replicate' :: Int  -> b -> [b]
replicate' n x
    | n <= 0 = []
    | otherwise = (x:(replicate' (n-1) x))

take' :: Int -> [a] -> [a]
take' n (x:xs)
    | n <= 0 = []
    | otherwise = x:(take' (n-1) xs)

reserve' :: [a] -> [a]
reserve' [] = []
reserve' (x:xs) = (reserve' xs) ++ [x]

Be a survivor of a disaster

Posted on by
Reply

这两天全靠红牛和咖啡续命了。

11月1号考完了这学期的第一门Final，在皇家展览馆考的。看了一下考场的座次表，三千人一起考试真的是美滋滋。考场的“服务人员”态度也特别好，看我手画Burndown Chart，就贴心的给我递过来了一把尺子 (可能是看我手画的太惨不忍睹了)。

因为这个暑假有四个月的时间，待在家里的话虽然可以轻松许多，但是还是觉得趁还可以实习，应该多锻炼一下自己。本来以为离放假还有一段时间，打算等考完试再去找实习，但是前两天算了一下日期，我发现再不找实习估计就来不及了，于是赶紧把简历投了起来。运气还不错的是，有好几个大佬都给了机会让我试一试。考完试的第二天，也就是11月2号，我约了微软的面试。正好打算考完试休息放松一天，于是2号就被我完全腾空用来面试了。

Continue reading →