由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Tricky Pointer Problems -- Which level are you?
相关主题
reverse random pointers of a single linked listPopulating Next Right Pointers in Each Node II
问到linked list 的题目贡献道M 家 onsite 面试题
linklist exerciseBST面试题
sorted linked list里insert一个node一道面试题
remove a node (and its memory) from a doubly linked list请教一道面试题
Populating Next Right Pointers in Each Node II题目: iterative binary tree post order traversal
请教LEETCODE讲解部分的LCA一道题的变种。。求教一道面试题
有人同看Populating Next Right Pointers in Each Node II的recursive写法么?一道面试题:Flatten a multilevel linked list
相关话题的讨论汇总
话题: node话题: pointer话题: level话题: printlist话题: head
进入JobHunting版参与讨论
1 (共1页)
i**********e
发帖数: 1145
1
These are some original pointer problems from me. Try to solve without a
compiler's help. Post your answers here by replying to this post.
Assume you have the following linked list defined as:
struct Node {
Node(int x) : val(x), next(NULL) {}
int val;
Node *next;
};
And you have a printList function which prints out the content of a list.
What are the outputs for the following code segments?
d*******d
发帖数: 2050
2
r******n
发帖数: 170
3
g**f
发帖数: 414
4
*p = new Node(4);
p = &((*p)->next);
m*********2
发帖数: 701
5
that's what i thought too.
But i tried it with GCC.
it works.
The first replier (dinohound) got it all right.

【在 g**f 的大作中提到】
: *p = new Node(4);
: p = &((*p)->next);

i**********e
发帖数: 1145
6
dinohound,你的答案是完全正确的。
看来大家还是对 LEVEL 3 的感到有些混淆,那我先说我理解的,欢迎大家补充一下。
*p = new Node(4);
p = &((*p)->next);
Level 3 相信大家想问的就是应该编译会出现错误,因为 (*p)->next 不就是 NULL 吗
?然后相信很多人会对 &((*p)->next) 理解成 &(NULL),而感到不解。
我给个简单些的例子,道理其实一样:
int *p = NULL;
那 &p 是什么呢?其实就是那个 p 变量的地址,p 变量储存的值到底是什么是没有关
系的。
同样的道理, p = &((*p)->next) 也就能理解成当前链表下一个节点的地址的地址。
所以 p 指向的东西(也就是下一个节点的地址),能通过 *p 来更改(使得下一个节
点的地址更改而指向一个新建的节点)。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
g**f
发帖数: 414
7
Good explanation. Got it.

【在 i**********e 的大作中提到】
: dinohound,你的答案是完全正确的。
: 看来大家还是对 LEVEL 3 的感到有些混淆,那我先说我理解的,欢迎大家补充一下。
: *p = new Node(4);
: p = &((*p)->next);
: Level 3 相信大家想问的就是应该编译会出现错误,因为 (*p)->next 不就是 NULL 吗
: ?然后相信很多人会对 &((*p)->next) 理解成 &(NULL),而感到不解。
: 我给个简单些的例子,道理其实一样:
: int *p = NULL;
: 那 &p 是什么呢?其实就是那个 p 变量的地址,p 变量储存的值到底是什么是没有关
: 系的。

d*******d
发帖数: 2050
8
thanks.
这种问题可以很磨人的.

【在 i**********e 的大作中提到】
: dinohound,你的答案是完全正确的。
: 看来大家还是对 LEVEL 3 的感到有些混淆,那我先说我理解的,欢迎大家补充一下。
: *p = new Node(4);
: p = &((*p)->next);
: Level 3 相信大家想问的就是应该编译会出现错误,因为 (*p)->next 不就是 NULL 吗
: ?然后相信很多人会对 &((*p)->next) 理解成 &(NULL),而感到不解。
: 我给个简单些的例子,道理其实一样:
: int *p = NULL;
: 那 &p 是什么呢?其实就是那个 p 变量的地址,p 变量储存的值到底是什么是没有关
: 系的。

t******g
发帖数: 252
9
I don't understand how the second line in level one work. Can someone please
explain?
I think p is allocated as a pointer to pointer. But where it's pointed to is
not allocated. Why is that not a problem?

【在 i**********e 的大作中提到】
: These are some original pointer problems from me. Try to solve without a
: compiler's help. Post your answers here by replying to this post.
: Assume you have the following linked list defined as:
: struct Node {
: Node(int x) : val(x), next(NULL) {}
: int val;
: Node *next;
: };
: And you have a printList function which prints out the content of a list.
: What are the outputs for the following code segments?

m*********2
发帖数: 701
10
LZ不如谈下这low-level detail.
For example:
1) How is Node** p represented in the low level?
p, the pointer to pointer to a Node, is on the stack?
where is *p located then? on the stack or the heap?
My understanding is:
Node p ==> the struct is on the stack.
Node *p ==> the pointer is on the stack, the struct is on heap
Node **P ==> the pointer of pointer is on the stack... not sure where
the other two is going to be.
In addition, does the complier keep track of RTTI of p (in case of Node
**p)? Does the complier know that it's a pointer to pointer to Node? or
it is just a generic pointer?
2)
so, when Node.Next is assigned to NULL
Node.NEXT still has valid address, pointing to 0?

