Author: 逸飞

Python metaclass 的原理和应用

元编程(meta programming)是一项很神奇的能力,可以通过代码在运行时动态生成代码。元类(meta classes)是 Python 提供的一种元编程的能力。在 Python 中,类也是一种对象,那么类这种对象就是元类的实例,所以我们可以在运行时通过实例化元类动态生成类。

使用 type “函数”

首先我们来了解一下 type,type 可以作为函数使用,用来获得对象的类型:

>>> class Foo:
...     pass
>>> obj = Foo()
>>> obj.__class__
<class "__main__.Foo">
>>> type(obj)
<class "__main__.Foo">
>>> obj.__class__ is type(obj)
True

实际上 type 并不是一个函数,而是一个类,我们可以使用 type(type) 来确定一下:

>>> type(type)
<class "type">

type 实际上不只是类,而是一个“元类”。我们接下来要可以看到,所有的元类都需要继承自 type。type 是所以类的元类,所以在上面的例子中 x 是 Foo 的实例,Foo 是 type 的实例,type 又是他自己的实例。

file

使用 type 动态创建类

如果传递给 type 的参数是三个的时候,type 的语义就不再是返回给定参数的类,而是实例化生成一个新的类。

type(name: str, bases: tuple, namespace: dict)

第一个参数是新生成的类的名字;第二个参数是新生成的类的基类列表;第三个参数是要个这个类绑定的属性的列表,比如说这个类的一些方法。实际上 class Foo 这种语法只是使用 type 生成类的语法糖而已。

最简单的一个例子,比如我们要创建 Foo[0..9] 这些类,可以这样做:

classes = []
for i in range(10):
    cls = type("Foo%s" % i, tuple(), {})
    classes.append(cls)

# 就像使用普通类一样初始化 Foo0

foo0  = clssses[0]()

如果要实现类的方法,一定要记得同样是要使用 self 变量的。在 Python 中 self 只是一个约定俗称的变量,而不是关键字。

def __init__(self, name):
    self.name = name

def print_name(self):
    print(self.name)

Duck = type("Duck", tuple(), {"__init__": __init__, "print_name": print_name})

duck = Duck("Donald")

duck.print_name()
# Donald

创建自己的元类

首先我们来回顾一下 Python 中类的初始化过程:

foo = Foo()

当这条语句运行的时候,Python 会依次调用 __new____init__ 方法。其中 __new__ 方法在 __init__ 之前调用,并返回已经创建好的新对象,而 __init__ 函数是没有返回结果的。一般情况下,我们都会覆盖 __init__ 方法来对新创建的对象做一些初始化操作。

现在回归到元类上,进入烧脑部分。前面我们说过元类的实例化就是类,所以大致相当于:

Foo = MetaFoo(name, bases, attrs)  # MetaFoo 默认情况下是 type
foo = Foo()

默认情况下,所有类的元类是 type,也就是在这个类是通过 type 来创建的,这和前面说的通过 type 来动态创建类也是一致的。

那么怎样定义一个 MetaFoo 呢?只需要继承自 type 就行了。因为元类的实例化就是类的创建过程,所以在元类中,我们可以修改 __new__ 来在 __init__ 之前对新创建的类做一些操作。

>>> class MetaFoo(type):
...     def __new__(cls, name, bases, namespace):
...         x = super().__new__(cls, name, bases, namespace)  # super实际上就是 type
...         x.bar = 100  # 为这个类增加一个属性
...         return x
...

>>> Foo = MetaFoo("Foo", tuple(), {})  # MetaFoo 在这里就相当于 type 了,可以动态创建类
>>> Foo.bar
100
>>> foo = Foo()
>>> foo.bar
100

在这里我们创建了 MetaFoo 这个元类,他会给新创建的类增加一个叫做 bar 的属性。

在实际的代码中,我们一般还是不会直接动态生成类的,还是调用 class Foo 语法来生成类比较常见一点,这时候可以指定 metaclass 参数就好了。可以通过 Foo(metaclass=MetaFoo) 这种方式来指定元类。

class Foo(metaclass=MetaFoo):
    pass

这种定义和上面的元类用法效果完全是一致的。

一个现实世界的元类例子

在 django.models 或者 peewee 等 ORM 中,我们一般使用类的成员变量来定义字段,这里就用到了元类。

class Field:
    pass

class IntegerField(Field):
    pass

class CharField(Field):
    pass

class MetaModel(type):
    def __new__(meta, name, bases, attrs):
        # 这里最神奇的是:用户定义的类中的 bases 和 attrs 都会作为参数传递进来
        fields = {}
        for key, value in attrs.items():
            if isinstance(value, Field):
                value.name = "%s.%s" % (name, key)
                fields[key] = value
        for base in bases:
            if hasattr(base, "_fields"):
                fields.update(base._fields)
        attrs["_fields"] = fields
        return type.__new__(meta, name, bases, attrs)

class Model(metaclass=MetaModel):
    pass

这样用户使用的时候就可以这样定义:

>>> class A(Model):
...     foo = IntegerField()
...
>>> class B(A):
...     bar = CharField()
...
>>> B._fields
{"foo": Integer("A.foo"), "bar": String("B.bar")}

程序在执行的时候就可以直接访问 X._fields,而不用每次都通过反射遍历一次,从而提高效率以及做一些验证。

不过,其实这个完全可以通过装饰器来实现:

def model(cls):
    fields = {}
    for key, value in vars(cls).items():
        if isinstance(value, Field):
            value.name = "%s.%s" % (cls.__name__, key)
            fields[key] = value
    for base in cls.__bases__:
        if hasattr(base, "_fields"):
            fields.update(base._fields)
    cls._fields = fields
    return cls

@model
class A():
    foo = IntegerField()

class B(A):
    bar = CharField()

但是用装饰器的话,就失去了一些类型继承的语义信息。

总结与思考

Python 中的元编程还是一种很强大的特性,但是也比较复杂,有时候很难以理解。实际上,过分的动态特性也导致了 Python 的解释器和静态分析、自动补全等很难优化,因为有好多信息必须到运行时才能知道。

实际上近些年新开发的语言越来越多地加入了静态类型的特性,比如 swift, rust, go 等。就连 Python 本身也增加了 type hinting 的功能,很遗憾的是,这个功能不是强制性的,所以也很难用来提升性能。

元类这块应该是我在 Python 语言方面了解的最后一大块知识了。接下来除了写业务代码不会再深究 Python 了,研究 Golang 去了~

Au revoir, Python!

参考

  1. https://realpython.com/python-metaclasses/
  2. https://stackoverflow.com/questions/392160/what-are-some-concrete-use-cases-for-metaclasses
  3. https://blog.ionelmc.ro/2015/02/09/understanding-python-metaclasses/
  4. https://stackoverflow.com/questions/2608708/what-is-the-difference-between-type-and-type-new-in-python

给 Python 程序员的 Go 语言教程

楔子

最近读到一亩三分地上一篇讲 Facebook 架构和国内对比的文章,感觉自己真是井底之蛙。头脑中一些架构方面的概念和 Status of the Art 的理念还相去甚远,迫切想要进一步了解一些先进知识。比如说,以前觉得 git flow 这个概念还挺不错的,实践了半年,发现 develop 分支完全是多余的;以前觉得每个项目分一个仓库方便管理,现在觉得 monorepo 似乎更好一点。另外就是对“互联网时代的 C 语言” Golang 有点想了解一下。

