Coder
BAN USERThis problem is similar to finding the next inorder successor of the given node.
public static void findNextLargest(TreeNode node,TreeNode target){
TreeNode temp=null;
if(target.right!=null){
temp = target.right;
while(temp.left!=null){
temp = temp.left;
}
System.out.println(temp.val);
return;
}
while(node!=null){
if(target.val < node.val){
temp = node;
node = node.left;
}else if(target.val > node.val){
node = node.right;
}else
break;
}
if(temp!=null)
System.out.println(temp.val);
return;
}
Java Code:
public class Practice93 {
public static void main(String[] args){
System.out.println(GetExcelColumnName(26*26+1));
System.out.println(getColumnNumber("ZA"));
}
public static int getColumnNumber(String str){
int sum=0;
for(int i =str.length()-1;i>=0;i--){
sum = sum + (int)(str.charAt(i) - 64) * (int)Math.pow(26, str.length()-i-1);
}
return sum;
}
private static String GetExcelColumnName(int n) {
String columnName = "";
while(n>0){
int val = (n-1)%26;
columnName = (char)(val+65) + columnName;
n = (n-val)/26;
}
return columnName;
}
}
Since the frog can jump only 1 or 2 steps, the number of combinations of 1's and 2's to reach to a given sum 'n' is given by (n+1)th term of the Fibonacci Series where
f[0] = 0;
f[1] = 1;
f[2] = 1;
f[3] = 2;
f[4] = 3
f[5] = 5;
f[6] = 8;
f[7] = 13 and so on.
So if n =5, then the number of possible steps will be (n+1)th term which is the 6th term in the fibonacci series whose value is 8.
Possible combinations :
1+1+1+1+1 = 1+1+1+2 = 1+1+2+1 = 1+2+1+1 = 2+1+1+1 = 2+2+1 = 2+1+2 = 1+2+2
Similarly, n = 6, then the number of possible steps will be (n+1)th term which is the 7th term in the fibonacci series whose value is 13.
Possible Combinations:
1 1 1 1 1 1
1 1 1 1 2
1 1 1 2 1
1 1 2 1 1
1 2 1 1 1
2 1 1 1 1
1 1 2 2
1 2 1 2
2 1 1 2
2 1 2 1
2 2 1 1
1 2 2 1
2 2 2
Java Code :
public class Problem90 {
public static void main(String[] args){
int target = 6;
System.out.println(findNumberOfSteps(target));
}
public static int findNumberOfSteps(int n){
int prepre=0,pre=1,sum=0;
for(int i=0;i<n;i++){
sum = pre + prepre;
prepre = pre;
pre = sum;
}
return sum;
}
}
Implementation of GK idea as Java Code.
import java.util.Comparator;
import java.util.PriorityQueue;
class Elem{
int val;
int pos;
int arr;
public Elem(int val, int pos, int arr) {
super();
this.val = val;
this.pos = pos;
this.arr = arr;
}
}
public class Problem88 {
static class ElemComparator implements Comparator<Elem>{
public int compare(Elem e1, Elem e2){
return e1.val - e2.val;
}
public static void main(String args[]){
int arr[][] = {{0,10,255}, {2 , 11 , 257} ,{4,12,258}};
ElemComparator ec = new ElemComparator();
PriorityQueue pq = new PriorityQueue(10,ec);
for(int i=0;i<arr.length;i++){
Elem e = new Elem(arr[i][0],0,i);
pq.add(e);
}
Elem mn;
int min = -1;
int max = 9999999;
Elem mx;
while(pq.size() == 3){
mn = (Elem)pq.poll();
mx = (Elem)(pq.toArray())[pq.size()-1];
if((mx.val - mn.val) < (max - min)){
min = mn.val;
max = mx.val;
}
int arr1 = mn.arr;
int pos = mn.pos;
//if(pos >= arr[arr1].length-1 || mx.pos >= arr[arr1].length-1)
// break;
if(pos < arr[arr1].length-1)
pq.add(new Elem(arr[arr1][pos+1],pos+1,arr1));
}
System.out.println("Range is :: "+ min + " - " + max);
}
}
}
Steps:
1. Take the sum of all the population.
2. Pick a random number between from 1 to the total.
3. Start subtracting the elements in the array from the chosen random number say 'rand'.
4. Check for the value of rand after each substraction. If the value is < = 0, then choose that country.
The below program will give you an brief idea of the algo.
Code:
public class Practice78 {
public static void main(String[] args){
int arr[] = {1000,3000,4544,16344,7890,500};
int sum=0;
for(int i=0;i<arr.length;i++){
sum = sum + arr[i];
}
Random r = new Random();
int rand = r.nextInt(sum+1);
for(int i=0;i<arr.length;i++){
rand =rand - arr[i];
if(rand <=0){
System.out.println("Random population choosen is :: "+arr[i]);
break;
}
}
}
}
We can solve this problem by storing the product of all rows in a rows array and then the product of all column in a column array. Then, we will be simple multiplication of the rows and column.
Code:
public class Practice77 {
public static void main(String[] args){
int[][] arr = {{1,2,3,1},
{1,0,-1,2},
{-1,1,1,1}};
int rows[] = new int[arr.length];
int col[] = new int[arr[0].length];
int tot = 1;
int colNo = 0;
for(int i=0;i<rows.length;i++){
tot = 1;
for(int j=0;j<col.length;j++){
tot = tot * arr[i][j];
}
rows[i] = tot;
}
for(int i=0;i<col.length;i++){
tot = 1;
for(int j=0;j<rows.length;j++)
tot = tot * arr[j][i];
col[i] = tot;
}
for(int i=0;i<rows.length;i++){
for(int j=0;j<col.length;j++){
int val = rows[i] * col[j];
if(val > 0){
arr[i][j] = 1;
}else if(val == 0){
arr[i][j] = 0;
}else{
arr[i][j] = -1;
}
}
}
for(int i=0;i<rows.length;i++){
System.out.println(Arrays.toString(arr[i]));
}
}
}
Use two pointers : slow and fast. Slow pointer moves forward by one step and fast by two steps. If your linked list does not have a cycle then your fast will reach the end of linked list and the check will terminate. If there is a cycle, then fast and slow pointer will collide at some point. So, if fast == slow then there is a cycle in the linkedlist.
- Coder January 29, 2014The best way to get the max value of int on 32 or 64 bit processors is by negating the 0(so that we get all 1's) and then doing an unsigned right shift (>>> in java).
int c = (~0) >>> 1;
In C, if we do normal shift (~0 >> 1), the compiler will perform arithmetic shift and will append the sign bit into the shifted bit. Instead, we would have to force a logical shift by explicitly declaring the value as unsigned, i.e. by doing something like this:
~0u >> 1;
This type of problem is typically known as Partition problem. The number of partitions of a number grows exponentially. I read somewhere that Its an NP-Complete problem. Here are few references that you can check to know more about it.
math.stackexchange.com/questions/217597/number-of-ways-to-write-n-as-a-sum-of-k-nonnegative-integers
en.wikipedia.org/wiki/Partition_%28number_theory%29#Intermediate_function
stackoverflow.com/questions/400794/generating-the-partitions-of-a-number#400810
Some of these links will provide you with the implementation in some lang. You can go through the math for wikipedia link.
The easiest way of finding the GCD of two numbers is by using the Euclidean algorithm.
en.wikipedia.org/wiki/Euclidean_algorithm.
Code:
Recursive Code
public static int gcd(int a,int b){
if(b==0)
return a;
else return gcd(b,a%b);
}
Non-Recursive:
public static int gcd(int a,int b){
while(b!=0){
int t = a%b;
a = b;
b = t;
}
return a;
}
We can solve the above problem using recursion with backtracking.
We start by moving from the bottom-right cell that is (m-1,n-1). We can move either left or top from each cell. Recursively call the findPath function with left cell and top cell. If you encounter a 0 at a cell position, discard that path. When we reach the (0,0) cell, increment the count variable.
Keep a count variable that keeps track of all the possible path.
Code :
public class Practice67 {
public static void main(String[] args){
int arr[][] = {{1,1,1,1},
{1,0,0,1},
{1,0,0,1},
{1,1,1,1}};
System.out.println(findPaths(arr,3,3,0));
}
public static int findPaths(int[][] arr,int m,int n,int count){
if(0 == m && 0 == n){
count++;
return count;
}
if(n > 0 && arr[m][n-1] != 0){
count = findPaths(arr,m,n-1,count);
}
if(m>0 && arr[m-1][n] != 0){
count = findPaths(arr,m-1,n,count);
}
return count;
}
}
Yeah, I forgot to consider that case. The following code will work for upper case as well.
public class Practice65 {
public static void main(String args[]){
String str1 = "AAAABBAABBAAABAB";
String str2 = "AABBAAA";
int j=0,i=0;
while(i<str1.length()){
if(str2.charAt(j) == str1.charAt(i)){
j++;
i++;
if(j == str2.length()){
System.out.println(i - str2.length());
break;
}
}else{
i = i - j; // Add this piece of code.
j=0;
i++;
}
}
}
}
Worst case Complexity : O(n)
public class Practice65 {
public static void main(String args[]){
String str1 = "abcdefcde";
String str2 = "de";
int j=0,i=0;
while(i<str1.length()){
if(str2.charAt(j) == str1.charAt(i)){
j++;
i++;
if(j == str2.length()){
System.out.println(i - str2.length());
break;
}
}else{
j=0;
i++;
}
}
}
}
Works for both positive and negative exponent.
Memory efficient implementation. Complexity : O(log n)
public class Practice63 {
public static void main(String[] args){
int a = 2;
int b = 3;
System.out.println(power(a,b));
}
public static double power(int a, int b){
double temp = 1;
boolean isNeg = false;
if(b<0){
b = -b;
isNeg = true;
}
while(b>0){
if((b&1) == 1){
temp = temp * a;
}
a = a*a;
b = b>>1;
}
if(isNeg)
return 1/temp;
else
return temp;
}
}
This is something that came to my mind. Correct me if I am wrong.
You can do the preorder traversal of the first tree. Store the result in a string. Do preorder traversal of second tree. Store result in second string. Find if second string is substring of first.
Next. Do the same for inorder traversal. If both the result come out to be true then T2 is subtree of T1.
Complexity will be : O(m+n).
Java Code. Complexity O(n). Done by using two array indexes.
public class TestOnly{
public static void main(String args[]){
int arr[] = {2,1,1,1,3,4,4,4,5};
int m = 2;
rearrange(arr,m);
System.out.println(Arrays.toString(arr));
}
public static void rearrange(int[] arr,int m){
int i=0;
int j=0,count=0;
while(i<arr.length-1){
count=1;
j = i + 1;
while( j<arr.length && arr[i] == arr[j]){
count++;
j++;
}
if(count > 2){
if(j>arr.length -1){
j = (j % arr.length);
}
int tmp = arr[i+m];
arr[i+m] = arr[j];
arr[j] = tmp;
i = i+m;
}
i++;
}
}
}
The following code finds the next highest and prev lowest number that contains the same number of 1's as the given number.
Number Properties Approach for Next Number
Observations:
»»If we “turn on” a 0, we need to “turn off” a 1
»»If we turn on a 0 at bit i and turn off a 1 at bit j, the number changes by 2^i - 2^j.
»»If we want to get a bigger number with the same number of 1s and 0s, i must be bigger than j.
Solution:
1. Traverse from right to left. Once we’ve passed a 1, turn on the next 0. We’ve now increased the number by 2^i. Yikes! Example: xxxxx011100 becomes xxxxx111100
2. Turn off the one that’s just to the right side of that. We’re now bigger by 2^i - 2^(i-1) Example: xxxxx111100 becomes xxxxx101100
3. Make the number as small as possible by rearranging all the 1s to be as far right as possible: Example: xxxxx101100 becomes xxxxx100011
To get the previous number, we do the reverse.
1. Traverse from right to left. Once we’ve passed a zero, turn off the next 1. Example: xxxxx100011 becomes xxxxx000011.
2. Turn on the 0 that is directly to the right. Example: xxxxx000011 becomes xxxxx010011.
3. Make the number as big as possible by shifting all the ones as far to the left as possible. Example: xxxxx010011 becomes xxxxx011100
package GoodProbs;
public class Practice48 {
public static void main(String args[]){
int a = 48;
System.out.println("Next high is :: "+getNextHigh(a));
System.out.println("Next Low is :: "+getPrevLow(a));
}
public static int getNextHigh(int a){
int num = a;
int bit = num & 1;
int count = 0;
int flag = 1;
while(num > 0 && (bit == 1 || flag == 1)){
if(bit == 1)
flag = 0;
count++;
num = num >> 1;
bit = num & 1;
}
if(bit == 0){
int xor = (int) (Math.pow(2, count-1) + Math.pow(2, count));
a = a ^ xor;
}
num = a;
int b = 0,c = ~0;
int var = 0;
for(int i=0;i<count-1;i++){
if((num & 1) == 1){
b = b + (int)Math.pow(2, i);
}else{
var++;
}
num = num >> 1;
c = c << 1;
}
while(var > 0){
b = b >> 1;
var--;
}
return (a & c) | b;
}
public static int getPrevLow(int a){
int num = a;
int bit = num & 1;
int count = 0;
int flag = 1;
while(num > 0 && (bit == 0 || flag == 1)){
if(bit == 0)
flag = 0;
count++;
num = num >> 1;
bit = num & 1;
}
if(bit == 1){
int xor = (int) (Math.pow(2, count-1) + Math.pow(2, count));
a = a ^ xor;
}
num = a;
int b = 0,c = ~0;
int var = 0;
for(int i=0;i<count-1;i++){
if((num & 1) == 1){
b = b + (int)Math.pow(2, i);
}else{
b = b << 1;
}
num = num >> 1;
c = c << 1;
}
return (a & c) | b;
}
}
Complexity : O(n)
public class TestOnly{
public static void main(String args[]){
int a[] = {1,2,3,4,5,6,7,8};
merge(a,1,4);
System.out.println(Arrays.toString(a));
}
public static void merge(int a[], int first, int second) {
while(first<second){
int tmp = a[second];
shiftArray(a,first,second);
a[first] = tmp;
first = first + 2;
second++;
}
}
public static void shiftArray(int[] a,int first,int second){
while(second>first){
a[second] = a[second-1];
second--;
}
}
}
Generate all the permutaion of the string and check against the dictionary whether the word is valid or not.
public class Practice55 {
public static void main(String args[]){
String str = "abc";
printPermu("",str);
}
public static void printPermu(String prefix,String str){
int n = str.length();
if(n == 0){
//Write here the code to check whether the word is present in dictionary. If yes, print it.
System.out.println(prefix);
}else{
for(int i=0;i<n;i++){
printPermu(prefix + str.charAt(i),str.substring(0,i) + str.substring(i+1,n));
}
}
}
}
Use MaxHeap and MinHeap concept. The size of the maxHeap can be either equal or one greater than minheap. When a new element arrives, insert them into the maxHeap or minHeap as per follows:
If MaxHeap and minHeap size is equal then
1. If the number is greater than root of maxHeap (It has to be inserted into minHeap then.) But since the size of minheap cannot exceed MaxHeap, we will take the root of minheap and insert into MaxHeap. Then insert the new element into minHeap.
2. Otherwise, if the number is smaller that root of maxHeap, then insert the number in maxHeap. (Remember the size of maxheap can be 1 greater than Minheap).
If the size of maxHeap and minHeap is not the same then
1. If number is small than root of maxHeap, it has to be inserted in maxHeap. Since the size is not same, it means that the maxHeap is already 1 greater than minheap. Since the difference cannot be more than 1, we shift the root of MaxHeap into minHeap and insert the number in MaxHeap.
2. Otherwise, If number is larger than root of maxHeap, insert it into minHeap.
Use priority queue to implement MinHeap and MaxHeap behaior.
Code :
public class Practice52{
static class ComparatorMax implements Comparator<Integer>{
public int compare(Integer arg0, Integer arg1) {
// TODO Auto-generated method stub
return arg1 - arg0;
}
}
static class ComparatorMin implements Comparator<Integer>{
@Override
public int compare(Integer arg0, Integer arg1) {
// TODO Auto-generated method stub
return arg0 - arg1;
}
}
public static void main(String args[]) throws IOException{
ComparatorMax maxHeapComparator = new ComparatorMax();
ComparatorMin minHeapComparator = new ComparatorMin();
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(10,maxHeapComparator);
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(10,minHeapComparator);
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true){
System.out.println("\n Enter the number :: ");
String str = br.readLine();
int num = Integer.parseInt(str);
if(num == -1){
break;
}
insertNum(num,maxHeap,minHeap);
System.out.println(displayMedian(maxHeap,minHeap));
}
}
public static double displayMedian(PriorityQueue<Integer> maxHeap,PriorityQueue<Integer> minHeap){
if(maxHeap.isEmpty()) return minHeap.peek();
if(minHeap.isEmpty()) return maxHeap.peek();
if(minHeap.size() == maxHeap.size())
return ((double)(minHeap.peek() + maxHeap.peek())/2);
else
return maxHeap.peek();
}
public static void insertNum(int num,PriorityQueue<Integer> maxHeap,PriorityQueue<Integer> minHeap){
if(maxHeap.size() == minHeap.size()){
if(maxHeap.peek()!= null && num > maxHeap.peek()){
maxHeap.offer(minHeap.poll());
minHeap.offer(num);
}else{
maxHeap.offer(num);
}
}else{
if(num < maxHeap.peek()){
minHeap.offer(maxHeap.poll());
maxHeap.offer(num);
}else{
minHeap.offer(num);
}
}
}
}
Use MaxHeap and MinHeap concept. The size of the maxHeap can be either equal or one greater than minheap. When a new element arrives, insert them into the maxHeap or minHeap as per follows:
If MaxHeap and minHeap size is equal then
1. If the number is greater than root of maxHeap (It has to be inserted into minHeap then.) But since the size of minheap cannot exceed MaxHeap, we will take the root of minheap and insert into MaxHeap. Then insert the new element into minHeap.
2. Otherwise, if the number is smaller that root of maxHeap, then insert the number in maxHeap. (Remember the size of maxheap can be 1 greater than Minheap).
If the size of maxHeap and minHeap is not the same then
1. If number is small than root of maxHeap, it has to be inserted in maxHeap. Since the size is not same, it means that the maxHeap is already 1 greater than minheap. Since the difference cannot be more than 1, we shift the root of MaxHeap into minHeap and insert the number in MaxHeap.
2. Otherwise, If number is larger than root of maxHeap, insert it into minHeap.
Use priority queue to implement MinHeap and MaxHeap behaior.
Code :
public class Practice52{
static class ComparatorMax implements Comparator<Integer>{
public int compare(Integer arg0, Integer arg1) {
// TODO Auto-generated method stub
return arg1 - arg0;
}
}
static class ComparatorMin implements Comparator<Integer>{
@Override
public int compare(Integer arg0, Integer arg1) {
// TODO Auto-generated method stub
return arg0 - arg1;
}
}
public static void main(String args[]) throws IOException{
ComparatorMax maxHeapComparator = new ComparatorMax();
ComparatorMin minHeapComparator = new ComparatorMin();
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(10,maxHeapComparator);
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(10,minHeapComparator);
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true){
System.out.println("\n Enter the number :: ");
String str = br.readLine();
int num = Integer.parseInt(str);
if(num == -1){
break;
}
insertNum(num,maxHeap,minHeap);
System.out.println(displayMedian(maxHeap,minHeap));
}
}
public static double displayMedian(PriorityQueue<Integer> maxHeap,PriorityQueue<Integer> minHeap){
if(maxHeap.isEmpty()) return minHeap.peek();
if(minHeap.isEmpty()) return maxHeap.peek();
if(minHeap.size() == maxHeap.size())
return ((double)(minHeap.peek() + maxHeap.peek())/2);
else
return maxHeap.peek();
}
public static void insertNum(int num,PriorityQueue<Integer> maxHeap,PriorityQueue<Integer> minHeap){
if(maxHeap.size() == minHeap.size()){
if(maxHeap.peek()!= null && num > maxHeap.peek()){
maxHeap.offer(minHeap.poll());
minHeap.offer(num);
}else{
maxHeap.offer(num);
}
}else{
if(num < maxHeap.peek()){
minHeap.offer(maxHeap.poll());
maxHeap.offer(num);
}else{
minHeap.offer(num);
}
}
}
}
Number Properties Approach for Next Number
Observations:
»»If we “turn on” a 0, we need to “turn off” a 1
»»If we turn on a 0 at bit i and turn off a 1 at bit j, the number changes by 2^i - 2^j.
»»If we want to get a bigger number with the same number of 1s and 0s, i must be bigger than j.
Solution:
1. Traverse from right to left. Once we’ve passed a 1, turn on the next 0. We’ve now increased the number by 2^i. Yikes! Example: xxxxx011100 becomes xxxxx111100
2. Turn off the one that’s just to the right side of that. We’re now bigger by 2^i - 2^(i-1) Example: xxxxx111100 becomes xxxxx101100
3. Make the number as small as possible by rearranging all the 1s to be as far right as possible: Example: xxxxx101100 becomes xxxxx100011
To get the previous number, we do the reverse.
1. Traverse from right to left. Once we’ve passed a zero, turn off the next 1. Example: xxxxx100011 becomes xxxxx000011.
2. Turn on the 0 that is directly to the right. Example: xxxxx000011 becomes xxxxx010011.
3. Make the number as big as possible by shifting all the ones as far to the left as possible. Example: xxxxx010011 becomes xxxxx011100
public class Practice48 {
public static void main(String args[]){
int a = 48;
System.out.println("Next high is :: "+getNextHigh(a));
System.out.println("Next Low is :: "+getPrevLow(a));
}
public static int getNextHigh(int a){
int num = a;
int bit = num & 1;
int count = 0;
int flag = 1;
while(num > 0 && (bit == 1 || flag == 1)){
if(bit == 1)
flag = 0;
count++;
num = num >> 1;
bit = num & 1;
}
if(bit == 0){
int xor = (int) (Math.pow(2, count-1) + Math.pow(2, count));
a = a ^ xor;
}
num = a;
int b = 0,c = ~0;
int var = 0;
for(int i=0;i<count-1;i++){
if((num & 1) == 1){
b = b + (int)Math.pow(2, i);
}else{
var++;
}
num = num >> 1;
c = c << 1;
}
while(var > 0){
b = b >> 1;
var--;
}
return (a & c) | b;
}
public static int getPrevLow(int a){
int num = a;
int bit = num & 1;
int count = 0;
int flag = 1;
while(num > 0 && (bit == 0 || flag == 1)){
if(bit == 0)
flag = 0;
count++;
num = num >> 1;
bit = num & 1;
}
if(bit == 1){
int xor = (int) (Math.pow(2, count-1) + Math.pow(2, count));
a = a ^ xor;
}
num = a;
int b = 0,c = ~0;
int var = 0;
for(int i=0;i<count-1;i++){
if((num & 1) == 1){
b = b + (int)Math.pow(2, i);
}else{
b = b << 1;
}
num = num >> 1;
c = c << 1;
}
return (a & c) | b;
}
}
public class Practice6 {
public static void main(String args[])throws IOException{
int arr[] = {4,5,6,7,8,1,2,3};
int num = 7;
int last = arr.length-1;
int first = 0;
performSearch(arr,first,last,num);
}
public static void performSearch(int arr[],int first,int last,int num){
int mid = (first + last)/2;
if(arr[mid] == num){
System.out.println("Index is :: "+mid);
return;
}
else if(arr[first]<arr[mid]){
if(num >= arr[first] && num<arr[mid])
binarySearch(arr,first,mid-1,num);
else
performSearch(arr,mid+1,last,num);
}else{
if(num>arr[mid] && num <= arr[last]){
binarySearch(arr,mid+1,last,num);
}else{
performSearch(arr,mid+1,last,num);
}
}
}
public static void binarySearch(int arr[],int first,int last,int num){
if(first<last){
int mid = (first+last)/2;
if(arr[mid] == num){
System.out.println("Index is :: "+mid);
return;
}
binarySearch(arr,first,mid-1,num);
binarySearch(arr,mid+1,last,num);
}else
return;
}
}
void findNext(Node *root,int target){
public static Node * prev = NULL;
if(root == NULL)
return;
else{
findNext(root->left,target);
if(prev != NULL){
if(prev -> value == target && prev->value < root->value){
printf("%d",root->value);
prev = root;
findNext(root->right,target);
}
}
public static void main(String args[]){
String ss = "(a(b))(c(d(f))g)(y(h))";
int maxcount=0,count=0;
for(int i=0;i<ss.length();i++){
if(ss.charAt(i) == '(')
count++;
else if(ss.charAt(i) == ')')
count--;
if(count > maxcount)
maxcount = count;
}
System.out.println("Max depth is :: "+maxcount);
}
public static void main(String args[]){
int moveBy = 30;
Date d = new Date();
Calendar c = Calendar.getInstance();
c.setTime(d);
for(int i=0;i<moveBy;i++){
c.add(c.DAY_OF_WEEK, 1);
while(c.get(c.DAY_OF_WEEK) == c.SATURDAY || c.get(c.DAY_OF_WEEK) == c.SUNDAY){
c.add(c.DAY_OF_WEEK, 1);
}
}
System.out.println("Business day for 5 days from now is "+c.getTime().toString());
}
public static void main(String args[]){
String str = "aaaabbbbcccddddefgh";
StringBuilder sbr = new StringBuilder("");
int count=0;
for(int i=0;i<str.length();){
count=1;
sbr.append(str.charAt(i));
while(i<str.length() && (i+1)<str.length() && str.charAt(i)==str.charAt(i+1)){
count++;
i++;
}
sbr.append(count);
i++;
}
System.out.println(sbr);
}
public static void main(String args[]){
int arr[] = {1, 0, 0, 1, 0, 0, 1, 0};
int sum=0,maxsum=0,num=0;
int startIndex=0,stopIndex=0,prevIndex=0;
for(int i=0;i<arr.length;i++){
if(arr[i] == 1){
num = -1;
}else if(arr[i] == 0){
num = 1;
}
sum = sum + num;
if(maxsum<sum){
maxsum = sum;
prevIndex = startIndex;
stopIndex = i;
}else if(sum<0){
sum = 0;
startIndex = i+1;
}
}
for(int j=prevIndex;j<=stopIndex;j++){
System.out.print(" "+arr[j]);
}
}
C code to merge two sorted linked list. The original list is destroyed and pointers are modified so as to obtain a sorted list. Hence space complexity is O(1) and time complexity is O(n+m) when n+m are total number of nodes in both the list.
Node *mergeList(Node *i, Node *j)
{
Node *node = i;
Node *node1 = j;
Node *temp,*index=NULL,*head=NULL;
int flag=0;
while(1){
if(node == NULL || node1 == NULL){
break;
}
if(node->value <= node1->value){
if(head == NULL){
head = node;
index = node;
node = node->next;
continue;
}
index->next = node;
index = node;
node = node->next;
}else{
if(head == NULL){
head = node1;
index = node1;
node1=node1->next;
continue;
}
index->next = node1;
index = node1;
node1 = node1->next;
}
}
if(node!=NULL){
index->next = node;
}else if(node1 != NULL){
index->next = node1;
}
return head;
}
void main(){
int i,j;
int arr[] = {1,2,2,2,4,4,4,48,48,48,48,48,48,48,48};
int length = 14;
int index,count=1,findex,fcount=-1;
for(i=0;i<length-1;){
count = 1;
while(arr[i]==arr[i+1]){
count++;
index=i;
i++;
}
if(arr[i]!=arr[i+1])
i++;
if(fcount<count){
fcount = count;
findex = index;
}
}
printf("\nLargest Frequency number :: %d",arr[findex]);
printf("\nFrequency :: %d",fcount);
}
Java code using Pattern and Matcher class.
public static void main(String args[])throws IOException{
File file = new File("Input.txt");
try {
FileReader fr = new FileReader(file);
BufferedReader br = new BufferedReader(fr);
String str = null,finalStr=null;
int count=0,finalCnt=-1;
while((str = br.readLine()) != null){
count=0;
Pattern p = Pattern.compile("[aeiouAEIOU]");
Matcher m = p.matcher(str);
while(m.find()){
count++;
}
if(count>finalCnt){
finalCnt = count;
finalStr = str;
}
}
System.out.println("Max vowel string :: "+finalStr);
System.out.println("Max vowel count :: "+finalCnt);
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
This piece of code will arrange all ASCII characters together in increasing order. I think this is what the question is about.
int arr[255];
char *str = "aadkfskfjsknvnskdfababal234jklfabfblafadfkj";
int i=0,j;
for(i=0;i<255;i++)
arr[i]=0;
i=0;
while(*str != '\0'){
arr[*str]++;
str++;
}
for(i=0;i<255;i++){
for(j=0;j<arr[i];j++){
printf("%c",i);
}
}
int isBalanced(Node *root){
int hl,hr;
if(root == NULL)
return 1;
hl = height(root->left);
hr = height(root->right);
if(abs(hl-hr) <=1 && isBalanced(root>left) && isBalanced(root->right))
return 1;
return 0;
}
int height(Node* root){
if(root == NULL){
return 0;
}
return 1 + max(height(root->left),height(root->right));
}
The best way to implement stack and queue is using linked list as it can grow dynamically. Also, since the operation are performed at the top of stack and Front and Rear of a Queue, they can be easily implemented in linked list using pointers to the head and tail.
Arrays are useful for quick random access. Since a stack or queue requires insertion/deletion operation at the extreme ends of list, linked list will give similar performance like arrays. Plus, it can grow dynamically as compared to Arrays.
Complexity : O(log n)
- Coder March 14, 2014