s*********l
发帖数: 103 | 1 http://discuss.techinterview.org/default.asp?interview.11.79942
You are given N blocks of height 1…N. In how many ways can you arrange
these blocks in a row such that when viewed from left you see only L blocks
(rest are hidden by taller blocks) and when seen from right you see only R
blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}. | g*********s
发帖数: 1782 | 2 brute-force?
blocks
R
3}
【在 s*********l 的大作中提到】
: http://discuss.techinterview.org/default.asp?interview.11.79942
: You are given N blocks of height 1…N. In how many ways can you arrange
: these blocks in a row such that when viewed from left you see only L blocks
: (rest are hidden by taller blocks) and when seen from right you see only R
: blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
: while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
| Z*****Z
发帖数: 723 | 3 Term:
13766
Web:
http://mitbbs.com/article1/JobHunting/31588989_3_0.html
blocks
}
【在 s*********l 的大作中提到】
: http://discuss.techinterview.org/default.asp?interview.11.79942
: You are given N blocks of height 1…N. In how many ways can you arrange
: these blocks in a row such that when viewed from left you see only L blocks
: (rest are hidden by taller blocks) and when seen from right you see only R
: blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
: while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
| s*********l
发帖数: 103 | 4 我的基本想法是构造满足条件的binary max heap,然后按中序输出,有点cartesian
tree的意思.
blocks
}
【在 s*********l 的大作中提到】
: http://discuss.techinterview.org/default.asp?interview.11.79942
: You are given N blocks of height 1…N. In how many ways can you arrange
: these blocks in a row such that when viewed from left you see only L blocks
: (rest are hidden by taller blocks) and when seen from right you see only R
: blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
: while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
| g*********s
发帖数: 1782 | 5 sorry, what's the connection to max heap?
【在 s*********l 的大作中提到】
: 我的基本想法是构造满足条件的binary max heap,然后按中序输出,有点cartesian
: tree的意思.
:
: blocks
: }
| s*********l
发帖数: 103 | 6 seems the number of nodes on the left-most path is L
and the number of nodes on the right-most path is R
Examples:
(1) given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
{2,1,3} corresponds to the cartesian tree
3
/
2
\
1
Left-most path: 3->2
Right-most path: 3
(2) while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
{1,3,2} corresponds to the cartesian tree
3
/ \
1 2
Left-most path: 3->1
Right-most path: 3->2
{2,3,1} corresponds to the cartesian tree
3
/ \
2 1
Left-most path: 3->2
Right-most path: 3->1
【在 g*********s 的大作中提到】
: sorry, what's the connection to max heap?
|
|