一年前休假的时候看了几眼 Golang,感觉还不错,但是想实际写点什么的时候发现 GOPATH 这个设计真是奇葩至极。而现在我的思想已经完全倒向 Monorepo 了,那么 GOPATH 也就看起来很可爱了,Golang 看起来也就很可爱了,也就决定再翻翻 Go 语言的书吧,以后说不定会写点儿什么呢。

忘了在哪里看过一句话:人的知识像一个网络,新学到的知识只有和已有的知识关联起来才能真正记得住、记得牢,否则的话像是一个孤岛的新知识很快就会被忘记了,于是就有了本文。

需要注意的是,本文并不是一个简单的语法对比,倘若只是语法的话,直接把代码一列其实就差不多了。除去语法之外,本文还在设计理念上做了一些对比。以下为目录。(没有链接的表示还没有写,敬请期待)

目录

  1. 语法基础
    1. 类型与变量
    2. 数据结构与控制语句
    3. 函数定义
    4. 面向对象
    5. 错误处理
    6. 包管理
  2. 并发与网络
    1. 并发机制
    2. Http 请求
  3. 常用标准库
    1. 时间解析
    2. 文件 IO
    3. 正则表达式
    4. 数学函数
    5. 定时机制

写这些文章的另一个目的就是对 Python 中相关的知识做个梳理,以便以后再学习新的语言(比如 rust, clojure)能够更有条理。

Ref

  1. Python slice notation. https://stackoverflow.com/questions/509211/understanding-slice-notation/50929x
  2. How to get type of go. https://stackoverflow.com/questions/20170275/how-to-find-a-type-of-an-object-in-go
  3. Golang online repo. https://repl.it/languages/go
  4. A tour of go. https://tour.golang.org/moretypes/6
  5. golang vs python. http://govspy.peterbe.com/#lists
  6. https://www.353.solutions/py2go/index.html

面试刷题总结(八)- 字符串

解决两个字符串的动态规划问题,一般都是用两个指针 i,j 分别指向两个字符串的最后,然后一步步往前走,缩小问题的规模。

解字符串问题常用的算法是采用滑动窗口的方法。

避免字符串 O(n) 比较的一个方法是使用 hash。

字符串问题本质上都是自动机问题,实际上还是图论问题。

后缀数组技巧

kmp

  1. next 数组的定义为:当前位置的子字符串,前缀和后缀匹配的最大长度为多少。
  2. KMP 计算 next 数组和查找字符串的过程几乎是一样的,所以关键就在于构造 next 数组。
  3. 构造 next 数组的关键就一句话:次大匹配就是(失败的)最大匹配处的子串的最大匹配,也即 j = next[j-1]
def kmp(t, p):
    """return all matching positions of p in t"""
    next = [0]
    j = 0  # j 表示当前自创中前缀和后缀匹配的最大长度
    # 注意这里是从 1 开始
    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = next[j - 1]  # 关键之处
        if p[i] == p[j]: # 相等时,最大匹配自然要 +1
            j += 1
        next.append(j)
    ans = []
    j = 0
    for i in range(len(t)):
        while j > 0 and t[i] != p[j]:
            j = next[j - 1]  # 关键之处
        if t[i] == p[j]:
            j += 1
        if j == len(p):
            ans.append(i - (j - 1))
            # 这里是匹配成功了,但是要接着找下一个,所以按失败处理
            j = next[j - 1]
    return ans

def test():
    p1 = "aa"
    t1 = "aaaaaaaa"

    assert(kmp(t1, p1) == [0, 1, 2, 3, 4, 5, 6])

    p2 = "abc"
    t2 = "abdabeabfabc"

    assert(kmp(t2, p2) == [9])

    p3 = "aab"
    t3 = "aaabaacbaab"

    assert(kmp(t3, p3) == [1, 8])

    print("all test pass")

if __name__ == "__main__":
    test()

自动机

Trie 是一个自动机,KMP 是一个自动机,AC 自动机是 Trie 上运行 KMP 得到的自动机。Trie 和 KMP 都可以用于单模匹配,AC 自动机可以用于多模匹配。AC 自动机是确定性有限状态自动机 (DFA)。

正则表达式构建出来的却是一个非确定性有限状态自动机(NFA),非确定指的是跳转的时候可能有多个分支。要实现非指数时间解,也就是不用回溯,其实就是把回溯的深度优先遍历改成了广度优先遍历从而实现了剪枝。

哈夫曼树

https://juejin.im/post/5d1c7df2e51d45775c73dd49

参考资料

  1. https://oi-wiki.org/string/hash/
  2. https://www.zhihu.com/question/21923021/answer/37475572
  3. https://swtch.com/~rsc/regexp/regexp1.html
  4. https://stackoverflow.com/questions/31429865/trie-for-unicode-character-set
  5. https://oi-wiki.org/string/sa/
  6. https://oi.men.ci/suffix-array-notes/
  7. https://blog.csdn.net/u013421629/article/details/83178970
  8. https://oi-wiki.org/string/ac-automaton/
  9. http://nark.cc/p/?p=1453
  10. https://lingeros-tot.github.io/2019/03/05/Warming-Up-%E8%87%AA%E5%8A%A8%E6%9C%BA%E6%A8%A1%E5%9E%8B/
  11. http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

LeetCode 1236/1242 设计一个(多线程)爬虫解法

单线程题目 LeetCode-1236

具体题目就不说了,直接去 LeetCode 上看就好了。1236 要求使用单线程即可,考察的主要是图的遍历。只要注意到对于新发现的节点需要考虑是否已经访问过就好了。在实际生产中,肯定也是要用广度优先,深度优先基本就会陷进一个网站出不来了。

from urllib.parse import urlsplit

class Solution:
    def crawl(self, startUrl: str, htmlParser: "HtmlParser") -> List[str]:
        domain = urlsplit(startUrl).netloc
        q = [startUrl]
        visited = set([startUrl])
        while q:
            newUrls = []
            for url in q:
                urls = htmlParser.getUrls(url)
                for newUrl in urls:
                    u = urlsplit(newUrl)
                    if u.netloc != domain:
                        continue
                    if newUrl in visited:
                        continue
                    visited.add(newUrl)
                    newUrls.append(newUrl)
            q = newUrls
        return list(visited)

多线程题目 LeetCode-1242

1242 题要求使用多线程来实现。在现实生活中,爬虫作为一个 IO 密集型的任务,使用多线程是一项必须的优化。

在上述的单线程版本中,我们使用了 visited 这个数组来存放已经访问过的节点,如果我们采用多线程的话,并且在每个线程中并发判断某个 URL 是否被访问过,那么势必需要给这个变量加一个锁。而我们知道,在多线程程序中,加锁往往造成性能损失最大,最容易引起潜在的 bug。那么有没有一种办法可以不用显式加锁呢?

其实也很简单,我们只要把需要把并发访问的部分放到一个线程里就好了。这个想法是最近阅读 The Go Programming Language 得到的启发。全部代码如下:

import threading
import queue
from urllib.parse import urlsplit

class Solution:
    def crawl(self, startUrl: str, htmlParser: "HtmlParser") -> List[str]:
        domain = urlsplit(startUrl).netloc
        requestQueue = queue.Queue()
        resultQueue = queue.Queue()
        requestQueue.put(startUrl)
        for _ in range(5):
            t = threading.Thread(target=self._crawl, 
                args=(domain, htmlParser, requestQueue, resultQueue))
            t.daemon = True
            t.start()
        running = 1
        visited = set([startUrl])
        while running > 0:
            urls = resultQueue.get()
            for url in urls:
                if url in visited:
                    continue
                visited.add(url)
                requestQueue.put(url)
                running += 1
            running -= 1
        return list(visited)

    def _crawl(self, domain, htmlParser, requestQueue, resultQueue):
        while True:
            url = requestQueue.get()
            urls = htmlParser.getUrls(url)
            newUrls = []
            for url in urls:
                u = urlsplit(url)
                if u.netloc == domain:
                    newUrls.append(url)
            resultQueue.put(newUrls)