【在 i**********e 的大作中提到】
: dinohound,你的答案是完全正确的。
: 看来大家还是对 LEVEL 3 的感到有些混淆,那我先说我理解的,欢迎大家补充一下。
: *p = new Node(4);
: p = &((*p)->next);
: Level 3 相信大家想问的就是应该编译会出现错误,因为 (*p)->next 不就是 NULL 吗
: ?然后相信很多人会对 &((*p)->next) 理解成 &(NULL),而感到不解。
: 我给个简单些的例子,道理其实一样:
: int *p = NULL;
: 那 &p 是什么呢?其实就是那个 p 变量的地址,p 变量储存的值到底是什么是没有关
: 系的。

相关主题
Populating Next Right Pointers in Each Node IIPopulating Next Right Pointers in Each Node II
请教LEETCODE讲解部分的LCA一道题的变种。。贡献道M 家 onsite 面试题
有人同看Populating Next Right Pointers in Each Node II的recursive写法么?BST面试题
进入JobHunting版参与讨论
t******g
发帖数: 252
11
Never mind. I get it.
p is a pointer to a pointer to Node. It was assigned pointer to head which
is itself a pointer to Node.
I think I was tired from a long day.

please
is

【在 t******g 的大作中提到】
: I don't understand how the second line in level one work. Can someone please
: explain?
: I think p is allocated as a pointer to pointer. But where it's pointed to is
: not allocated. Why is that not a problem?

i**********e
发帖数: 1145
12
Node *head = new Node(3);
Node **p = &head;
*p = new Node(4);
p = &((*p)->next);
*p = new Node(5);
Attached is an image to visualize the pointers for level three.
Remember, a pointer always occupy 4 bytes of memory no matter what type it
is. It stores nothing but the address of the data it is pointing to (which
is a 32 bit integer). The data type is only used to do pointer arithmetic (
ie, to calculate the number of bytes to jump over to the next element in an
array).
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
i**********e
发帖数: 1145
13
The pointer is always on the stack (it stores a 32-bit integer (the address
of the data it is pointing to)). The data it is pointing to can be on the
stack or the heap.
For example,
int *p = new int(3); // p is pointing to an int on the heap
int x = 3;
int *p = &x; // p is pointing to an int on the stack
The compiler knows that it's a pointer to pointer to Node. (you declare it
as Node **p). The pointer type is used for pointer arithmetic purpose. That'
s why a generic pointer (void *) could not perform pointer arithmetic.
Node.NEXT will have a valid address. Every variable must have a valid
address, right? Yes, and it is pointing to NULL. which means the pointer
itself has a value of 0. On the other hand, if the pointer is pointing to a
valid data, then the pointer itself would have the address of the valid data
(which must be NON-NULL(NON-ZERO)).
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
G**********s
发帖数: 70
14
------------ LEVEL ZERO -----------------
Node *head = new Node(3);
Node *p = head;
p = new Node(4);
0.a) printList(head);
3
0.b) printList(p);
4
------------ LEVEL ONE ------------------
Node *head = new Node(3);
Node **p = &head;
*p = new Node(4);
1.a) printList(head);
4
1.b) printList(*p);
4
------------ LEVEL TWO ------------------
Node *head = new Node(3);
Node **p = &head;
*p = new Node(4);
*p = (*p)->next;
2.a) printList(head);
null
2.b) printList(*p);
null
------------ LEVEL THREE -----------------
Node *head = new Node(3);
Node **p = &head;
*p = new Node(4);
p = &((*p)->next);
*p = new Node(5);
3.a) printList(head);
4->5
3.b) printList(*p);
null
G**********s
发帖数: 70
15
感谢你设计的题目帮我顺便又复习了一下,好玩!!
解pointer的题,要virtulize memory,脑子里就要生成一个像你画的那个图,这些题
就简单多了。
1 (共1页)
进入JobHunting版参与讨论
相关主题
一道面试题:Flatten a multilevel linked listremove a node (and its memory) from a doubly linked list
[leetcode] merge k lists 求助Populating Next Right Pointers in Each Node II
How can one determine whether a singly linked list has a cycle?请教LEETCODE讲解部分的LCA一道题的变种。。
一个简单的java题有人同看Populating Next Right Pointers in Each Node II的recursive写法么?
reverse random pointers of a single linked listPopulating Next Right Pointers in Each Node II
问到linked list 的题目贡献道M 家 onsite 面试题
linklist exerciseBST面试题
sorted linked list里insert一个node一道面试题
相关话题的讨论汇总
话题: node话题: pointer话题: level话题: printlist话题: head