l*****a
发帖数: 14598 | 1 1)u want to use this pointer to delete this node
2) u need to adjust its previous node and next node to make sure that
they have no relationship with this node
then u can delete this node
3) after u delete this node use this pointer, how can u let it point to the
others?
now u can't use its pre/next node to delete this node as well.
so what u said is a paradox
we |
|
i**p
发帖数: 902 | 2 So you indirectly say "no" to the question.
But I will say it is possible.
the |
|
i**p
发帖数: 902 | 3 Here is my answer.
move the pointer, say P pointing to the 2nd node, the one before the removed
one.
P->next = p->next->next;
free(P->next->Pre);
P->next->pre = p; |
|
h*****f
发帖数: 248 | 4 If it is a doubly linked list, you can insert at O(n) and check the previous
and next nodes to see whether the new node can be merged. |
|
h*****f
发帖数: 248 | 5 If it is a doubly linked list, you can insert at O(n) and check the previous
and next nodes to see whether the new node can be merged. |
|
c*********t
发帖数: 2921 | 6 是不是Java里的list,和C++ STL里的list都是doubly linked list?
谢谢！ |
|
s******o
发帖数: 2233 | 7 stl::list is doubly-linked list |
|
|
l*****a
发帖数: 14598 | 9 来自主题: JobHunting版 - a电面面经 第二题 hash_map+doubly linked list
第三题是OOD |
|
k****i
发帖数: 552 | 10 in the array, keep an extra doubly link pointing to the next item being
added, and the previous one.
every time you delete, update the links.
Not sure if that's what the interview wants.
c |
|
h****n
发帖数: 1093 | 11 第一次：
1)如何设计系统去处理很多的user requests。
cache，load balance？
2)implement LRU(least recently used) cache.
hash+doubly linked list？
第二次：
1）1-100的整数，有一个数出现一次，其余的数出现两次。找到仅出现一次的那个数。
XOR？
2）找到输入数组中所有的pair which sum up to a given value。要求考虑数重复
出现的情况。现在发现自己的程序有bug。
two pointers？
3）hashset vs. hashtable. 不熟悉，就回答了对hash的理解。
set没有value？
总体感觉不难。对interviewers感觉比较舒服。希望能拿到onsite。 |
|
h****n
发帖数: 1093 | 12 必须是doubly linked list，否则无法在O（1）内做更新和删除操作
仅出现两次的话也一样做，因为数有范围，所以你把输入和1-100这些数做XOR，剩下的
那个数就是出现两次的数了
你这个bug是面试官指出来的么，因为2 sum题一般都是假设数都是不一样的
user
target |
|
z********i
发帖数: 568 | 13 这个有意思。doubly linked list可以O（1）内作删除吗？需要线性时间去找到要删除
的元素吧？
如果每个数都出现一次，这个方法可行。如果有的数没有出现，会有麻烦。我是用flag
数组作的。
Bug是我后来想到的。我没有用hash，是先sort，再用两个index一前一后开始找。 |
|
y***u
发帖数: 174 | 14 直接上java的doubly linked hashmap吧。 |
|
G****A
发帖数: 4160 | 15 来自主题: JobHunting版 - BB 电面 how about a queue using doubly-linked list?
push --> O(1)
pop --> O(1)
traverse --> O(n) |
|
c********t
发帖数: 5706 | 16 大侠说说对于链表的quick sort，doubly 有什么意义？ |
|
e******i
发帖数: 106 | 17 看了点资料，用JAVA写的，直接extend LinkedHashMap或直接用，面试会要求你写个
doubly linked list 和hashmap来implement么。 |
|
c********t
发帖数: 5706 | 18 啥是LRU? 为啥要用doubly linked list，而不用arraylist? |
|
x******a
发帖数: 6336 | 19 ／／main（）
#include
#include
#include "linkedlist.h"
int main()
{
LinkedList myList(5, "luke");
Iterator myIterator=myList.begin();
myList.insert(myIterator, "leia");
myIterator.forward();
myList.erase(myIterator);
myList.insert(myIterator, "chewbca"); 《＝＝＝＝＝＝出问题。
myList[2]="han";
for (int i=0; i
std::cout<
}
myList.insert(myIterator, "chewbca"); 《＝＝＝＝＝＝出问题。
这一句运行起来ta... 阅读全帖 |
|
|
x******a
发帖数: 6336 | 21 发现问题出现在这两行，
myList.erase(myIterator);
myList.insert(myIterator, "chewbca");
我先通过iterator删除一个元素，然后再通过这个interator插入一个元素好象不work
。 如果iterator往前再往后挪一下就work了，是不是删除元素影响到iterator了？ |
|
c********t
发帖数: 5706 | 22 you are not supposed to use iterator to insert or delete element;
work |
|
l*********8
发帖数: 4642 | 23 myIterator = myList.erase(myIterator);
work |
|
x******a
发帖数: 6336 | 24 Thanks a lot! it worked.
再请教一个问题：我想历遍一个通过frontinsert生成的linkedlist，为什么看不到第
一个insert的元素？谢谢
#include
#include "singlylinkedlist.h"
int main(int argc, const char * argv[])
{
SingleLinkedList aList;
int i=0;
while(i<10){
aList.firstInsert(i);
++i;
}
aList.traverse();
}
输出是
9 8 7 6 5 4 3 2 1
没有0
template< typename T> class ListElement;
template< typename T> class SingleLinkedList;
template
class ListElement{
public:
ListElement(cons... 阅读全帖 |
|
l*********8
发帖数: 4642 | 25 traverse函数里
while (pt!=NULL) { |
|
p*****p
发帖数: 379 | 26 不是面经，只是讨论一下
1. sort a doubly linked list (say, LinkedList in Java)
2. find the next bigger integer (e.g. 5436->5463)
此题肯定有很多质疑，但是只要列出合理的，你认为需要的assumption都可以
3. create a binary tree from the sums of an array
例子（底层数量一定是2的幂）：
3 -5 4 -6
结果
-4
-2 -2
3 -5 4 -6
（就是两两求和） |
|
l*********8
发帖数: 4642 | 27 1. sort a doubly linked list
我觉得可以用类似quick sort的算法吧？ |
|
s****A
发帖数: 80 | 28 search for a node in a doubly linked circular list
假设只有一个match
node * llist::search(int val){
node *t=head, *p=NULL;
while(t)
{
if (t->data==val) {p=t; break;}
else if(t==head->prev) break;
else t=t->next;
}
return p;
} |
|
c*****a
发帖数: 808 | 29 如果用java list interface，我只懂arraylist, linkedlist
如果arraylist就跟array没区别
linkedlist的话，不清楚是什么implementation,doubly/singly? |
|
l****i
发帖数: 2772 | 30 CS fresh PhD. 西雅图，已经接到HR电话，悲剧，攒RP，发面经。
第一轮，2个人。每个人先介绍了几分钟。给题，boggle，先让我分析怎么解决。代码
写到8个方向递归的时候，被打断，说知道我后面会怎么写了，让我先分析这个程度的
复杂度，他们有其他问题要问。最后15分钟，问了一大堆behavior，关于team work的
一类的问题，有矛盾怎么解决，team里有人不干活，team里有人和你不同意见等等，要
求给出一些以前经历的例子。
第二轮，老美白人。开始问了很多object oriented的问题。abstract class，
interface，什么情况下如何选择，inheritance VS composition等等。然后一个
coding，按行统计词频，不难，hashtable解决。 写code的中间，问了很多次复杂度，
基本上我写一行code，他会问一下这一行的复杂度。然后给了一个OOD，一个tree的结
构，计算表达式。然后又出了一题OOD，题目还没解释完，外面的第3轮人就敲门了。
第三轮，南美或者欧洲女。这一轮我很崩溃。第一轮，按层遍历二叉树。直接问我，你... 阅读全帖 |
|
|
y**x
发帖数: 67 | 32 official offer 出来了，实在一般。可能我的级别很低吧,entry level，“associate
” SE。有牛人指点一下怎么negotiate啊，是不是太少了？78k + 6280/year bonus +
1000share/4years。不知道这种转正式的software engineer要多久呢？好了，以下面
经，反正也没签什么NDA，我一股脑全贡献出来啦：
第一次onsite screen。不知为何没有phone screen，可能因为我住的近，他们直接叫
我过去了。一个小时一个白哥。问了how to delete a node from binary search tree
。CLRS上直接有解法。白哥答案要求的很笼统，写个psuedo code就pass了。连找
successor node的具体实现都不用写出来。后来又问不用mutex怎么实现share data
between threads。我说GPU里面有一个东西叫thread synchronizer （我master学位做
了些CUDA编程），白哥没理解，说他会用个queue把thread都qu... 阅读全帖 |
|
m**********4
发帖数: 774 | 33 自己写个DOUBLY LINKEDLIST吧，自己写java能通过的。 |
|
f**********3
发帖数: 295 | 34 大牛，LinkedHashMap就已经搞定了，不用写了... 综合各大牛的意见，貌似还是自己
写个doubly linked list比较靠谱。貌似问题是java的LinkedList把node藏的太深了。
LinkedHashMap |
|
w********s
发帖数: 214 | 35 代码太多啦，不需要写doublelinkedlist 这个类，Java自带的linkedlist本身就是
doubly linked list.
那个key是用来取址的。内存当然要有page address + offset才能retrieve content啦。
每次你refresh key的时候先 remove the key from the linkedlist (keys) then add
it back.
几行应该就可以吧 |
|
r*******n
发帖数: 3020 | 36 用circle doubly-linked list 用一个dummy head就行了 |
|
g*******u
发帖数: 3948 | 37 删除 x 要首先找到 x吧
怎么delete也是O(1)呢 |
|
|
w**z
发帖数: 8232 | 39 O(1) means constant time, irrelevant to the size of the hashtable.
search is O(1), delete is O(1), search + delete is still O(1) |
|
l*****a
发帖数: 14598 | 40 看起来就是要一个LRU啊，你搞得确实有点复杂
doubly linked list+hashmap should be enough |
|
l*****a
发帖数: 14598 | 41 看起来就是要一个LRU啊，你搞得确实有点复杂
doubly linked list+hashmap should be enough |
|
s******d
发帖数: 424 | 42 想知道这属于什么难度的 是不是不同的组难度有差别？
Round 1 (Written)
1. Given an array, output an array where every index conains nearest
greatest element to that element on right side.
2. Program to convert sorted array to Binary Search Tree
3. Find first non-repeating character in String
ex: geeksforgeeks: f
geeksforgeeksFirst:o
Round 2 (F2F)
1. Given linked list as a-x-b-y-c-z
output it as a-b-c-z-y-x
that is reverse alternate element and append to end of list
2. Output nearest number greater than given number such t... 阅读全帖 |
|
|
s**x
发帖数: 7506 | 44 这个怎么样？the idea is remove each node and add it to a new list.
// assume not circular doubly linked list.
void reverse2(Node * &head, Node * &tail)
{
if (head == tail)
return;
Node *newHead = NULL;
Node *newTail = NULL;
Node *cur = head;
while(cur) {
Node *tmp = cur->next;
cur->next = newHead;
cur->prev = NULL;
if (newHead == NULL} newTail = cur;
else newHead->prev = cur;
newHead = cur;
cur = tmp;
}
head = ... 阅读全帖 |
|
w****3
发帖数: 110 | 45 额，那应该怎么实现呢？似乎java里面没有已经写好的doubly linked list？
doublelinkedlist, |
|
x****h
发帖数: 3 | 46 EE MS毕业，面的是2014 New Grad，非常非常感谢版上大牛的内推，机会难得，很遗憾
最后没有拿到Offer。
Phone Intervew：
1. Palindrome String (LeetCode)
2. Sum3 (LeetCode)
3. Letter Combinations of a Phone Number (LeetCode)
因为都是熟题，电面非常顺利，Sum3还给了排序和HashTable两种解法，当天就通知了
Onsite。
Onsite Interview：
一共三轮，每轮45分钟，因为是Master所以没有System Design：
1. 半轮Culture Fit的问题，另外一道Coding，Sort List (LeetCode)，要求In Place
，递归的解法要用到Call Stack，讨论了一下没想到更优化的方法，就写了递归Merge
的解法。
2. 两道Coding题目，一道可以化为普通的Binary Search，另外一道是Anagrams (
LeetCode)，都很快搞定，之后剩下将近20分钟就让我提问题了，随便聊了一下感觉... 阅读全帖 |
|
l*****a
发帖数: 14598 | 47 那就把binary tree的结构当成doubly linked list看？ |
|
y***n
发帖数: 1594 | 48 写了Flattern this multilevel data structure： http://ideone.com/11xcqw
Restore 不知道如何写，感觉要存一下那里开始Flat的才行。
doubly
. |
|
p****6
发帖数: 724 | 49
doubly
.
if(node == null) return node;
Stack stack = new Stack();
ListNode head = new ListNode(-1);
head.next = node;
while(node!=null){
if(node.other!=null){
if(node.next!=null)
stack.add(node.next);
node.next = node.other;
node.other = null;
}else{
if(node.next == null && !stack.isEmpty()){
L... 阅读全帖 |
|
x****B
发帖数: 103 | 50 你把这个链表想像成二叉树或者带父亲节点的二叉树。然后前序遍历？
doubly
. |
|
