一道简单的面试题
不知道是不是我引起的话题， 老赵出了个O1的面试题 。
// Please write an sequence list implements the interface with the required
// time complexity described in the comments. The users can add the same
// element as many times as they want, but it doesn't support the null item.
// You can use any types in .NET BCL but cannot use any 3rd party libraries.
// PS: You don't need to consider the multi-threaded environment.
interface IMyList < T > : IEnumerable < T >
{
// O(1)
// Add an item at the beginning of the list.
void AddFirst ( T item );
// O(1)
// Add an item at the end of the list.
void AddLast ( T itme );
// O(1)
// Remove the item from the list. If the list contains multiple
// copies/references of the item, remove one of them.
void Remove ( T item );
// O(1)
// Reverse the list.
void Reverse ();
}
这道题有实用性吗？当然有，因为这题是采用了缓存的思想，在很多代码中经常见到。
这道题我当时的第一反应就是:
insert要O1，那么需要该集合是链表结构。
reverse要O1,那么该集合要符合双向链表的结构。
remove O1，那么需要hash结构保持对相应结点的引用，在删除的时候还要注意不要使得指针断裂。
但是老赵要求能在30分钟内完成，一般15分钟就要完成。
因此我面对的问题是，作为冒牌.NET程序员，我对.NET中的双向链表结构的实现不是很熟悉。
这时有两种选择，自己创建双链表结构，或者查找msdn找到.NET中双链表的实现。
我觉得在30分钟内实现一个双链表完成这道题目对我来说基本上完不成，因为要考虑的事情比较多。因此使用内置数据结构看似是更好的做法。
查找MSDN，我找到了LinkedListNode和LinkedList这两个数据结构，但是我在第一步就发现了问题：
LinkedListNode的Previous属性和Next属性是只读的。我顿时疑惑产生，这样子怎么生成双链表呢？
这时就需要LinkedList了。
这时最开始的实现:
public class MyClass <T> : IMyList <T>
{
bool isReversed = false ;
LinkedList <T> list = new LinkedList <T>();
Dictionary <T, List <T>> dic = new Dictionary <T, List <T>>();
public void AddFirst(T item)
{
if (!isReversed)
{
list.AddFirst(item);
}
else
{
list.AddLast(item);
}
CacheItemInDic(item);
}
private void CacheItemInDic(T item)
{
List <T> sameValueItems;
if (!dic.TryGetValue(item, out sameValueItems))
{
sameValueItems = new List <T>();
}
sameValueItems.Add(item);
}
public void AddLast(T item)
{
if (!isReversed)
{
list.AddLast(item);
}
else
{
list.AddFirst(item);
}
CacheItemInDic(item);
}
public void Remove(T item)
{
T cachedItem;
List <T> sameValueItems;
if (!dic.TryGetValue(item, out sameValueItems))
{
return ;
}
else
{
cachedItem = sameValueItems[0];
}
// 写到这里的时候，突然发现问题
list.Remove(item);
}
public void Reverse()
{
isReversed = !isReversed; ;
}
public IEnumerator <T> GetEnumerator()
{
throw new NotImplementedException ();
}
System.Collections. IEnumerator System.Collections. IEnumerable .GetEnumerator()
{
return GetEnumerator();
}
}
写到这里，我意识到怎么能保证Remove是O1的呢？在链表中要remove一个元素很简单，只要交换一下指针即可。但是.NET中Node的指针是只读的。并且，Remove一个元素要先检查这个元素是否在链表中，而检查这个动作如果只有value的情况下无疑使O(N)复杂度的， 在这里我陷入了思考中……
除非我们缓存的是一个节点而不是value，并且这个节点要能在O(1)时间内判断自己是否属于这个链表。问题来了，怎么判断呢？一个个遍历肯定是不行的，只有加入这个节点的时候，同时赋给这个节点一个指向这个节点的所属链表的指针才行。.NET中的LinkedList是不是这个样子的呢？作为一个冒牌.NET程序员还是不清楚，查MSDN吧，万幸，果然每个Node在插入LinkedList的时候都附上了相应的指针，也就是Node的list属性。
这样我之前写的代码就错误了，做出如下修改一下:
public class MyClass <T> : IMyList <T>
{
bool isReversed = false ;
LinkedList <T> list = new LinkedList <T>();
Dictionary <T, List < LinkedListNode <T> >> dic = new Dictionary <T, List < LinkedListNode <T>>>();
public void AddFirst(T item)
{
LinkedListNode <T> node ;
if (!isReversed)
{
node = list.AddFirst(item);
}
else
{
node = list.AddLast(item);
}
CacheItemInDic(item, node );
}
private void CacheItemInDic(T item, LinkedListNode <T> node )
{
List < LinkedListNode <T>> sameValueNodes;
if (!dic.TryGetValue(item, out sameValueNodes))
{
sameValueNodes = new List < LinkedListNode <T>>();
}
sameValueNodes.Add(node);
}
public void AddLast(T item)
{
LinkedListNode <T> node;
if (!isReversed)
{
node = list.AddLast(item);
}
else
{
node = list.AddFirst(item);
}
CacheItemInDic(item, node);
}
public void Remove(T item)
{
LinkedListNode <T> cachedNode;
List < LinkedListNode <T> > sameValueNodes;
if (!dic.TryGetValue(item, out sameValueNodes))
{
return ;
}
else
{
cachedNode = sameValueNodes[0];
}
if (cachedNode == null ) return ;
list.Remove(cachedNode);
}
public void Reverse()
{
isReversed = !isReversed; ;
}
public IEnumerator <T> GetEnumerator()
{
LinkedListNode <T> node;
if (!isReversed)
node = list.First;
else
node = list.Last;
while ( true )
{
if (node == null )
yield break ;
yield return node.Value;
if (!isReversed)
node = node.Next;
else
node = node.Previous;
}
}
System.Collections. IEnumerator System.Collections. IEnumerable .GetEnumerator()
{
return GetEnumerator();
}
}
写了点代码测试下:
static void Main()
{
MyClass < int > collection = new MyClass < int >();
for ( int i = 1; i < 11; i++)
{
if (i%2 ==0)
collection.AddFirst(i);
else
collection.AddLast(i);
}
foreach ( var i in collection)
{
Console .WriteLine(i);
}
collection.Reverse();
foreach ( var i in collection)
{
Console .WriteLine(i);
}
}
最终，边查边改，我花了一个多小时才完成这道简单的题目。按老赵的说法，就是“薪水是0"的水平。好吧，被打击了。但是博客还是要继续写下去的。
数据结构与算法
一道简单的面试题，据说90%人不能在30分钟内做出来，我也是。
摘要: 不知道是不是我引起的话题，老赵出了个O1的面试题。// Please write an sequence list implements the interface with the required// time complexity described in the comments. The users can add the same// element as many times as they want, but it doesn't support the null item.// You can use any types in .NET BCL but cannot 阅读全文
posted @ 2012-03-30 12:13 浪雪 阅读(1570) | 评论 (4) 编辑
Dictionary源码解析（未完成）
摘要: private void Insert(TKey key, TValue value, bool add){ if (key == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } if (this.buckets == null) { this.Initialize(0); } int num = this.comparer.GetHashCode(key) & 2147483647; int num2 = num % t... 阅读全文
posted @ 2012-02-21 20:28 浪雪 阅读(32) | 评论 (0) 编辑
基本有序，一次只能确定一个(未完成)
摘要: 提纲:1.在一次比较过程中，我们能确定位置的只有一个数。但是我们能使得数组中的元素“基本有序"基于比较的排序算法，一次只能得出一个结果。最好的情况就是把问题分解成两个1/2的规模，而不是一个1/4,另一个3/4。因为你无法知道你是否处于另一个糟糕的状况之中。因为一次比较只能得出 “大于” 或者 “小于”两个结果，所以底数为log2,而问题的所有解的规模最初是n，当第一轮排序完成后，未排序的元素是n-1个，同理，第二轮排序完成后剩下的元素是n-2个，以此类推。这种等差数列相乘用符号表示就是n!。所以基于比较的排序最好的情况就是log(n!)，近似于O(nlogn)2.拿快速排序法举例。 阅读全文
posted @ 2012-02-16 20:37 浪雪 阅读(13) | 评论 (0) 编辑
数学归纳法与递归还有斐波那契数列(未完成)
摘要: 提纲1.n和n+1的关系结论必须由一个整数n决定结论的定义必须明确，这样我们才可能检验由第n项过渡到下一项也就是n+1的时候，结论是否还能成立。我们期望得到这样一个结果：只要这个结论对n成立，那么对n+1也成立。所以我们要做的有两件事，一是证实结论在取某个值时是正确的，二就是证实取下一个值也是正确的。我们考虑，如果取某个值，那么这个值取什么数好呢？很显然，什么事情我们都希望从最简单的情况出发，因此取1就是我们的选择，也就是n=1。因此n=1时成立，所以n+=1,也就是n=2的时候也成立，同理，n=3的时候也成立。从任意整数过渡到下一个，我们就普遍的证明了这个结论。普遍的证明说明已经遍历了所有情 阅读全文
posted @ 2012-02-16 20:34 浪雪 阅读(21) | 评论 (0) 编辑
从两个数组中查找相同的数字谈Hashtable
摘要: 假设数组A有n个元素，数组B有n个元素。看到这种题的时候，我们最直观的就是通过两层for循环来对比每个数组中的数字。因此A数组中的每个元素都会和B数组中的每个元素对比过一次，所以总共要对比的次数是n个n相加（或者是n个m相加)，也就是n2(或者为n x m).因此我们想能不能有更快的方法呢？让其中一个数组的查找的时间复杂度不再是O(n)就可以了。也就是我们在这个数组中查找一个数，不是通过遍历的方式。但是不是通过遍历的方式能在一个数组中找到一个自己想要的数吗？看起来必须有什么特殊的方法才行。我们再回过头来看数组是什么组成的：1.下标2.下标所代表的元素我们按位置查找时，数组的速度是O(1)的，因 阅读全文
posted @ 2012-02-15 23:25 浪雪 阅读(1257) | 评论 (2) 编辑
由两个单链表的公共节点谈正确理解概念的重要性(未完成)
摘要: 1.X型，Y型，V型？提纲:对单链表的"单"字的理解。正确画图给我们审视已知条件的帮助。 阅读全文
posted @ 2012-02-14 13:10 浪雪 阅读(11) | 评论 (0) 编辑
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息