h*****n
发帖数: 209 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: hanuman (天竺神猴), 信区: Programming
标 题: 为什么Cache LRU多用doubly linked list而不是single linked list来实现呢?
发信站: BBS 未名空间站 (Thu Oct 23 16:56:37 2014, 美东)
在Cache LRU实现的时候，为什么都是用doubly linked list而不是single linked
list呢？
请大牛赐教。 |
|
h*****n
发帖数: 209 | 2 【 以下文字转载自 Programming 讨论区 】
发信人: hanuman (天竺神猴), 信区: Programming
标 题: 为什么Cache LRU多用doubly linked list而不是single linked list来实现呢?
发信站: BBS 未名空间站 (Thu Oct 23 16:56:37 2014, 美东)
在Cache LRU实现的时候，为什么都是用doubly linked list而不是single linked
list呢？
请大牛赐教。 |
|
i**p
发帖数: 902 | 3 It seems impossible to remove a node (and its memory) from a doubly (bi-directions) linked list without a temp variable to help.
Request:
Don't lose the pointer to the list.
Your comments. |
|
i**p
发帖数: 902 | 4 OK, let me change the question like this.
A list with 8 nodes is pointed to the head by a pointer. Is it possible to
remove the 3rd node and its memory without any other variable helping?
the list is a doubly bi-direction linked.
to |
|
x*****0
发帖数: 452 | 5 同问，在Introduction to algorithm 3rd, page 260,
"searching takes constant time
on average. Since insertion takes O(1) worst-case time and deletion takes O(
1) worst-case time when the lists are doubly linked“
除非delete(point_to_x), delete时传入的是指向x的指针。这样就可skip查找x。 |
|
h*****n
发帖数: 209 | 6 在Cache LRU实现的时候，为什么都是用doubly linked list而不是single linked
list呢？
请大牛赐教。 |
|
h*****n
发帖数: 209 | 7 在Cache LRU实现的时候，为什么都是用doubly linked list而不是single linked
list呢？
请大牛赐教。 |
|
L***s
发帖数: 1148 | 8 你的理解是对的。circular doubly linked list
是 circular buffer 这种 ADT 的一种具体实现方式。 |
|
k***t
发帖数: 276 | 9 参照网上的思路写了一个。哪位大拿给Review一下。谢了。
我平时只写C，不用C++。所以可能有初级错误：）
#include
#include // HashMap
#include
using namespace std;
// cache entry
struct Entry {
int v; // dummy structure
};
class LRU {
private:
list > mlist;
unordered_map >::iterator> mht;
int cnt;
const static int MAX_SIZE = 10000;
public:
LRU () {cnt=0;}
~LRU () {}
void addEntry (string mURL, Entry mEntry) {
mlist.push_fron... 阅读全帖
|
|
l*****o
发帖数: 214 | 10 一点想法，不知到对不对：
用doubly linked list
step 1. scan text, if in the target word set, add to doubly linked list,
until the doubly linked list has all the target words: you get [word1, word1
, word2, word1, word1, word3]
step 2. from the end of the linked list, go backwards, until find all the
words in target word set, remove the words before, and the result is a
probably shorter list with first element A: you get [word2, word1, word1,
word3], and record the span
step 3. keep scanning the text, push wor... 阅读全帖 |
|
l*****g
发帖数: 685 | 11 用doubly linked list + hashtable, 找时间最久的object和任意一个object, 时间都
是O(1)
用min-heap当然也可以，不过你得给每个object加额外的timestamp，需要对timestamp
做很多比较操作
另外，因为min-heap里的element的index一直在变动，而hashtable却需要存比较固定
的index(或reference)来search, 所以这个min-heap不适合用常用的array来implement
；而只能用tree来implement；那样，跟doubly linked list相比就更没有优势，因为
min-heap的tree node需要保存
3个指针(left, right, parent).
综合起来，还是doubly linked list简单的多 |
|
s*********s
发帖数: 140 | 12 想请教一下数据结构的选择。如果用java，是选择API已有的LinkedList, 还是自己实
现一个Doubly linked list? 如果用Singly LinkedList, replacement的时间就不是O(
1).如果用Doubly LinkedList, 45min面试时间又怕不够。面试官一般来说会直接让你
用Doubly LinkedList吗？ |
|
f**********t
发帖数: 1001 | 13 // Given a doubly linked list with a data item, a previous and a next ptr
along with another pointer "child" that may point to the head of another
doubly linked list of same type(it will lead to a general tree type of
structure) or it may be null. Flatten the tree into a linked list... minimum
space and time complexity(order n). The doubly linked lists's head and tail
are given.
struct List;
struct ListNode {
char val;
ListNode *pre, *next;
List *child;
};
struct List {
ListNode *head, *... 阅读全帖 |
|
f*******w
发帖数: 1243 | 14 背景：EE 非名校PhD 无线通信方向，预计夏天毕业，两次实习经历（12年Broadcom，
13年Amazon）
2月的时候发现时间紧迫，开始锁定SDE的目标狂投简历……真正意义上的海投，大大小
小有近百家吧，基本没有找人refer。偶尔在版上看到有人帮忙refer的时候也会问一下
，不过好像都被简历拒了- -
所有面经放上……
Bloomberg:
02/21 电面阿三，没有写具体code，都是说思路
Why bloomberg?
Mention and describe one of your projects. What is your role on this project?
Polymorphism in C++, how to implement virtual functions (vtable), different
types of polymorphisms (dynamic/static).
Two sum (with or without extra memory)
Kth node to the last (Linked List)
Implement m... 阅读全帖 |
|
S*******C
发帖数: 822 | 15 public class LRUCache {
private int capacity;
//key : key, value : node
private Map map;
private Node prehead = new Node(-1, -1);
private Node posttail = new Node(10, 10);
public LRUCache(int capacity) {
map = new HashMap<>(capacity);
this.capacity = capacity;
connect(prehead, posttail);
}
public int get(int key) {
synchronized(map) {
Node p = map.get(key);
if(p == null) {
retur... 阅读全帖 |
|
s******e
发帖数: 493 | 16 Basically there are three ways to create singleton: lazy init, eager init
and holder pattern.
Both of eager init and holder pattern depend on JVM class loading process to
guarantee the singleton. The holder pattern was introduced in trying to
avoid
creating a singleton unnecessarily in the case of the eager
initialization.
For lazy init, no matter using doubly checked lock or not, you can both
create a singleton if you use it correctly. The reason trying to introduce
doubly checked lock was to r... 阅读全帖 |
|
发帖数: 1 | 17 可能这个题目的作者也没有想清楚,好像只要选一个BST就可以了?
doubly linked list能做到 initialize是nlogn(排序),剩下CRUD都是log n因为doubly
linked list可以binary search
关于架构,这个只是考虑到如果是maintain多个node(原题说只考虑一个node,one-to-
many),因为node之间的out-going edges是独立的,所以可以每个node都独立maintain一
个红黑树或者doubly linked list,只有删除node的时候需要互相通讯一下. |
|
j**l
发帖数: 2911 | 18 要求in place就地转换
１．从BST转为sorted doubly-linked list可以用类似中序遍历的递归方法做，结果唯
一。
２．那么反过来，从sorted doubly-linked list转换为一棵BST, 结果不唯一，该如何
做才能尽可能的保证BST是平衡的呢(minimal height)？如果是从sorted array转为最
小高度的平衡BST，有类似binary search的思想。对双向链表，有什么好的思路？
1的白板代码如下
void TreeToList(Tree* root, Tree* &head, Tree* &tail)
{
// This is a very special case
if (root == NULL)
{
head = NULL;
tail = NULL;
return;
}
Tree* temp_head;
Tree* temp_tail;
if (root->left != NULL)
{
|
|
h**********d
发帖数: 4313 | 19 我叫着这题和cache那题不差不多吗，就用hashtable + doubly linked list就可以实
现insert, delete in O(1)
至于getRandom(), 可以在insert的时候吧hashcode再用一个数组或者list存下来，然
后生产一个random数，在数组里找到相应的hashcode，再去hashtable里面，和doubly
linked list里面删？ |
|
M7
发帖数: 219 | 20 来自主题: JobHunting版 - MS面经。 非名校CS PHD, 5月毕业。去年12月网投的，一周后说要电面。
电面：
1. 博士做什么题目？最挑战的部分是什么？
2. If you started this (your research) over, what do you want to do first fo
r the same project?
3. What is a good program?
4. Why do you rate your preferences for SDE, SDET and PM. 我当时perfer SDE。
面试官要我be flexible.
5. A game is about to ship, how do you want to to test it?
6. Given a year and unlimited funding, what do you want to do?
没有coding问题。说是三到四周给回音。结果两天后（而且是在周末）recruiter就说通
过了。要onsite SDET。
Onsite:
10:30和recruiter聊了一下: why MS?
11... 阅读全帖 |
|
g**e
发帖数: 6127 | 21 convert bst to single linked list in-place感觉比convert成doubly linked list
还难一些。tree rotation感觉写起来挺麻烦的，不知道有没有简洁的方法？转doubly
linked list写递归很容易。
用链表的排序来建立 BST. |
|
H****s
发帖数: 247 | 22 std::list不能有loop而且std::list是doubly linked list, how could a doubly
linked list contains a cycle if the begin() is not equal to end()? |
|
j********2
发帖数: 82 | 23 Sorry. It is like this:
Given a doubly linked list, besides the next and previous pointers, each
element has a child pointer, which may or may not point to a separate doubly
linked list. These child lists may have one or more children of their own.
Now do the following:
a. Flattern this multilevel data structure
b. Restore the original structure from the flatterned structure
e.g.
L1 --> L2 --> L3 --> L7 --> L8
|
v
L4 --> L5-->L6... 阅读全帖 |
|
x*********3
发帖数: 1438 | 24 没区别，就是问如果要prev咋办，给了几种方法，比如，vector, stack, doubly
linked list。
然后他说那用doubly linked list 试试？另开一个linked list，把tree搞进去，prev
, next就都出来了。
很简单的，算最容易的一次面试了。 |
|
D**********e
发帖数: 147 | 25 Aquarius Horoscope for November 2010
By Susan Miller
Every once in awhile in life you reach a moment in time when everything you
have done in your career over
past months and years begins to crystallize into something very big and very
exciting. You are reaching that
point now in November, dear Aquarius. As the month begins, planets are
migrating into your tenth house
of fame and honors. Your first clue that your status and fortunes may be
ready to rise substantially could
come on November 4, wh... 阅读全帖 |
|
t***y
发帖数: 182 | 26 source:
http://astrologyzone.com/forecasts/monthly/capricorn_full.php
Most people think of January as the time for a fresh start, but for you, it'
s not only the New Year, but also birthday time, making this a doubly
exciting important time. Capricorns like to give their lives form, goals,
and structure, and you want to map out an outline of a plan, but over the
past two years, you've experienced so many twists and turns, partly due to
the eclipses in Cancer and Capricorn, that you aren't sure i... 阅读全帖 |
|
y**t
发帖数: 50 | 27 I think here s/he refers to the so called "doubly connected domain"
in complex analysis,am I right?If so,it just means how manys holes
in the domain.Doubly connected contains a hole,multiply connected
contain more, etc.
In algebraic topology,it's called n-connectedness just as visionc said,
the lower homotopy groups are zero. |
|
x***u
发帖数: 336 | 28 the matrix with your desired property is called doubly stochastic matrix.
First for an arbitrary matrix you can't always be able to normalize it, say,
the first column is all 1's, and all the other entries are 0.
if you just want to find a doubly stochastic matrix close to the original one,
There is a simple algorithm to do that:
randomly pick up a row and normalize it
ramdomly pick up a column and normalize it
repeat until the matrix is close to what you want.
This algorithm is proved to be con |
|
c******s
发帖数: 693 | 29 你一是no point
二是喜欢装逼
三是错的一塌糊涂
Sir Isaac Newton (1643–1727) invented the principle of the doubly
reflecting navigation instrument (a reflecting quadrant - see Octant
(instrument)), but never published it. Two men independently developed the
octant around 1730: John Hadley (1682–1744), an English mathematician, and
Thomas Godfrey (1704–1749), a glazier in Philadelphia. The octant and
later the sextant, replaced the Davis quadrant as the main instrument for
navigation.
Zheng He (1371–1433), Chinese m... 阅读全帖 |
|
H****g
发帖数: 14447 | 30 1. 证实了毛泽东1975年写给周恩来这首诗。
《江山靠谁守·诉衷情》
当年忠贞为国筹，
何曾怕断头？
如今天下红遍，
江山靠谁守？
业未竟，
身躯倦，
鬓已秋。
你我之辈，
忍将夙愿，
付与东流？
2. 证实了1976年之前根本没有所谓饿死三千万或者大饥荒之说。
3. 毛泽东1975年的担心，或者说1964年的担心，都变成了现实。
4. 毛泽东唯一的遗产就是留给人民的造反精神，终将成燎原之火。
Mao Tse-Tung: Father of Chinese Revolution
By Fox Butterfield
Special to The New York Times
HONG KONG, Sept. 9--Mao Tse-tung, who began as an obscure peasant, died one
of history's great revolutionary figures.
Born at a time when China was wracked by civil strife, beset with terrible
poverty and enc... 阅读全帖 |
|
w********s
发帖数: 343 | 31 http://www.asiasentinel.com/index.php?option=com_content&task=v
The dispute between China and the Philippines over ownership of the rocks
and reefs variously known as Scarborough Shoal/Panatag Shoal/Huangyan Island
is at one level very petty. But at another it demonstrates what can best be
described blatantly racist bravado on the part of Beijing.
Manila would do well to learn up some of its own pre-Spanish history so as
to better expose the arrogance of a nation which regards other, non-Han
peo... 阅读全帖 |
|
h*********n
发帖数: 11319 | 32 Any race based policy crosses the red line. Policies as important as
education/employment, doubly so. |
|
b********n
发帖数: 38600 | 33 What is doubly disgusting is that countries like Poland, Lithuania and
Romania, which claimed to have suffered under the Soviet "jackboot", are now
doing the same things they are accusing the KGB of doing in the past. Talk
about hypocrisy. And next week, the US and the EU will continue lecturing
the world about "human rights". |
|
c*****g
发帖数: 21627 | 34 EAD cards for H4 visa holders: USCIS needs to give it to all of them
By Sujeet Rajan
It’s heartening that in all the imbroglio and limbo
over illegal immigration, the US government finally took action after years
to help legal immigrants, who form the real backbone of this country: it’s
done the right thing by granting work permits, EAD cards, to H4 visa holders
, beginning late summer of this year.Read the story on EAD cards to be
issued to H4 visa holders, effective May 26, 2015:
It’s apparent... 阅读全帖 |
|
b********n
发帖数: 38600 | 35 Netanyahu's actions illustrate something that George Washington said in his
Farewell Address:
http://avalon.law.yale.edu/18th_century/washing.asp
"In the execution of such a plan, nothing is more essential than that
permanent, inveterate antipathies against particular nations, and passionate
attachments for others, should be excluded; and that, in place of them,
just and amicable feelings towards all should be cultivated. The nation
which indulges towards another a habitual hatred or a habitual... 阅读全帖 |
|
s*****r
发帖数: 43070 | 36 【 以下文字转载自 JobHunting 讨论区 】
发信人: wsclock (精确), 信区: JobHunting
标 题: F家详细面经，有工作经验被拒(超长慎入)
关键字: facebook,interview
发信站: BBS 未名空间站 (Fri Sep 22 20:45:31 2017, 美东)
简单总结：CS博士，奔5了，申请facebook software engineer，不是headquarter。
onsite后第三天收到据信。估计死在system design上。面试简况如下。详细的在后面。
Screening 和final round头两个都是coding interview，都做到了bug free。题目不
难，即使没刷过题，也容易有思路。唯一不足的是，有一个coding写的代码不是时间复
杂度最低的。虽然后来给出了优化的办法，但是没有时间写优化的代码了。
下一个是system design，感觉不太好。其中一个问题是估计要多少个server，我解答
的时候，最大的失误可能是没有问每秒钟多少个transaction，面试官也没给这个条件
。面试官指出... 阅读全帖 |
|
t**x
发帖数: 20965 | 37 America’s crisis is, in short, a social crisis, not an economic crisis.
最糟糕的是，
美国的天量美元对应的是废铜烂铁的军事装备
和
年久失修的基础设施
加上
不节能不环保不安全的 single family houses
Almost all of the policy discourse in Washington DC centers on naïve
attempts to raise the economic growth rate, as if a higher growth rate would
somehow heal the deepening divisions and angst in American society. This
kind of growth-only agenda is doubly wrong-headed.
First, most of the pseudo-elixirs for growth—especially the Republican
Party’s... 阅读全帖 |
|
发帖数: 1 | 38 包括诺贝尔经济学奖得主和前总统顾问在内的1100多名经济学家联名签署了一封公开信
，对美国总统Trump在贸易问题上的强硬态度施以警告。这份预定于周四公布的信函许
多段落直接引用了1930年经济学家们给政府的谏言信，告诫美国不要采取大萧条初期时
的那些贸易保护主义措施。
回顾历史，1929年3月胡佛就任美国总统，同年夏天经济出现萧条，为了挽救美国经济
，特别是贫困交加的农民，1930年胡佛签署了贸易保护主义法案--斯姆特霍利关税法案
（Smoot-Hawley Tariff Act）。此后美国经济开始急剧恶化，与景气时相比，GDP跌幅
一度达30%，失业率达到20%以上。1930年5月，1028名经济学家联名上书时任总统胡佛
，希望否决这个法案。迫于党派压力，最终胡佛还是签署了斯姆特霍利关税法案。
By Josh Wingrove • Bloomberg
To some of the biggest voices in U.S. economics, it could be 1930 all over
again.
More than 1,100 economists, i... 阅读全帖 |
|
h*******i
发帖数: 4386 | 39 http://mgv.pku.edu.cn/
饶毅还是所长，现在被米国拒签打脸，好像米华给娃取了假洋鬼子名，mike zhang,
steven wang, kevin huang, 却被米国虐成gay ass一样，doubly 屈辱啊
哈哈 |
|
g********d
发帖数: 4174 | 40 Former Minnesota Senate majority leader Amy Koch has been a vocal opponent
of gay marriage, and in 2009, she tried to amend the Minnesota Constitution
to add language stipulating that “a marriage between a man and a woman is
the only domestic legal union that shall be valid or recognized in Minnesota
.” Because she cares a whole super lot about the sanctity of marriage, and
wished to see it not be taken lightly, or diluted by the gays.
Except! Apparently not her own. Koch was carrying on in secr... 阅读全帖 |
|
l****z
发帖数: 29846 | 41 By DICK MORRIS & EILEEN MCGANN
Published on DickMorris.com
on January 24, 2011
All the public opinion polls now confirm that President Obama has moved up
sharply and significantly in popularity and job approval since he began to
tack toward the center after the November election. Rasmussen and Zogby
both have him over 50% job approval for the first time in almost a year.
The key event was his high-minded speech in the aftermath of the Tucson
shootings and his clear separation from the blame-or... 阅读全帖 |
|
l****z
发帖数: 29846 | 42 By Andrew G. Bostom
Once again a mere flicker -- in this case burning a copy of the Koran in
Florida -- has ignited the inferno of deeply seated infidel-hatred that
pervades the contemporary Muslim world, precipitating violence, death, and
general mayhem amongst our Afghan " allies."
This eruption was hardly pastor Terry Jones' fault. The insane orgy of
murderous Muslim violence in Afghanistan was a direct result of Islamic
doctrine. Jones' simple non-violent act effectively administered a
diag... 阅读全帖 |
|
l****z
发帖数: 29846 | 43 Paul A. Rahe · Feb. 10 at 5:21pm
You have to hand it to Barack Obama. He has unmasked in the most
thoroughgoing way the despotic propensities of the administrative
entitlements state and of the Democratic Party. And now he has done
something similar to the hierarchy of the American Catholic Church. At the
prospect that institutions associated with the Catholic Church would be
required to offer to their employees health insurance covering contraception
and abortifacients, the bishops, priests,... 阅读全帖 |
|
l****z
发帖数: 29846 | 44 Christopher Helman, 04.13.11, 07:10 PM EDT
For all the outcry over GE, a number of corporate titans are paying much
higher rates than the average citizen.
image
In Detail: What The Top 20 U.S. Companies Pay In Taxes
As many Americans finish up their personal tax returns over the next few
days, they'll marvel with horror at how much hard-earned cash gets siphoned
up by the government. At times like this, it's satisfying to have a
corporate bogeyman to hate--like General Electric, which has faced ... 阅读全帖 |
|
l****z
发帖数: 29846 | 45 On the evening of January 11, 1996, while Mitt Romney was in the final years
of his run as the head of Bain Capital, Barack Obama formally joined the
New Party, which was deeply hostile to the mainstream of the Democratic
party and even to American capitalism. In 2008, candidate Obama deceived the
American public about his potentially damaging tie to this third party. The
issue remains as fresh as today’s headlines, as Romney argues that Obama
is trying to move the United States toward European-... 阅读全帖 |
|
l****z
发帖数: 29846 | 46 15-24岁年轻人失业率，法国22%，意大利36%，西班牙51%，这还不包括那些离开学校和
就业市场的人
Young, Educated and Jobless in France
By STEVEN ERLANGER
LILLE, France — Justine Forriez wakes up early to go onto the computer to
look for a job. She calls university friends and contacts; she goes to the
unemployment office every week, though mostly for the companionship, and has
taken a course in job hunting. She has met with 10 different recruiters
since May and sent out 200 résumés.
Ms. Forriez is not poor or disadvantaged, and she holds ... 阅读全帖 |
|
V**3
发帖数: 12756 | 47 Duke rebuke: Professor defiant after school condemns racially charged
remarks
A Duke University professor was defiant after the school last week condemned
his "noxious" and "offensive" words in a letter published in The New York
Times in which he compared African-Americans unfavorably to Asian-Americans.
The school's rebuke came after a student backlash against Political Science
Professor Jerry Hough, 80, whose May 9 letter sought to address racism and
the Baltimore riots. Hough said African-Ame... 阅读全帖 |
|
T*********I
发帖数: 10729 | 48 这个教授真勇敢。也说的真好，
African-Americans don't try to integrate into society, while
Asians “worked doubly hard” to overcome racism instead of blaming it.
Political correctness is getting in the way of thoughtful and frank debate. |
|
s********t
发帖数: 4150 | 49 This was his full remarks:
This editorial is what is wrong. The Democrats are an alliance of
Westchester and Harlem, of Montgomery County and intercity Baltimore.
Westchester and Montgomery get a Citigroup asset stimulus policy that
triples the market. The blacks get a decline in wages after inflation.
But the blacks get symbolic recognition in an utterly incompetent mayor who
handled this so badly from beginning to end that her resignation would be
demanded if she were white.The blacks get awfu... 阅读全帖 |
|
J**X
发帖数: 2433 | 50 这老头也基本上没说对什么。
Asians work doubly hard，没错，但目标不是融合而是好的生活。
起名字那段话更是好笑。
who |
|
