anand
BAN USER@Xiang,
Can you please tell me the output of your program. I am not getting correct output.
if the question is related to max subSequence palindrome then output would be
12345gfg/gfg54321 of length 16
Well my code just prints maxlength
private static int FindLongestPalindrom(String string) {
return FindLongestPalindrom(string.toCharArray(),0,string.length()-1);
}
private static int FindLongestPalindrom(char[] s, int i, int j) {
if(i==j)
return 1;
else if(i==j+1){
if(s[i] == s[j]){
return 2;
}else{
return 1;
}
}else if(s[j] == s[i+1])
return FindLongestPalindrom(s, i+1, j-1)+2;
else
return Math.max(FindLongestPalindrom(s, i+1, j), FindLongestPalindrom(s, i, j-1));
}
We might still improve by using memoization.
@Adi,
I think we can add base cases before solving the above equation.
like if actualsum and expectedsum are equal then missing numbers are N+1 and N+2,
if (expectedsum - actualsum)^2 =(expectedsumsq - actualsumsq)
then missing number are expectedsum - actualsum and N+1.
private static int getLongestPath(NodeT root) {
int maxPath[] = new int[1];
getLongestPath(root,maxPath);
return maxPath[0];
}
private static int getLongestPath(NodeT root, int[] maxPath) {
if(root == null)
return 0;
else{
int lH = getLongestPath(root.left,maxPath);
int rH = getLongestPath(root.right,maxPath);
if(maxPath[0]<lH+rH+1){
maxPath[0] = lH+rH+1;
}
return 1 + Math.max(lH, rH);
}
}
{
public class NextBiggerNode {
public static void main(String[] args){
NodeT root = new NodeT(5);
root.left = new NodeT(3);
root.right = new NodeT(8);
root.left.left = new NodeT(2);
root.left.right = new NodeT(4);
root.right.left = new NodeT(6);
root.right.right = new NodeT(10);
getNextBiggerNode(root, root.right.right);
}
private static void getNextBiggerNode(NodeT root, NodeT input) {
NodeT mainGrandParent = null;
NodeT parent = root;
NodeT ptr = root;
boolean isLeftElement = false;
while(ptr != null && ptr.data != input.data){
if(ptr.data > input.data){
mainGrandParent = parent;
parent = ptr;
ptr = ptr.left;
isLeftElement = true;
}else{
parent = ptr;
ptr = ptr.right;
isLeftElement = false;
}
}
if(ptr == null)
System.out.println("Not found");
else{
if(ptr.right != null){
ptr = ptr.right;
while(ptr.left != null)
ptr = ptr.left;
}else{
if(isLeftElement)
ptr = parent;
else
ptr = mainGrandParent;
}
if(ptr != null)
System.out.println(ptr.data+" found");
else
System.out.println("No next large element");
}
}
}
}
public class PurchaseQBooksWithMinPrice {
public static void main(String[] args){
int arr[]= {100,200,120,130,165};
int quanity[] = {10,20,30,15,25};
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]+" "+quanity[i]);
}
System.out.println();
quickSort(arr,quanity, arr.length);
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]+" "+quanity[i]);
}
System.out.println(getPrice(arr,quanity,50));
}
private static int getPrice(int[] arr, int[] quanity,int totalQ) {
int tq=0;
int price = 0;
for(int i = 0; i<arr.length;i++){
if(tq == totalQ){
return price;
}
if(tq + quanity[i] < totalQ){
price += arr[i]*quanity[i];
tq = tq + quanity[i];
}else if(tq + quanity[i] > totalQ){
price += (totalQ-tq)*arr[i];
tq = totalQ;
}
}
if(tq == totalQ){
return price;
}else{
return -1; //Incase the total quantity is less than quantity given as input
}
}
private static void quickSort(int[] arr, int[] quantity, int length) {
recQuickSort(arr,quantity, 0, length - 1);
}
private static void recQuickSort(int[] arr,int []quantity, int left, int right) {
if(right - left <= 0)
return;
else{
int pivot = arr[right];
int partition = partitionIt(arr,quantity,left, right, pivot);
recQuickSort(arr,quantity, left, partition-1);
recQuickSort(arr,quantity, partition+1, right);
}
}
private static int partitionIt(int[] arr,int[] quantity, int left, int right, int pivot) {
int leftPtr = left - 1;
int rightPtr = right;
int temp;
while(true){
while(arr[++leftPtr]<pivot);
while(rightPtr > 0 && arr[--rightPtr]>pivot);
if(leftPtr >= rightPtr)
break;
else{
temp = arr[leftPtr];
arr[leftPtr]= arr[rightPtr];
arr[rightPtr]= temp;
temp = quantity[leftPtr];
quantity[leftPtr]= quantity[rightPtr];
quantity[rightPtr]= temp;
}
}
temp = arr[leftPtr];
arr[leftPtr]= arr[right];
arr[right] = temp;
temp = quantity[leftPtr];
quantity[leftPtr]= quantity[right];
quantity[right] = temp;
return leftPtr;
}
}
private static Node reverseALinkedList(Node root, int k) {
Node current = root;
Node prev = null;
Node next = null;
int i = 0;
while(current != null && i != k){
next = current.next;
current.next = prev;
prev = current;
current = next;
i++;
}
if(next != null){
root.next = reverseALinkedList(next, k);
}
return prev;
}
Sort the arrry ignoring the sign of the integer. lets say the input is {2 5 8 -7 2,9} and it will be sorted as {2,2,5,-7,8,9} and iterate the array as the minimum sum lies with next element. Let me know if there is any bug in the code.
public class FindPairWithSumClosestToZero {
public static void main(String[] args){
int a[] = {2, 5, 8, -7, 2, 9};
qSort(a, a.length);
int l=0,min = abs(a[1]+a[0]);
for(int i = 1; i < a.length - 1; i++ ){
if(abs(a[i]+a[i+1]) < min){
min = abs(a[i]+a[i+1]);
l = i;
}
}
System.out.println(a[l]+","+a[l+1]);
}
private static void qSort(int[] a, int n) {
recQuickSort(a, 0, n-1);
}
private static void recQuickSort(int[] arr, int left, int right) {
if(right - left <= 0)
return;
else{
int pivot = abs(arr[right]);
int partition = partitionIt(arr,left, right, pivot);
recQuickSort(arr, left, partition-1);
recQuickSort(arr, partition+1, right);
}
}
private static int abs(int i) {
return i<0?-i:i;
}
private static int partitionIt(int[] arr, int left, int right, int pivot) {
int leftPtr = left - 1;
int rightPtr = right;
int temp;
while(true){
while(abs(arr[++leftPtr])<pivot);
while(rightPtr > 0 && abs(arr[--rightPtr])>pivot);
if(leftPtr >= rightPtr)
break;
else{
temp = arr[leftPtr];
arr[leftPtr]= arr[rightPtr];
arr[rightPtr]= temp;
}
}
temp = arr[leftPtr];
arr[leftPtr]= arr[right];
arr[right] = temp;
return leftPtr;
}
}
package page1;
public class FindTheMissingAndRepeatingElement {
/**
* @param args
*/
public static void main(String[] args) {
int a[] = {5,4,4,1,2};
for(int i = 0;i < a.length;i++){
if(a[Math.abs(a[i]) - 1]>0){
a[Math.abs(a[i]) - 1] = - a[Math.abs(a[i]) - 1];
}else
System.out.println(a[i]);
}
for(int i = 0;i< a.length;i++ ){
if(a[i]>0){
System.out.println(i+1);
}
}
}
}
public class Print2Coils {
/**
* @param args
*/
public static void main(String[] args) {
int r,c,i=1;
int n = 2;
int a[][] = new int[4*n][4*n];
for(r=0;r<4*n;r++){
for(c=0;c<4*n;c++){
a[r][c] = i;
i++;
}
}
for(r=0;r<4*n;r++){
for(c=0;c<4*n;c++){
System.out.print(a[r][c]+" ");
}
System.out.println();
}
print2Coils(a,4*n);
}
private static void print2Coils(int[][] a, int n) {
printCoil(a,n/2,n/2-1,1,n);
System.out.println();
printCoil(a,n/2-1,n/2,-1,n);
}
private static void printCoil(int[][] a, int r, int c, int i, int n) {
int x = 0;
int y = 0;
int z = 2;
System.out.print(a[r][c]+" ");
while(true){
while(x<z){
r = r-i;
if(r<0||r>=n)
break;
System.out.print(a[r][c]+" ");
x++;
}
if(r<0||r>=n)
break;
while(y<z){
c=c+i;
if(c<0||c>=n)
break;
System.out.print(a[r][c]+" ");
y++;
}
if(c<0||c>=n)
break;
x=y=0;
z=z+2;
i=-i;
}
}
}
Repcloptonchirsty, Android Engineer at 8x8
Hello, I am an Organic chemist and my all study and degree is complete from New York.Apart from this ...
Can we do DFS without using Extra space? I see we use stack for DFS and queue for BFS.
- anand July 01, 2013