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 is 1 byte, inte
阅读全文

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 从设计之初的想法应该是高效的，反映速度快，因为很多东西都由user space（Micr
阅读全文

中国城市房地产分析

简介 到2018年中国房地产似乎出了大问题，有的地方开始调控政策，海南的限购，西安却开始吸引人才计划，2018年一个季度人口增加30万，3%，房价也随之猛烈上涨。 有的人说房地产要崩盘了，不是政府压着早就破了； 有的人说中国的房地产泡沫不是全局现象，泡沫不大，而且政府控制着不可能破灭，如果政府不控制，涨的更厉害。 政府主流媒体的认为现在买房都是刚需，政府不能让房价迅速上涨。 那么这么多观点究竟谁说的对？ 先分析以下是否是刚需，如果是的话为什么要调控呢？ 刚需指的是需求大，但是供应少。按照市场规律，这时候价格会上涨，供应会随之增加，供应增加以后价格会下降，最终达到一个平衡的状态。所以如果是刚需的话，政府采取的方式应该是提高供应，方法是地方政府批更多，更便宜的地给开发商。但是，政府现在批的地没有增加很多（全国的开工面积是增加的2017 年1.7B平米, 2010年1.6B平米；北京2017年新开工12M平米，2008年11M平米），主要采取的方式是限制贷款，限制购买，和限制价格的三限制政策。 为什么会这样？一种可能是刚需是假的。造成需求大的原因有：人口增长（中国城市化不可避免的，城市人口从10%到60%；资源分配集中在大城市，更多的医疗，学校，工作，基础设施，北京2010年大约20M，现在21M，2000只有13M）；收入增长（收入在过去二十几年里面翻了十倍，有些地方房价也涨了10倍，有的地方涨的更多）；租房价格增长(alternative)（北京租金2016大约71每平米，2018年88每平米， 2008年大约53每平米）。 注意中国的平均数据不能反应各地的实际情况。 拿全国的数据来说，先分析以下需求，首先是人数增长，2013年城镇人口731M, 2017年813M，增长了11%。房地产竣工面积非常稳定大约每年0.7B平米，按照每个城市人均30平米计算，80M的新增人口需要2.4B平米的住房。销售面积每年都超过1B平米，并且统计局表明销售面积不包括二手房，因为期房预售的情况比较普遍，房子还没竣工就卖了。所以等于说这五年卖了超过5B平米的房子，但是需求只有2.4B。 原因之一应该是已有住房的人，想要更多的人均住房面积，住更大的房子。平均到2013年731M的城市人口上每个人增加了3平米，似乎也是合理的。目前城市人均住房面积大约是36平米，2012年32平米，基本和之前估
阅读全文