superlayone

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

中序遍历BST，设置一个prev指针，记录当前节点中序遍历时的前节点，如果当前节点大于prev节点的值，说明需要调整次序。用一个pair保存prev和cur

superlayone

最长递增子序列 (Longest Increasing Subsequence)

假设存在一个序列data[9] ={ 2，1 ，5 ，3 ，6，4， 8 ，9， 7}，可以看出来它的LIS长度为5。

我们定义一个序列b，然后逐个考察这个序列。 此外，我们用一个变量Len来记录现在最长算到多少了

首先，把data[1]有序地放到b里，令b[1] = 2，就是说当只有1一个数字2的时候，长度为1的LIS的最小末尾是2。这时Len=1

然后，把data[2]有序地放到b里，令b[1] = 1，就是说长度为1的LIS的最小末尾是1，d[1]=2已经没用了，这时Len=1

superlayone

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

时间复杂度为O(n),n代表链表总节点数

	/**
	 * Definition for singly-linked list.
	 * struct ListNode {

superlayone

豌豆荚的北京现场面

高效地、线程安全地实现C++单例

首先我目前只会加锁机制版本的，不知道是不是面试官特意强调的高效版

	//Singleton.h
	class Singleton
	{
		public:
			static Singleton* GetInstance();
 private:

superlayone

##Leetcode-Reverse Linked List II##

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note: Given m, n satisfy the following condition:

superlayone

豌豆荚二面

总的来说还是不错的。以下说说面试的内容（容我吐槽面试官的电话信号太烂了，听不清楚，还有不挂代理的gmail进去太慢了）

1、首先问了我项目上的有些事情，很快就过去了

superlayone

设计一个LRU缓存，支持如下操作

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

思路

哈希表存储映射关系可以在O(1)时间内实现快速查找，利用双向链表存储节点信息，O(1)时间内交换节点。头结点保存最近使用的，尾节点保存最近最少使用的，get时更新最近使用节点（即将当前节点更新至头结点）

superlayone

腾讯2014实习生笔试

1、有四个人，四顶帽子，两个黑色，两个白色，说出自己帽子颜色的释放，否则死亡，每个人只能看前方不能看后方,位置如下：

	>W	
<B	|	>B
|	|	|	>W
|	|	|	|
A	B	C	D

superlayone

一个链表有一个int数据域，一个next指针域，一个random指针域，random要么指向一个随机的node，要么置空，对此链表进行深拷贝

	/**
	 * Definition for singly-linked list with a random pointer.
	 * struct RandomListNode {
	 *     int label;
	 *     RandomListNode *next, *random;
	 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
	 * };

superlayone

Minimum Window Substring

这是宿舍人面试豌豆荚的一道题，正好没做过，拿来做做

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC".