sudip.innovates
BAN USERThis can be done by simple DFS, extending for only 2 edges.
Worst case complexity would be O(n2)
/**
0->1 100
1->2 200
2->3 50
0->3 400
1->3 100
0 1 2 3
0 0 100 0 400
1 100 0 200 100
2 0 200 0 50
3 400 100 50 0
*/
public static void main(String[] args){
int[][] nodes = new int[][]{{0, 100, 0, 400}, {100, 0, 200, 100}, {0, 200, 0, 50}, {400, 100, 50, 0}};
int org = 0;
int dest = 3;
List<Integer> visited = new ArrayList<Integer>();
visited.add(org);
int n = mincost(nodes, org, dest, 0, 0, Integer.MAX_VALUE, visited);
System.out.println(n);
}
public static int mincost(int[][] nodes, int org, int dest, int hops, int cost, int mincost, List<Integer> visited){
if(org == dest){
if(hops < 4){
mincost = Math.min(mincost, cost);
}
return mincost;
}
if(hops > 3)
return mincost;
int[] connections = nodes[org];
int n = connections.length;
for(int i = 0; i < n; i++){
if(connections[i] != 0 && !visited.contains(i)){
visited.add(i);
mincost = mincost(nodes, i, dest, hops+1, cost+connections[i], mincost, visited);
visited.remove(new Integer(i));
}
}
return mincost;
}
I think that for k=2 it would be, 0,1,10,11. The binary string should be "1101" [decimal value 13], containing all the different values. Similarly for k=3 it would be 111001 [decimal value 57]. This is pretty open questions and would have multiple follow up questions.
Posting the code here with exponential complexity, based on the the above understanding. As ChrisK mentioned the complexity would be (n*2^n). Given the complexity this will not run with k more than 3. Would really love to see a better approach.
public static void main(String[] args) {
int n = 4;
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 200; i++)
sb.append(" ");
StringBuffer sbin = new StringBuffer();
for (int i = 0; i < n; i++)
sbin.append("1");
String min = create(Integer.parseInt(sbin.toString(), 2), Integer.parseInt(sbin.toString(), 2), sbin.toString(), 0, 0, sb.toString(), new HashSet<>());
System.out.println("--------"+min + "=" + Integer.parseInt(min, 2));
}
public static String create(int nn, int n, String str, int indexPrim, int indexBin, String min, Set<String> set) {
if (n == -1) {
if (contains(str, nn) && str.length() < min.length()) {
min = new String(str);
}else if (str.length() < min.length()){
min = create(nn, nn, str, 0, 0, min, set);
}
return min;
}
String nb = Integer.toBinaryString(n);
if (str.contains(nb)) {
set.add(nb);
min = create(nn, n - 1, str, 0, 0, min, set);
} else {
char[] prim = str.toCharArray();
char[] bin = nb.toCharArray();
for (int i = indexPrim; i < prim.length; i++) {
for (int j = indexBin; j < bin.length; j++) {
if (prim[i] == bin[j]) {
min = create(nn, n, str, i + 1, j + 1, min, set);
} else if (i < prim.length) {
String s = str.substring(0, i);
String p = str.substring(i, str.length());
String t = s + bin[j] + p;
min = create(nn, n, t, i + 1, j + 1, min, set);
} else {
min = create(nn, n, str + bin[j], i + 1, j + 1, min, set);
}
}
}
}
return min;
}
public static boolean contains(String str, int n){
for(int i = n; i >= 0; i--){
if(!str.contains(Integer.toBinaryString(n)))
return false;
}
return true;
}
O(logn) soln. -
public static void main(String[] args){
int[] arr = {10, 12, 14, 15, 10, 7, 2, 1, 0};
int n = find(arr);
System.out.println(n);
}
public static int find(int[] arr){
int n = arr.length;
int l = 0;
int h = n-1;
while(l <= h){
int mid = (h-l)/2 +l;
if(mid-1 >= 0 && mid+1 < n && arr[mid-1] < arr[mid] && arr[mid] > arr[mid+1])
return arr[mid];
else if(mid-1 >= 0 && mid+1 < n && arr[mid-1] < arr[mid] && arr[mid] < arr[mid+1])
l = mid+1;
else
h = mid-1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = { 73, 74, 75, 71, 70, 76, 72 };
calcFreq(arr);
}
public static void calcFreq(int[] arr) {
int n = arr.length;
int[][][] maxind = new int[100][2][2];
for (int i = 0; i < 100; i++){
Arrays.fill(maxind[i][0], 1000);
Arrays.fill(maxind[i][1], 1000);
}
for (int i = n - 1; i >= 0; i--) {
for (int k = 100; k >= 0; k--) {
if(k == arr[i])
maxind[k][0][1] = i;
if (arr[i] - k > 0 && (i > maxind[k][0][1] || maxind[k][0][1] == 1000)) {
maxind[k][0][0] = arr[i] - k;
maxind[k][1][0] = i;
}
}
}
for (int i = 0; i < n; i++) {
int index = maxind[arr[i]][1][0];
System.out.print((index == 1000 ? "Nothing" : (index-i)) + " ");
}
}
public static void main(String[] args) {
int[] arr = { 6, 3, 0, 2, 2, 0, 0 };
int n = arr.length;
int[] elem = new int[n];
for (int i = 0; i < n; i++)
elem[i] = i + 1;
create(arr, elem, n);
for (int i = 0; i < n; i++)
System.out.print(elem[i] + " ");
}
public static void create(int[] arr, int[] elem, int n) {
for (int i = n - 2; i >= 0; i--) {
if (!balance(arr[i], elem, i, n))
create(arr, elem, n);
}
}
public static boolean balance(int k, int[] elem, int st, int n) {
int y = k;
for (int i = st + 1; i < n; i++)
if (elem[st] < elem[i])
k--;
if (k == 0)
return true;
else {
int[] arr = Arrays.copyOfRange(elem, st, n);
int p = kthlargest(arr, y);
for (int i = st + 1; i < n; i++) {
if (p == elem[i]) {
swap(elem, i, st);
break;
}
}
return false;
}
}
public static int kthlargest(int[] arr, int k) {
int max = -1;
int i = 0;
while (k >= 0) {
for (int p = arr.length / 2 - 1; p >= 0; p--)
heapify(arr, p, arr.length);
heapify(arr, 0, arr.length - i);
max = arr[0];
arr[0] = Integer.MIN_VALUE;
swap(arr, 0, arr.length - i - 1);
i++;
k--;
}
return max;
}
public static void heapify(int[] arr, int i, int n) {
int l = 2 * i + 1;
int r = 2 * i + 2;
int max = i;
if (l < n && arr[l] > arr[max])
max = l;
if (r < n && arr[r] > arr[max])
max = r;
if (max != i) {
swap(arr, i, max);
heapify(arr, max, n);
}
}
public static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
String str = "(((abc))((d)))))";
unmatched(str);
}
/**
* ((a) -> -10a1 (a)) -> 0a1-1 (((abc))((d))))) -> 000abc1100d111-1-1
*
*
*/
public static void unmatched(String str) {
char[] carr = str.toCharArray();
int n = carr.length;
int i = 0;
StringBuffer sb = new StringBuffer();
String d = "";
Stack<Character> stack = new Stack<>();
int c = 0;
while (i < n) {
if(i > 0 && carr[i] == '(' && carr[i-1] == ')')
c = 1;
if (carr[i] == '(') {
stack.push(carr[i]);
d += sb.toString();
sb = new StringBuffer();
c++;
} else if (carr[i] == ')') {
c--;
if (!stack.isEmpty()) {
stack.pop();
String s = sb.toString();
if(c == 0){
s = d+s;
d = "";
}
if (s.length() > 0)
sb = new StringBuffer("0" + s + "1");
} else {
sb.append("-1");
}
} else {
sb.append(carr[i]);
}
i++;
}
String p = sb.toString();
sb = new StringBuffer(d + p);
while (!stack.isEmpty()) {
char t = stack.pop();
if (t == ')')
sb.append("-1");
else {
String s = sb.toString();
sb = new StringBuffer("-1" + s);
}
}
System.out.println(sb.toString());
}
public static void main(String[] args){
int[] arr = {1, 4};
int n = -1;
int r = closest(arr, n);
System.out.println(r);
}
//2,5,6,7,8,8,9
public static int closest(int[] arr, int n){
int min = Integer.MAX_VALUE;
int minv = 0;
int l = 0;
int h = arr.length-1;
while(l <= h){
int mid = (h-l)/2+l;
int diff = Math.abs(n-arr[mid]);
if(diff == 0)
return arr[mid];
if(diff < min){
min = diff;
minv = arr[mid];
}
if(arr[mid] > n)
h = mid-1;
else
l = mid+1;
}
return minv;
}
public static void main(String[] args){
int n = 17;
boolean ret = isSquareSum(n);
System.out.println(ret);
}
public static boolean isSquareSum(int n){
int m = (int)Math.sqrt(n);
int[] arr = new int[n+1];
for(int i = 0; i <= m; i++){
arr[(int)Math.pow(i, 2)] = 1;
}
for(int i = 0; i <= m; i++){
if(arr[i] > 0 && n-arr[i] >= 0 && arr[n-arr[i]] == 1)
return true;
}
return false;
}
public static void main(String[] args){
int[][] arr = {{1, 0, 0, 1, 0}, {0, 0, 1, 0, 1}, {0, 0, 0, 1, 0}, {1, 0, 1, 0, 1}};
rectangles(arr);
}
public static void rectangles(int[][] arr){
int n = arr.length;
int m = arr[0].length;
for(int i = 0; i < n; i++){
int index1 = -1;
int index2 = -1;
for(int j = 0; j < m; j++){
if(arr[i][j] == 1 && index1 == -1)
index1 = j;
else if(arr[i][j] == 1 && index2 == -1)
index2 = j;
if(index1 != -1 && index2 != -1){
check(arr, i, index1, i, index2);
index1 = index2;
index2 = -1;
}
}
}
}
public static void check(int[][] arr, int i1, int j1, int i2, int j2){
int n = arr.length;
int m = arr[0].length;
for(int i = i1+1; i < n; i++){
int[] row = arr[i];
if(row[j1] == 1 && row[j2] == 1){
System.out.println("Corner 1 - " + i1 + ", " + j1);
System.out.println("Corner 2 - " + i1 + ", " + j2);
System.out.println("Corner 3 - " + i + ", " + j1);
System.out.println("Corner 4 - " + i + ", " + j2);
System.out.println();
}
}
}
public static void main(String[] args){
Node N5 = new Node(5, null);
Node N3 = new Node(3, N5);
Node N1 = new Node(1, N3);
Node N7 = new Node(7, null);
Node N6 = new Node(6, N7);
Node N4 = new Node(4, N6);
Node N2 = new Node(2, N4);
merge(N1, N2);
}
//1,3,5 2,4
public static void merge(Node list1, Node list2){
Node head = new Node(list1.val);
Node node = head;
list1 = list1.next;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
node.next = list1;
list1 = list1.next;
}else if(list2.val < list1.val){
node.next = list2;
list2 = list2.next;
}
node = node.next;
}
if(list1 != null){
node.next = list1;
}
if(list2 != null){
node.next = list2;
}
while(head != null){
System.out.print(head.val + " ");
head = head.next;
}
}
static class Node{
int val;
Node next;
public Node(int val){
this.val = val;
}
public Node(int val, Node node){
this.val = val;
this.next = node;
}
}
public static void main(String[] args) {
Trie root = new Trie(false);
add(root, "car".toCharArray());
add(root, "caw".toCharArray());
add(root, "cauw".toCharArray());
match(root, "c*w".toCharArray(), 0, "", false);
}
// caw, c*w
public static void match(Trie trie, char[] carr, int index, String str, boolean leaf) {
if (index == carr.length) {
if (leaf)
System.out.println(str);
return;
}
char c = carr[index];
if (c == '*') {
Trie[] next = trie.next;
for (int i = 0; i < 26; i++) {
if (next[i] != null) {
match(next[i], carr, index + 1, str + (char)(i + 'a'), trie.leaf);
match(next[i], carr, index, str + (char)(i + 'a'), trie.leaf);
}
}
} else if (trie.next[c - 'a'] == null) {
return;
} else {
match(trie.next[c - 'a'], carr, index + 1, str + carr[index], trie.leaf);
}
}
// car
public static void add(Trie trie, char[] carr) {
int n = carr.length;
for (int i = 0; i < n; i++) {
if (trie.next[carr[i] - 'a'] == null) {
Trie node = new Trie(false);
trie.next[carr[i] - 'a'] = node;
if (i == n - 2)
node.leaf = true;
}
trie = trie.next[carr[i] - 'a'];
}
}
static class Trie {
Trie[] next = new Trie[26];
boolean leaf;
public Trie(boolean leaf) {
this.leaf = leaf;
}
}
O(n^2) + exp(k) -
public static void main(String[] args) {
int n = 6;
int[][] connected = new int[n][n];
connected[0][3] = 1;
connected[3][0] = 1;
connected[1][2] = 1;
connected[2][1] = 1;
connected[0][2] = 1;
connected[2][0] = 1;
connected[0][4] = 1;
connected[4][0] = 1;
int m = max(connected);
System.out.println(m);
}
// S = {a,b,c,d,e,f} and relations {a,d}, {b,c}, {a,c}, {a,e}
public static int max(int[][] connected) {
int n = connected.length;
Map<Integer, List<List<Integer>>> map = new HashMap<Integer, List<List<Integer>>>();
int[] dp = new int[n];
dp[0] = 1;
List<List<Integer>> o = new ArrayList<List<Integer>>();
List<Integer> lo = new ArrayList<Integer>();
lo.add(0);
o.add(lo);
map.put(0, o);
for (int i = 1; i < n; i++) {
dp[i] = dp[i - 1];
List<List<Integer>> olist = new ArrayList<List<Integer>>();
List<Integer> l = new ArrayList<Integer>();
l.add(i);
olist.add(l);
map.put(i, olist);
for (int j = i - 1; j >= 0; j--) {
List<List<Integer>> connections = map.get(j);
if (null != connections) {
for (List<Integer> nodes : connections) {
boolean canconnect = true;
for (int node : nodes) {
if (connected[i][node] == 1) {
canconnect = false;
break;
}
}
if (canconnect) {
dp[i] = Math.max(dp[i], nodes.size() + 1);
List<List<Integer>> nconn = map.get(i);
List<Integer> list = new ArrayList<Integer>();
for (int k : nodes) {
list.add(k);
}
list.add(i);
nconn.add(list);
}
}
}
}
}
return dp[n - 1];
}
If I understand correct, assuming that the max. gas available at station located at distance
3 is 15
6 is 4
8 is 5
...
and we start with 17 units of gas to reach 20 units of distance.
let us consider the total gas required to reach the destination. At each stop let us determine if we need to refill with gas to get to the end or not.. if we see that the max. gas available at a station is less than required to reach the final destination, then we would have to stop at some other station to refill. If in some place before we reach destination we run out of gas, then the distance cannot be traversed.
A DP O(n) solution -
public static void main(String[] args){
int[] dist = {3, 6, 8, 15};
int[] gas = {15, 4, 5, 6};
int initialgas = 17;
int finaldistance = 20;
int n = minstops(dist, gas, initialgas, finaldistance);
System.out.println(n);
}
public static int minstops(int[] dist, int[] gas, int initialgas, int finaldistance){
int[] dp = new int[finaldistance+1];
int stationindex = 0;
int remaingas = initialgas;
int remaindistance = finaldistance;
for(int i = 0; i <= finaldistance; i++){
remaingas -=1;
remaindistance -= 1;
if(stationindex < dist.length && dist[stationindex] == i){
if(remaingas < remaindistance){
remaingas += gas[stationindex];
if(i > 0)
dp[i] = dp[i-1]+1;
}else{
if(i > 0)
dp[i] = dp[i-1];
}
stationindex +=1;
}else if(remaingas <= 0 && remaindistance > 0){
return -1;
}else{
if(i > 0)
dp[i] = dp[i-1];
}
}
return dp[finaldistance];
}
O(n) + k soln. -
public static void main(String[] args){
int[] nums = {0,0,0,0,1};
int n = findMiniFlip(nums);
System.out.println(n);
}
//1011000; 00001
public static int findMiniFlip(int[] nums) {
int n = nums.length;
String s = "";
for(int i = 0; i < n; i++)
s += nums[i];
long num = Integer.parseInt(s, 2);
int minXor = n;
long mask = (1<<(n-1));
while(n-1 > 0){
long temp = (num ^ mask);
minXor = Math.min(minXor, countones(temp));
n--;
mask = (mask | (1<<n));
}
return minXor;
}
public static int countones(long n){
int c = 0;
while(n > 0){
n = n & (n-1);
c++;
}
return c;
}
public static void main(String[] args){
int[] coins = {10, 50, 100, 500};
int[] quantity = {5, 3, 2, 2};
Set<Integer> sums = new HashSet<Integer>();
possibility(coins, quantity, 0, 0, sums);
System.out.println(sums);
}
public static Set<Integer> possibility(int[] coins, int[] quantity, int index, int sum, Set<Integer> sums){
sums.add(sum);
int n = coins.length;
if(index > n-1)
return sums;
for(int i = index; i < n; i++){
int count = quantity[i];
for(int j = 1; j <= count; j++){
sums = possibility(coins, quantity, i+1, sum+coins[i]*j, sums);
sums = possibility(coins, quantity, i+1, sum, sums);
}
}
return sums;
}
A simple BFS approach, considering with only 1 node. We can extend this to multiple nodes to check the longest paths. The neighbors are one direction mapped for simplicity-
public static void main(String[] args){
UndirectedGraphNode u0 = new UndirectedGraphNode(0);
UndirectedGraphNode u1 = new UndirectedGraphNode(1);
UndirectedGraphNode u2 = new UndirectedGraphNode(2);
UndirectedGraphNode u3 = new UndirectedGraphNode(3);
UndirectedGraphNode u4 = new UndirectedGraphNode(4);
UndirectedGraphNode u5 = new UndirectedGraphNode(5);
UndirectedGraphNode u6 = new UndirectedGraphNode(6);
UndirectedGraphNode u7 = new UndirectedGraphNode(7);
u0.neighbors.add(u6);
u0.neighbors.add(u4);
u0.neighbors.add(u5);
u0.neighbors.add(u1);
u1.neighbors.add(u3);
u3.neighbors.add(u2);
u2.neighbors.add(u7);
int max = Integer.MIN_VALUE;
int n = maxpath(u0, new ArrayList<>(), "", 0, max);
System.out.println(n);
}
public static int maxpath(UndirectedGraphNode graph, List<String> paths, String path, int len, int max){
if(graph == null)
return max;
List<UndirectedGraphNode> neighbors = graph.neighbors;
if(neighbors.size() > 0){
for(UndirectedGraphNode node: neighbors){
if(!paths.contains(path+node.label)){
if(node != null){
max = maxpath(node, paths, path+node.label, len+1, max);
}
}
}
}else{
paths.add(path);
max = Math.max(max, len);
return max;
}
return max;
}
static class UndirectedGraphNode {
int label;
List<UndirectedGraphNode> neighbors;
public UndirectedGraphNode(int x){
label = x;
neighbors = new ArrayList<UndirectedGraphNode>();
}
}
O(n) soln. -
public static void main(String[] args){
int[] arr = {3,2,999,1};
int index = -1;
int k = arr.length;
for(int i = 0; i < arr.length; i++){
if(arr[i] == 999){
index = i;
break;
}
}
sort(arr, index, k);
}
//considering ' ' as 999
public static void sort(int[] arr, int index, int k){
int n = arr.length;
if(k == 0){
for(int i = 1; i < n; i++){
System.out.print(arr[i] + " ");
}
System.out.print(999);
return;
}else if(k > 0 && index == 0){
index = n-2;
for(int i = 1; i <= index; i++){
arr[i-1] = arr[i];
}
arr[index] = 999;
}
if(index-1 >= 0 && index+1 < n && arr[index-1] > arr[index+1]){
swap(arr, index, index+1);
swap(arr, index-1, index+1);
}else{
swap(arr, index, index-1);
}
sort(arr, index-1, k-1);
}
public static void swap(int[] arr, int i, int j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
String s = "CatMat";
Set<String> dict = new HashSet<String>();
dict.add("Cat");
dict.add("Mat");
dict.add("Ca");
dict.add("tM");
dict.add("t");
dict.add("a");
dict.add("C");
dict.add("Dog");
dict.add("og");
dict.add("Do");
int n = wordBreak(s, dict, 0, s.length());
System.out.println(n == s.length() ? -1 : n);
}
public static int wordBreak(String s, Set<String> dict, int l, int h) {
if (l > h)
return s.length();
String temp = s.substring(l, h);
if (dict.contains(temp))
return 0;
String str = "";
int min = s.length();
for (int i = l; i < h; i++) {
str += s.charAt(i);
if (dict.contains(str)) {
min = Math.min(min, wordBreak(s, dict, i + 1, h)+1);
}
}
return min;
}
O(n) soln. -
public static void main(String[] args){
int[] arr = {188930, 194123, 201345, 154243, 154243};
int k = 3;
diff(arr, k);
}
//188930, 194123, 201345, 154243, 154243
public static void diff(int[] arr, int k){
int n = arr.length;
int[] dpi = new int[n];
int[] dpd = new int[n];
int increase = 0;
int decrease = 0;
for(int i = 1; i < n; i++){
if(arr[i] > arr[i-1]){
int t = increase+1;
increase += t;
dpi[i] = increase;
if(k >= 2)
dpd[i] = dpd[k-2];
else
dpd[i] = 0;
decrease = dpd[i];
}else if(arr[i] < arr[i-1]){
int t = decrease+1;
decrease += t;
dpd[i] = decrease;
if(k >= 2)
dpi[i] = dpi[k-2];
else
dpi[i] = 0;
increase = dpi[i];
}
}
for(int i = k-1; i < n; i++){
int incr = dpi[i];
int decr = dpd[i];
if(i-k >= 0){
incr -= dpi[i-k];
decr -= dpd[i-k];
}
System.out.print((incr-decr) + " ");
}
}
O(n*m) soln-
public static void main(String[] args) {
String[] arr = { "aab", "aabb", "bc" };
String ret = shortest(arr);
System.out.println(ret);
}
// aab, aabb, bc
public static String shortest(String[] arr) {
int n = arr.length;
String ret = arr[0];
for (int i = 1; i < n; i++) {
char[] rarr = ret.toCharArray();
char[] narr = arr[i].toCharArray();
int p = 0;
int q = 0;
while (p < rarr.length-1 && q < narr.length-1) {
if (rarr[p] == narr[q]) {
int k = q;
q = match(rarr, narr, p, q, (p == rarr.length - 1));
if(q==k)
p++;
} else {
p++;
}
}
if (q < narr.length)
ret += arr[i].substring(q, narr.length);
}
return ret;
}
public static int match(char[] rarr, char[] narr, int p, int q, boolean end) {
int k = q;
while (p < rarr.length && q < narr.length) {
if (rarr[p] == narr[q]) {
p++;
q++;
} else
break;
}
if (p >= rarr.length - 1 || end)
return q;
else
return k;
}
public static void main(String[] args) {
int[] start = {1,2,3,-1,4,5};
int[] target = {5,1,-1,3,2,4};
int n = start.length;
int index = -1;
for(int i = 0; i < n; i++){
if(start[i] == -1){
index = i;
break;
}
}
move(start, target, n, false, index);
}
//123-145, 51-1324
public static boolean move(int[] start, int[] target, int n, boolean achieved, int index){
boolean alligned = true;
for(int i = 0; i < n; i++){
if(start[i] != target[i]){
alligned = false;
break;
}
}
if(alligned)
return true;
else{
int car = target[index];
if(car == -1){
swap(start, index, 0);
System.out.print(start[index] + " ");
achieved = move(start, target, n, achieved, 0);
}else{
int carInd = -1;
for(int i = 0; i < n; i++){
if(start[i] == car){
carInd = i;
break;
}
}
swap(start, index, carInd);
System.out.print(start[index] + " ");
achieved = move(start, target, n, achieved, carInd);
}
return achieved;
}
}
public static void swap(int[] start, int i, int j){
int t = start[i];
start[i] = start[j];
start[j] = t;
}
Considering 32 bit m/c
public static void main(String[] args) {
String text = "this is google!";
System.out.println("Actual text - " + text);
String encode = encode(text);
System.out.println("Encode - " + encode);
String decode = decode(encode);
System.out.println("Decode - " + decode);
}
public static String encode(String text) {
int n = text.length();
char[] carr = text.toCharArray();
int[] arr = new int[n / 4 +1];
int i = -1;
for (int k = 0; k < n; k++) {
if (k % 4 == 0)
i++;
int val = arr[i];
arr[i] = ((val << 8) | (int) (carr[k]));
}
String encoded = "";
for (int k = 0; k < arr.length; k++) {
int v = arr[k];
String tp = "";
while(v > 0){
tp = (char) (v%10 + 'a') + tp;
v = v/10;
}
encoded += tp + '#';
}
return encoded;
}
public static String decode(String text) {
int n = text.length();
char[] carr = text.toCharArray();
int[] arr = new int[n];
String s = "";
int ind = 0;
for (int i = 0; i < n; i++) {
if(carr[i] == '#'){
arr[ind] = Integer.parseInt(s);
s = "";
ind++;
}else{
s += String.valueOf((carr[i] - 'a'));
}
}
String decode = "";
int i = 0;
while (i < n) {
int k = 3;
while (k >= 0) {
int val = arr[i];
decode += (char) ((val & (255 << 8*k)) >> 8*k);
k--;
}
i++;
}
return decode;
}
public static void main(String[] args) {
int count = count(50);
System.out.println(count);
}
public static int count(int n){
int[] dp = new int[n];
dp[0] = 2;
dp[1] = 4;
for(int i = 2; i < n; i++){
dp[i] = dp[i-1]+dp[i-2]+1;
}
return dp[n-1];
}
public static void main(String[] args) {
int[] arr = { 10, 20, 70, 80, 30, 20, 100, 70, 50, 90 };
int n = 5;
int[] taken = new int[arr.length];
int[] pos = new int[n];
pos(arr, 1, taken, pos, n - 1, false);
}
public static boolean pos(int[] arr, int index, int[] taken, int[] pos, int n, boolean found) {
if (n == 0) {
found = validate(arr, taken, pos, 1, false);
if (found) {
for (int i = 0; i < pos.length; i++)
System.out.print(pos[i] + " ");
}
for (int i = 0; i < taken.length; i++)
if (taken[i] == 2)
taken[i] = 0;
return found;
}
int k = taken.length;
for (int i = 0; i < k; i++) {
if (taken[i] == 0) {
pos[index] = arr[i];
taken[i] = 1;
if (!found)
found = pos(arr, index + 1, taken, pos, n - 1, found);
pos[index] = 0;
taken[i] = 0;
}
}
return found;
}
public static boolean validate(int[] arr, int[] taken, int[] pos, int index, boolean ret) {
int n = pos.length;
if(index >= n-1)
return true;
for (int i = index; i < n; i++) {
for (int j = i + 1; j < n; j++) {
boolean found = false;
for (int k = 0; k < taken.length; k++) {
if (taken[k] == 0 && Math.abs(pos[i] - pos[j]) == arr[k]) {
taken[k] = 2;
found = true;
break;
}
}
if (!found && !ret)
return false;
}
if(!ret)
ret = validate(arr, taken, pos, index + 1, ret);
}
return ret;
}
O(n) soln. -
public static void main(String[] args) {
int[] arr = {1,1,1,5};
int n = max(arr);
System.out.println(n);
}
public static int max(int[] arr){
int n = arr.length;
int[] dp = new int[n];
dp[0] = arr[0];
dp[1] = Math.max(arr[0] + arr[1], arr[0] * arr[1]);
dp[1] = Math.max(dp[1], arr[1] != 0 ? arr[0] / arr[1] : 0);
dp[1] = Math.max(dp[1], arr[0] - arr[1]);
int prev = -1;
for(int i = 2; i < n; i++){
prev = dp[i-2];
dp[i] = Math.max(dp[i-1] + arr[i], dp[i-1] * arr[i]);
dp[i] = Math.max(dp[i], arr[i] != 0? dp[i-1] / arr[i]: 0);
dp[i] = Math.max(dp[i], dp[i-1] - arr[i]);
dp[i] = Math.max(dp[i], prev*(arr[i-1] * arr[i]));
dp[i] = Math.max(dp[i], prev*(arr[i-1] + arr[i]));
dp[i] = Math.max(dp[i], prev*(arr[i] != 0? arr[i-1] / arr[i] : 0));
dp[i] = Math.max(dp[i], prev*(arr[i-1] - arr[i]));
dp[i] = Math.max(dp[i], prev+(arr[i-1] * arr[i]));
dp[i] = Math.max(dp[i], prev+(arr[i-1] + arr[i]));
dp[i] = Math.max(dp[i], prev+(arr[i] != 0? arr[i-1] / arr[i]: 0));
dp[i] = Math.max(dp[i], prev+(arr[i-1] - arr[i]));
dp[i] = Math.max(dp[i], prev-(arr[i-1] * arr[i]));
dp[i] = Math.max(dp[i], prev-(arr[i-1] + arr[i]));
dp[i] = Math.max(dp[i], prev-(arr[i] != 0? arr[i-1] / arr[i]: 0));
dp[i] = Math.max(dp[i], prev-(arr[i-1] - arr[i]));
if(arr[i-1] * arr[i] != 0)
dp[i] = Math.max(dp[i], prev/(arr[i-1] * arr[i]));
if(arr[i-1] + arr[i] != 0)
dp[i] = Math.max(dp[i], prev/(arr[i-1] + arr[i]));
if((arr[i] != 0? arr[i-1] / arr[i]: 0) != 0)
dp[i] = Math.max(dp[i], prev/(arr[i] != 0? arr[i-1] / arr[i]: 0));
if(arr[i-1] - arr[i] != 0)
dp[i] = Math.max(dp[i], prev/(arr[i-1] - arr[i]));
}
return dp[n-1];
}
O(n) -
public static void main(String[] args) {
String str = "the brown fox ran fast";
reverse(str);
}
public static void reverse(String str){
int n = str.length()-1;
char[] carr = str.toCharArray();
Stack<String> stack = new Stack<String>();
String temp = "";
while(n >= 0){
if(carr[n] == ' '){
stack.push(temp);
temp = "";
}else{
temp += carr[n];
}
n--;
}
stack.push(temp);
while(!stack.isEmpty()){
System.out.print(stack.pop() + " ");
}
}
Sorry the previous is not formatted.
Based on ChrisK's solution, here is a thread based implementation. I think the skip list can be avoided if we can calculate the array index -
public class SessionsGetAndPut {
public static void main(String[] args) {
int[] sessionArr = new int[320000];
Put put = new Put(sessionArr);
Get get = new Get(sessionArr);
for (int i = 0; i < 1000; i++) {
Thread pTh = new Thread(put);
Thread gTh = new Thread(get);
pTh.start();
gTh.start();
}
}
static class Put implements Runnable {
private int[] sessionArr;
public Put(int[] sessionArr) {
super();
this.sessionArr = sessionArr;
}
@Override
public void run() {
put();
}
public void put() {
Random rand = new Random();
int session = rand.nextInt(1000000);
System.out.println("Putting session value - " + session);
int val = sessionArr[session / 32];
int mod = session % 32;
sessionArr[session / 32] = (val | (1 << mod));
}
}
static class Get implements Runnable {
private int[] sessionArr;
public Get(int[] sessionArr) {
super();
this.sessionArr = sessionArr;
}
@Override
public void run() {
System.out.println("Got session value - " + get());
}
public int get() {
Random rand = new Random();
int session = -1;
while (session == -1) {
int loc = rand.nextInt(1000000);
int val = sessionArr[loc / 32];
int mod = loc % 32;
if ((val & (1 << mod)) > 0)
session = loc;
sessionArr[loc / 32] = (val & ~(1 << mod));
}
return session;
}
}
}
Based on ChrisK's solution, here is a thread based implementation. I think the skip list can be avoided if we can calculate the array index -
public class SessionsGetAndPut {
public static void main(String[] args) {
int[] sessionArr = new int[320000];
Put put = new Put(sessionArr);
Get get = new Get(sessionArr);
for (int i = 0; i < 1000; i++) {
Thread pTh = new Thread(put);
Thread gTh = new Thread(get);
pTh.start();
gTh.start();
}
}
static class Put implements Runnable {
private int[] sessionArr;
public Put(int[] sessionArr) {
super();
this.sessionArr = sessionArr;
}
@Override
public void run() {
put();
}
public void put() {
Random rand = new Random();
int session = rand.nextInt(1000000);
System.out.println("Putting session value - " + session);
int val = sessionArr[session / 32];
int mod = session % 32;
sessionArr[session / 32] = (val | (1 << mod));
}
}
static class Get implements Runnable {
private int[] sessionArr;
public Get(int[] sessionArr) {
super();
this.sessionArr = sessionArr;
}
@Override
public void run() {
System.out.println("Got session value - " + get());
}
public int get() {
Random rand = new Random();
int session = -1;
while (session == -1) {
int loc = rand.nextInt(1000000);
int val = sessionArr[loc / 32];
int mod = loc % 32;
if ((val & (1 << mod)) > 0)
session = loc;
sessionArr[loc / 32] = (val & ~(1 << mod));
}
return session;
}
}
}
public static void main(String[] args) {
Node N5 = new Node(5, null);
Node N4 = new Node(4, N5);
Node N3 = new Node(3, N4);
Node N2 = new Node(2, N3);
Node N1 = new Node(1, N2);
separate(N1);
System.out.println("----------------");
Node N50 = new Node(5, null);
Node N40 = new Node(4, null);
Node N30 = new Node(3, N50);
Node N20 = new Node(2, N40);
Node N10 = new Node(1, N30);
merge(N10, N20);
}
// 1->3->5
// 2->4
public static void merge(Node n1, Node n2) {
Node node = null;
Node head = null;
while (n1 != null && n2 != null) {
if (node == null) {
node = new Node(n1.val, null);
head = node;
} else {
node.next = new Node(n1.val, null);;
node = node.next;
}
node.next = n2;
node = node.next;
n1 = n1.next;
n2 = n2.next;
}
if (n1 != null) {
node.next = n1;
node = node.next;
}
if (n2 != null) {
node.next = n2;
node = node.next;
}
node.next = null;
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
}
// 1->2->3->4->5
public static void separate(Node node) {
Node nodeE = null;
Node nodeO = null;
Node nhE = null;
Node nhO = null;
int i = 1;
while (node != null) {
if (i % 2 == 0) {
if (nodeE == null) {
nodeE = node;
nhE = nodeE;
} else {
nodeE.next = node;
nodeE = nodeE.next;
}
node = node.next;
} else {
if (nodeO == null) {
nodeO = node;
nhO = nodeO;
} else {
nodeO.next = node;
nodeO = nodeO.next;
}
node = node.next;
}
i++;
}
nodeE.next = null;
nodeO.next = null;
while (nhE != null) {
System.out.print(nhE.val + " ");
nhE = nhE.next;
}
System.out.println();
while (nhO != null) {
System.out.print(nhO.val + " ");
nhO = nhO.next;
}
}
static class Node {
int val;
Node next;
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
The idea of creating new levels, with rooms connected to other rooms, containing keys, treasure...
Needs some tuning on random generator -
public static void main(String[] args) {
Level level = new Level();
for (int i = 0; i < level.rooms.length; i++) {
System.out.println("Room - "+ level.rooms[i].room + " Treasure - "
+ level.rooms[i].treasure + " Connected to - " + level.rooms[i].connectRooms + " Contains keys - " + level.rooms[i].roomkeys);
}
boolean res = ispossible(level.rooms, 0, false, new ArrayList<Integer>(), new ArrayList<Integer>());
System.out.println(res);
}
public static boolean ispossible(Room[] rooms, int index, boolean possible, List<Integer> keys, List<Integer> roc) {
if (index < 0 || index > rooms.length - 1)
return possible;
if (rooms[index].treasure)
return true;
Room room = rooms[index];
List<RoomConnections> connectedRooms = room.connectRooms;
keys.addAll(room.roomkeys);
for (RoomConnections rc : connectedRooms) {
if (!possible && ((rc.blocked && keys.contains(room.room)) || !rc.blocked) && !roc.contains(rc.room.room)){
roc.add(room.room);
possible = ispossible(rooms, rc.room.room, possible, keys, roc);
roc.remove(new Integer(room.room));
}
}
return possible;
}
public static class Level {
static final int MINBOUND = 2;
static final int MAXBOUND = 10;
Room[] rooms = null;
public Level() {
Random r = new Random();
int roomCount = r.nextInt(MAXBOUND-MINBOUND) + MINBOUND;
int treasureRoom = roomCount;
while(treasureRoom > roomCount-1){
treasureRoom = r.nextInt(MAXBOUND-MINBOUND) + MINBOUND;
}
rooms = new Room[roomCount];
for (int i = 0; i < roomCount; i++) {
Room room = null;
if (i == treasureRoom)
room = new Room(i, true);
else
room = new Room(i, false);
rooms[i] = room;
}
int[][] ri = new int[roomCount][roomCount];
for (int i = 0; i < ri.length; i++) {
for (int j = 0; j < ri.length; j++) {
if(i == j) continue;
if (ri[i][j] == 0) {
ri[i][j] = r.nextInt(3);
ri[j][i] = ri[i][j];
}
}
}
for (int i = 0; i < ri.length; i++) {
int[] ro = ri[i];
Room room = rooms[i];
for (int j = 0; j < ro.length; j++) {
Room adjroom = rooms[j];
RoomConnections roomConn = null;
if (ro[j] == 2) {
roomConn = new RoomConnections(adjroom, true);
int lock = roomCount;
while(lock > roomCount-1 || lock == treasureRoom){
lock = r.nextInt(MAXBOUND-MINBOUND) + MINBOUND;
}
rooms[lock].roomkeys.add(j);
room.connectRooms.add(roomConn);
} else if (ro[j] == 1) {
roomConn = new RoomConnections(adjroom, false);
room.connectRooms.add(roomConn);
}
}
}
}
}
public static class Room {
int room;
boolean treasure;
List<RoomConnections> connectRooms = new ArrayList<RoomConnections>();
List<Integer> roomkeys = new ArrayList<Integer>();
public Room(int room, boolean treasure) {
this.room = room;
this.treasure = treasure;
}
@Override
public int hashCode() {
return room;
}
}
public static class RoomConnections {
Room room;
boolean blocked;
public RoomConnections(Room room, boolean blocked) {
this.room = room;
this.blocked = blocked;
}
}
public static void main(String[] args) {
Point[] points = { new Point(0, 0), new Point(0, 3), new Point(0, 6), new Point(2, 0), new Point(2, 3),
new Point(2, 6), new Point(5, 6), new Point(6, 0), new Point(6, 4) };
int area = -1;
for (int i = 0; i < points.length; i++) {
area = Math.max(area, area(points, points[0], true, false, -1, -1,-1, Integer.MAX_VALUE, Integer.MAX_VALUE));
}
System.out.println(area);
}
public static int area(Point[] points, Point p, boolean matchx, boolean matchy, int l, int b, int area, int x, int y) {
if (matchx && matchy){
boolean r = matchXY(points, l, b, area, x, y);
if(r){
area = Math.max(area, l*b);
}
return area;
}
if (matchx)
area = matchX(points, p, l, b, area, x, y);
if (matchy)
area = matchY(points, p, l, b, area, x, y);
return area;
}
public static int matchX(Point[] points, Point p, int l, int b, int area, int x, int y) {
int n = points.length;
for (int i = 0; i < n; i++) {
Point pn = points[i];
if (pn.x == p.x && pn.y != p.y)
area = area(points, pn, false, true, Math.abs(pn.y - p.y), b, area, x, p.y);
}
return area;
}
public static int matchY(Point[] points, Point p, int l, int b, int area, int x, int y) {
int n = points.length;
for (int i = 0; i < n; i++) {
Point pn = points[i];
if (pn.y == p.y && pn.x != p.x)
area = area(points, pn, true, true, l, Math.abs(pn.x - p.x), area, p.x, y);
}
return area;
}
public static boolean matchXY(Point[] points, int l, int b, int area, int x, int y) {
int n = points.length;
for (int i = 0; i < n; i++) {
Point pn = points[i];
if (pn.x == x && pn.y == y)
return true;
}
return false;
}
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
DP soln. - O(n^2)
public static void main(String[] args) {
int[][] grid = {{0,0,1,3,0}, {1,2,4,0,0}, {0,0,10,0,0}, {1,5,4,0,1}};
int n = maxHappy(grid);
System.out.println(n);
}
/**
0,0,1,3,0
1,2,4,0,0
0,0,10,0,0
1,5,4,0,1
*/
public static int maxHappy(int[][] grid){
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n+1][m+1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
}
}
return dp[n][m];
}
public static void main(String[] args) {
Trie root = new Trie(' ');
add(root, "cat");
add(root, "cats");
add(root, "and");
add(root, "sand");
add(root, "dog");
boolean ret = match(root, "*t", 0, false);
System.out.println(ret);
}
public static boolean match(Trie node, String match, int index, boolean ismatch) {
if (node == null)
return ismatch;
if (index > match.length() - 1)
return true;
char c = match.charAt(index);
if (c == '*') {
for (int i = 0; i < 26; i++)
if (!ismatch)
ismatch = match(node.next[i], match, index + 1, ismatch)
|| match(node.next[i], match, index, ismatch);
} else if (c == '.') {
for (int i = 0; i < 26; i++)
if (!ismatch)
ismatch = match(node.next[i], match, index + 1, ismatch);
} else {
if (node.next[c - 'a'] == null)
return false;
else
ismatch = match(node.next[c - 'a'], match, index + 1, ismatch);
}
return ismatch;
}
public static void add(Trie root, String str) {
char[] arr = str.toCharArray();
int n = arr.length;
int k = 0;
while (k < n) {
Trie node = root;
for (int i = k; i < n; i++) {
Trie t = node.next[arr[i] - 'a'];
if (t == null) {
t = new Trie(arr[i]);
node.next[arr[i] - 'a'] = t;
}
if (i == n - 1)
t.isEnd = true;
node = t;
}
k++;
}
}
static class Trie {
char c;
Trie[] next = new Trie[26];
boolean isEnd;
public Trie(char c) {
this.c = c;
}
}
public static void main(String[] args) {
Trie root = new Trie("");
add(root, "abc.pqr.google.com");
add(root, "pqr.google.com");
add(root, "pqr.google.net");
add(root, "yahoo.com");
add(root, "abc.yahoo.com");
display(root, "");
}
public static void display(Trie node, String str) {
if (node == null)
return;
if (node.next.isEmpty())
return;
List<Trie> next = node.next;
for (Trie trie : next) {
display(trie, str + "." +trie.word);
System.out.println(str + "." +trie.word + " - " + trie.count);
}
}
public static void add(Trie root, String str) {
String[] arr = str.split("\\.");
int n = arr.length;
int k = 0;
while (k < n) {
Trie node = root;
for (int i = k; i < n; i++) {
Trie t = null;
for (Trie tr : node.next){
if (tr.word.equals(arr[i])) {
t = tr;
break;
}
}
if (t == null) {
t = new Trie(arr[i]);
node.next.add(t);
}
t.count += 1;
node = t;
}
k++;
}
}
static class Trie {
String word;
List<Trie> next = new ArrayList<Trie>();
int count;
public Trie(String word) {
this.word = word;
}
}
public static void main(String[] args) {
String[] s = { "WWWWWWWW", "WWW O WW", "WWW OW", "WWW WWWW", "WO WWWW", "WWW WWWW", "WO W", "WWWWWWWW" };
int[][] arr = new int[s.length][s[0].length()];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
if (s[i].charAt(j) == 'W')
arr[i][j] = -1;
else
arr[i][j] = Integer.MAX_VALUE;
}
}
int[] find = find(arr);
System.out.println(find[0] + ", " + find[1]);
}
// wall -1, office = 0, hall 1
public static int[] find(int[][] arr) {
int[] ret = new int[2];
int minsum = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
if (arr[i][j] != -1) {
find(arr, i, j, 0);
int sum = sum(arr);
if (minsum > sum) {
minsum = sum;
ret[0] = i;
ret[1] = j;
}
}
}
}
return ret;
}
public static int sum(int[][] arr) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
if (arr[i][j] != -1){
sum += arr[i][j];
arr[i][j] = Integer.MAX_VALUE;
}
}
}
return sum;
}
// wall -1, office = 0, hall 1
public static void find(int[][] arr, int i, int j, int steps) {
if (i < 0 || j < 0 || i > arr.length - 1 || j > arr[0].length - 1)
return;
if (arr[i][j] == -1)
return;
if (arr[i][j] < steps)
return;
arr[i][j] = steps;
int[] dx = { 0, 0, -1, 1 };
int[] dy = { -1, 1, 0, 0 };
for (int k = 0; k < 4; k++) {
find(arr, i + dx[k], j + dy[k], steps + 1);
}
}
public static void main(String[] args){
Map<Double, List<String>> map = group(Arrays.asList(new String[]{"May", "student", "students", "dog", "studentssess", "god", "Cat", "act",
"tab", "bat", "flow", "wolf", "lambs", "Amy", "Yam", "balms", "looped", "poodle", "john", "alice" }));
for(List<String> strs: map.values()){
System.out.println(strs);
}
}
public static Map<Double, List<String>> group(List<String> words){
Map<Double, List<String>> map = new HashMap<Double, List<String>>();
for(String str: words){
double hash = hash(str);
List<String> list = map.get(hash);
if(list == null)
list = new ArrayList<String>();
list.add(str);
map.put(hash, list);
}
return map;
}
public static double hash(String str){
String s = str.toLowerCase();
char[] carr = s.toCharArray();
int n = carr.length;
double hash = 0.0;
double K = 29.51;
int[] arr = new int[26];
for(int i = 0; i < n; i++){
if(arr[carr[i]-'a'] == 0){
hash += K*carr[i];
arr[carr[i]-'a'] = 1;
}
}
return hash;
}
Recursive approach -
public static void main(String[] args) {
int N = 5;
int K = 2;
System.out.println(count(N, K, K, 1, 1, 0));
}
// N=5, K= 2
public static int count(int N, int K, int k, int p, int count, int total) {
for (int i = p; i <= N; i++) {
if(K > 0 && i + 1 <= N) {
total = count(N, K - 1, k, i + 2, count*5, total);
}
if (i <= N) {
count *= 26;
}
}
if (K == 0){
total += count;
}
return total;
}
public static void main(String[] args){
int x = 1;
int y = 1;
int k = 2;
System.out.println(count(x, y, k));
}
public static int count(int x, int y, int k){
int[][] dp = new int[x+1][y+1];
for(int i = 1; i < dp.length; i++){
dp[i][0] = 1;
dp[0][i] = 1;
}
for(int i = 1; i < dp.length; i++){
for(int j = 1; j < dp.length; j++){
if(i == x && j == y){
if(dp[i-1][j] == k-1)
dp[i][j] = dp[i-1][j];
if(dp[i][j-1] == k-1)
dp[i][j] += dp[i][j-1];
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[x][y];
}
public static void main(String[] args) {
Set<List<Integer>> set = new HashSet<>();
choose(1, new int[5], 0, set);
System.out.println(set.size());
}
/**
* Given numbers 1 through 52, take 5 unique numbers and determine if the
* number 42 can be made using any combination of addition (+), subtraction
* (-), multiplication (*), and division (/) on those 5 numbers
*/
public static void choose(int n, int[] nums, int ind, Set<List<Integer>> set) {
if (n > 52)
return;
if (ind == 5) {
check(nums, new ArrayList<Integer>(), 0, set);
return;
}
nums[ind] = n;
choose(n + 1, nums, ind + 1, set);
choose(n + 1, nums, ind, set);
}
public static void check(int[] nums, List<Integer> list, int ind, Set<List<Integer>> set) {
if (ind > 4) {
int sum = 0;
for (int i : list)
sum += i;
if (sum == 42){
List<Integer> s = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
s.add(nums[i]);
}
set.add(s);
//System.out.println(set);
}
return;
}
// for add
list.add(nums[ind]);
check(nums, list, ind + 1, set);
list.remove(new Integer(nums[ind]));
// for subtract
list.add(-nums[ind]);
check(nums, list, ind + 1, set);
list.remove(new Integer(-nums[ind]));
// for multiply
int get = 1;
if (list.size() > 0) {
get = list.get(list.size() - 1);
list.remove(list.size() - 1);
}
list.add(get * nums[ind]);
check(nums, list, ind + 1, set);
list.remove(new Integer(get * nums[ind]));
list.add(get);
// for divide
get = 1;
if (list.size() > 0) {
get = list.get(list.size() - 1);
list.remove(list.size() - 1);
}
list.add(get / nums[ind]);
check(nums, list, ind + 1, set);
list.remove(new Integer(get / nums[ind]));
list.add(get);
}
Correcting the approach -
public static void main(String[] args){
BT N12 = new BT(12, null, null);
BT N11 = new BT(11, N12, null);
BT N10 = new BT(10, null, N11);
BT N9 = new BT(9, N10, null);
BT N8 = new BT(8, null, null);
BT N6 = new BT(6, null, null);
BT N5 = new BT(5, null, null);
BT N7 = new BT(7, N5, N8);
BT N4 = new BT(4, N7, null);
BT N3 = new BT(3, N6, null);
BT N2 = new BT(2, N3, N4);
BT N1 = new BT(1, N2, N9);
int[] maxdist = new int[1];
maxdist[0] = Integer.MIN_VALUE;
depth(N1, -1, maxdist);
System.out.println(maxdist[0]+1);
}
public static int depth(BT node, int dist, int[] maxdist){
if(node == null)
if(dist == -1)
return 0;
else {
maxdist[0] = Math.max(maxdist[0], dist);
return dist-1;
}
dist = depth(node.left, dist==-1?-1:dist+1, maxdist);
dist = depth(node.right, dist==-1?-1:dist+1, maxdist);
return dist;
}
static class BT{
int val;
BT left;
BT right;
public BT(int val, BT left, BT right){
this.val = val;
this.left = left;
this.right = right;
}
}
@Alex - Got it.. Thanks for correcting :)
- sudip.innovates October 20, 2017@Alex - Can you please explain the scenario, when the longest path would not include the root?
- sudip.innovates October 20, 2017@hprem991 - For me to learn -
Can you please explain "As we square up high value integer, it wont fit in another integer", why would we try to fit a higher value in a lower one?
Can you explain your understanding?
public static void main(String[] args){
calc("BAC");
}
public static void calc(String str){
int n = str.length()-1;
char[] carr = str.toCharArray();
int sum = carr[n] - 'A' +1;
n--;
int i = 1;
while(n >= 0){
sum += (carr[n] - 'A' + 1)*(int)Math.pow(26, i);
n--;
i++;
}
System.out.println(sum);
}
public static void main(String[] args) {
//recursion approach
int[] arr = { 1, -1, 2, -2 };
List<List<Integer>> list = new ArrayList<>();
subsetzero(arr, 0, 0, 0, list, new ArrayList<>());
System.out.println("->" + list.size());
//dp approach
int m = count(arr);
System.out.println("-->"+m);
}
public static int count(int[] arr) {
int n = arr.length - 1;
sort(arr, 0, n);
int posind = posindex(arr, 0, n);
int negsum = 0;
for (int i = 0; i < posind; i++)
negsum += arr[i];
int possum = 0;
for (int i = posind; i <= n; i++)
possum += arr[i];
negsum = Math.abs(negsum);
int[][] negdp = new int[negsum + 1][posind + 1];
for (int p = 0; p <= negsum; p++) {
for (int q = 1; q <= posind; q++) {
int pov = Math.abs(arr[q - 1]);
negdp[p][q] = negdp[p][q - 1];
if (p == pov)
negdp[p][q] += 1;
else if (p >= pov && p - pov <= negsum)
negdp[p][q] = Math.max(negdp[p][q - 1], negdp[p - pov][q - 1]);
}
}
int[][] posdp = new int[possum + 1][n - posind + 2];
for (int p = 0; p <= possum; p++) {
for (int q = 1; q <= n - posind + 1; q++) {
posdp[p][q] = posdp[p][q - 1];
if (p == arr[q + posind - 1])
posdp[p][q] += 1;
else if (p >= arr[q + posind - 1] && p - arr[q + posind - 1] <= possum)
posdp[p][q] = Math.max(posdp[p][q - 1], posdp[p - arr[q + posind - 1]][q - 1]);
}
}
int count = 0;
if (negsum > possum) {
while (negsum >= 0) {
if (posdp[negsum][n - posind] > 0)
count += Math.min(negdp[negsum][posind], posdp[negsum][n - posind +1]);
negsum--;
}
} else {
while (possum >= 0) {
if (negdp[possum][posind] > 0)
count += Math.min(posdp[possum][n - posind +1], negdp[possum][posind]);
possum--;
}
}
return count;
}
public static int posindex(int[] arr, int l, int h) {
if (l >= h)
return -1;
while (l < h) {
int mid = (h - l) / 2 + l;
if (mid - 1 >= 0 && arr[mid] >= 0 && arr[mid - 1] < 0)
return mid;
else if (mid - 1 >= 0 && arr[mid] < 0 && arr[mid - 1] < 0)
l = mid + 1;
else if (mid - 1 >= 0 && arr[mid] > 0 && arr[mid - 1] > 0)
h = mid - 1;
}
return -1;
}
public static void sort(int[] arr, int l, int h) {
int i = l;
int j = h;
int mid = arr[(h - l) / 2 + l];
while (i <= j) {
while (arr[i] < mid)
i++;
while (arr[j] > mid)
j--;
if (i <= j) {
swap(arr, i, j);
i++;
j--;
}
}
if (l < j)
sort(arr, l, j);
if (i < h)
sort(arr, i, h);
}
public static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
//1, -1, 2, -2
//[-2, -1, 1, 2]
public static void subsetzero(int[] arr, int sum, int k, int count, List<List<Integer>> list, List<Integer> li) {
if (sum == 0 && li.size() > 0 && !list.contains(li)){
count = count + 1;
list.add(new ArrayList<>(li));
}
if (k > arr.length - 1)
return;
li.add(arr[k]);
subsetzero(arr, sum + arr[k], k + 1, count, list, li);
li.remove(new Integer(arr[k]));
subsetzero(arr, sum, k + 1, count, list, li);
}
public static void main(String[] args){
BT N9 = new BT(9, null, null);
BT N8 = new BT(8, null, null);
BT N7 = new BT(7, null, null);
BT N6 = new BT(6, null, null);
BT N5 = new BT(5, null, null);
BT N4 = new BT(4, N8, N9);
BT N3 = new BT(3, N6, N7);
BT N2 = new BT(2, N4, N5);
BT N1 = new BT(1, N2, N3);
System.out.println(dia(N1));
}
public static int dia(BT root){
return depth(root.left) + depth(root.right)+1;
}
public static int depth(BT node){
if(node == null)
return 0;
int lh = depth(node.left)+1;
int rh = depth(node.right)+1;
return Math.max(lh, rh);
}
static class BT{
int val;
BT left;
BT right;
public BT(int val, BT left, BT right){
this.val = val;
this.left = left;
this.right = right;
}
}
complexity - O(logn) + n
public static void main(String[] args){
int[] arr = {-3, -1, 0, 2, 4};
int p = find(arr, 0, arr.length-1);
sort(arr, p);
}
public static void sort(int[] arr, int p){
int n = arr.length;
int i = p;
int j = p+1;
while(i >= 0 && j < n){
int pos = Math.abs(arr[i]);
if(pos <= arr[j]){
System.out.print((int)(Math.pow(pos, 2)) + " ");
i--;
}else if(pos > arr[j]){
System.out.print((int)(Math.pow(arr[j], 2)) + " ");
j++;
}
}
while(i >= 0){
int pos = Math.abs(arr[i]);
System.out.print((int)(Math.pow(pos, 2)) + " ");
i--;
}
while(j < n){
System.out.print((int)(Math.pow(arr[j], 2)) + " ");
j++;
}
}
public static int find(int[] arr, int l, int h){
int n = arr.length;
while(l < h){
int mid = (h-l)/2 + l;
if(mid-1 >= 0 && mid+1 < n && arr[mid-1] < 0 && arr[mid+1] >= 0)
return mid;
else if(mid-1 >= 0 && mid+1 < n && arr[mid-1] < 0 && arr[mid+1] < 0)
l = mid+1;
else if(mid-1 >= 0 && mid+1 < n && arr[mid-1] > 0 && arr[mid+1] > 0)
h = mid-1;
}
return -1;
}
I would take the approach of a tree structure containing has values.
Finally try to match the hash values of sub sequence anagrams for values in the tree.
Creating the tree is O(logn)
Creating sub seq anagrams for the string to be searched for - O(k2) (k length of word to be searched)
Searching is O(logN).
Total search - O(k^2) + O(logn)
Here is the working code -
Few things -
The more the tree in balanced, the better search time, like AVL tree
In place of BST, if we use tree with n nodes, depending on the no. of words in the dictionary, the better the search time.
public static void main(String[] args) {
String str = "ACRAT";
BT root = new BT(10.0, null, null, "");
// "A", "CAR", "ACA", "ART", "RAC"
add(root, hash("A".toCharArray()), "A");
add(root, hash("CAR".toCharArray()), "CAR");
add(root, hash("ACA".toCharArray()), "ACA");
add(root, hash("ART".toCharArray()), "ART");
add(root, hash("RAC".toCharArray()), "RAC");
Set<String> sub = sub(str);
Set<String> ans = new HashSet<>();
for (String string : sub) {
find(root, hash(string.toCharArray()), ans);
}
System.out.println(ans);
}
// ACRAT
public static Set<String> sub(String str) {
if(str == null || (str != null && str.length() == 0))
return new HashSet<>();
char head = str.charAt(0);
String rem = str.substring(1, str.length());
Set<String> res = sub(rem);
Set<String> ans = new HashSet<>();
ans.add(String.valueOf(head));
for (String string : res) {
ans.add(string);
for (int i = 0; i <= string.length(); i++) {
String pre = string.substring(0, i);
String post = string.substring(i, string.length());
ans.add(pre+head+post);
}
}
return ans;
}
public static void find(BT node, double hash, Set<String> ans) {
if (node == null)
return;
if (node.hval == hash) {
ans.add(node.word);
return;
}
if (hash < node.hval)
find(node.left, hash, ans);
if (hash > node.hval)
find(node.right, hash, ans);
}
// better to have height balanced AVL tree, or nTree
public static void add(BT node, double hash, String word) {
if (node == null)
return;
if (node.left == null && node.hval > hash) {
BT bt = new BT(hash, null, null, word);
node.left = bt;
} else if (node.right == null && node.hval < hash) {
BT bt = new BT(hash, null, null, word);
node.right = bt;
}
if (hash < node.hval)
add(node.left, hash, word);
if (hash > node.hval)
add(node.right, hash, word);
}
public static double hash(char... carr) {
int n = carr.length;
int i = 0;
double hash = 0.0;
double k = 2.73;
while (i < n) {
hash += carr[i] * k;
i++;
}
return hash;
}
static class BT {
double hval;
BT left;
BT right;
String word;
public BT(double hval, BT left, BT right, String word) {
this.hval = hval;
this.left = left;
this.right = right;
this.word = word;
}
}
We can use a semaphore (using same queue concept), to give a specific number of threads access and keep remaining waiting.
Java code -
- sudip.innovates November 29, 2017