anand
BAN USERimport java.util.*;
public class FristAndLastOccurenceInSortedArray {
public static void main(String[] args) {
int[] arr = {1,2,4,4,4,5,6,7,9,10};
printFirstAndLastOccurence(arr, 4);
}
private static void printFirstAndLastOccurence(int[] arr, int key) {
Stack<Integer> stk1 = new Stack<Integer>();
stk1.push(0);
stk1.push(arr.length - 1);
int first = 0;
int last = 0;
while (!stk1.isEmpty()) {
int high = stk1.pop();
int low = stk1.pop();
int mid = (low + high) / 2;
if (low <= high) {
mid = (low + high) / 2;
if (arr[mid] == key) {
if (first == 0 && last == 0) {
first = mid;
last = mid;
} else if (mid < first) {
first = mid;
} else if (mid > last) {
last = mid;
}
}
if (key <= arr[mid]) {
stk1.push(low);
stk1.push(mid - 1);
} else {
stk1.push(mid + 1);
stk1.push(high);
}
}
}
System.out.println("First : " + first + " Last : " + last);
}
}
/* We can solve this by using HashMap or HashSet. Hope this is also one of the effective solution */
public class ReverseArrayOnlyOneCharacter {
public static void main(String[] args) {
String str = "aabdceaaabbbcd";
int[] tmparr = new int[str.length()];
for (int i = str.length() - 1; i >= 0; i--) {
int ch = (int) str.charAt(i);
int mod = (((ch - 97) % 26) % (str.length() - 1));
if (tmparr[mod] == ch) {
continue;
} else {
System.out.println((char)ch);
tmparr[mod] = ch;
}
}
}
}
public void smallestPathOfAll() {
List<List<Integer>> list = new ArrayList<List<Integer>>();
_allPaths(root, 0, 0, list, new ArrayList<Integer>());
//now compute sum of all paths and find min sum
List<Integer> minpath = null;
int minsum = Integer.MAX_VALUE;
for (List<Integer> ll : list) {
int sum = 0;
for (Integer data : ll) {
sum += data;
}
if (sum < minsum) {
minsum = sum;
minpath = ll;
}
}
String appendix = "";
for (Integer data : minpath) {
System.out.print(appendix + data);
appendix = "->";
}
System.out.println("===" + minsum);
}
private void _allPaths(TreeNode node, int pathLocation,
int pathsize, List<List<Integer>> list,
List<Integer> tmplist) {
if (node == null) {
return;
}
tmplist.add(pathLocation, node.data);
pathsize++;
if (node.left == null && node.right == null) {
fillPath(pathsize, list, tmplist);
pathsize--;
}
_allPaths(node.left, pathLocation + 1, pathsize, list, tmplist);
_allPaths(node.right, pathLocation + 1, pathsize, list, tmplist);
}
public void subTreeLevelSum(List<Integer> item) {
if (root == null) {
return;
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
sumSubTreeWithLevel(root, item, 1, map);
Set<Integer> set = map.keySet();
int min = Integer.MAX_VALUE;
int givenkey = Integer.MAX_VALUE;
for (Integer key : set) {
int sum = map.get(key);
if (sum < min) {
givenkey = key;
min = sum;
}
}
System.out.println("Minimum Sum : " + min + " with a given key : " + givenkey);
}
private void sumSubTreeWithLevel(TreeNode node, List<Integer> items, int level, Map<Integer, Integer> map) {
if (node == null) {
return;
}
if (items.contains(node.data)) {
int sum = sumUpTheBinaryTree(level, node);
map.put(node.data, sum);
}
sumSubTreeWithLevel(node.left, items, level + 1, map);
sumSubTreeWithLevel(node.right, items, level + 1, map);
}
private int sumUpTheBinaryTree(int level, TreeNode node) {
if (node == null) {
return 0;
}
int sum1 = sumUpTheBinaryTree(level + 1, node.left);
int sum2 = sumUpTheBinaryTree(level + 1, node.right);
int result = node.data * level + sum1 + sum2;
return (result);
}
INPUT:
TreePath t = new TreePath();
t.insert(4);
t.insert(2);
t.insert(3);
t.insert(1);
t.insert(6);
t.insert(5);
t.insert(7);
// t.postorder();
List<Integer> items = new ArrayList<Integer>();
items.add(6);
items.add(2);
t.subTreeLevelSum(items);
OUTPUT:
-------------
Minimum Sum : 16 with a given key : 2
public class CountDuplicateChars {
public static void main(String[] args) {
String str = "aabbacklccl";
int[] count = new int[26];
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
int reminder = ((int) ch) % 97;
count[reminder] = count[reminder] + 1;
}
StringBuffer sb = new StringBuffer();
for (int i = 0; i < count.length; i++) {
if (count[i] > 0) {
int ch = 97 + i;
sb.append(Character.toString((char) ch)+count[i]);
}
}
System.out.println(sb.toString());
}
}
package com.my.algo.problemsolving;
public class SpiralTraversal {
public static void main(String[] args) {
int arr[][]=
{{1, 2, 3, 4, 5, 6},
{7, 8, 9, 10, 11, 12},
{13, 14, 15, 16, 17, 18},
{19, 20, 21, 22, 23, 24},
{25, 26, 27, 28, 29, 30},
{31, 32, 33, 34, 35, 36}};
int rowcount = 6;
int colcount = 6;
int total = rowcount * colcount;
int count = 0;
int idx1 = 0;
int idx3 = rowcount - 1;
int idx4 = idx1;
while (count < total) {
for (int i = idx1; i < colcount; i++) {
System.out.print(arr[idx1][i] + " ");
count++;
}
for (int j = idx1 + 1; j <= rowcount - 1; j++) {
System.out.print(arr[j][colcount - 1] + " ");
count++;
}
idx3 = colcount - 1;
for (int k = idx3 - 1; k >= idx1; k--) {
System.out.print(arr[idx3][k] + " ");
count++;
}
idx4 = rowcount - 1;
for (int p = idx4 - 1; p > idx1; p--) {
System.out.print(arr[p][idx1] + " ");
count++;
}
rowcount--;
colcount--;
idx1 = idx1 + 1;
}
}
}
OUTPUT:
-------------
1 2 3 4 5 6 12 18 24 30 36 35 34 33 32 31 25 19 13 7 8 9 10 11 17 23 29 28 27 26 20 14 15 16 22 21
Complexity : O(n) with no additional space
public class MaxProductOfThreeNumbers {
static int maxproduct(int[] array) {
if (array == null || array.length < 3) {
throw new IllegalArgumentException("Invalid argument");
}
Integer max1 = Integer.MIN_VALUE;
Integer max2 =Integer.MIN_VALUE;
Integer max3 = Integer.MIN_VALUE;
for (int i = 0; i < array.length; i++) {
int comp = array[i];
if (comp > max1) {
max1 = comp;
}
if (max2 < max1) {
int tmp = max2;
max2 = max1;
max1 = tmp;
}
if (max2 > max3) {
int tmp = max2;
max2 = max3;
max3 = tmp;
}
}
System.out.println("Max values : " + max1 + ", " + max2 + ", " + max3);
return (max1.intValue() * max2.intValue() * max3.intValue());
}
public static void main(String[] args) {
int[] array = {5, 6, 2, 8, 4, 1, 10, 12, 3, 15};
System.out.println("Max product : "+ maxproduct(array));
}
}
OUTPUT:
-------------
Max values : 10, 12, 15
Max product : 1800
Complexity : O(n)
package com.my.algo.problemsolving;
public class MissingElement {
public static void main(String[] args) {
int[] a1 = {1,2,3,4,5,6,7};
int[] a2 = {1,2,4,5,6,7};
int sum1 = 0; int sum2 = 0;
if (a1.length == a2.length) {
System.out.println("Both arrays are identical.. not missing");
System.exit(0);
}
for (int i = 0; i < a1.length; i++) {
sum1 += a1[i];
}
for (int i = 0; i < a2.length; i++) {
sum2 += a2[i];
}
if (a1.length > a2.length)
System.out.println("Missing element : " + (sum1 - sum2));
else
System.out.println("Missing element : " + (sum2 - sum1));
}
}
public class DuplicateCharsInString {
public static void main(String[] args) {
String str = "aabbacklccl";
int[] count = new int[26];
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
int reminder = ((int) ch) % 97;
count[reminder] = count[reminder] + 1;
}
StringBuffer sb = new StringBuffer();
for (int i = 0; i < count.length; i++) {
if (count[i] > 0) {
int ch = 97 + i;
sb.append(Character.toString((char) ch)+count[i]);
}
}
System.out.println(sb.toString());
}
}
class ReverseArray {
public static void arrayWithSubsetN(int[] array, int n) {
int i = 0;
while (i < array.length) {
int start = i;
int j = i;
int end = (i + n) - 1;
boolean flag = false;
for (j = i ; j < end && end < array.length; j++) {
if (array[j] > array[j + 1]) {
flag = false;
break;
}
flag = true;
}
if (flag) {
while (start < end) {
int tmp = array[start];
array[start] = array[end];
array[end] = tmp;
start++;
end--;
}
i = ((i + n) - 1) + 1;
continue;
}
i++;
}
}
}
public class ArrayReverse {
public static void main(String[] args) {
int[] array = {1,2,3,4,5,6,7,8,9,10,12};
ReverseArray.arrayWithSubsetN(array, 3);
for (int i = 0; i< array.length; i++) {
System.out.print(array[i] + " ");
}
}
}
- anand June 20, 2016