prabodh.prakash
BAN USERLooks like a DP problem.
in a two dimensional array A, I define a function
F(i, j) =
= 0 if max {F(i-1, j), F(i, j-1), F(i-1, j-1)} = 0 and A[i, j] != first character of input string
= 1 if max {F(i-1, j), F(i, j-1), F(i-1, j-1)} = 0 and A[i, j] == first character of input string
= 1 + max {F(i-1, j), F(i, j-1), F(i-1, j-1)} if index of A[i, j] in input String = 1 + index of max {F(i-1, j), F(i, j-1), F(i-1, j-1)} in the input string; 0 otherwise
At any (i, j) if the value is the length of the input string, we know, we have found the answer.
Thus, the matrix
c b k
d a l
g t i
will be transformed to
1 0 0
0 2 0
0 3 0
thus, at position [3, 2] : we know, we have formed the word
comment, if you find any issue with the logic
- prabodh.prakash March 14, 2013Nice solution. It is very important to write the problem on pen and paper before thinking in mind :-)
- prabodh.prakash March 14, 2013Logic is great ! let me just quickly write the code and see if that works always.
- prabodh.prakash March 14, 2013Can somebody please explain the solution in details? I have tried understanding this earlier also, but failed.
My question is: why are we trying to be near to S/2?
Was asked in Flipkart phone round.
- prabodh.prakash March 13, 2013Did not check his algo. I coded this on my computer and posted my solution with illustrative example
- prabodh.prakash March 13, 2013so, any given weight can be of three forms
(-1, 0, 1) where
-1 : when is on the left side(i.e. its weight is getting subtracted)
0: not on any side (does not contribute to the weight)
1: when it is on the right side (i.e. its weight is getting added).
So, for n weights, the answer will be permutation of (-1, 0, 1) + (-1, 0, 1) + ..... + n times..where for any weight choices are: (-1, 0, 1).
Valid answers are sum greater than zero.
Taking example from the question, weights are 100, 250. Thus, the combination will be
(-1, 0, 1) + (-1, 0, 1)
-1 + -1 = -100 + -250 = invalid
-1 + 0 = -100 + 0 = invalid
-1 + 1 = -100 + 250 = 150
0 + -1 = 0 + -250 = invalid
0 + 0 = 0 + 0 = invalid
0 + 1 = 0 + 250 = 250
1 + -1 = 100 + -250 = invalid
1 + 0 = 100 + 0 = 100
1 + 1 = 100 + 250 = 350
thus making 100, 250, 150, 350 as answer.
comment if you find any bug with the logic
- prabodh.prakash March 13, 2013package interview.permute;
public class Sum
{
public void findMinimumSum(int[] A)
{
int minimumSum = Integer.MAX_VALUE;
int currentDifferene = minimumSum;
int i = 0;
int j = A.length -1;
while (i != j && currentDifferene != 0)
{
if (currentDifferene == Integer.MAX_VALUE)
currentDifferene = A[j] - A[i];
else
{
currentDifferene -= A[i];
}
if (currentDifferene < 0)
{
j--;
if (j == i)
break;
}
if (currentDifferene == 0)
break;
i++;
}
for (int count = 0 ; count < A.length ; count++)
{
if (count <= i)
System.out.print(" " + "-" + A[count]);
else
System.out.println(" " + A[count]);
}
}
public static void main(String[] args)
{
int[] A = new int[]{1, 3, 4};
Sum s = new Sum();
s.findMinimumSum(A);
}
}
this seems to be working
What I am trying to do is:
1. Sort the array
2. Remove any duplicate (at the end, you will have to add then in pairs, for e.g. 2, -2 etc)
[I have skipped above two steps in my code, to make the logic simpler]
3. Traverse from start and end, keep minimizing the sum, until you reach zero, or you end up on the same element..
Please comment back, if you find any bug
Your logic can lead to infinite loop
- prabodh.prakash March 13, 2013public class Permute1
{
StringBuilder out = new StringBuilder();
public void permute (String input, int start, int length)
{
if (out.length() == length)
{
System.out.println(out);
return;
}
for (int i = start ; i < input.length() ; i++)
{
out.append(input.charAt(i));
permute (input, i + 1 , length);
out.setLength(out.length() - 1);
}
}
public static void main(String[] args) {
Permute1 p = new Permute1();
p.permute("abcd", 0, 2);
}
}
Java solution
- prabodh.prakash March 13, 2013public void printTree(Node root)
{
if (root == null)
{
return;
}
out1.append(root.getData());
if (root.getLeft() == null && root.getRight() == null)
{
System.out.println(out1);
}
if (root.getLeft() != null)
{
printTree(root.getLeft());
out1.setLength(out1.length() - 1);
}
if (root.getRight() != null)
{
printTree(root.getRight());
out1.setLength(out1.length() - 1);
}
}
Thanks :-)
- prabodh.prakash March 14, 2013