作者归档：在线疯狂

Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.

不得不承认这道题目解决起来非常的巧妙。像大多数难题一样，需要经过非常巧妙的观察才可以用简洁的方式求解。

朴素解法, O(m+n):

将两个数组进行合并，然后寻找第k小的元素可能非常直观。合并操作需要花费额外的O(m + n)的空间。线性运行时间已经很好了，但我们还能再做一些优化吗？

朴素解法的优化, ...

给定一个包含n个元素的数组，怎样从中找出第k大的数。

What is the most efficient algorithm to find the kth smallest element in an array having n elements?

此问题被称为求第k顺序统计量（kth order statistic）。

求解该问题的线性时间算法（既包括确定性算法，也包括非确定性算法）列举如下：

1. Quickselect （快速选择）

2. Median-of-medians (BFPRT) （中位数的中位数）

3. Introselect （内省选择）

4. Unnamed algorithm using soft heaps （使用软堆的未命名算法）

快速选择 ...

我选择PHP，MySQL和WordPress作为我的个人项目平台已经有几年时间了。当你不需要任何别的东西时，事情变得非常简单。只需要建立网站，支付一个主机托管计划，上传文件就大功告成了。即使预算比较紧张也可以找到一些便宜（甚至免费）的网络主机作为起步，在需要时加以扩展。

在我做前端开发的过程中接触过几个不同的技术栈。但无论它是什么——Python，.NET或者别的东西——要使用这些技术做一些严肃的开发还是比较困难的。OK，我已经完成了Codecademy课程，掌握了一些基础知识，现在我想要用Django或者.NET建立我的个人主页。我在哪里可以找到一个价格合理的托管平台？

然后偶然间，我发现了Ghost博客平台，并把我的波兰语 blog搭建在上面。Google了许多Node.js主机，我还不想付钱买一个VPS。最后，我找到了Red Hat（红帽云）的OpenShift。它几乎免费，开源而且强大。简直难以置信。

但很快我发现这并不是一个典型的网络主机。完全理解其工作原理并开始着手有效的使用它需要花费一些时间。但这是值得的。

OpenShift是什么？

大部分关于OpenShift的文字描述提到了术语"PaaS"（platform-as-a-service 平台即服务）和"云"，但它们都没有从一般终端用户的角度描述服务的工作原理。我们换一个角度来加以解释。

想象一个NES终端。或者红白机。如果你是波兰人，你可能会想到Pegasus（一种类似于红白机的电子产品）。

你的终端大概就是一个小盒子，上面有一个可以插入卡带的洞。如果想要玩超级玛丽，只需要把超级玛丽的游戏卡带放在插槽中。想要玩一两圈Micro Machines（微型机器，一种赛车游戏），用另一盘卡带就行了。十分简单。

现在想象一下你有3个任天堂终端。它们每一个都有3个卡槽，你可以放置任何你想要的卡带。这就是OpenShift大概的样子。你放置卡带的洞就叫做gears（齿轮）

每一个应用可能包含许多个放置在齿轮里的卡带。如果你坚持要完全免费，每个应用至多可以使用3个卡带。每一个卡带代表一项特定的工具或者技术——通常是编程环境或者数据库实例。如果你需要WordPress博客，你选择PHP和MySQL卡带。第三个齿轮可以用来放置phpMyAdmin卡带，或者让应用具备可伸缩性。

另外还可以在同一个账号中搭建WordPress博客，Django应用和Redmine实例。你只需要用不同的卡带创建3个应用就行。

你是说：可伸缩？

齿轮可以是小型、中型或者大型。小齿轮在免费计划中就可以使用，包含1GB的磁盘空间，512MB的内存和无限制的带宽。对我来说这足够运行我的大部分站点项目了。但是如果用户达到上万级别这可能不太够用。

这时候可伸缩性就能够派上用场了。

如果你将应用设置为可伸缩，OpenShift将其放在一个HAProxy实例的代理之后。它监控网络流量并在需要时自动在另一个齿轮里克隆一个卡带，从而可以应付大规模的访问。当网络流量回到正常水平时，空闲的卡带会被自动销毁。就这么简单。

免费？但是真的，真的免费吗？

现在有3个计划可供使用，并且其中的2个是免费的。OpenShift免费版本限制为3个小齿轮的3个应用。OpenShift青铜版几乎和OpenShift免费版一样，外加可以使用中型和大型齿轮（至多16个）。如果需要全功能和专业支持，你可以使用OpenShift白银版，20美元/每月，外加标准齿轮限制之外的费用。

这就是全部内容吗？

不，我们还没有讲完。还有许多令人兴奋的东西呢。

使用OpenShift是一个不同于传统网络主机的崭新体验。它绝对是一个可以撰写很多博客的主题，并且我会在将来描述更多的内容。与此同时，你可以自己尝试一下OpenShift。另外，可以阅读一下Katie Miller 和 Steven Citron-Pousty编写的电子书，包含了你需要了解的所有基础知识。另外还可以访问OpenShift团队的推特。

原文链接：http://lukesays.com/openshift-just-not-another-hosting-platform

题目描述：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], ...

Implement the reversal of a singly linked list iteratively and recursively.

链表逆置既可以用迭代实现也可以使用递归实现。在我看来，迭代法应该比其递归形式的等价实现更加高效，内存开销更小。（试想对一个包含百万个元素的链表执行递归的逆置操作!很快栈空间就会用尽）

递归实现的代码行数更少，但是要想把代码写对会比较困难。另一方面，迭代实现代码行数较多但是比较容易验证。

1) 迭代实现:

void reverse(Node*& head) {
  if (!head) return;
  Node* prev = NULL;
  Node* curr = head;
  while (curr) {
    Node* next = curr->next;
    curr->next = prev; ...