i****c
发帖数: 102 | 1 some of them:
·given an array, each element is a string pair: the first string is a
parent node, and the second is a child node. construct a binary tree
·OO design: design a restaurant reservation system， tic-tac-toe and its
implementation
·how to evaluate search engine results (enum all metrics you can think of,
e.g., recall and click)
·synchronization of hashmap
·sorting integer (large range) with limit memory
·given a int array, check whether there is an element in array satisfying A
[i]=i, considering different constraints (e.g., contains negative numbers or
not, with or without duplication? )
·given a maze, implement algorithm to find whether there are paths between
two locations
·decide whether a binary tree is symmetric or not | k*******p
发帖数: 8821 | | l*********r
发帖数: 674 | 3 given a maze, implement algorithm to find whether there are paths between
two locations
这个是用BFS吧。如果要print path，应该怎样save path最efficient呢？ | r******e
发帖数: 80 | 4 有什么好的策略回答这样的问题呢？ 不给更多的功能描述，一点思路都没有啊。
要是事先不知道tic-tac-toe怎么办呀？ 过来人看能不能给点建议。
/*
·OO design: design a restaurant reservation system， tic-tac-toe and its
implementation
*/ | d****2
发帖数: 12 | 5 >> given an array, each element is a string pair: the first string is a
parent node, and the second is a child node. construct a binary tree
I can only think of way that needs to use a queue. Is there any other better
or classic solution? | c*****n
发帖数: 96 | 6 One thing needs to be clarified is: for each element in the array, do we
know the child node is a left child or right child.
Assuming the answer is yes, we can use a hash table: the key is the parent
node; the value is the two child nodes with a flag indicating if the parent
node is a child node of any node in the array. Iterate the array once to
populate the hash table. If we know the root node, it's trivial to build a
binary tree using pre-order traverse. The root node should be the node which
is not a child node of any nodes. Iterate the hash table key can get the
root node. The time complexity should be O(n).
better
【在 d****2 的大作中提到】
: >> given an array, each element is a string pair: the first string is a
: parent node, and the second is a child node. construct a binary tree
: I can only think of way that needs to use a queue. Is there any other better
: or classic solution?
| i****c
发帖数: 102 | 7 This is a good question to ask during the interview.
The answer is the first child scaned is the left node.
An example of another interesting question is: Can the final tree has only o
ne node?
You solution is right, and can build the tree and detect the root node when
scan the string array. Therefore, one time of iteration is enough if more me
mory is given
parent
which
【在 c*****n 的大作中提到】
: One thing needs to be clarified is: for each element in the array, do we
: know the child node is a left child or right child.
: Assuming the answer is yes, we can use a hash table: the key is the parent
: node; the value is the two child nodes with a flag indicating if the parent
: node is a child node of any node in the array. Iterate the array once to
: populate the hash table. If we know the root node, it's trivial to build a
: binary tree using pre-order traverse. The root node should be the node which
: is not a child node of any nodes. Iterate the hash table key can get the
: root node. The time complexity should be O(n).
:
| c*****n
发帖数: 96 | 8 should be DFS ?
PrintPath(string currentPath, node current, node dest)
{
if (current == dest)
{
printf (currentPath + node);
return;
}
MarkNodeAsVisited(node);
foreach (node n in node.AdjacentNodes)
{
if (n is not visited)
{
PrintPath(currentPath + n, n, dest);
}
}
MarkNodeAsNotVisited(node);
}
【在 l*********r 的大作中提到】
: given a maze, implement algorithm to find whether there are paths between
: two locations
: 这个是用BFS吧。如果要print path，应该怎样save path最efficient呢？
|
| p****m
发帖数: 59 | 9 All we have at this step is a hash table. Could you explain where the
preorder
traversal is coming from? Also, given a preorder traversal, how to contruct
a
binary tree? Thanks.
parent
which | c*****n
发帖数: 96 | 10 Assuming each item in the hash table is an array of size 2, the first
element is the left child key, the second one is right node key
Node BuildTree (string nodeKey, HashTable hTable)
{
if (node == null)
return null;
Node node = new node(nodeKey);
// build left sub tree
node.lchild = BuildTree(hTable[nodeKey][0], hTable);
// build right sub tree
node.rchild = BuildTree(hTable[nodeKey][1], hTable);
return node;
}
contruct
【在 p****m 的大作中提到】
: All we have at this step is a hash table. Could you explain where the
: preorder
: traversal is coming from? Also, given a preorder traversal, how to contruct
: a
: binary tree? Thanks.
: parent
: which
| | | d****2
发帖数: 12 | 11 Thank you for posting the solution. It should work. But I have one more
confusion. I didn't see how you can find the root in O(n) without using the
second hashtable (a child -> parent map).
Can you clarify it?
【在 c*****n 的大作中提到】
: Assuming each item in the hash table is an array of size 2, the first
: element is the left child key, the second one is right node key
: Node BuildTree (string nodeKey, HashTable hTable)
: {
: if (node == null)
: return null;
:
: Node node = new node(nodeKey);
:
: // build left sub tree
| z*******0
发帖数: 30 | 12 One more DFS search. Using topological sort, we can find the root node, and
then build the binary tree. | i**9
发帖数: 351 | 13 >·given an array, each element is a string pair: the first string is a
>parent node, and the second is a child node. construct a binary tree
聊一下思路，iterate整个array,hash一遍,key为 the first string,value为 一个
string list(可能包含一个或两个 the second string),
用另外一个hashtable找到整个 tree的root(没有parent的即为root)
找到root后,在第一个hashtable dfs 找到所有nodes construct the binary tree, | U*****R
发帖数: 60 | 14 /*
·OO design: design a restaurant reservation system， tic-tac-toe and its
implementation
*/
The first question: what is tic-tac-toe?
I am not sure whether the following answer is OK. Any revision is welcomed.
Basically speaking, the system consists of three layers:
(1) presentation layer (UI). We can have on basic boundary class and then
produce different inheritance classes for Web UI and Client UI under various
contexts, such as labtop, mobile phone.
(2) Application layer. We can have several control classes here. They are
booking class, timer class, consistency class, admin class. In the booking
class, we can add, edit, remove booking records. In the timer class, the
system can remove any records out of date. In the consistency class, it
checks whether two records' time and room conflict. The admin class is
responsible for staff who use the system.
(3) Storage layer. We need two tables. One is admin table containing staff
login info. The other is booking record table. It can have several fields:
agent, guest number, table, time... | U*****R
发帖数: 60 | 15 ·how to evaluate search engine results (enum all metrics you can think of,
e.g., recall and click)
1. efficiency. How quick. Elapsed indexing time,...
2. effectiveness. How accurate. Compare the ranking produced by search
engine with the one by relevance judgement (user relevance and topical
relevance). Recall and Precision
3. Query logging. How human interact with search engine.
The following document is fairly complete.
http://www.pearsonhighered.com/croft1epreview/pdf/chap8.pdf | U*****R
发帖数: 60 | 16 synchronization of hashmap
Can I answer that it depends on how hashmap is implemented.
If hashmap is based on separate chaining , we can assign a mutex lock for
each slot.
If hashmap is based on open addressing, we have to use one mutex lock for
the whole map.
Is my answer right? |
|
