Raj
BAN USER- 2of 2 votes
Answersgiven preorder traversal [5,3,2,4,8,7,9] of a BST, how do we identify the leaf nodes without building the tree ?
- Raj in United States
@Anonymous Thanks for the reply!
Please try other use cases like, only single leaf node| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures
Can we do some thing like this ?.
1. visit matrix[i][j] != 0 then
keeping counting the number of ones seen
before this like row two will have (8,2) and
column 3 will have (1,4) and rowID of this > than
rowID of (8,2) then we have and remember
this max row and column 1’s count with rowID constraint
then we can solve this in O(M*N) right ?.
1.We can reduce the swaps only if order doest matter, then we can use the two pointer solution given.
2. If the order has to be retained, then only option left is to shift the elements then we can reduce the swaps.
it mainly depends whether the order has to be retained or not
no, if B is before A then we leave it as is, then, how does it guarantee that it is in sorted order. consider this example
input : 5 3 10 1 2 8 6 after sort it would be 1 2 6 8 5 3 10, as 5 and 3 where before 10, they didn't get moved they are not in the order.
I think we need O(n) MoveToFront calls.
We can use one of the following
1. Table representation
total#rows total#columns total#nonZeroValues // header row first row of table
//next rows below the actual values
// if a row as two values then there will be two rows here
2. LinkedList representation
// this is bit complex, than first one
//it has three nodes HeaderNode, RowNode and ColumnNode
//HeaderNode -> Total#rows,Total#column, pointer to next row
//RowNode -> Row#,pointerToNextRow,pointerToNextColumn
//ColumnNode -> Column#,Value, pointerToNextColumn(if a row as more than one nonZero values)
1. We can capture the indexes of each character in the pattern
- Raj April 14, 20172. then find the range with minimum difference between start and end of the range
- pick the first occurrence of each character pick the min and max
- drop the min and pick the next element from the queue it was dropped
repeat 2 until one of the source exhausts
3. return the range with minimum difference.