在上面的代码中,我们开启了 5 个线程并发请求,每个 worker 线程都做同样的事情:

  1. 从 requestQueue 中读取一个待访问的 url;
  2. 执行一个很耗时的网络请求:htmlParser.getUrls
  3. 然后把获取到的新的 url 处理后放到 resultQueue 中。

而在主线程中:

  1. 从 resultQueue 中读取一个访问的结果
  2. 判断每个 URL 是否已经被访问过
  3. 并分发到 requestQueue 中。

我们可以看到在上述的过程中并没有显式使用锁(当然 queue 本身是带锁的)。原因就在于,我们把对于需要并发访问的结构限制在了一个线程中。

当然如果可以用锁的话,也可以在每个 worker 线程中计数。而这种情况下,为了使用 running > 0 这个条件,一定要首先在发现新的 url 的时候 running++,在处理完整个页面之后再 running–。

面试刷题总结(九)- 数学知识

数学类问题一定要记得进位 v = v1 + v2 + carry

最大公约数和最小公倍数

辗转相除法(欧几里得算法). 原理在于 gcd(a, b) == gcd(b, a % b)

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

排列组合

卡特兰数,为什么除以 n+1

牛顿迭代法

格雷码

二进制

  • 判断一个数是不是 2 的正整数次幂:n > 0 && (n & (n - 1)) == 0
  • 对 2 的非负整数次幂取模:x & (mod - 1)
  • 判断符号是否相同:(x ^ y) >= 0
  • 获取某一位:(a >> b) & 1
  • 遍历某个集合的子集:for (int s = u; s; s = (s - 1) & u)
  • 一的个数:while (n) {n = n & (n-1); count++}

求幂

long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

全排列

几何

有时候几何题也会出现在面试中。不过,毕竟是 coding interview 而不是 math interview,这部分复习的优先级不高。

参考

  • https://oi-wiki.org/math/

面试刷题总结(一) – 递归问题

递归是几乎一些算法的基础。实际上我认为算法题大致可以分为两类:递归和其他。

实际上计算机能解的唯二问题:

  1. 足够简单的问题:比如 x * x, x^0 = 1.
  2. 把复杂问题约简到简单问题:比如 x^n = x^(n/2) * x^(n/2)

分治、树、深度优先搜索等等实际上都是递归。

递归的核心思想:明白每个函数能做的事,并相信它们能够完成,千万不要试图跳进细节。

在面试的时候,如果允许写递归(一般是允许的),那一定要写递归解。

解题思路

对一个给定的问题:

  1. 确定哪些情形是基础情形,不需要再做递归。比如说:高度为 0 的树,或者 null 根节点,空字符串等。
  2. 把问题转化为规模更小的问题。
def fact(a, n):
    if n == 1:
        return a
    return a * fact(a, n-1)  # or n/2 or whatever...

def fact(a, n):
    if n == 1:
        return a
    h = fact(a, n/2)
    return h * h

好多时候,需要编写一个私有的 helper 方法,更改一下函数的签名。对于 Python 或者 JavaScript 的话,直接写一个闭包函数是最好的,也避免了全局变量。

Algorithme by Jeff Erickson

最后推荐一本神书:Algorithms by Jeff Erickson. 这本书全书都是在按照递归的思路讲解。

其它的书和文章的问题在于每个知识点似乎都是孤立的,比如说动态规划就在重点讲解状态转移方程和状态矩阵,而分治就在讲解如何用递归树计算时间复杂度等等。这种讲解方式下,每个知识点之间看不到有什么关联,往往熟悉了这个又忘了那个。实际上这些知识点都是有联系的,所谓的动态规划不过是状态空间搜索的一个巧妙转换,本质上和回溯是一致的,都是递归而已。每个技巧的内核都是一致的,只不过特异化之后有不同的表现,如果你不去抓住内核,通过一个主干把所有知识串联起来,而只看表面现象,那么永远也记不住的。

其他的书就好比盲人摸象,而这本书则是讲解的大象的骨骼结构和肌肉构造。分治和动归这些算法好比是大象的耳朵、尾巴等等部位,可以在外部摸到,而递归则是大象的骨架,虽然摸不到,但是只有画出了骨骼,才能把大象画好。

参考

  1. https://stackoverflow.com/questions/25367781/tips-on-solving-binary-tree-binary-search-tree-problems-using-recursion-java

Netflix 公司文化学习笔记

在头条的时候经常听一鸣说到“context, not control”,开始以为是他原创的,后来才知道原来是从 Netflix “偷”来的。不过当时其实自己并不能特别理解这其中的含义,直到后来在创业公司,偶然想到才感觉真是醍醐灌顶,于是特意找来完整的 Netflix 文化 PPT 学习了一下,并做了一写笔记。

file

Value are what we value

file
file

公司价值观体现在我们珍视什么。几乎每个公司都有一些听起来很高大上的价值观,然而这些金玉在外的话语是没有用的。

  1. 公司真正的价值观体现在公司奖励哪些行为,提升哪些人,以及解雇哪些人。
  2. 公司的价值观也体现在员工们珍视的行为和技能中。

High Performance

file
file
file
file
file
file

Freedom & Responsibility

file
file
file

Context, not Control (My favorite part :p )

file
file
file
file

Highly Aligned, Loosely Coupled

file

Pay Top of Market

file
file

Promotions and Development

file
file
file

What are some profitable one-person online businesses?

Here are a list of examples I collected from Hacker News that claim to run a successful one-person online business. You could find the original threads at the end of this post.

Quiz Website

I run a popular Quiz website. I make around $6,000 per month from Google adsense. I work between 2-3 hours a week usually posting quiz links on my Pinterest page. My only expense is hosting which is around $20 per month (Digital Ocean). I have never advertised my website and it gets all the traffic from Pinterest Organically. Compare to my salary, I’m an IT Administrator in my day job and make $400 per month. I live in Ethiopia 🙂 I thought this inspires my fellow HN. Good day.

  • How do you manage to kickstart something like this? You mentioned you get your traffic organically via Pinterest, but there had to be something you did initially that set off that growth.

My website started five years ago, It didn’t get any traffic the first three years before one of my quiz went viral. Now I have around 70k followers on Pinterest.

  • This is important. I have seen this a lot. Persistence. Many people keep pushing,keep pushing even if there is no positive feedback loop for a long time. After a while, they beat time. Kudos.

Cursive-IDE

