Sunny
BAN USERTo me the approach seems like :
Pick the max length string, see if it fits in 10-width, if yes fit it in. Then for the remaining width see if there is a string that can fit in, if yes fit it in too.
Continue this process until you fit all strings, and count number of lines.
Intuitively this should give minimum number of lines, the reason is once you fit in the max length string, you have 1 line lost already.
Implementation wise, I can have 2 heaps: 1 max, 1 min.
Pick the top from max and fit it in first, if there is space remaining, peek from min see if it fits in remaining space.
Continue to fill up the lines.
Any comments would be most welcome.
Thinking out loud her - answer is not complete.
The remaining runs to win is T_b - T_a. It has to be achieved in 120 - B_b where B_b is the number of balls faced by Team B till now.
Now each ball has a possibility in the set { 0, 1, 2 ,3, 4, 5, 6, NoBall, Wide, Wicket }
The possibilities which contribute to runs are {1,2,3,4,5,6,Wide,NoBall}
There are 120 - B_b balls remaining lets say it is "b" for simplicity.
For each ball there are 10 possibilities and hence b*10 total possiblitites to pick from
But scoring possiblities are 8. hence b*8 possibilities
Probability of picking these possibities are b*8/b*10 = 4/5.
Its not over yet.
lets say target is T = T_a - T_b + 1
then T can be expressed as linear expression of those 8 possibilities.
let us say each coefficient in that linear expression is a_1, a_2, a_3, ....a_8.
Now lets say there are "n" such linear expressions
Out of those "n" such linear expressions only some are valid
--> when the sum of coefficients a_1 to a_8 is b
Lets say this number is "m".
If n == 0 then probability is 0
else if m == 0 then probability is 0
else
total probability is (4/5)*(m/n)
If it is a binary search tree, you could do in-order with going to right first and then to left.
This will make in-order traverse in descending order and stop traversal at count = 3.
If this is not a binary search tree, then convert the tree to a max heap - should be O(n) I believe. then pop three times to get the third highest.
I m not sure why to use any exotic structures for this problem, I can think of the solution below:
a) Copy the whole array into a temporary array and sort it.
b) Iterate through each element in original array and do binary search in the sorted array to give last occurrence - not the element - but the occurrence i.e. index of the element in the sorted array. Then you get next bigger by sorted[ lastOccurrence + 1 ] if lastOccurrence < originalarray.length - 1.
Replace the original 's element with this one.
Complexity :
Space = O(n)
Time = O(nlogn) for sort
O(nlogn) for replace. - because for each i in n there is a binary search with log n time.
a) Sort array B
b) For each element in A, search for the last occurrence of that element in B. The index will give you the number of elements in B less than or equal to the element in A - this could be done in O( log n ) - binary search.
The whole complexity should be : a) O(nlogn) for sorting B b) O(nlogn) for finding less than or equal to elements in B
You could do something like below in Java:
The idea is after each row/column - change direction and reduce the width of elements to print.
public class PrintSpiralArray
{
public static void main ( String... args )
{
PrintSpiralArray psa = new PrintSpiralArray();
int[][] a = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
psa.print( Direction.POS_X, 0, a[0].length, a.length, 0, -1, a, 0);
}
public void print( Direction d, int range, int xwidth, int ywidth, int i, int j, int[][] a, int grabbed )
{
if ( grabbed == a[0].length*a.length )
{
return;
}
else
{
switch( d )
{
case POS_X:
if ( range == xwidth )
{
ywidth--;
range = 0;
d = Direction.NEG_Y;
}
else
{
j++;
range++;
grabbed = printAndGrab( a, i, j, grabbed );
}
break;
case NEG_Y:
if ( range == ywidth )
{
xwidth--;
range = 0;
d = Direction.NEG_X;
}
else
{
i++;
range++;
grabbed = printAndGrab( a, i, j, grabbed );
}
break;
case NEG_X:
if ( range == xwidth )
{
ywidth--;
range = 0;
d = Direction.POS_Y;
}
else
{
j--;
range++;
grabbed = printAndGrab( a, i, j, grabbed );
}
break;
case POS_Y:
if ( range == ywidth )
{
xwidth--;
range = 0;
d = Direction.POS_X;
}
else
{
i--;
range++;
grabbed = printAndGrab( a, i, j, grabbed );
}
break;
}
print ( d, range, xwidth, ywidth, i, j, a, grabbed );
}
}
private int printAndGrab( int[][] a, int i, int j, int grab )
{
System.out.print( a[i][j] + " ");
return ++grab;
}
enum Direction
{
POS_X,
POS_Y,
NEG_X,
NEG_Y
}
}
I think the allBalancedNodes() can be achieved in O(n) with post Order traversal.
Have a variable called total in the node like below:
class Node
{
int total; // -- a variable indicating sum seen until now
int key;
int value;
Node left;
Node right;
Node parent;
}
isBalanced() definition:
public boolean isBalanced()
{
return ( ( left == null && right == null ) || ( left != null && right != null && left.total == right.total ) );
}
Post order traversal updating total on each node :
public void postOrderTraversal( Node node )
{
if ( node == null ) return;
postOrderTraversal( node.left );
postOrderTraversal( node.right );
node.total = node.value;
if ( node.left != null ) node.total += node.left.total;
if ( node.right != null ) node.total += node.right.total;
System.out.println( " Is balanced : " + node.isBalanced() );
}
Is it not
?
- Sunny February 06, 2018