Data Structure Review(1)

Triangle Array:
Assume location (i, j,k)

The first case 0<=i

One example of array is

0 1 2| 0 1 3| 0 1 4
0 2 3 0 2 4
1 2 3 0 3 4
1 2 4
1 3 4
2 3 4

The first element of a column is (0, 1, k)

We have to go through k choose 3 elements to reach the point (since the range is from 0 to k-1, after choose the three elements, the order is fixed)
After that is (0,j,k), we have to go through j chose element to reach that
At last (i,j,k) we have to go another i choose i element, So total cost for reaching that point is: k choose 3 + j choose 2 + i choose i


I do not think the triangle array has any advantage

评论

发表评论

此博客中的热门博文

Embedded System interview Question

1. What are static variables? Static variable in a function only remain one copy of itself. Static variable in a module can be used by any function in the module Static function can only be called in its class 2.  What are volatile variables? Volatile variables may change its value unexpectedly in the program. The program will check its value every time, it tries to use it. If a variable is not volatile, the program may keep a copy of the var in its cache. 3. What do you mean by const keyword ? A constant variable is a read only variable. You cant change its value else where except initialization. 4. What is interrupt latency? Interrupt latency is the time between the generation of interrupt and the time for interrupt  handler  to process it. 5. How you can optimize it? We may use polling and message passing for interrupt to handle interrupt immediately. 6. What is size of character, integer, integer pointer, character pointer? The size of character i...
阅读全文

MicroKernel & Exokernel 操作系统未来可能的发展

图片
MicroKernel  可以叫做微内核，有人认为传统的monolithic kernel 提供的东西太多，我们可以给内核减负。 最典型的例子就是L4 micro kernel (图中的kernel)只提供最简单的服务，比如IPC (inter process communication), scheduling, address space  剩下的都交给Server 去处理，Server 类似于传统的monolithic kernel 比如Linux, 但是需要改动,L4 把它改为L4Linux. 源代码修改，此外他们还修改了Windows XP (windows 并非完全的不开源，在授权的情况下可以看到源代码). 修改的目的，很简单：以前Server talks to hardware directly, 现在多加了一层 Kernel (L4),它处理所有的hardware interrupt, 然后作为message 传递给server, server 再传递给software. 比如浏览器process 需要一个network packet。 收到packet 以后,L4 作出interrupt,传给Server(比如L4Linux),Server 再与L4,通过IPC 请求packet内容，L4会map到L4Linux的address space，Server 再传给Software(e.g. Firefox).  再比如page fault（由于内存容量有限，有些内容被暂时swap 到硬盘，application 想用的时候发现不在了，就产生page fault） 产生,首先处理interrupt的是Kernel, Kernel sends IPC to L4Linux, L4Linux从自己manage的physical memory 里面分一个page出来，给application,并更新自己的shadow page table(不是真正的page table) .L4Linux 产生一个返回值告诉L4, 已经完成。L4 updates its true hardware page table. Micro Kernel 从设计之初的想法应该是高效的，反映速度快，因为很多东西都由u...
阅读全文

什么是Recurrent Neural Network

图片
什么是Recurrent Neural Network？ 循环神经网络 / 递归神经网络 ( Recurrent Neural Network )，主要解决的是 序列 类的问题，有时候顺序非常关键。比如，我喜欢苍老师的电影，和苍老师喜欢我的电影，意思完全不同；我想和马云爸爸一样有钱和马云爸爸想和我一样有钱，意思也完全不同。 那么RNN是如何工作的呢？ 最重要的就是这个公式，当前状态由，上一个状态和当前输入而决定 ht 带表当前时刻的隐藏状态hidden state, ht-1就是上一个状态的hidden state, xt, 是当前时刻的输入 我    喜欢    星球大战 举个例子，我喜欢星球大战，把这句话，分成三个词，x0 是我，x1是喜欢，x2是星球大战 h0 由初始状态，和x0， "我" 来决定 h1  就由h0和x1"喜欢"来决定 h2 由h1, 和x2 "星球大战"来决定 ht-1 乘以它的weight Wh 加上 Xt 乘以它的weight Wx 两个相加， 经过激活函数tanh, 最后就得到ht了 Wh, Wx, 都没有下角标t, 所以这两个weight 是由各个时刻共享的 训练的过程就是更新这两个weight的过程，把它们优化成最佳值 刚才讲的是最基础的RNN模型，下面看一下encoder/decoder 模型是如何利用RNN 来对诗的 Encoder/Decoder 顾名思义，由两个部分组成 encoder 部分的输入是已知诗的第一句，举个例子，床 前 明 月 光，五个字， decoder 部分的输入是encoder 的输出，加上自己的上一次输出。 比如说，预测第一个字，因为decoder 自己还没有输出，所以用起始符，来表示自己上一次的输出，加上encoder 处理床前明月光的输出，这样decoder 就输出了，疑这个词 预测第二个字的时候，疑这个字就变成了输入 假设刚才输出不是疑这个字，输出了低这个字，那么预测第二个字的时候，低就变成了输入 假设预测第五个字输出是霜，预测第六个字的时候，霜变成了输入，输出是终止符，表示不用...
阅读全文