I develop and sell Cursive (https://cursive-ide.com), which has paid my bills nicely for a couple of years now. Currently I make more than I made in my last job at Google. I never thought I’d be able to make a living selling developer tools, much less into a niche market, but I’m constantly amazed by how well Cursive does.

The work is a mix of fun and boring slog, like most jobs I guess. A lot of my time is spent on support, both technical and sales, so when I work less I actually end up getting more frustrated because a higher percentage of the work is not as fun as writing new features. I’ve also had a bad year of having to work around IntelliJ bugs, but normally I like the actual development work a lot. I have friendly enthusiastic users who constantly make my day. It’s a pretty sweet gig, and being able to decide how I spend my time, and which bits of my time I spend working, is priceless.

I got started during a sabbatical from my last job, just building something that I wanted myself. It turns out that lots of other people wanted it too.

Product Pix

I own Product Pix (https://www.proproductpix.org). It removes the background from product photos, with the intended audience being mostly people who sell stuff online and need to set their background against a white background.

It makes $1300/month right now, up from $0 6 months ago. Living in the Bay Area, that would put me well below the poverty line if it were my sole source of income, so I’m not gonna call it “successful” just yet.

How I got started: I do machine learning, and I methodically searched for places where people buy a service transactionally on platforms like Fiverr and that I think can be automated away (or greatly automated with human reviewers in the loop) with state of the art machine learning models. There are hundreds or thousands of such opportunities that individuals can solve on their own.

I’ll be more comfortable giving sage advice once I’ve crossed the $10K/month threshold, but still I’d say a willingness to try a lot of shit out and get digging on stuff you have 0 familiarity with is mandatory. In this project I’ve had to learn javascript, frontend, photography, google ads campaign management etc.

Another tip I wish someone had told me is, build a pricing page from day one. The temptation to get some signal you’re useful to people will drive you to offer stuff for free, but that will end up getting you a lot of unwanted attention from people who will never ever pay.

Instagram Posting Service

My business is in my bio, don’t want to link it here. Pays about the same as my previous job at Microsoft did, but with a lot less involvement — I haven’t touched the main code in about a year now. I probably spend about two or three hours a week on customer support, that’s it, really. No marketing spend, all word-of-mouth and Google.

The idea came about when I wanted to post to Instagram, but the API didn’t allow it. So I spent about a week trying to automate the process using a phone, with screenshot OCR and a state machine. After a lot of messing around with it, I had a working prototype. Made a website, added a $5/month Stripe plan to see if people were willing to pay for it, sent it to a few friends, posted it on Twitter, and eventually, people signed up and tried it out. It worked, then it didn’t work, then I fixed it, then it worked again, this went on and on for a few weeks until it became quite useable.

About two months in, local offices of Toyota and Samsung signed up, and they loved it, money wasn’t an issue. That was the moment I realized it may be worth doing it properly.

It grew organically, and I bought lots and lots of Android phones, which are simple workers getting jobs off a queue, and host them in two locations roughly. Phones last for about two years, then I buy new ones (<$100 a phone). Each phone pays for itself in less than a month, server costs are less than $200 a month.

Facebook tried to sue me after I filed for a trademark, we figured it out (I rebranded). Been going steady ever since, but I consider it to be shut down by yet another Instagram move sooner or later. But I said that after 3 weeks of running it, and it’s been almost five years I think.

I made it a point to not use any private Instagram APIs, like all my competitors did — instead, I don’t emulate the Instagram app, I emulate the person tapping the phone, and use only the official app for it. I think that let me survive this long.

Updown.io

I run https://updown.io since 2012, a website monitoring service I created. I’m working about 5-10 hours per week on it. It makes about $6,000 per month and is still growing linearly. I also keep a full-time job alongside for now as an engineering manager. The key for me is to take time, make something useful, delight your clients, and don’t try to become uber or airbnb.

Sports App Business

I am mainly in sports apps. I think it is still possible to have succes. It requires a lot of patience. Don’t focus on the revenue part. And don’t try to build a new hype. Very slim chance you build the next angry birds. Instead try to build a product that is based on an already successful specific category/ product. Very important is that you understand your customer and genuinely try to make a product that is better than the competition. You should love your own product. The good thing is that bigger companies tend to destroy their own product with too many ads, notifications, non relevant features etc. Furthermore I believe it’s important that your product contents can be automated without too much manual work. After all you are the only person with only so much time. I know a guy who created a fitness diet app. He cooked and photographed more than a thousand meals. He wrote many articles. In the end he gave up. It took him 80 hours per week to maintain and update all the content. His app was making maybe 100 a month. I know another guy who created a successful formula 1 live app. He is using paid data feeds and scrapes a lot of additional data. Everything automated. Spends like 10 hours a week maintaining things. Makes about 100k a month. Similar story for a guy who created a popular weather app. In essence the only thing what they do is aggregation of data and present it in a relatively simple app. Also don’t spend too much time on analytics, seo and other optimizations. It may take 2 years before you get traction anyway. First the product then after (if it’s worth) the optimization. One concrete product where I think you can still have success is a baby monitor with 2 phones. Couple of good apps only. All premium priced. Not too difficult technically. I don’t have time for it, so go for it 🙂

PageFlow

I run https://pageflows.com and have been living off it full time for a little over a year.

The business makes a bit more than what I was earning a few years ago as a junior developer in London, so it’s not a huge amount of money, but it’s enough.
It’s a fairly boring business to run and not as predictable or sexy as some sort of micro saas, but it’s I’m happy with how things have been so far. Happy to answer any questions you have.

Most customers are indeed businesses. Great shout on some sort of team/business plan – it’s on my to-do list!

I’ve commended to a response below with the business model, but yeah I’ve just started trialling a freemium model yesterday so need to update the rest of the site with clearer pricing plans etc.

Until yesterday there was no freemium access, it was just paid up-front to access all the content. $39 per quarter or $99 per year.

Your use case is kinda where the idea came from, most product people do something similar. The hard part is adding enough relevant content on Page Flows for enough people!

Wakatime

Seven years ago I solo-started an automatic time tracker for programmers called WakaTime [1] and launched here on HN [2]. Partly from listening to developers too much, I waited way too long (almost a year) before adding a paid plan, but now it generates more MRR than an SF developer salary not including stock options. Technically I make more from RSUs and stock from past startups as a regular employee, but if I wasn’t lucky with those then it would be my highest income stream.

1: https://wakatime.com/about
2: https://news.ycombinator.com/item?id=6046227

For anyone thinking it’s egregiously difficult to start a solo-project: You’re right, but if you stick with it your persistence will pay off. For solo-products, I think grit is the deciding factor between success and failure.

There were several stages of MVP. First usable version took a month and half to build and public launch with 2 IDEs supported was 2 and half months after starting to build.

May 3 2013 – Started development Flask website & Vim plugin (https://wakatime.com/blog/1-why-i-built-wakatime)
June 25 2013 – Finished Vim plugin and Website (https://github.com/wakatime/vim-wakatime/commit/4346a055e301…)
July 1 2013 – Started Sublime plugin (https://github.com/wakatime/sublime-wakatime/commit/b7fe36f8…)
July 15 2013 – Finished Sublime plugin and public launch (https://news.ycombinator.com/item?id=6046227)

Unfortunately I don’t have WakaTime data until after finishing the Vim plugin, but everything after that I can see how long the actual coding took by dogfooding.

ERP plugins

I have a one-person lifestyle business. I like it primarily because it gives me the flexibility to live anywhere in the world. I hated my old desk job and the idea of 2 weeks vacation every year.

I run a SaaS product that integrates with ERPs. I pretend to my customers that I have a team (so much so that I have multiple email addresses to people that don’t exist that actually just forward to me). One of our customers thinks they’re paying for a team of 6, but it’s actually just me.

My monthly billings last month was 73k USD. I am a tax resident of a tax haven although I do live 3-6 months at a time in a different country.

The only advice I’d give anyone looking to build a lifestyle business is to keep your ambitions and by extension- product feature set in check. I know several other people who operate like me, and the common thread is we have businesses that can easily take VC funds, hire, and expand. But for lifestyle priorities, we chose not to.

A lot of people I’ve met (particularly in Chiang Mai, Thailand) copy popular, common, and easy online businesses such as drop shipping, social media XYZ, or coding. Unless you live in a really low cost area, it’s not a good life. The key is have a very specific niche that can be scaled upwards if you want, but you always have the option not to. Those the ideas and businesses that seems to provide the ideal balance in lifestyle.

EDIT: The product came about at my last job where I built it to make my own job easier. Essentially it did 95% of what job which at the time enabled me to be the “best performer” while not actually working that hard.

Flowx.io

I develop Flowx [https://www.flowx.io], an Android weather app. It makes around $2,500 USD/month with about $500/month in costs excluding my time. It covers about 60% of my total costs including my time which is 40+ hours a week. I cover my remaining costs through contract work. This might not seem like a success but the business allowed us to move to the Rarotonga, Cook Islands from Auckland, New Zealand. Lifestyle-wise and building-a-business-wise, I think it’s a success.

Just an added note. I started Flowx as a side-project in 2012. In 2016, we moved to Rarotonga and we decided then to try to grow it into a business. It was making ~$100/month at that stage. Since then, it has grown it to $2500/month through added pro features and a better subscription prices.

Stay focused

I sell freemium software that blocks distractions on your computer so that you can focus on doing work. Unlike my competitors, it’s a one-time payment business model.
The idea for my product first came to me when a friend in university had trouble staying focused on writing papers. He was constantly playing World of Warcraft and needed a way to temporarily block himself from playing the game. So I quickly made a little VB.NET app and service that would watch for the game executable and kill the process if it starts. It did the job well enough and he ended up graduating 🙂

At that point, some other students approached me and asked for my little app to help them study. That’s when, half-way through university (2010), I made a website for my app and had it available for free. I continued to maintain it and over 4 years, added more features including: blocking websites, adding breaks, scheduling, and passwords.

In 2014, I split the product into a free and paid tier. It wasn’t an easy decision, but I was spending a lot of time on it by this point and customer support was also starting to take a serious hit on my personal time. In about two years (2016), I was making more money from the paid product than my well paying government day job. So, I decided to quit my job and work on my business full time.

Although I felt it was risky, the alternative was passing up an opportunity many people dreamed of having. I never planned to start a business in the first place and I kind of felt/still feel imposter syndrome. For now, I’m just enjoying my new found freedom and continue to be thankful for my new job. I’m going to keep it a lifestyle business for now, but I wouldn’t be opposed to selling it as my exit plan.

I’ve spent (effectively) $0 in advertising since developing it and I’d say my customers come from organic search, external links, and word-of-mouth.

browserless.io

I run a headless browser service called browserless.io. Got started due to lack of a comparable service, and all others seemed more geared for testing.

It’s been around two years now, and makes more than any prior engineering job I’ve ever had. You do have a lot of other stresses you might not otherwise have, but you’ll also work a lot less than at a traditional job!

I’m working on a few interviews for some sites, which go more into the details, and will post here when they’re done.

EDIT: feel free to comment here on anything or email me at joel at browserless dot io

Website builder

I created a SaaS website builder for a small niche market. I’ve been running it for about 8 years. I gross a bit over $14,000 per month with about $500 in expenses for servers and third-party APIs. I work 1-2 hours per week answering customer support emails. Basically, I automated away my old job as a web designer 🙂

The smartest decision I made was targeting a small niche market that larger businesses wouldn’t bother with. I often get kind emails from customers thanking me for helping their industry. I kept things simple, didn’t add features unless I really believed customers needed them, and didn’t try to generalize the solution. I think those are the main reasons why the product worked.

By far the hardest part was/is marketing. I’m still bad at it. I’ve tried may things. Most failed or were too hard to sustain. Some succeeded, like Facebook ads, but those successes were often hard to recreate. At this point it’s mostly word of mouth.

Working alone can be psychologically challenging. When I have a problem, there’s no one to help because no one else knows how the platform works. With no one to bounce ideas off of, it’s easy to get stuck in a rut going round and round the same set of possible solutions. And I really have to monitor myself to ensure that I don’t get too isolated. This was an issue in the early years, but now I have a routine that gets me up and out and into the world every day. I would strongly advise anyone considering the solo route to carefully consider the social and mental health aspects of working alone.

I feel very grateful to my former self for doing the hard work that pays my bills today. And I’m tremendously grateful for open source tools and resources like Stack Overflow without which I would never have made it this far alone.

meme tshirt

I ran a Shopify site selling meme shirts for 3 years.

You might recognize classics such as “Legalize 4Loko 2020” and “BREAD” as featured in Elle magazine.

All on-demand printing. Order goes through Shopify’s API to the supply center, order gets fulfilled, shipped. No inventory. Kinda pricey, but zero maintenance. Set and forget.

Find the most extremely dank and niche memes possible so you hit the little nugget inside of someone’s brain that makes them want to spend $15-30 on a t-shirt.

A good print would net me somewhere like 300 orders a month. A sweatshirt could go for $50-60. You have options.

ML golf predict

I made https://www.golfforecast.co.uk – an ML algorithm to predict golf.

After 5 years it’s making enough from subscriptions for me to live off (3K gbp/mo). The algorithm is always a work in progress but it’s seeing consistent returns now so I’m making money from that too 🙂 plus it makes golf a lot more entertaining.

IPINFO.IO

I started https://ipinfo.io as a side project, and then ran it fulltime as a one-person SaaS app for over a year. We’re now a team of 8, profitable, and growing quickly. We’re still 100% bootstrapped, and I have zero plans to raise any outside funding.

We started with a simple IP geolocation API, which now handles over 20 billion API requests per month. We’ve added new data to that service, such as IP type classification (hosting, isp, or business, and soon education too), IP to company, and carrier detection. And we’ve also launched some other products, like hosted domain API (all domains hosted on an IP, sometimes called reverse IP), IP ranges belonging to an organization, and an ASN API. We’ve got a lot in the pipeline too, including some domain related offerings (see https://host.io for an early preview).

So it’s definitely possible 🙂 What sort of SaaS product are you thinking of launching? Would be happy to chat! Shoot me an email at ben@ipinfo.io

NANAGRAM

I’m working on NanaGram (https://nanagram.co) solo and bootstrapped. Although I’m not making a full-time income yet, it’s generating a profit. It’s mostly automated.

NanaGram is the 3rd greatest generator of happiness and fulfillment in my life (after my wife and my dog). I get a constant stream of good vibes from customers, most recently voicemails from grandmothers! (https://nanagram.co/blog/feedback-by-vm)

Good luck 🙂

PhantomJSCloud

I run https://PhantomJsCloud.com
I started it as a free MVP about 2 years ago while in Thailand, and given that I was attracting a slow but steady stream of users I decided to build out a commercial v1 from it.

The freemium SaaS went live in March and it’s growing monthly. If I still lived in Thailand I would consider it very successful, but I am in the Seattle area now so it’s ramen profitable.

The biggest surprise I got was how slow organic growth takes. Every month I gain more users + MRR but discovery seems to be the biggest problem. I tried Google Adwords in June but Google decided to cost me upwards of $5/click for basic keyword targeting so gave that up. I tried Adwords again in November and now google thinks I’m more relevant, so I pay starting at $0.20/click for the same keywords that cost $5/click 6 months previous. I am currently doing experiments to see if the acquisition cost justifies that spend.

From a effort perspective, the SaaS api+backend itself was about 50% of the effort. The subscription service + user dashboard was another 50%.

From a skills perspective, I think doing a SaaS as a solo founder is only practical if you have extremely broad skillsets: Business management, UX, full-stack webdev, devops, sales, marketing, support. Thankfully I have some experience in all those (except sales) so I was able to either do or fake everything required. If you don’t have all those skills, you are going to be increasingly reliant on luck, which isn’t a winning strategy.

I solicit users to email whenever they have a question/comment/issue and reply to everything. Overall I think I have provided email support to aprox 50% of my paying customers, and maybe half of the support was provided before they decided to pay, so it is very important 🙂

it’s actually a really great way to understand your customer’s needs, and your products actual (in the eyes of the user) deficiencies. I also use uservoice to help the highly-desired features/requests to “bubble up” but if a customer asks for something and it’s an easy enhancement I go ahead and implement it. Likewise if the same problem is annoying a bunch of people, I need to either document a workaround or make it easier.

Yes, “inbound marketing” (a blog) is probably the biggest accelerator to growth I can (and should) do. I’m holding off for now though, as I need to make the product more friendly to business users first. Right now PhantomJsCloud is focused on developers, so I need to make some non-dev friendly tooling first. That’s my excuse at least.
Regarding StackOverflow, yes, that’s actually how I validated the free MVP (answering SO questions and if my product might be beneficial, providing a link to my product) but generally those traffic sources don’t seem to scale very well past MVP validation. I haven’t tried Quora though, I will add that to my todo list 🙂

SingalBox

I’m running https://SignalBox.ai alone, I wrote all of the software and am working on partnering and sales right now.
Previously I have 2 other startups, one was media monitoring and one was forex.

The media monitoring is B2B only. The forex trading is automated and run from my home research cluster.

Both are generating enough revenue to live off (media monitoring 120k forex, 60-80k)

I guess they fit the definition of solo founder and online, but they have no public facing websites (except SignalBox)

EDIT: I also run a slack group for Solo Founders, If you would like an invite, please email me

  • Sales are a big struggle to me. Where did you find this partnerships?

Network. Go to the meetups.
Don’t rely on serendipity, we can do better than that. Use your programming skills.

Pull the meetup list, get all of their twitter profiles, search everyones last 1000 tweets for topics you are interested in. Pull all of their code on github. Push it through the profiler and find the talent.

Mirror github if you have to. Pull the whole darn thing, it’s only a couple of hundred gigs (if you dont pull the code) Profile everyone based on their stars, contributions, watchers and pull requests.

How many other meetups do they go to? What’s their history like on other forums?

Put the pics of these people on your phone, and then go and find them at the meetup. Pull their customer lists / testimonials and any other publicly available data.

Look at their company DNS records. Pull their company filings if they’re available. Know their revenue, know their customers. Who’s making the decisions at this company? Who is signing the cheques?

Scientia potentia est

dropshipping guitars on shopify

I run an ecommerce store from Shopify which fulfills the orders by drop-shipping through AliExpress.
This is definitely doable for one person, and it isn’t technically challenging for a software developer–but the hardest part (at least for me) is marketing, creating content, advertising, and so on.

Actually running a Shopify store and fulfilling by drop-shipping is simple. I would definitely recommend that as a good place to start, one person can do it.

There are a few good ways, but it really helps if you know the products well. For me, my site sells guitar parts and DIY kits. And I’ve been playing guitar since I was about 10 years old, so that helps a ton.
I had a few other stores before this that didn’t sell well at all, and I have to say that’s because I just didn’t know the products, or what the end users really wanted/needed/cared about.

Great ways to pick products: – Terapeak (http://www.terapeak.com/), but this is paid – eBay completed listings – Or most simple (and what I use) — once you know your products, search AliExpress and sort by “best-selling”. That’s my go-to.

Feel free to check my store for ideas (or if you want to buy something!). URL is: http://modshop.guitars/

pinpoard

I run Pinboard, $257K in gross revenue for 2016. A ton of money for one person, not quite enough for two people.

Do you have a writeup on your marketing?

My marketing is, I spend all my time talking smack on Twitter.

bugmuncher

I run BugMuncher (https://www.bugmuncher.com), it started as a side-project 5 years ago, then in September 2015 I packed in freelancing to focus on BugMuncher full time.

As of November 2016 BugMuncher reached profitability – ie: it’s my sole source of income, and covers all of my living expenses.

price comparison

I run https://www.fortsu.es (also https://www.fortsu.co.uk, https://www.fortsu.de and https://www.fortsu.com) a price comparison website for running shoes. Original one is focused on spanish market while expanding into interesting ones.

It started as side project some years ago when I wanted to buy running shoes online and it has been improved over the time. To-Do list never ends 😉

At the beginning it was basically word of mouth and niche related forums on the internet.
Then I started reading about SEO and advertising. Organic search more or less work but I got almost no traffic from a couple of banners on related pages during few months. I didn’t try advertising networks like AdWords.

I don’t see big brands as my competition. I have partnered with some but I don’t think they sell much on the internet (typically higher price tags) compared to full equipped city centre stores.

iOS app

I started selling macOS (and now iOS) software on my own website back in 2007. https://clickontyler.com My original goal was to earn enough money to refinish the hardwood floors in my house. Since then, however, it’s taken on a life of its own and become a suite of three main products. It enables me to live comfortably in the Nashville suburbs.

webhosting reviews

1 man startup – http://reviewsignal.com/webhosting/compare I do web hosting reviews. Not the scummy pay-for-placement stuff you see, but an actual review site. It tracks what people are saying about hosting companies on Twitter and publishes the results.
The story is told a bit here http://techcrunch.com/2012/09/25/web-hosting-reviews-are-a-c… I was just tired after 10 years of still relying exclusively on my experience and the experiences of people I knew. Figured there must be a better way and I had been working with Twitter data for thesis and saw this opportunity.

selling online

I started selling online, total sales so far over $300k. Multiple sources, some retail, some wholesale.
What I’ve learned:

  1. Not all rules matter. A large part of my business is stretching certain rules, either from the marketplace, or from the source (e.g. a store that doesn’t allow resale). That said, you can’t get away with breaking rules unless you have a very good understanding of why the rule exists, who’s motivated to uphold it, and generally what the risks are. Don’t screw over customers.

  2. There’s a lot more to be made by taking risks than there is to be lost. I’ve easily lost over $1k multiple times in various ways, but when I “win” it’s to the tune of 10 or 30 times that. Take smart risks, only where the realistic upside justifies it.

  3. Be willing to pay for information. There are courses out there in almost any topic. Personally I’ve largely carved my own path and paid very little , but I’d still recommend courses for others. Also read a lot of whatever free information is out there, and network with people who have more experience.

  4. Don’t do too many things at once. It will kill you. I’ve been full time in college and it’s extremely tough to balance everything. Delegate as soon as you can afford to, anything others can do that doesn’t take a lot of brains pay people to do.

  5. Don’t be afraid to scale, but do it slowly. My first purchase of over 10k was 6 months after I started, iirc.

(Several of these are probably specific to this kind of business, may not be generally applicable. Startups have a much different road where profitability isn’t the most important at first.)

selling open source software to government

I was working for Automattic after an acqui-hire thing. After a year there, I found that I missed working in security. I found a full-scope penetration testing gig three blocks from my apartment.

In my spare time, I started to tinker with a few ideas and released them as an open source project. Said project saw a lot of interest within the hacker community very quickly. I didn’t expect this. Folks formed an opinion on it pretty quickly. Some people hate it. Others love it. Of those who know it, very few are in-between.

I left my pen testing job with a decent amount of money saved up. I didn’t know exactly what I would go and do afterwards. I spent some time tinkering with Android, just for giggles.

I was very reluctant to start a business that used my “successful?” open source project. Partially because it leverages another open source project owned by another company.

I was at a conference in 2011 and someone from a US government agency asked if I was selling anything. I said no. He said that was too bad, because he had end of year money, and he liked my open source stuff. It was then that I decided to look at expanding my open source kit into a commercial product.

April will mark the two year anniversary of my first customer. My customers are well known organizations and they trust my software to assess how well they protect their networks. I’m constantly in awe of this.

website counter

https://www.improvely.com and https://www.w3counter.com

Five figures a month, just me, I’ve written about my solo business a couple times in other Ask HN threads. Ten years ago (almost to the day), in my college dorm, I was looking at the Webalizer web stats report my web host provided for my blog, and thought “I could do something much cooler than this”. So I did. I had built a few educational sites and threw some ads on them for a couple years before that, but W3Counter was the first service I actually charged a subscription for, and now I make a living building and selling this stuff.

vintage computer hardware

I don’t know exactly how you define “successful online business,” but I am currently a university student making $500 – $2000 a month at about 5 to 10 hours a week.
Basically, there is a market for vintage computer hardware, so I post some adds offering to take away old office items they can’t just throw away. Such as old keyboards, terminals, etc. and they pay me a nominal fee ($1 – $5 per item depending) to rid them of their “trash”. I then resell those items after cleaning them up a bit for extremely high profit margins $35 – $120 for 20 minutes of work (since I was payed to take away the trash).

One of the things I did was sold Model M keyboards which I made USB compatible: http://austingwalters.com/keyboards/

Another way I make money is by tutoring or helping out with programming, I use to help out local people, but I have since switched over to Google Helpouts. Usually, it’s just explaining some algorithms and writing some C code. Pretty easy, no real upkeep, and I can set what ever hours I want.

pingrow

Just launched Pinegrow Web Designer (http://pinegrow.com) two months ago. The company is actually run by my wife and me, but I do all the work with Pinegrow while she is taking care of our other projects.
Pinegrow has been paying most of our bills since launch and I have a lot of expansions in the pipeline: full support for Foundation alongside Bootstrap, developer edition that’ll work with templates, a similar app for designing emails…

cramfighter

I run a small business called Cram Fighter (http://cramfighter.com) that is targeted at students (mostly medical) that are preparing for standardized exams. I got the idea after watching my wife preparing for her board exams and it seemed like a perfect little project to learn iOS programming. Initially my goal was to do earn maybe $5k annually, but now I’m on track to surpass my salary as senior developer by next year.
You’ll find a lot of one-person businesses targeting tiny, but profitable, niches like mine. What’s great about it is that often when you find a tiny opportunity, it opens up a lot of other problems that need solving that you would never find otherwise. It’s also a great way to learn the skills of running a business in a relatively stress-free way (at least compared to running a startup).

The only downside is if you’re anything like me, you’ll get antsy working on small projects and yearn to tackle bigger, more ambitious problems. Sometimes 1-person companies have the potential for turning into a company with startup-like growth, sometimes not. I’m still trying to figure out how far I can take my company.

office snapshots

I run http://officesnapshots.com which publishes photos of office design projects from around the world.
I started it in 2007 as a gin side project to teaching history. I’m no longer teaching and it is the majority of my income.

laptop battery meter

I sell a laptop battery meter (http://batterybarpro.com). It’s not income replacing; it makes about $1,000 per month, but it’s been crucial in saving enough for down payments one two houses.
I’ve tried to get the revenue numbers up, but I’ve never been able to break a $2,000 month.

robots everywhere

http://www.robots-everywhere.com I used to employ two people, but I automated them away. I am successful in the sense that I have clear title to my home at age 33, if that counts.

excel version control

I run https://www.spreadgit.com, a hosted version control system for Excel. Doing this solo and full time. It’s been a hell of a ride so far but I love it.

write a book

I wrote a book[1] that generates about $2k of revenue per month. Not quite your definition of success, but it’s given me a taste. I’m now in the beta testing process for my next thing[2].

smart shooter

I develop and sell Smart Shooter.
http://kuvacode.com

Its a traditional desktop app (windows, mac), but only sold online via our own website or the mac app store. I created it about 4 years ago, and work on it solely in my spare time. In fact I’m employed full time at a major tech company but this I keep separate.

To claim its profitable is a bit misleading, because of cause the major cost in developing such software is my own time. I’ve incorporated as a limited company here in Finland but do not pay myself a salary, so the only costs to the business are web hosting and occasional hardware purchases (computers, cameras).

I started this as a project for personal interest; at the time I was working as a software engineer developing financial trading software. Smart Shooter was a good way to develop something that covered both my interests in graphics programming and digital photography, to alleviate the borebom from my day job.

So for me its been successful, its still an pleasureable hobby, allows me an excuse to play around with the latest cameras, and brings in some pocket money. It doesn’t generate enough revenue that I could quit my main job, but the possibilities could be there if situations change.

payment gateway

I am running a complete payment gateway that supports VISA and MasterCard and mobile payments by SMS.
The name of the service is: https://www.bizify.me

For an introduction to the service: https://www.bizify.me/hacker-news/

asterisk consulting

I sell Asterisk reporting sw for win @samreports.com. It makes about $1000 a month in revenues. I also work as iOS developer for the man. I have a free iOS app on the AppStore (HRTecaj), soon to be commercial, when I add ATMs. I was Asterisk integrator, and learned a lot about the system, made software to present call reports in customisable and pleasant way. SAMReports has been selling, consistently, for 4 years. I made a few updates, but now I’m working on a major update.

sell books

I run http://lsathacks.com, and have a related book series
I sell e-books on my site and through affiliates, and sell print books on amazon. All told I make around $3,000 a month in passive revenues. I also make $4000-$5000 more in tutoring revenues.

However, the site is fairly new (I just sold the books through affiliates/print previously). As I grow the site I expect I may be able to get over $10,000 per month passive.

The LSAT is an admission exam for American and Canadian law schools. My materials/lessons teach people how to do better on it.

radio community

I own and operate http://www.radioreference.com and http://www.broadcastify.com. I do all the development, business management, and support.
I have a team of community volunteers that do a lot of day to day moderation and member management.

I got started simply building a set of community resources for the radio communications and hobbyist market.

We’re very profitable and these businesses provide the majority of my family’s income.

electricain calculator pro

I developed the Electrician Calculator Pro, a National Electrical Code compliant calculator for engineers, electricians, lighting designers, etc:
http://www.electriciancalculator.com

I first created the Android version about 3 years ago, then the iOS version about 1 year ago. It currently makes just enough to cover some bills, although I believe it has a greater potential. I’m currently looking for ways to make this a recurring revenue stream instead of a one time payment gig.

vlad studio – wallpapers

I’ve been running http://www.vladstudio.com (where I publish my wallpapers and other stuff) for several years, and for quite some time, it was my primary source of income. Unusual, because my premium accounts are not really a “product”, but just a way to “like” or “donate”.

m3u editor

Running a profitable SAAS has been my dream from the moment I wrote my first line of code.
Here on HN and IndieHackers I’ve always looked up to the people who pay their bills with recurring revenue from their tools.

I’ve tried, many times, to do the same, without much success. A couple of rather successful HN pitches, but none of my projects ever even paid me a beer (let alone my rent).

Until this month! Last year I built myself and my girlfriend a tool. Even though I did build it for other people to use it, I had never thought someone actually would. Long story short, half a year later I provide my service to more than 5000 (fully organic) users.

This month is the first month in which revenue is high enough to pay my rent with it. Disclaimer: I share my rent with my girlfriend, but it does sound cool to say.

Looking back at the proces, it does match with a lot of other success stories I read over the years in the HN community. The main lesson which I can now confirm: build something that scratches your own itch.

So… Thanks you guys, for keeping me motivated and inspired.

Gardening app

My only successful product to this date is an app I built because my wife asked me to. It is in an non-technical domain which I knew nothing about. I thought it was rather non-promising, but, since it was a pet-peeve of hers, I gave it a try.

It was an awesome (and very bonding) experience – she explained me the problem(s), and I tried to simplify and structure it (didn’t think gardening could be so complicated). Both of us were in their respective element, and from back and forth an app was forged.

Ref

  1. https://news.ycombinator.com/item?id=21332072
  2. https://news.ycombinator.com/item?id=19701783
  3. https://news.ycombinator.com/item?id=22098425

在 IPython 中自动重新导入包

在使用 IPython 交互性测试编写的函数的时候,可以打开自动重新导入包的功能,这样每次保存后就可以直接测试了。

In [1]: %load_ext autoreload

In [2]: %autoreload 2

其中三个数字的含义是:

  • %autoreload 0 – 关闭自动重新导入
  • %autoreload 1 – 只在 import 语句重新导入
  • %autoreload 2 – 调用的时候自动重新导入

如果想要在 IPython 中自动启用

$ ipython profile create
$ vim ~/.ipython/profile_default/ipython_config.py
c.InteractiveShellApp.extensions = ["autoreload"]
c.InteractiveShellApp.exec_lines = ["%autoreload 2"]

面试刷题总结(七) – 树和图

图的表示方法

标准的表示方法应该是邻接表。在邻接表中我们使用链表来表示相邻节点。

任意优先搜索(Whatever First Search)

这是 Jeff Erickson 在书中提到的搜索算法框架,一个框架就综合了所有遍历算法。

树的遍历实际上和图的遍历完全一样,只是不需要标记有没有访问过当前节点。

WhateverFirstSearch(s):
  把 s 放入 bag
  while bag 非空:
    从 bag 取出 v
    if v 未标记:
      标记 v
      for 每个边 vw:
        把 w 放入 bag 中

如果 bag 的算法选用 stack,那么就可以实现深度优先遍历,如果选用 queue 就可以实现广度优先遍历。

如果选用 priority queue,那么就可以实现最优优先遍历。

  1. 如果我们使用每个边作为排序依据,那么就可以得到最小生成树,也就是传说中的 Prim 算法。
  2. 如果我们使用 dist(v) + w(v->w) 作为排序依据,那么就得到了传说中的 Dijkstra 算法。其中 dist(v) 为从源点 s -> v 的距离。
  3. 未完待续

对于没有连通的图,我们还可以使用 WFSALL 来遍历所有节点

WFSALL(G):
  for 所有节点 v:
    取消标记 v
  for 所有节点 v:
    if v 未标记:
      WhateverFirstSearch(v)

深度优先搜索

深度优先搜索实际上就是上面的 任意优先搜索 算法的特例化

DFS(v):
  标记 v
  PreVisit(v)
  for 每个边 vw:
    if w 未标记:
      parent(w) <- v
      DFS(w)
  PostVisit(v)

其中的 PreVisit 和 PostVisit 就是我们可以插入的目标函数,通过改变这两个函数就可以实现不同的算法。

拓扑排序

拓扑排序就可以简单地使用深度优先搜索实现,只不过在最后需要把顺序倒过来。

TopologicalSort(G):
  pass

二叉树外部节点总是等于内部节点加 1

解决树问题的思路

树的最大问题在于要从底层叶节点开始思考,而不是自上而下看图。递归是从基础 case 开始向上递归的。一定要画出访问的顺序图。

访问顺序图

  1. 对于任何树的问题,还是优先考虑递归,因为树本身就是一个递归性质的数据结构。
  2. 树还是天然 Devide and Conquer 的,也就是说可以分层左右两个树分别处理,然后合并得到答案。

解树的问题就只有两种方法:

  1. 分治:后序遍历,并通过左右子树和根节点一起解决问题。
        1
      /   \
    2      3
  /  \   +---+
4      5   B
+------+
    A
  1. 遍历:在遍历过程中解决问题,比如记录最大值等。

对于树的题目,到底是迭代解还是递归解呢?

*最好写递归解,比较简单。写迭代性解首先考虑栈。函数调用过程本来就会用到栈使用栈可以模拟递归调用。使用栈还可以把需要反转的操作自动反转。比如在 zigzag 层序遍历的时候。

递归的出口是选 NULL 还是叶子节点?

最好选择 null,具体来说:

  1. 有一个 corner case 是直接就传一个 null 的节点进来,所以要选 null
  2. 叶子节点比较复杂,只要判断 null 的 return 之后结果 ok, 就 null

改变函数签名与参数传递

参考回溯文档中的讲解

常见问题总结

遍历

参考 这里

二叉查找树

一定是用中序遍历来解的

其他常见的树

2-3-4 树

234 树的意思是每个节点的子节点可能有 2、3、4 个,所有的叶节点都在同一深度。

插入

对于 2-节点和 3-节点,显然是比较简单的,我们只要直接插入就行了。对于 4-节点来说,我们不能插入。不过解决方法也很简单,我们把 4-节点分裂,然后把中间节点提到上一级,然后就有两个 2-节点了,这时候就可以插入了。

在自上而下插入的过程中,我们还会把遇到的每一个 4-节点都分裂,这样保证了我们

红黑树

红黑树是为了解决二叉查找树不平衡的问题发明的。

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点永远是黑色的。
  3. 所有的叶子节点都是空节点(即 null),并且是黑色的。
  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点。)
  5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

Null 也算节点,从头到尾都是黑色节点,红色节点只能是内部节点。每条路径都包含相同的黑色节点。

红黑树保证的是没有一个节点长度是其他路径的 2 倍,而不是每一个路径之间的差在常数倍,比如说下面这个树。

为了保证平衡,也就是第 5 个条件,插入的新节点必须是红的,如果恰好插入到了一个黑色节点下面,那就结束了,如果插入到了一个红色节点下面,需要调整。

跳表

跳表显然不是一颗普通意义上的树,但是因为他的时间复杂度和红黑树类似,并且实现起来简单,不容易出 bug,所以很多时候,都把跳表作为红黑树的一个替代来使用,比如在 Redis 中。

B 树

B 树用于基于硬盘的数据库的索引。为什么不直接用二叉树呢?B 树本质上来说就是 2-3-4-n 树,因为硬盘读取相对于内存访问来说实在太慢了,所以减少树的层级有利于提升速度。

更多的树

有些题看起来是树,实际上是利用递归关系的,或者只是利用到了一个性质,但本质上是其他问题

参考资料

  1. https://stomachache007.wordpress.com/2017/03/12/%E4%B9%9D%E7%AB%A0%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-3-binary-tree-divide-conquer/
  2. https://blog.csdn.net/yang_yulei/column/info/easydatastruct
  3. https://web.archive.org/web/20200112020131/https://merunas.io/tree-data-structures/
  4. 《数据结构与算法分析:C 语言描述》
  5. https://stackoverflow.com/questions/8765558/why-dont-we-use-2-3-or-2-3-4-5-trees