DeathEater
BAN USERJust count the number of inversions.. there's a O(nlogn) solution for that, using divide and conquer.
- DeathEater November 05, 2012int global_max=0;
ArrayList<TreeNode> global_max_path=null;
void findMaxPath (TreeNode t, int sum, ArrayList<TreeNode> path)
{
if(t == null)
{
if(sum > global_max)
{
global_max=sum;
global_max_path = path;
}
}
else
{
ArrayList<TreeNode> left_path = new ArrayList<TreeNode>(path);
findMaxPath(t.left,sum+t.data,path.add(t));
ArrayList<TreeNode> right_path = new ArrayList<TreeNode>(path);
findMaxPath(t.right,sum+t.data,path.add(t));
}
}
findMaxPath(t,0,new ArrayList<TreeNode>());
Naive solution is O(n^2)
With DP, we can achieve an O(N) solution.
The idea is to have a class like::
class DP1
{
int max_profit;
int min_val;
public DP1(int min_val,int max_profit)
{
this.max_profit = max_profit;
this.min_val = min_val;
}
public DP1()
{}
}
The min_val field contains the min value of the max-min=profit, for each DP(i).
The main idea is: when do we change the min_val for a particular DP(i) ?
We do that, when arr[i] - dp[i-1].min_val becomes less than 0.
Then, we set the profit to 0, and update dp[i].min_val=arr[i].
Heres, the code::
public class MaximumProfit
{
public static int maxProfit (int[] arr, int n)
{
DP1[] dp_arr = new DP1[n];
dp_arr[0] = new DP1(arr[0],0);
for(int i=1;i<n;i++)
{
dp_arr[i] = new DP1();
if(dp_arr[i-1].max_profit < (arr[i] - dp_arr[i-1].min_val))
{
dp_arr[i].min_val = dp_arr[i-1].min_val;
dp_arr[i].max_profit = arr[i] - dp_arr[i-1].min_val;
}
else
{
if(arr[i]- dp_arr[i-1].min_val < 0)
{
dp_arr[i].min_val=arr[i];
dp_arr[i].max_profit=0;
}
else
{
dp_arr[i].min_val = dp_arr[i-1].min_val;
dp_arr[i].max_profit = dp_arr[i-1].max_profit;
}
}
}
return dp_arr[n-1].max_profit;
}
public static void main(String[] s)
{
int[] arr = {1, 4 , 5 ,2, 3};
System.out.println(maxProfit(arr, arr.length));
}
}
@Spsneo:
arr[i] = (int*)( arr + r + (i-1)*c ) needs to have 2 changes::
1) r should be replace by r*sizeof(int*). The first chunk of memory is an array of r integer pointers. To pass that, we need to add r*sizeof(int*) bytes to int** arr.
2) (i-1)*c should be replaced by (i-1)*sizeof(int)*c. The reasoning being the same as above.
You need to multiply each c with 4 too, since each integer is of 4 bytes.
So, it should be:::
arr[0] = temp;
arr[1]= temp + 4*c;
arr[2]= temp + 2*4*c;
....
19 new processes will be created. 20 including the original one.
- DeathEater September 03, 2012correct.
- DeathEater August 16, 2012Although, I am not sure what code is expected here.
- DeathEater August 14, 2012From my understanding of the question, if w and z are the lengths of the sides of the rectangle, the probability should be: 2/((w+1)*(z+1)), given that (x,y) can only be integer co-ordinates.
The idea behind this is simple. The total no. of integral co-ordinates in a rectangle of w,z dimensions are (w+1)*(z+1), including the end-points. Now, the guy can only fall of the island if hes on any one of those 4 points, and makes 2 wrong directions (for eg. west and north at the top left point) at each of these 4 points.
Thus, number of deathly moves= 4*2=8
Total number of possible moves= (w+1)*(z+1)*4, since at each point i can move in 4 directions.
Thus, probability of the guy dying is: 2/((w+1)*(z+1)).
We just keep a note of the last digit we chose. If the last digit is 1, we can choose both 1 and 0 for this position. If its 0, we can only choose 1, not 0, for this position.
- DeathEater August 13, 2012public class generateRestrictedBinaryString {
public static void main(String[] s) {
int K = 5;
System.out.println(numberOfPossibleBinaryStrings(K, 0));
}
static int numberOfPossibleBinaryStrings(int k, int last_digit) {
if (k == 1) {
if (last_digit != 0) {
return 2;
} else {
return 1;
}
} else {
if (last_digit != 0) {
return numberOfPossibleBinaryStrings(k - 1, 0)
+ numberOfPossibleBinaryStrings(k - 1, 1);
} else
return numberOfPossibleBinaryStrings(k - 1, 1);
}
}
}
The idea is simple: A restricted permutation. Unlike checking all possible permutations of the 9 digits, I follow a strategy in which I only consider those possible options of the digits in the current method call, which satisfy a particular criteria, which is that the digit in current consideration, along with the earlier digits, is divisible by a desired number between 1 and 9.
- DeathEater August 13, 2012public class Generate9DigitNumber {
public static void main(String[] s) {
int number = generateNumber(9, "");
String str_num = new Integer(number).toString();
if (str_num.length() != 9) {
System.out.println("Required number not found!");
} else
System.out.println(str_num);
}
static int generateNumber(int digits, String number) {
System.out.println(number);
if (digits == 0)
return Integer.parseInt(number);
else if (digits == 1) {
for (int i = 1; i <= 9; i++) {
String temp = number + i;
Integer temp_int = Integer.parseInt(temp);
if (temp_int % (9 - digits + 1) == 0)
return temp_int;
}
// Rite digit not found
return Integer.parseInt(number);
} else {
for (int i = 1; i <= 9; i++) {
String temp = number + i;
Integer temp_int = Integer.parseInt(temp);
if (temp_int % (9 - digits + 1) == 0) {
return generateNumber(digits - 1, temp);
}
}
return Integer.parseInt(number);
}
}
}
}
- DeathEater August 13, 2012We just need to serialize the binary tree in such a way that when we are de-serializing, we can identify the elements in the right and left subtrees. Thus, we can serialize the pre-order traversal of the tree with a special character ('#' etc.) between the left and right subtree of each node. Also, to make things simple, we can insert another special character ('$' etc.) in place of NULL pointers.
Now, we can recursively deserialize, since for each tree, we can always identify the root, elements in the left subtree and elements in the right subtree.
Nice approach.
An O(N) time and O(N) auxillary space solution, would be to::
1) Scan the original list and create the copy list, one node at a time, populating ONLY the "next" pointers in each node. Also, while scanning the original list create a map between the addresses of corresponding nodes in original and copied list.
2) Now, scan the original list once again and for each "arbitrary" pointer in each node of the original list, get the corresponding value from the map, and copy that value in "arbitrary" field of the node of the copied list.
Theres also a NlogN solution for this problem.
Since its a BST and not a regular binary tree, we can reconstruct the binary tree from the pre-order traversal.
Algo::
a) First Element of the array is root.
b) Scan the array till we encounter an element greater than the root. This element marks the beginning of the right subtree.
c) Now, we have the elements of both the left and right tree. So, we recursively apply the above algorithm.
This algorithm will take NLogN time.
Once the BST is constructed, we can do a tree traversal and determine the internal nodes with one/two children in linear time
- DeathEater January 31, 2018