b******u
发帖数: 81 | 1 第一电面，美国大哥。
第二电面，印度MM。
第三电面，中国弟弟。悲剧。
死而无怨。
印度MM： 写 code： LINDE LIST 两两互换。
中国弟弟：写 code： BINARY SEARCH TREE 第五大的数。 |
g*********e
发帖数: 14401 | |
l*********8
发帖数: 4642 | 3 LINDE LIST 是指 Linked List?
BINARY SEARCH TREE 第五大的数， 应该是逆中序遍历到第五个吧？
【在 b******u 的大作中提到】
: 第一电面，美国大哥。
: 第二电面，印度MM。
: 第三电面，中国弟弟。悲剧。
: 死而无怨。
: 印度MM： 写 code： LINDE LIST 两两互换。
: 中国弟弟：写 code： BINARY SEARCH TREE 第五大的数。
|
t********e
发帖数: 143 | 4 void bstVisit(const node *p_node, const int n, int &m)
{
if (!p_node)
return;
bstVisit(p_node->p_right, n, m);
m++;
if (m == n)
printNode(p_node);
bstVisit(p_node->p_left, n, m);
} |
p*****2
发帖数: 21240 | |
Z*****Z
发帖数: 723 | 6
else // no need to proceed if already found target
【在 t********e 的大作中提到】
: void bstVisit(const node *p_node, const int n, int &m)
: {
: if (!p_node)
: return;
: bstVisit(p_node->p_right, n, m);
: m++;
: if (m == n)
: printNode(p_node);
: bstVisit(p_node->p_left, n, m);
: }
|
s*******s
发帖数: 44 | 7 public static int find(Node root, int n, Integer rank) {
if (root == null)
return rank;
rank = find(root.right, n, rank);
rank++;
if (rank == n) {
System.out.println(root.value);
return rank;
}
return find(root.left, n, rank);
}
【在 p*****2 的大作中提到】
: 你是用C面试吗？第二题用java还有点麻烦
|
p*****2
发帖数: 21240 | 8
打印出来当然不麻烦了。如果要返回去就麻烦一些了。
【在 s*******s 的大作中提到】
: public static int find(Node root, int n, Integer rank) {
: if (root == null)
: return rank;
: rank = find(root.right, n, rank);
: rank++;
: if (rank == n) {
: System.out.println(root.value);
: return rank;
: }
: return find(root.left, n, rank);
|
s*******s
发帖数: 44 | 9 恩，而且才发现不需要Integer，int就行。。
要返回只能用Pair？
【在 p*****2 的大作中提到】
:
: 打印出来当然不麻烦了。如果要返回去就麻烦一些了。
|
s******n
发帖数: 3946 | 10 void bstVisit(const node *p_node, int n)
{
if (!p_node || !n)
return;
bstVisit(p_node->p_right, n);
n--;
if (!n)
printNode(p_node);
bstVisit(p_node->p_left, n);
} |
|
|
b******u
发帖数: 81 | 11 原题。这题我基本做出来了，但是不很顺。
Given a singly linked list swap the adjacent nodes in the list
1-4-5-6-3
4-1-6-5-3
【在 l*********8 的大作中提到】
: LINDE LIST 是指 Linked List?
: BINARY SEARCH TREE 第五大的数， 应该是逆中序遍历到第五个吧？
|
p*****2
发帖数: 21240 | 12
得定义个class吧。好像java就得这么搞。
【在 s*******s 的大作中提到】
: 恩，而且才发现不需要Integer，int就行。。
: 要返回只能用Pair？
|
p*****2
发帖数: 21240 | 13
这题考的也挺多。不过也还没练过。我总觉得面试应该能做出来。
【在 b******u 的大作中提到】
: 原题。这题我基本做出来了，但是不很顺。
: Given a singly linked list swap the adjacent nodes in the list
: 1-4-5-6-3
: 4-1-6-5-3
|
p*****2
发帖数: 21240 | 14
你看了上边的答案了吗？
【在 b******u 的大作中提到】
: 原题。这题我基本做出来了，但是不很顺。
: Given a singly linked list swap the adjacent nodes in the list
: 1-4-5-6-3
: 4-1-6-5-3
|
b******u
发帖数: 81 | 15 我上面还是做错了。刚看了 tradertobe 的答案, PERFECT! 用C#抄了一遍。
public static int? FindNthNumber(Node n, ref int rank, int nth)
{
if (n == null) return null;
int? result = FindNthNumber(n.right, ref rank, nth);
if (result == null)
{
if (rank == nth)
{
result = n.Num;
}
else
{
rank ++;
result = FindNthNumber(n.left, ref rank, nth);
}
}
return result;
}
【在 p*****2 的大作中提到】
:
: 你看了上边的答案了吗？
|
b***d
发帖数: 87 | 16 定义个类变量也可以的（类似全局变量）。不知道面试当中是否允许这样用？？
【在 p*****2 的大作中提到】
:
: 你看了上边的答案了吗？
|
p*****2
发帖数: 21240 | 17
是可以。就看面试怎么要求了。我觉得打印，全局最好。反正应该也不是面试的重点。
【在 b***d 的大作中提到】
: 定义个类变量也可以的（类似全局变量）。不知道面试当中是否允许这样用？？
|
l*****a
发帖数: 14598 | 18 这样好不好
有一道著名的题 find next node in InOrder Traverse.
Now we can implement it's opposite action.
find previous node in InOrder Traverse.
node * FindNthNode(node * root,int n)
{
if((root==null)||(n<=0)) return null;
find rightmost;
if(n==1) return rightmost;
node * current=rightmost;
for(int i=2;i<=n;i++)
{
current=GetInOrderPreNode(current);
if(current==null) return null;
}
return current;
}
【在 p*****2 的大作中提到】
:
: 是可以。就看面试怎么要求了。我觉得打印，全局最好。反正应该也不是面试的重点。
|
p*****2
发帖数: 21240 | 19
那个东西我还没写过呢。
【在 l*****a 的大作中提到】
: 这样好不好
: 有一道著名的题 find next node in InOrder Traverse.
: Now we can implement it's opposite action.
: find previous node in InOrder Traverse.
: node * FindNthNode(node * root,int n)
: {
: if((root==null)||(n<=0)) return null;
: find rightmost;
: if(n==1) return rightmost;
: node * current=rightmost;
|
b******u
发帖数: 81 | 20 哈哈，和我以为做错了的思路是一样的。
不过写下来的程序没有tradertobe的好看。
我改写的 C#程序 返回了结果。
【在 l*****a 的大作中提到】
: 这样好不好
: 有一道著名的题 find next node in InOrder Traverse.
: Now we can implement it's opposite action.
: find previous node in InOrder Traverse.
: node * FindNthNode(node * root,int n)
: {
: if((root==null)||(n<=0)) return null;
: find rightmost;
: if(n==1) return rightmost;
: node * current=rightmost;
|
|
|
b******u
发帖数: 81 | 21 SWAN 做的很漂亮，只要两个输入！
【在 s******n 的大作中提到】
: void bstVisit(const node *p_node, int n)
: {
: if (!p_node || !n)
: return;
: bstVisit(p_node->p_right, n);
: n--;
: if (!n)
: printNode(p_node);
: bstVisit(p_node->p_left, n);
: }
|
z****h
发帖数: 164 | 22 请问什么是“LINDE LIST 两两互换。”？
【在 b******u 的大作中提到】
: 第一电面，美国大哥。
: 第二电面，印度MM。
: 第三电面，中国弟弟。悲剧。
: 死而无怨。
: 印度MM： 写 code： LINDE LIST 两两互换。
: 中国弟弟：写 code： BINARY SEARCH TREE 第五大的数。
|
p*****2
发帖数: 21240 | 23
这题我准备有时间的时候做一下。
【在 z****h 的大作中提到】
: 请问什么是“LINDE LIST 两两互换。”？
|
l*****a
发帖数: 14598 | 24 why not now?
at most 10 minutes
【在 p*****2 的大作中提到】
:
: 这题我准备有时间的时候做一下。
|
p*****2
发帖数: 21240 | 25
有TCO的比赛，不想分散注意力。而且调错闹钟了，很困。不过昨晚算法想了一下，感
觉有点不太简洁。
【在 l*****a 的大作中提到】
: why not now?
: at most 10 minutes
|
l*****a
发帖数: 14598 | 26 他的算法对吗？
举个例子
A
\
\
B
find the 2nd largest
you will call func(A,2)
that is func(B,2); n=1; func(null,1)
func(B,2) is func(null,2), n=1; func(null,1)
where can you get the result A?
我什么地方搞错了吗？
【在 b******u 的大作中提到】
: SWAN 做的很漂亮，只要两个输入！
|
p*****2
发帖数: 21240 | 27
你咋还这么积极呢？
【在 l*****a 的大作中提到】
: 他的算法对吗？
: 举个例子
: A
: \
: \
: B
: find the 2nd largest
: you will call func(A,2)
: that is func(B,2); n=1; func(null,1)
: func(B,2) is func(null,2), n=1; func(null,1)
|
l*****a
发帖数: 14598 | 28 这道题我一直不知道比较好的解法是什么。。。
有人提出来了，我正好学习一下。。
但是还没太看懂。。
【在 p*****2 的大作中提到】
:
: 你咋还这么积极呢？
|
p*****2
发帖数: 21240 | 29
累死了。脑子快崩溃了。这两天有时间再跟你研究这题。
【在 l*****a 的大作中提到】
: 这道题我一直不知道比较好的解法是什么。。。
: 有人提出来了，我正好学习一下。。
: 但是还没太看懂。。
|
p*****2
发帖数: 21240 | 30
回来讨论这题。你觉得上边大家给出的算法不够好，还是都不对呀？
【在 l*****a 的大作中提到】
: 这道题我一直不知道比较好的解法是什么。。。
: 有人提出来了，我正好学习一下。。
: 但是还没太看懂。。
|
|
|
b******u
发帖数: 81 | 31 C#改了一下。输入应该是 pointer. 改进后的结果是对的。
SWAN 做法的可取之处是只需要两个INPUT。 用n--，而不是 rank++;
static void bstVisit(Node p_node, ref int n)
{
if (p_node == null || n < 0 ) return;
bstVisit(p_node.right, ref n);
n--;
if (n == 0) System.Console.WriteLine(p_node.Num);
bstVisit(p_node.left, ref n);
}
【在 l*****a 的大作中提到】
: 他的算法对吗？
: 举个例子
: A
: \
: \
: B
: find the 2nd largest
: you will call func(A,2)
: that is func(B,2); n=1; func(null,1)
: func(B,2) is func(null,2), n=1; func(null,1)
|
p*****2
发帖数: 21240 | 32
如果用Java也没什么区别吧？
【在 b******u 的大作中提到】
: C#改了一下。输入应该是 pointer. 改进后的结果是对的。
: SWAN 做法的可取之处是只需要两个INPUT。 用n--，而不是 rank++;
: static void bstVisit(Node p_node, ref int n)
: {
: if (p_node == null || n < 0 ) return;
:
: bstVisit(p_node.right, ref n);
: n--;
: if (n == 0) System.Console.WriteLine(p_node.Num);
:
|
b******u
发帖数: 81 | 33 应该没区别.
【在 p*****2 的大作中提到】
:
: 如果用Java也没什么区别吧？
|
z****h
发帖数: 164 | 34 int n是传值得。这样写不对吧。。。
【在 s******n 的大作中提到】
: void bstVisit(const node *p_node, int n)
: {
: if (!p_node || !n)
: return;
: bstVisit(p_node->p_right, n);
: n--;
: if (!n)
: printNode(p_node);
: bstVisit(p_node->p_left, n);
: }
|
l*****a
发帖数: 14598 | 35 use reference is right
【在 b******u 的大作中提到】
: C#改了一下。输入应该是 pointer. 改进后的结果是对的。
: SWAN 做法的可取之处是只需要两个INPUT。 用n--，而不是 rank++;
: static void bstVisit(Node p_node, ref int n)
: {
: if (p_node == null || n < 0 ) return;
:
: bstVisit(p_node.right, ref n);
: n--;
: if (n == 0) System.Console.WriteLine(p_node.Num);
:
|
z****h
发帖数: 164 | 36 有区别。java 没有 pass by reference
【在 b******u 的大作中提到】
: 应该没区别.
|
z****h
发帖数: 164 | 37 我觉得java只能用static variable了。或者用parent指针。
请指正。 |
p*****2
发帖数: 21240 | 38
我的意思是如果用Java，那个方法也没变的更简洁
【在 z****h 的大作中提到】
: 有区别。java 没有 pass by reference
|
z****h
发帖数: 164 | |
p*****2
发帖数: 21240 | 40
import java.io.*;
import java.util.*;
public class test
{
public static void main(String[] args)
{
new test().run();
}
PrintWriter out = null;
void run()
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
int[] values = new int[]
{ 1, 4, 5, 6, 3 };
Node head = null;
Node prev = null;
for (int i : values)
{
Node node = new Node(i);
if (head == null)
head = node;
else
{
prev.next = node;
}
prev = node;
}
Print(head);
head = Switch(head);
Print(head);
out.close();
}
void Print(Node head)
{
while (head != null)
{
out.print(head.value + " ");
head = head.next;
}
out.println();
}
Node Switch(Node head)
{
Node prev = null;
Node p1 = null;
Node p2 = null;
while (true)
{
if (prev == null)
p1 = head;
else
p1 = prev.next;
if (p1 == null)
break;
p2 = p1.next;
if (p2 == null)
break;
p1.next = p2.next;
p2.next = p1;
if (prev == null)
head = p2;
else
prev.next = p2;
prev = p1;
}
return head;
}
}
class Node
{
int value;
Node next;
public Node(int v)
{
value = v;
}
}
【在 z****h 的大作中提到】
: 请问什么是“LINDE LIST 两两互换。”？
|
|
|
p*****2
发帖数: 21240 | 41
用java返回一个值应该就可以了吧。
【在 z****h 的大作中提到】
: 我觉得java只能用static variable了。或者用parent指针。
: 请指正。
|
s********r
发帖数: 137 | |
z****h
发帖数: 164 | 43 不行吧。。。
给个实现？
【在 p*****2 的大作中提到】
:
: 用java返回一个值应该就可以了吧。
|
p*****2
发帖数: 21240 | 44
上边没有吗？
【在 z****h 的大作中提到】
: 不行吧。。。
: 给个实现？
|
z****h
发帖数: 164 | 45 上边的不对
【在 p*****2 的大作中提到】
:
: 上边没有吗？
|
p*****2
发帖数: 21240 | 46
import java.io.*;
import java.util.*;
public class test2
{
public static void main(String[] args) throws Exception
{
new test2().run();
}
PrintWriter out = null;
void run() throws Exception
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
Node node1 = new Node(1);
Node node4 = new Node(4);
Node node3 = new Node(3);
node3.left = node1;
node3.right = node4;
Node node6 = new Node(6);
Node node9 = new Node(9);
Node node8 = new Node(8);
node8.left = node6;
node8.right = node9;
Node root = new Node(5);
root.left = node3;
root.right = node8;
Find(root, 9, 0);
out.close();
}
int Find(Node node, int k, int c)
{
if (node == null)
return c;
c = Find(node.right, k, c);
c++;
if (c == k)
out.println(node.value);
return Find(node.left, k, c);
}
}
class Node
{
int value;
Node left;
Node right;
public Node(int v)
{
value = v;
}
}
【在 z****h 的大作中提到】
: 上边的不对
|
z****h
发帖数: 164 | 47 对的。多谢！
【在 p*****2 的大作中提到】
:
: import java.io.*;
: import java.util.*;
: public class test2
: {
: public static void main(String[] args) throws Exception
: {
: new test2().run();
: }
: PrintWriter out = null;
|
z****h
发帖数: 164 | 48 这样行吗？
还是只能算投机取巧？
private Node swap(Node head) {
Node curr = head;
while(curr != null && curr.next != null)
{
int tmp = curr.value;
curr.value = curr.next.value;
curr.next.value= tmp;
curr = curr.next.next;
}
return head;
}
【在 p*****2 的大作中提到】
:
: import java.io.*;
: import java.util.*;
: public class test2
: {
: public static void main(String[] args) throws Exception
: {
: new test2().run();
: }
: PrintWriter out = null;
|
z****h
发帖数: 164 | 49 这样应该不算投机了
private Node swapAdjancentNode(Node head) {
Node curr = head;
boolean isFirst = true;
Node pre = null;
while(curr != null && curr.next != null)
{
Node third = curr.next.next;
curr.next.next = curr;
if(isFirst)
{
head = curr.next;
isFirst = false;
}else
{
pre.next = curr.next;
}
curr.next = third;
pre = curr;
curr = third;
}
return head;
}
【在 z****h 的大作中提到】
: 这样行吗？
: 还是只能算投机取巧？
: private Node swap(Node head) {
: Node curr = head;
: while(curr != null && curr.next != null)
: {
: int tmp = curr.value;
: curr.value = curr.next.value;
: curr.next.value= tmp;
: curr = curr.next.next;
|
