sudip.innovates
BAN USERSimple soln. O(n)
public static void main(String[] args){
int[] arr = {0,1,1,0,1,0,1,0,0,1,1,1,0};
sort(arr);
for(int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
public static void sort(int[] arr){
int i = 0;
int j = arr.length-1;
while(i <= j){
while(arr[i] == 0)
i++;
while(arr[j] == 1)
j--;
if(i < j){
swap(arr, i, j);
i++;
j--;
}
}
}
public static void swap(int[] arr, int i, int j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
After posting the soln above, seems that we can have O(n2) approach, using additional space which is much cleaner -
public static void main(String[] args){
String str = "*)(*";
System.out.println(isValid(str));
}
public static boolean isValid(String str){
char[] carr = str.toCharArray();
int n = carr.length;
Stack<Character> stack = new Stack<Character>();
Queue<Character> queue = new LinkedList<Character>();
int i = 0;
while(i < n){
if(carr[i] == '(' || carr[i] == '*')
stack.push(carr[i]);
else{
while(!stack.isEmpty()){
char c = stack.pop();
if(c == '(')
continue;
else
queue.add(c);
}
}
if(!queue.isEmpty() && stack.isEmpty()){
while(!queue.isEmpty()){
stack.add(queue.poll());
}
}
i++;
}
boolean valid = true;
int countWild = 0;
if(!stack.isEmpty()){
char c = stack.pop();
if(c == '*'){
valid = true;
countWild++;
}else if(c == ')'){
valid = false;
}else if(c == '(' && countWild > 0){
countWild--;
}else if(c == '(' && countWild <= 0){
return false;
}
}
return valid;
}
@mulish
The idea is to check for magical binary sequence of any length starting from MSB to LSB, which has value less than previous. Once found swap the magical seq.
In this example 10 appears at the 7th index, while 1100 appears at 5th index. As 1100 values is greater than 10, we swap them.
Brute Force -
public static void main(String[] args) {
String str = "(*)(*)(**";
char[] carr = str.toCharArray();
System.out.println(validString(carr, 0, false));
}
// (*)(*)(**
public static boolean validString(char[] carr, int i, boolean valid) {
int n = carr.length;
Stack<Character> stack = new Stack<Character>();
while (i < n) {
if (carr[i] == '(' || carr[i] == ' ')
stack.push(carr[i]);
else if (carr[i] == ')') {
while (!stack.isEmpty()) {
char c = stack.pop();
if (c == ' ')
continue;
else if (c == ')')
return false;
else
break;
}
} else if (carr[i] == '*') {
carr[i] = '(';
valid |= validString(carr, 0, valid);
carr[i] = ')';
valid |= validString(carr, 0, valid);
carr[i] = ' ';
valid |= validString(carr, 0, valid);
carr[i] = '*';
}
i++;
}
while (!stack.isEmpty() && stack.peek() == ' ')
stack.pop();
if (stack.isEmpty())
valid = true;
else if(!valid)
valid = false;
return valid;
}
public static void main(String[] args) {
String str = "11011000";
System.out.println(magicstr(str));
}
public static String magicstr(String str) {
int n = str.length();
int maxInd = -1;
int maxLen = -1;
int maxVal = -1;
for (int i = 1; i < n; i++) {
for (int j = i+1; j < n; j++) {
int mag = ismagic(str, i, j);
if (mag > maxVal && maxVal > -1) {
String nq = "";
String t1 = str.substring(maxInd, maxInd + maxLen);
String t2 = str.substring(i, j + 1);
String pre1 = str.substring(0, maxInd);
String po1 = str.substring(j+1, n);
String mi1 = str.substring(maxInd + maxLen+1, i + 1);
nq = pre1;
nq += t2;
nq += mi1;
nq += t1;
nq += po1;
str = magicstr(nq);
} else if (mag > maxVal && maxVal == -1) {
maxInd = i;
maxLen = j - i + 1;
maxVal = mag;
break;
}
}
}
return str;
}
public static int ismagic(String str, int i, int j) {
if (i == j)
return -1;
String bis = str.substring(i, j+1);
if (bis.length() == 0)
return -1;
int bi = Integer.parseInt(bis, 2);
int count1 = 0;
int count0 = 0;
int n = bis.length()-1;
while (n >= 0) {
if (((bi & (1 << n)) != 0) && ( (bi & (1 << n)) == 1 || (bi & (1 << n)) % 2 == 0))
count1++;
else
count0++;
if (count1 < count0)
return -1;
n--;
}
if (count1 == count0)
return Integer.parseInt(bis);
return -1;
}
public static void main(String[] args) {
String str = "11011000";
System.out.println(magicstr(str));
}
public static String magicstr(String str) {
int n = str.length();
int maxInd = -1;
int maxLen = -1;
int maxVal = -1;
for (int i = 1; i < n; i++) {
for (int j = i+1; j < n; j++) {
int mag = ismagic(str, i, j);
if (mag > maxVal && maxVal > -1) {
String nq = "";
String t1 = str.substring(maxInd, maxInd + maxLen);
String t2 = str.substring(i, j + 1);
String pre1 = str.substring(0, maxInd);
String po1 = str.substring(j+1, n);
String mi1 = str.substring(maxInd + maxLen+1, i + 1);
nq = pre1;
nq += t2;
nq += mi1;
nq += t1;
nq += po1;
str = magicstr(nq);
} else if (mag > maxVal && maxVal == -1) {
maxInd = i;
maxLen = j - i + 1;
maxVal = mag;
break;
}
}
}
return str;
}
public static int ismagic(String str, int i, int j) {
if (i == j)
return -1;
String bis = str.substring(i, j+1);
if (bis.length() == 0)
return -1;
int bi = Integer.parseInt(bis, 2);
int count1 = 0;
int count0 = 0;
int n = bis.length()-1;
while (n >= 0) {
if (((bi & (1 << n)) != 0) && ( (bi & (1 << n)) == 1 || (bi & (1 << n)) % 2 == 0))
count1++;
else
count0++;
if (count1 < count0)
return -1;
n--;
}
if (count1 == count0)
return Integer.parseInt(bis);
return -1;
}
O(n^2) soln.
O(nLog(n)) with sweep algo is also possible.
public static void main(String[] args){
Point[][] points1 = {{new Point(1,1), new Point(10,1)}, {new Point(1,2), new Point(10,2)}};
int n = intersections(points1);
System.out.println(n);
Point[][] points2 = {{new Point(10,0), new Point(0,10)}, {new Point(0,0), new Point(10,10)}};
n = intersections(points2);
System.out.println(n);
Point[][] points3 = {{new Point(-5,-5), new Point(0,0)}, {new Point(1,1), new Point(10,10)}};
n = intersections(points3);
System.out.println(n);
Point[][] points4 = {{new Point(10,0), new Point(0,10)}, {new Point(1,1), new Point(10,10)}, {new Point(0,0), new Point(10,10)}, {new Point(-5,2), new Point(10,10)}};
n = intersections(points4);
System.out.println(n);
}
// not handling same intersection for more than 2 lines
public static int intersections(Point[][] points){
int n = points.length;
Line[] lines = new Line[n];
for(int i = 0; i < n; i++){
int x1 = points[i][0].x;
int y1 = points[i][0].y;
int x2 = points[i][1].x;
int y2 = points[i][1].y;
double slope = 0.0;
if(x1 == x2)
slope = 0.0;
else if(y1 == y2)
slope = 1.0;
else
slope = (y2-y1)/(x2-x1);
lines[i] = new Line(points[i][0], points[i][1], slope);
}
sortslopes(lines, 0, n-1);
int intersects = 0;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
Line l1 = lines[i];
Line l2 = lines[j];
if(l1.st.x >= l2.st.x && l1.en.x <= l2.en.x && l1.st.y <= l2.en.y && l1.en.y >= l2.st.y)
intersects++;
}
}
return intersects;
}
public static void sortslopes(Line[] lines, int l, int h){
if(l >= h)
return;
double mid = lines[(h-l)/2 + l].slope;
int i = l;
int j = h;
while(i <= j){
while(lines[i].slope < mid)
i++;
while(lines[j].slope > mid)
j--;
if(i <= j){
swap(lines, i, j);
i++;
j--;
}
}
if(i < h)
sortslopes(lines, i, h);
if(l < j)
sortslopes(lines, l, j);
}
public static void swap(Line[] lines, int i, int j){
Line t = lines[i];
lines[i] = lines[j];
lines[j] = t;
}
static class Line{
Point st;
Point en;
double slope;
public Line(Point st, Point en, double slope){
this.st = st;
this.en = en;
this.slope = slope;
}
}
static class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
2.
public static void main(String[] args){
int N = 3;
Map<Integer, List<List<Integer>>> sch = new TreeMap<Integer, List<List<Integer>>>();
int[][] teams = new int[N][N];
int[] tn = new int[N];
schedule(sch, 0, 0, 0, teams, tn);
for(Map.Entry entry: sch.entrySet()){
System.out.println("Day-"+entry.getKey() + " " + entry.getValue());
}
}
public static int schedule(Map<Integer, List<List<Integer>>> sch, int day, int p, int q, int[][] teams, int[] tn){
int n = teams.length;
if(p != q){
int dtext = day;
List<List<Integer>> games = sch.get(dtext);
List<Integer> game = new ArrayList<Integer>();
game.add(p);
game.add(q);
if(games == null){
games = new ArrayList<List<Integer>>();
}
games.add(game);
sch.put(dtext, games);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j || teams[i][j] == 1 || tn[i] == 1 || tn[j] == 1)
continue;
teams[i][j] = 1;
teams[j][i] = 1;
tn[i] = 1;
tn[j] = 1;
day = schedule(sch, day, i, j, teams, tn);
tn[i] = 0;
tn[j] = 0;
}
}
return day+1;
}
1.
O(n)
public static void main(String[] args){
SegT root = null;
root = add(root, 2, 10, 5);
add(root, 5, 7, 2);
add(root, 12, 15, 4);
add(root, 6, 10, 12);
int n = getMax(root, Integer.MIN_VALUE);
System.out.println(n);
}
public static int getMax(SegT node, int max){
if(node == null)
return max;
max = Math.max(max, node.bwidth);
max = getMax(node.left, max);
max = getMax(node.right, max);
return max;
}
public static SegT add(SegT node, int start, int end, int bwidth){
if(node == null){
node = new SegT(start, end, bwidth);
return node;
}
merge(node, start, end, bwidth);
return null;
}
public static void merge(SegT node, int start, int end, int bwidth){
if(node == null)
return;
if(start >= node.start && end <= node.end){
node.bwidth += bwidth;
return;
}else if(start > node.start && start < node.end && end > node.end){
node.end = end;
node.bwidth += bwidth;
return;
}else if(start < node.start && end < node.end && end > node.start){
node.start = start;
node.bwidth += bwidth;
return;
}else if(start < node.start && node.left == null){
SegT n = new SegT(start, end, bwidth);
node.left = n;
return;
}else if(start > node.start && node.left == null){
SegT n = new SegT(start, end, bwidth);
node.right = n;
return;
}else if(start > node.end){
merge(node.right, start, end, bwidth);
}else{
merge(node.left, start, end, bwidth);
}
}
static class SegT{
int start;
int end;
int bwidth;
SegT left;
SegT right;
public SegT(int start, int end, int bwidth){
this.start = start;
this.end = end;
this.bwidth = bwidth;
}
}
DP Soln. -
public static void main(String[] args) {
int[][] snakes = {{99, 78}, {95, 75}, {93, 73}, {87, 24}, {64, 60}, {62, 19}, {54, 34}, {17, 7}};
int[][] ladders = {{4, 14}, {9, 31}, {20, 38}, {28, 84}, {51, 67}, {63, 81}, {71, 91}};
int m = minThrowsDP(snakes, ladders);
System.out.println(m);
}
public static int minThrowsDP(int[][] snakes, int[][] ladders){
int[] dp = new int[101];
for(int i = 7; i < 101; i++){
dp[i] = Integer.MAX_VALUE;
}
for(int i = 7; i <= 100; i++){
for(int k = 1; k <= 6; k++){
dp[i] = Math.min(dp[i], dp[i-k]+1);
}
for (int p = 0; p < ladders.length; p++){
if (ladders[p][0] == i){
dp[ladders[p][1]] = dp[i];
}
}
}
return dp[100];
}
O(N^2)
public static void main(String[] args) {
String str = "aabcbaaaaaaaaaesdgttgd";
String r = longestPalindromeSubstring(str);
r = r.replace("#", "");
System.out.println(r);
}
// aabcb
public static String longestPalindromeSubstring(String str) {
String s = "#";
for (int i = 0; i <= str.length() - 1; i++)
s += str.charAt(i) + "#";
char[] carr = s.toCharArray();
int n = carr.length - 1;
String lsp = "";
int i = 0;
while (i <= n) {
int p = i - 1;
int q = 0;
String palin = String.valueOf(carr[i]);
while (p >= 0) {
q = 2 * i - p;
if (p >= 0 && q <= n && carr[p] == carr[q])
palin = s.substring(p, q + 1);
else
break;
p--;
}
i++;
if (palin.length() > lsp.length())
lsp = palin;
}
return lsp;
}
public static void main(String[] args) {
String str = "DABC";
int[] vals = new int[26];
vals['A'-'A'] = 1;
vals['B'-'A'] = 13;
vals['C'-'A'] = 110;
vals['D'-'A'] = 50;
int n = print(vals, str.toCharArray());
System.out.println(n);
}
public static int print(int[] vals, char[] carr){
int n = carr.length -2;
char next = carr[n+1];
int sum = vals[next-'A'];
int mul = 1;
while(n >= 0){
//uncomment next line if the sum should be + 50 - 1 - 13 + 110
// keep commentted if the sum be - 50 - 1 - 13 + 110
//mul = 1;
if(next > carr[n])
mul = -1;
sum += vals[carr[n]-'A']*mul;
next = carr[n];
n--;
}
return sum;
}
public static void main(String[] args) {
String[] cnos = { "2", "4", "600", "60", "100", "10", "50", "5", "77" };
String start = "60";
String end = "50";
int stInd = -1;
int eInd = -1;
sort(cnos, 0, cnos.length, new HashMap<String, Double>());
for (int i = 0; i < cnos.length; i++) {
if (cnos[i].equals(start)) {
stInd = i;
}
}
rotate(cnos, stInd);
for (int i = 0; i < cnos.length; i++) {
if (cnos[i].equals(end)) {
eInd = i;
}
}
swap(cnos, eInd, cnos.length-1);
int[] minclicks = new int[1];
minclicks[0] = Integer.MAX_VALUE;
countclicks(start, end, cnos, "", cnos.length, 0, minclicks, 0, cnos.length - 1);
System.out.println(minclicks[0]);
}
public static int countclicks(String start, String end, String[] cnos, String ch, int n, int clicks,
int[] minclicks, int stInd, int len) {
if(n < 0)
return clicks;
if (ch.equals(end) && n == 0) {
minclicks[0] = Math.min(clicks, minclicks[0]);
return clicks;
}
String last = start;
for (int i = stInd; i <= len; i++) {
clicks = countclicks(start, end, cnos, cnos[i], n-1, clicks+clicks(last, cnos[i]), minclicks, i + 1, len);
last = cnos[i];
}
return clicks;
}
public static void rotate(String[] arr, int p){
int n = p;
int m = arr.length;
while(n > 0){
int i = p;
String t = arr[i];
int x = m;
while(i >= 0 && x > 0){
if(i == 0)
i = arr.length;
String te = arr[i-1];
arr[i-1] = t;
t = te;
i--;
x--;
}
n--;
p--;
}
}
public static int clicks(String lastChannel, String nextChannel) {
int lch = Integer.parseInt(lastChannel);
int nch = Integer.parseInt(nextChannel);
if (lch - nch == 1 || lch - nch == -1)
return 1;
int index = -1;
if (lastChannel.length() <= nextChannel.length()) {
index = nextChannel.indexOf(lastChannel);
if (index == 0)
return nextChannel.length() - lastChannel.length();
} else {
index = lastChannel.indexOf(nextChannel);
if (index == 0)
return lastChannel.length() - nextChannel.length();
}
return nextChannel.length();
}
public static void sort(String[] arr, int l, int h, Map<String, Double> hMap) {
if(l >= h)
return;
int n = arr.length;
String mid = arr[(h - l) / 2 + l];
int i = 0;
int j = n - 1;
if (hMap.get(mid) == null)
hMap.put(mid, hash(mid));
double midhash = hMap.get(mid);
while (i < j) {
if (hMap.get(arr[i]) == null)
hMap.put(arr[i], hash(arr[i]));
if (hMap.get(arr[j]) == null)
hMap.put(arr[j], hash(arr[j]));
double iVal = hMap.get(arr[i]);
double jVal = hMap.get(arr[j]);
while (iVal < midhash) {
i++;
if (hMap.get(arr[i]) == null)
hMap.put(arr[i], hash(arr[i]));
iVal = hMap.get(arr[i]);
}
while (jVal > midhash) {
j--;
if (hMap.get(arr[j]) == null)
hMap.put(arr[j], hash(arr[j]));
jVal = hMap.get(arr[j]);
}
if (i <= j) {
swap(arr, i, j);
i++;
j--;
}
}
if (i < h)
sort(arr, i, h, hMap);
if (j > l)
sort(arr, l, j, hMap);
}
public static double hash(String str) {
char[] carr = str.toCharArray();
int i = 0;
double hash = 0;
while (i <= carr.length - 1) {
hash += Integer.parseInt(String.valueOf(carr[i]))+0.1;
i++;
}
return hash;
}
public static void swap(String[] arr, int i, int j) {
String t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
Complexity - O(n + lg(n))
Space - lg(n)
Interested in some other better approaches...
public static void main(String[] args){
T N6 = new T(7, null, null);
T N5 = new T(80, null, null);
T N4 = new T(30, null, null);
T N3 = new T(2, N6, null);
T N2 = new T(6, N4, N5);
T N1 = new T(50, N2, N3);
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
max(N1, 1, map);
int level = 0;
int minsum = N1.val;
for(Map.Entry<Integer, Integer> entry: map.entrySet()){
int lvl = entry.getKey();
int sum = entry.getValue();
if(sum > 0 && sum < minsum){
minsum = sum;
level = lvl;
}
}
System.out.println("Level " + level + " with sum = " + minsum);
}
public static void max(T node, int l, Map<Integer, Integer> map){
if(node == null)
return;
T left = node.left;
T right = node.right;
max(left, l+1, map);
max(right, l+1, map);
int sum = 0;
if(map.get(l) == null)
map.put(l, 0);
else
sum = map.get(l);
if(left != null){
sum += left.val;
map.put(l, sum);
}
if(right != null){
sum += right.val;
map.put(l, sum);
}
}
static class T{
int val;
T left;
T right;
int height;
public T(int val, T left, T right){
this.val = val;
this.left = left;
this.right = right;
}
}
O(n) approach -
public static void main(String[] args){
T N10 = new T(12, null, null);
T N9 = new T(11, null, null);
T N8 = new T(3, N10, null);
T N7 = new T(10, null, null);
T N6 = new T(9, null, null);
T N5 = new T(8, null, null);
T N4 = new T(7, N8, N9);
T N3 = new T(6, N6, N7);
T N2 = new T(5, N4, N5);
T N1 = new T(4, N2, N3);
int startFire = 9;
height(N1);
int left = catchFire(N1.left, startFire, -1);
if(left == -1)
left = N1.leftHt-1;
else
left = N1.leftHt - left;
int right = catchFire(N1.right, startFire, -1);
if(right == -1)
right = N1.rightHt-1;
else
right = N1.rightHt - right;
System.out.println((left+right+1));
}
public static int catchFire(T node, int startFire, int fireHt){
if(node == null)
return fireHt;
fireHt = catchFire(node.left, startFire, fireHt);
fireHt = catchFire(node.right, startFire, fireHt);
if(node.left != null && node.left.val == startFire)
fireHt = node.height-1;
if(node.right != null && node.right.val == startFire)
fireHt = node.height-1;
return fireHt;
}
public static void height(T node){
if(node == null)
return;
height(node.left);
height(node.right);
if(node.left != null && node.right != null){
node.height = Math.max(node.left.height, node.right.height) +1;
node.rightHt = node.right.height +1;
node.leftHt = node.left.height +1;
}
else if(node.left != null){
node.height = node.left.height+1;
node.leftHt = node.left.height+1;
}
else if(node.right != null){
node.height = node.right.height+1;
node.rightHt = node.right.height+1;
}
}
static class T{
int val;
T left;
T right;
int height;
int rightHt;
int leftHt;
public T(int val, T left, T right){
this.val = val;
this.left = left;
this.right = right;
}
}
XOR ing a number with itself gives 0. If we XOR all the nos. from 0 to N, and also XOR the result with the elements in the array, the duplicate values are nullified, only the one missing remains-
Code -
public static void main(String[] args){
int[] arr = {0, 1, 3, 4, 9, 5, 7, 6, 2};
int N = 9;
System.out.println(missingnumber(arr, N));
}
public static int missingnumber(int[] arr, int N){
int res = 0;
int n = arr.length;
for(int i = 0; i <= N; i++)
res = res^i;
for(int i = 0; i < n; i++)
res = res^arr[i];
return res;
}
Using hashing - O(m+n)
public static void main(String args[]) {
String a = "AB";
String b = "ABCDBACDAB";
indices(a, b);
}
public static void indices(String a, String b){
double hash = hash(a);
int n = b.length();
for(int i = 0; i < n-a.length()+1; i++){
String s = b.substring(i, a.length()+i);
double h = hash(s);
if(h == hash)
System.out.print(i + " ");
}
}
public static double hash(String str){
int n = str.length();
double k = 9.3451;
double h = 0;
for(int i = 0; i < n; i++)
h += str.charAt(i)*k;
return h;
}
Using hashing - O(m+n)
public static void main(String args[]) {
String a = "AB";
String b = "ABCDBACDAB";
indices(a, b);
}
public static void indices(String a, String b){
double hash = hash(a);
int n = b.length();
for(int i = 0; i < n-a.length()+1; i++){
String s = b.substring(i, a.length()+i);
double h = hash(s);
if(h == hash)
System.out.print(i + " ");
}
}
public static double hash(String str){
int n = str.length();
double k = 9.3451;
double h = 0;
for(int i = 0; i < n; i++)
h += str.charAt(i)*k;
return h;
}
public static void main(String args[]) {
IT it = null;
it = add(it, new IT(15, 20));
it = add(it, new IT(10, 30));
it = add(it, new IT(17, 19));
it = add(it, new IT(5, 20));
it = add(it, new IT(12, 15));
it = add(it, new IT(30, 40));
System.out.println(getCount(it, 18, 0));
}
public static int getCount(IT it, int t, int count){
if(it == null)
return count;
if(t < it.st || t <= it.max)
count = getCount(it.left, t, count);
if(t > it.st || t >= it.max)
count = getCount(it.right, t, count);
if(t >= it.st && t <= it.en)
count += 1;
return count;
}
public static IT add(IT it, IT node){
if(it == null){
it = node;
it.max = node.en;
}
else
addIn(it, node);
update(it);
return it;
}
public static void addIn(IT it, IT node){
if(it.st > node.st && it.left == null){
it.left = node;
node.max = node.en;
}
if(it.st < node.st && it.right == null){
it.right = node;
node.max = node.en;
}
int lm = -1;
int rm = -1;
if(it.st > node.st)
addIn(it.left, node);
if(it.st < node.st)
addIn(it.right, node);
node.max = Math.max(lm, rm);
node.max = Math.max(node.max, node.en);
}
public static int update(IT it){
if(it.left == null && it.right == null)
return it.max;
if(it.left == null)
return it.right.max;
if(it.right == null)
return it.left.max;
int lm = update(it.left);
int rm = update(it.right);
it.max = Math.max(lm, rm);
it.max = Math.max(it.max, it.en);
return it.max;
}
static class IT{
int st;
int en;
int max;
IT left;
IT right;
public IT(int st, int en){
this.st = st;
this.en = en;
}
}
public static void main(String args[]) {
seiveOfEratosthenesMod(90000, 99999);
}
public static void seiveOfEratosthenesMod(int l, int h){
int[] arr = new int[h-1];
for(int i = 0; i < h-1; i++)
arr[i] = i+2;
int n = (int)Math.sqrt(h);
int in = 2;
while(in <= n){
for(int k = 0; k < h-1; k++){
if(arr[k] != in && arr[k] % in == 0)
arr[k] = -1;
}
in++;
}
int[] cond = new int[h-1];
int prev = -1;
for(int k = 0; k < h-1; k++){
if(arr[k] != -1 && prev != -1 && (prev + arr[k] - 1) < h-1 && arr[prev + arr[k] - 1] != -1){
cond[prev + arr[k] - 1] = arr[prev + arr[k] - 1];
}
if(arr[k] != -1)
prev = arr[k];
}
for(int la = l; la < h-1; la++){
if(cond[la] > 0)
System.out.print(cond[la] + " ");
}
}
@mani0119 considering ma abs diff as 1. Here is the updated code -
/**
output -
1 2 3 4 5 6 7 8 9
10 11 12 21 22 23 32 33 34 43 44 45 54 55 56 65 66 67 76 77 78 87 88 89 98 99
100 101 110 111 112 121 122 123 210 211 212 221 222 223 232 233 234 321 322 323 332 333 334 343 344 345 432 433 434 443 444 445 454 455 456 543 544 545 554 555 556 565 566 567 654 655 656 665 666 667 676 677 678 765 766 767 776 777 778 787 788 789 876 877 878 887 888 889 898 899 987 988 989 998 999
*/
public static void main(String args[]) {
countandprint(3);
}
public static void countandprint(int n){
int count = 9;
int[] arr = new int[count];
for(int i = 0; i < arr.length; i++)
arr[i] = i+1;
int k = 0;
while(n > 0){
count = count*3-1-k;
int[] arrh = new int[count];
int j = 0;
for(int i = 0; i < arr.length; i++){
System.out.print(String.valueOf(arr[i]) + " ");
String no = String.valueOf(arr[i]);
int post = arr[i]%10;
if(j < count && (post-1) >= 0){
arrh[j] = Integer.parseInt(no + String.valueOf(post-1));
j++;
}
if(j < count){
arrh[j] = Integer.parseInt(no + String.valueOf(post));
j++;
}
if(j < count && (post+1) < 10){
arrh[j] = Integer.parseInt(no + String.valueOf(post+1));
j++;
}
}
System.out.println();
arr = new int[count];
arr = Arrays.copyOf(arrh, arrh.length);
n--;
k += 2;
}
}
@ChrisK.. yes for the sample output in the question... seemed to me that -1 is not getting considered.. only 0&-1.. if -1 needs to be considered.. then definitely 121, 132 would be an option....
- sudip.innovates October 08, 2017O(m+n)
public static void main(String args[]) {
System.out.println(anagramPresent("GLE", "GOOGLE"));
}
public static boolean anagramPresent(String a, String b){
double hash = hash(a);
for(int i = 0; i <= b.length()-a.length(); i++){
String sub = b.substring(i, i+a.length());
if(hash(sub) == hash)
return true;
}
return false;
}
public static double hash(String str){
int n = str.length();
int hash = 0;
double K = 8.6534;
for(int i = 0; i < n; i++){
hash += (str.charAt(i))*K;
}
return hash;
}
Looking at the problem,may be this is what the interviewer meant??
The outer while loop in O(n).
The inner for loop is dependent on the 'n', where the loop would be for -
9*1, 9*2-1, (9*2-1)*2-2, ... times.
The total iterations would be [9*1] + [9*2-1] + [(9*2-1)*2-2] + ...n
This is constant K*n.
Total complexity = n + K*n..
please check if I am going wrong somewhere...
The code -
/**
output -
1 2 3 4 5 6 7 8 9
11 12 22 23 33 34 44 45 55 56 66 67 77 78 88 89 99
111 112 122 123 222 223 233 234 333 334 344 345 444 445 455 456 555 556 566 567 666 667 677 678 777 778 788 789 888 889 899 999
*/
public static void main(String args[]) {
countandprint(3);
}
public static void countandprint(int n){
int count = 9;
int[] arr = new int[count];
for(int i = 0; i < arr.length; i++)
arr[i] = i+1;
int k = 0;
while(n > 0){
count = count*2-1-k;
int[] arrh = new int[count];
int j = 0;
for(int i = 0; i < arr.length; i++){
System.out.print(String.valueOf(arr[i]) + " ");
String no = String.valueOf(arr[i]);
int post = arr[i]%10;
if(j < count){
arrh[j] = Integer.parseInt(no + String.valueOf(post));
j++;
}
if(j+1 < count && (post+1) < 10){
arrh[j] = Integer.parseInt(no + String.valueOf(post+1));
j++;
}
}
System.out.println();
arr = new int[count];
arr = Arrays.copyOf(arrh, arrh.length);
n--;
k++;
}
}
complexity - O(k) & no extra space -
public static void main(String args[]) {
int[] A = {1, 2, 3, 6, 10};
int[] B = {1, 4, 5, 7};
int k = 5;
print(A, B, k, 0, 0, 1, 1);
}
public static void print(int[] A, int[] B, int k, int i, int j, int p, int q){
int n = A.length;
int m = B.length;
System.out.print("("+A[i] + ", " + B[j]+") ");
while(k > 1 && i < n && p < n && j < m && q < m){
while(k > 1 && i < n && p < n && j < m && q < m && A[i] + B[q] < A[p] + B[j]){
System.out.print("("+A[i] + ", " + B[q]+") ");
q++;
k--;
}
while(k > 1 && i < n && p < n && j < m && q < m && A[p] + B[j] < A[i] + B[q]){
System.out.print("("+A[p] + ", " + B[j]+") ");
p++;
k--;
}
}
if(k > 1 && i < n && p < n && j < m && q < m)
print(A, B, k, i, j, p, q);
}
public static void main(String args[]) {
int N = 4;
List<Integer> list = new ArrayList<Integer>();
list.add(0);
print(N, 0, list);
}
/**
Starting from num = 0, add 2^i (where i can be any non-negative integer) to num until num == N. Print all paths of how num turns from 0 to N.
For example if N = 4,
Paths printed are [0,1,2,3,4], [0,1,2,4], [0,1,3,4], [0,2,4], [0,2,3,4], [0,4].
[0,2,4] is made from 0 + 2^1 + 2^1. [0,1,3,4] from 0 + 2^0 + 2^1 + 2^0
*/
public static void print(int N, int sum, List<Integer> list){
if(sum > N)
return;
if(sum == N){
System.out.println(list);
return;
}
int i = 0;
while(((int)Math.pow(2, i) + sum) <= N){
int n = (int)Math.pow(2, i) + sum;
list.add(n);
print(N, n, list);
list.remove(new Integer(n));
i++;
}
}
public static void main(String args[]) {
/**
* 0
* / \ 4
* / \ / \
* 3 \ / \
* \ 1----5
* \ /
* \ /
* 2
* /_\
*
* 7 cycles
*/
int[][] adjM = { { 0, 1, 0, 0, 0, 0}, { 0, 0, 1, 0, 1, 0}, { 0, 0, 1, 1, 0, 0}, { 1, 0, 0, 0 , 0, 0}, { 0, 0, 0, 0 , 0, 1}, { 0, 1, 0, 0 , 0, 0}};
int n = cyclesCount(adjM);
System.out.println(n);
}
public static int cyclesCount(int[][] adjm) {
int n = adjm.length;
int count = 0;
List<List<Integer>> nodesPath = new ArrayList<List<Integer>>();
for (int i = 0; i < n; i++) {
int[] conodes = adjm[i];
List<Integer> cnodes = new ArrayList<Integer>();
cnodes.add(i);
for (int j = 0; j < conodes.length; j++) {
if (adjm[i][j] == 1){
cnodes.add(j);
adjm[i][j] = -1;
count += cycles(adjm, i, j, 0, nodesPath, cnodes);
adjm[i][j] = 1;
}
}
}
return count;
}
public static int cycles(int[][] adjm, int snode, int cnode, int count, List<List<Integer>> nodesPath,
List<Integer> conodes) {
if (snode == cnode && !nodesPath.contains(conodes)) {
List<Integer> temp = new ArrayList<>(conodes);
nodesPath.add(temp);
return count + 1;
}
if (snode == cnode && nodesPath.contains(conodes))
return count;
int[] nodes = adjm[cnode];
int n = nodes.length;
for (int i = 0; i < n; i++) {
if (adjm[cnode][i] == 1) {
adjm[cnode][i] = -1;
if(i != snode)
conodes.add(i);
Collections.sort(conodes);
count = cycles(adjm, snode, i, count, nodesPath, conodes);
adjm[cnode][i] = 1;
if(i != snode)
conodes.remove(new Integer(i));
}
}
return count;
}
Based on hashing -
public static void main(String args[]) {
String[] arr = {"ab", "ab", "abc", "bca"};
int n = count(arr);
System.out.println(n);
}
public static int count(String[] arr) {
int n = arr.length;
Map<String, Integer> map = new HashMap<>();
int count = 0;
String p = arr[0];
for (int i = 1; i < n; i++) {
int k = p.length();
int l = arr[i].length();
for (int j = 0; j < l; j += k) {
if (arr[i].length() >= (j + k) && getHash(p, map) == getHash(arr[i].substring(j, j + k), map)) {
count += 1;
break;
}
}
p = arr[i];
}
return count;
}
public static int getHash(String str, Map<String, Integer> map) {
if(map.containsKey(str))
return map.get(str);
char[] c = str.toCharArray();
int h = 0;
double cons = 2.35;
for (int i = 0; i < c.length; i++) {
h += ((int) c[i] * cons);
}
map.put(str, h);
return h;
}
Printing from the array -
public static void main(String args[]){
Integer[] nodes = {3, 9, 20, null, null, 15, 7};
printFromLeaf(nodes, 1);
System.out.println(nodes[0]);
}
public static void printFromLeaf(Integer[] nodes, int index){
int n = nodes.length-1;
if(index > n)
return;
int left = index*2;
int right = index*2 + 1;
if(left-1 <= n && nodes[left-1] != null)
printFromLeaf(nodes, left);
if(right-1 <= n && nodes[right-1] != null)
printFromLeaf(nodes, right);
if(left-1 <= n && right-1 <= n && nodes[left-1] != null && nodes[right-1] != null)
System.out.println(nodes[left-1] + ", " + nodes[right-1]);
}
DP Soln, O(N^2)
public static void main(String args[]){
int[] arr = {2,3,6};
int k = 10;
int n = productSubArrCount(arr, k);
System.out.println(n);
}
public static int productSubArrCount(int[] arr, int k){
int n = arr.length;
int[][] dp = new int[k+1][n+1];
for(int i = 1; i <= k; i++){
for(int j = 1; j <= n; j++){
dp[i][j] = dp[i][j-1];
if(i >= arr[j-1] && arr[j-1] > 0 && i/arr[j-1] < (k+1))
dp[i][j] += dp[i/arr[j-1]][j-1]+1;
}
}
return dp[k][n];
}
public static void main(String args[]){
System.out.println(count("12345"));
}
public static int count(String str){
int n = str.length();
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
package rough;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class NextInLine {
int[][] arrs;
int[] indexes = null;
int n = 0;
Queue<Integer> queue;
Integer prev = null;
boolean removeDuplicate;
public NextInLine( boolean removeDuplicate, int[]... arrs) {
this.n = arrs.length;
this.arrs = arrs;
indexes = new int[n];
queue = new LinkedList<Integer>();
this.removeDuplicate = removeDuplicate;
}
public Integer getNext() {
List<Integer> kList = new ArrayList<>();
while (!queue.isEmpty()) {
kList.add(queue.poll());
}
for (int i = 0; i < n; i++) {
if(arrs[i].length > indexes[i]){
kList.add(arrs[i][indexes[i]]);
}
indexes[i] += 1;
}
Integer[] arr = kList.toArray(new Integer[kList.size()]);
minHeap(arr);
for (int i = 0; i < arr.length; i++)
queue.add(arr[i]);
if (!removeDuplicate && !queue.isEmpty()){
return queue.poll();
}else if(!queue.isEmpty()){
int poll = queue.poll();
if(prev == null || (prev != null && poll != prev)){
prev = poll;
return poll;
}
return getNext();
}
return null;
}
private void minHeap(Integer[] arr) {
int n = arr.length;
while (n > 0) {
if ((n / 2) > 0 && arr[n - 1] < arr[(n / 2) - 1]) {
swap(arr, (n - 1), ((n / 2) - 1));
minHeap(arr);
}
n--;
}
}
private void swap(Integer[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
NextInLine nxtLine = new NextInLine(true, new int[] { 1, 2, 3, 4, 7, 9 }, new int[] { 3, 5, 6, 8, 10 });
Integer n = -1;
while (n != null) {
n = nxtLine.getNext();
if(n != null)
System.out.print(n + " ");
}
}
}
DP Soln - O(N^3)
public static void main(String[] args) throws java.lang.Exception {
int[] coins = { 1, 2, 3 };
int[] count = { 1, 1, 3 };
int sum = 9;
int n = countWays(coins, count, sum);
System.out.println(n);
}
/**
* Coin change problem with finite number of coins available denominations
* of coins = {1,2,3} count of coins = ={1,1,3} find the number of ways for
* getting change for S=6
*/
public static int countWays(int[] coins, int[] count, int sum) {
int n = coins.length;
int[][] dp = new int[sum + 1][n + 1];
int ret = 0;
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= count[j - 1]; k++) {
if (i > coins[j - 1] * k)
dp[i][j] += dp[i - coins[j - 1] * k][j - 1];
if (i == coins[j - 1] * k)
dp[i][j] += 1;
}
}
}
for (int i = 0; i <= n; i++) {
ret += dp[sum][i];
}
return ret;
}
Both recursion and DP
public static void main(String[] args) throws java.lang.Exception {
int[] arr = { 1, 3, 4, 5, 6, 15 };
int sum = 15;
getsubsets(arr, sum, 0, new ArrayList<Integer>());
countsubsets(arr, sum);
}
public static void getsubsets(int[] arr, int sum, int i, List<Integer> list) {
if (sum < 0)
return;
if (sum == 0) {
System.out.println(list);
return;
}
if (i < 0 || i > arr.length - 1)
return;
int n = arr.length;
for (int k = i; k < n; k++) {
list.add(arr[k]);
getsubsets(arr, sum - arr[k], k + 1, list);
list.remove(new Integer(arr[k]));
}
}
public static void countsubsets(int[] arr, int sum){
int n = arr.length;
int[][] dp = new int[sum+1][n+1];
for(int i = 1; i <= sum; i++){
for(int j = 1; j <= n; j++){
if(i > arr[j-1])
dp[i][j] = dp[i-arr[j-1]][j-1];
else
dp[i][j] = dp[i][j-1];
if(arr[j-1] == i)
dp[i][j] += 1;
}
}
System.out.println("DP soln - ");
System.out.println("count - " + dp[sum][n]);
}
Actually there would be 18 combinations for '132241043'
132241043
[1]
[1,3][13]
[1,3,2][13,2]
[1,3,2,2][1,3,22][13,2,2][13,22]
[1,3,2,2,4][1,3,2,24][1,3,22,4][13,2,2,4][13,2,24][13,22,4]
[1,3,2,2,4,1][1,3,2,24,1][1,3,22,4,1][13,2,2,4,1][13,2,24,1][13,22,4,1]
[1,3,2,2,4,1,0][1,3,2,2,4,10][1,3,2,24,1,0][1,3,2,24,10][1,3,22,4,1,0][1,3,22,4,10][13,2,2,4,1,0][13,2,2,4,10][13,2,24,1,0][13,2,24,10][13,22,4,1,0][13,22,4,10]
[1,3,2,2,4,1,0,4][1,3,2,2,4,1,04][1,3,2,2,4,10,4][1,3,2,24,1,0,4][1,3,2,24,1,04][1,3,2,24,10,4][1,3,22,4,1,0,4][1,3,22,4,1,04][1,3,22,4,10,4][13,2,2,4,1,0,4][13,2,2,4,1,04][13,2,2,4,10,4][13,2,24,1,0,4][13,2,24,1,04][13,2,24,10,4][13,22,4,1,0,4][13,22,4,1,04][13,22,4,10,4]
public static void main(String[] args) {
String str = "132241043";
int n = combinations(str);
System.out.println(n);
}
/**
* A message containing letters from A-Z is being encoded to numbers using
* the following mapping:
*
* 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing
* digits, determine the total number of ways to decode it.
*
* For example, Given encoded message "12", it could be decoded as "AB" (1
* 2) or "L" (12).
*/
public static int combinations(String str) {
int n = str.length();
int[] dp = new int[n];
dp[0] = 1;
char[] ch = str.toCharArray();
boolean multiply = true;
for (int i = 1; i < n; i++) {
String s = String.valueOf(String.valueOf(ch[i - 1]) + String.valueOf(ch[i]));
if (multiply && Integer.parseInt(s) <= 26){
dp[i] = dp[i - 1] * 2;
multiply = false;
}else if(!multiply && Integer.parseInt(s) <= 26){
dp[i] = (dp[i - 1]/2) + (dp[i - 1]/2) * 2;
multiply = true;
}else{
multiply = true;
dp[i] = dp[i - 1];
}
}
return dp[n - 1];
}
public static void main(String[] args){
int n = findNumberOfPaths(1, 4);
System.out.println(n);
}
static int findNumberOfPaths(int digit, int step){
int[][] keypad = new int[4][3];
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
keypad[i][j] = i*3 + j+1;
}
}
keypad[3][0] = -1;
keypad[3][2] = -1;
keypad[3][1] = 0;
int x = -1;
int y = -1;
if(digit == 0){
x = 3;
y = 1;
}else{
x = digit / 3;
y = (digit % 3) -1;
}
return findNumberOfPaths(keypad, x, y, step, 0);
}
static int findNumberOfPaths(int[][] keypad, int x, int y, int step, int count){
if(x < 0 || y < 0 || x > 3 || y > 2)
return count;
if(keypad[x][y] < 0)
return count;
if(step == 0)
return count+1;
int[] mx = {2, 2, -2, -2, -1, 1, 1, -1};
int[] my = {-1, 1, 1, -1, 2, 2, -2, -2};
for(int i = 0; i < 8; i++){
count = findNumberOfPaths(keypad, x+mx[i], y+my[i], step-1, count);
}
return count;
}
public static void main(String[] args) {
int[] arr1 = { 1, 2, 5 };
int[] arr2 = { 3,4 };
int n = getMedian(arr1, arr2);
System.out.println(n);
}
public static int getMedian(int[] arr1, int[] arr2) {
int n = arr1.length;
int m = arr2.length;
int q = n + m;
if (q % 2 == 0)
return (getKthPositionValue(arr1, arr2, q / 2) + getKthPositionValue(arr1, arr2, q / 2+1)) / 2;
else
return getKthPositionValue(arr1, arr2, q / 2+1);
}
public static int getKthPositionValue(int[] arr1, int[] arr2, int k) {
int n = arr1.length;
int m = arr2.length;
int i = 0;
int j = 0;
while (i < n && j < m) {
if (i < arr1.length && j < arr2.length && arr1[i] < arr2[j]) {
i++;
k--;
if (k == 0)
return arr1[i - 1];
}
if (i < arr1.length && j < arr2.length && arr2[j] < arr1[i]) {
j++;
k--;
if (k == 0)
return arr2[j - 1];
}
}
if (i < arr1.length - 1 && (k + i -1) < n) {
return arr1[k + i -1];
}
if (j < arr2.length - 1 && (k + j -1) < m) {
return arr2[k + j -1];
}
return -1;
}
public static void main(String[] args) {
int[] arr = { 48, 20, 1, 3, 4, 6, 9, 24 };
sort(arr, 0, arr.length - 1);
int l = left(arr);
System.out.println(l);
}
public static int left(int[] nums) {
int n = nums.length - 1;
int count = 0;
for (int i = n; i >= 0; i--) {
if(nums[i] > -1){
List<Integer> indexes = new ArrayList<Integer>();
left(nums, nums[i], i-1, indexes, false);
if (indexes.size() > 0) {
nums[i] = -1;
for (Integer ind : indexes) {
nums[ind] = -1;
}
}
}
}
for (int i = 0; i < nums.length; i++) {
if(nums[i] > -1)
count++;
}
return count;
}
public static boolean left(int[] nums, int sum, int p, List<Integer> indexes, boolean found) {
if (sum < 0)
return found;
if (sum == 0)
return true;
if (p < 0)
return found;
if (!found && nums[p] != -1) {
indexes.add(p);
found = left(nums, sum - nums[p], p - 1, indexes, found);
if (!found) {
indexes.remove(new Integer(p));
found = left(nums, sum, p - 1, indexes, found);
}
}else if (!found) {
found = left(nums, sum, p - 1, indexes, found);
}
return found;
}
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;
}
public static void main(String[] args){
int[] buildings = {1, 2, 1, 2, 10, 9};
System.out.println(calcMoves(buildings));
}
//1, 2, 3, 4, 8, 7, 6, 5
//1, 2, 1, 2, 10, 9
public static int calcMoves(int[] buildings){
int j = buildings.length -1;
int i = 0;
int moves = 0;
while(i < j){
int iI = i;
int jI = j;
while(i+1 <= j && buildings[i] < buildings[i+1]){
i++;
}
if(i > iI)
moves++;
while(j-1 >= i && buildings[j] < buildings[j-1]){
j--;
}
if(j < jI)
moves++;
i++;
j--;
}
return moves;
}
public static void main(String[] args){
String s1 = "abcdefg";
String s2 = "acb";
System.out.println(lcs(s1, s2));
}
public static boolean lcs(String s1, String s2){
int n = s1.length();
int m = s2.length();
int[][] dp = new int[n+1][m+1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s1.charAt(i-1) == s2.charAt(j-1))
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
int len = dp[n][m];
if(len == m)
return true;
return false;
}
public static void main(String[] args) {
String s1 = "north";
String s2 = "east";
String s3 = "west";
String s4 = "south";
String result = "earth";
long s = System.currentTimeMillis();
solve(s1, s2, s3, s4, result);
System.out.println("Time: " + (System.currentTimeMillis()-s));
}
public static void solve(String s1, String s2, String s3, String s4, String result) {
Map<Integer, Map<Character, Integer>> map = new HashMap<Integer, Map<Character, Integer>>();
s1 = reverse(s1);
s2 = reverse(s2);
s3 = reverse(s3);
s4 = reverse(s4);
result = reverse(result);
for (int i = 0; i < 5; i++) {
Map<Character, Integer> t = new HashMap<Character, Integer>();
if (i < s1.length() && t.get((Character) s1.charAt(i)) != null) {
int c = t.get((Character) s1.charAt(i));
t.put((Character) s1.charAt(i), c + 1);
} else if(i < s1.length()){
t.put((Character) s1.charAt(i), 1);
}
if (i < s2.length() && t.get((Character) s2.charAt(i)) != null) {
int c = t.get((Character) s2.charAt(i));
t.put((Character) s2.charAt(i), c + 1);
} else if(i < s2.length()){
t.put((Character) s2.charAt(i), 1);
}
if (i < s3.length() && t.get((Character) s3.charAt(i)) != null) {
int c = t.get((Character) s3.charAt(i));
t.put((Character) s3.charAt(i), c + 1);
} else if(i < s3.length()) {
t.put((Character) s3.charAt(i), 1);
}
if (i < s4.length() && t.get((Character) s4.charAt(i)) != null) {
int c = t.get((Character) s4.charAt(i));
t.put((Character) s4.charAt(i), c + 1);
} else if(i < s4.length()) {
t.put((Character) s4.charAt(i), 1);
}
map.put(i, t);
}
int[] nos = new int[10];
for (int i = 0; i < 10; i++)
nos[i] = -1;
int[] alph = new int[26];
for (int i = 0; i < 26; i++)
alph[i] = Integer.MAX_VALUE;
int n = solutions(map, result.toCharArray(), 0, nos, alph, 0, 0, new ArrayList<String>());
System.out.println("Total = " + n);
}
public static int solutions(Map<Integer, Map<Character, Integer>> map, char[] res, int i, int[] nos, int[] alph,
int carry, int count, List<String> list) {
if (i == map.size()) {
if(carry == 0){
String str = "";
for(int l = 0; l < 26; l++){
if(alph[l] != Integer.MAX_VALUE){
str += ((char)('a'+l)) + ":" + alph[l] + " ";
}
}
if(!list.contains(str)){
list.add(str);
//System.out.println(str);
return count + 1;
}
return count;
}else{
return count;
}
}
Map<Character, Integer> m = map.get(i);
int p = 0;
for (Map.Entry<Character, Integer> en : m.entrySet()) {
char c = en.getKey();
int mul = en.getValue();
if (alph[c - 'a'] != Integer.MAX_VALUE) {
p += mul * alph[c - 'a'];
} else {
for (int g = 0; g < nos.length; g++) {
if (nos[g] == -1) {
nos[g] = g;
alph[c - 'a'] = g;
count = solutions(map, res, i, nos, alph, carry, count, list);
alph[c - 'a'] = Integer.MAX_VALUE;
nos[g] = -1;
}
}
}
}
for(int q = 0; q <= i; q++){
Map<Character, Integer> mh = map.get(q);
for (Map.Entry<Character, Integer> en : mh.entrySet()) {
char c = en.getKey();
if(alph[c -'a'] == Integer.MAX_VALUE)
return count;
}
}
p += carry;
if (alph[res[i] - 'a'] != Integer.MAX_VALUE && (p % 10) == alph[res[i] - 'a']) {
count = solutions(map, res, i + 1, nos, alph, (p / 10), count, list);
} else if (alph[res[i] - 'a'] != Integer.MAX_VALUE && (p % 10) != alph[res[i] - 'a']) {
return count;
} else if (alph[res[i] - 'a'] == Integer.MAX_VALUE && nos[p % 10] == -1) {
alph[res[i] - 'a'] = (p % 10);
nos[p % 10] = (p % 10);
count = solutions(map, res, i + 1, nos, alph, (p / 10), count, list);
alph[res[i] - 'a'] = Integer.MAX_VALUE;
nos[p % 10] = -1;
} else if (alph[res[i] - 'a'] == Integer.MAX_VALUE && nos[p % 10] != -1) {
return count;
}
return count;
}
public static String reverse(String str) {
char[] arr = str.toCharArray();
String rev = "";
for (int i = arr.length - 1; i >= 0; i--)
rev += arr[i];
return rev;
}
public static void main(String[] args) {
System.out.println(reverse("1+2*3-204"));
}
/**
* Reverse this string 1+2*3-20. Note: 20 must be retained as is. Expected
* output: 20-3*2+1
*/
public static String reverse(String str) {
char[] c = str.toCharArray();
int i = 0;
Stack<String> st = new Stack<String>();
while (i < c.length) {
String t = "";
while (!st.isEmpty() && isN(st.peek()) && isN(String.valueOf(c[i]))) {
String k = st.pop();
t = k + t;
}
t += String.valueOf(c[i]);
st.push(String.valueOf(t));
i++;
}
String ret = "";
while (!st.isEmpty())
ret += st.pop();
return ret;
}
public static boolean isN(String str) {
boolean f = true;
try {
Integer.parseInt(str);
} catch (Exception e) {
f = false;
}
return f;
}
DP Solution O(n2)
public static void main(String[] args)
{
char[][] fill = {
{'.', 'X', 'X', 'X', 'X', 'X', 'X', '.', '.', '.', '.' },
{'.', '.', '.', 'X', '.', '.', 'X', 'X', '.', '.', 'X' },
{'.', '.', '.', 'X', 'X', 'X', 'X', '.', '.', '.', '.' },
{'.', '.', 'X', '.', '.', '.', '.', '.', 'X', '.', '.' },
{'.', '.', 'X', 'X', 'X', '.', '.', 'X', 'X', '.', '.' },
{'.', '.', '.', '.', '.', 'X', 'X', '.', '.', '.', '.' }
};
System.out.println(maxContagiousShape(fill));
}
public static int maxContagiousShape(char[][] fill){
int n = fill.length;
int m = fill[0].length;
int[][] dp = new int[n][m];
//for extreme left corner, max contagious size would be 1 if it is 'X'
if(fill[0][0] == 'X')
dp[0][0] = 1;
//contagious shapes in 1st row
for(int i = 1; i < m; i++){
if(fill[0][i] == 'X')
dp[0][i] = dp[0][i-1] + 1;
else
dp[0][i] = dp[0][i-1];
}
//contagious shapes in 1st column
for(int i = 1; i < n; i++){
if(fill[i][0] == 'X')
dp[i][0] = dp[i-1][0] + 1;
else
dp[i][0] = dp[i-1][0];
}
//fill up the remaining
for(int i = 1; i < n; i++){
int contX = 0;
for(int j = 1; j < m; j++){
if(fill[i][j] == 'X')
contX += 1;
else
contX = 0;
if(fill[i][j] == '.'){
if(fill[i-1][j] == 'X' && fill[i][j-1] == 'X')
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) +1;
if(fill[i-1][j] == 'X' && fill[i][j-1] == '.')
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) +1;
if(fill[i-1][j] == '.' && fill[i][j-1] == 'X')
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
if(fill[i-1][j] == '.' && fill[i][j-1] == '.')
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}else{
if(fill[i-1][j] == 'X' && fill[i][j-1] == 'X')
dp[i][j] = Math.max(dp[i-1][j]+contX, dp[i][j-1] +1);
if(fill[i-1][j] == 'X' && fill[i][j-1] == '.')
dp[i][j] = Math.max(dp[i-1][j]+1, dp[i][j-1] +2);
if(fill[i-1][j] == '.' && fill[i][j-1] == 'X')
dp[i][j] = Math.max(dp[i-1][j]+contX, dp[i][j-1] +1);
if(dp[i-1][j] == '.' && dp[i][j-1] == '.')
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[n-1][m-1];
}
public static void main(String[] args) {
String[] game = {"########", "#@....G#", "##.##@##", "#..@..S#", "#@.....#", "########"};
System.out.println(shortestDist(game));
}
public static int shortestDist(String[] game) {
int Sx = -1;
int Sy = -1;
int orient = 0;
char[][] arr = new char[game.length][game[0].length()];
for (int i = 0; i < game.length; i++) {
for (int j = 0; j < game[0].length(); j++) {
arr[i][j] = game[i].charAt(j);
if (arr[i][j] == 'S') {
Sx = i;
Sy = j;
}
if (arr[i][j] == '@') {
orient += 1;
}
}
}
int[] min = new int[1];
min[0] = Integer.MAX_VALUE;
List<String> nodes = new ArrayList<String>();
nodes.add(Sx + ":" + Sy);
shortestDistance(arr, 0, min, Sx, Sy, arr.length - 1, arr[0].length - 1, nodes, orient);
return min[0];
}
// n = length-1
public static int shortestDistance(char[][] game, int step, int[] min, int x, int y, int n, int m,
List<String> nodes, int orient) {
if (x < 0 || y < 0 || x > n || y > m)
return step;
if (game[x][y] == '#')
return step;
if (game[x][y] == 'G'&& orient <= 0) {
min[0] = Math.min(min[0], step);
return step;
}
int[] v = { 1, 0, -1, 0 };
int[] h = { 0, 1, 0, -1 };
for (int i = 0; i < 4; i++) {
String uf = (x + v[i]) + ":" + (y + h[i]);
if (!nodes.contains(uf)) {
nodes.add(uf);
if(x + v[i] >= 0 && y + h[i] >= 0 && x + v[i] < n && y + h[i] < m && game[x + v[i]][y + h[i]] == '@'){
orient -= 1;
}
shortestDistance(game, step + 1, min, x + v[i], y + h[i], n, m, nodes, orient);
nodes.remove(uf);
}
}
return step;
}
public static void main(String[] args) {
Elem[] e = new Elem[7];
e[0] = new Elem(0, 0);
e[1] = new Elem(-1, 1);
e[2] = new Elem(6, 2);
e[3] = new Elem(4, 3);
e[4] = new Elem(5, 4);
e[5] = new Elem(6, 5);
e[6] = new Elem(6, 6);
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
}
public static int getMaxIndex(Elem[] e) {
maxHeapMod(e);
e[0].acc += 1;
int index = e[0].index;
for (int i = 0; i < e.length; i++)
e[i].acc += 1;
swap(e, 0, e.length - 1);
return index;
}
//0 -1 6 4 5 6 6
public static void maxHeapMod(Elem[] e) {
int n = e.length - 1;
for (int i = n; i > 0; i--) {
int j = ((i + 1) / 2) - 1;
if (e[i].acc == e[j].acc) {
if (e[i].val > e[j].val) {
swap(e, i, j);
maxHeapMod(e);
} else if (e[i].val == e[j].val && e[i].index < e[j].index) {
swap(e, i, j);
maxHeapMod(e);
}
} else if (e[i].acc < e[j].acc) {
swap(e, i, j);
maxHeapMod(e);
}
}
}
public static void swap(Elem[] e, int i, int j) {
Elem t = e[i];
e[i] = e[j];
e[j] = t;
}
static class Elem {
int val;
int index;
int acc;
public Elem(int val, int index) {
this.val = val;
this.index = index;
}
}
public class GetMinTimeForAssignedTask {
public static void main(String[] args) {
int[] nums = new int[]{1,1,1,2,2,2};
int k = 2;
System.out.println(getMiniTime(nums, k));
}
static int getMiniTime(int[] nums, int k){
int max = 0;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
}
int[] arr = new int[max+1];
int t = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
t = Math.min(t, allocate(nums, arr, k, i, new Time(), 0).minTime);
}
return t;
}
//111222
static Time allocate(int[] nums, int[] arr, int k, int task, Time time, int st){
if(null == nums && null == arr) return time;
boolean done = true;
for (int i = 0; i < nums.length; i++) {
if(nums[i] > 0){
done = false;
break;
}
}
if(done) {
time.minTime = Math.min(time.minTime, time.time);
return time;
}
boolean assigned = false;
for (int i = st; i < nums.length; i++) {
if(arr[nums[i]] == 0 && nums[i] > 0){
for (int j = 0; j < arr.length; j++) {
if(arr[j] > 0)
arr[j]--;
}
assigned = true;
int u = nums[i];
arr[nums[i]] = k;
nums[i] = 0;
time.time += 1;
if(st == nums.length-1) st = 0;
time = allocate(nums, arr, k, i, time, st+1);
nums[i] = u;
time.time -= 1;
}
}
if(!assigned){
for (int j = 0; j < arr.length; j++) {
if(arr[j] > 0)
arr[j]--;
}
time.time += 1;
time = allocate(nums, arr, k, 0, time, 0);
}
return time;
}
}
class Time{
int time;
int minTime = Integer.MAX_VALUE;
}
public class SortAnArrayIntoSequenceOfHighestAndLowest1 {
public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int[] res = sort(arr);
for (int i = 0; i < res.length; i++) {
System.out.print(res[i] + " ");
}
}
static int[] sort(int[] arr){
if(arr == null) return arr;
if(arr.length == 1) return arr;
int k = 0;
boolean getMax = true;
while(k < arr.length){
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int minIndex = -1;
int maxIndex = -1;
for (int i = k; i < arr.length; i++) {
if(!getMax && min > arr[i]){
min = arr[i];
minIndex = i;
}
if(getMax && max < arr[i]){
max = arr[i];
maxIndex = i;
}
}
if(!getMax){
int m = arr[k];
arr[k] = arr[minIndex];
arr[minIndex] = m;
}else{
int m = arr[k];
arr[k] = arr[maxIndex];
arr[maxIndex] = m;
}
k++;
getMax = !getMax;
}
return arr;
}
public class SecondMinElement {
public static void main(String[] args) {
BTN N7 = new BTN(3, null, null);
BTN N6 = new BTN(5, null, null);
BTN N5 = new BTN(2, null, null);
BTN N4 = new BTN(4, null, null);
BTN N3 = new BTN(3, N6, N7);
BTN N2 = new BTN(2, N4, N5);
BTN N1 = new BTN(2, N2, N3);
int[] arr = new int[2];
arr[0] = Integer.MAX_VALUE;
arr[1] = Integer.MAX_VALUE;
int[] res = getMin(N1, arr);
System.out.println("Second min - " + res[1]);
}
static int[] getMin(BTN node, int[] arr){
if(node == null) return arr;
arr = getMin(node.left, arr);
arr = getMin(node.right, arr);
if(node.val < arr[0]){
arr[0] = node.val;
}if(node.val < arr[1] && node.val > arr[0]){
arr[1] = node.val;
}
return arr;
}
}
class BTN{
int val;
BTN left;
BTN right;
public BTN(int val, BTN left, BTN right) {
super();
this.val = val;
this.left = left;
this.right = right;
}
}
public class CanRunTasks {
public static void main(String[] args) {
int[][] S = new int[][]{{0, 4}, {1, 3}, {2, 5}, {3, 5}};
int[][] T = new int[][]{{0, 4}, {1, 2}, {2, 3}};
System.out.println(canRun(S, T, new ArrayList<>(), 0, false));
}
static boolean canRun(int[][] S, int[][] T, List<Integer> serverIndexes, int taskIndex, boolean canAllocate){
int[] alloc = allocateATask(S, T, serverIndexes, taskIndex);
if(alloc[1] <= -1){
return true;
}if(alloc[0] <= -1 && alloc[1] > -1){
return false;
}
if(T[taskIndex][1] > 0){
serverIndexes.add(alloc[0]);
canAllocate = canRun(S, T, serverIndexes, alloc[1], canAllocate);
}else{
canAllocate = canRun(S, T, new ArrayList<>(), alloc[1]+1, canAllocate);
}
return canAllocate;
}
static int[] allocateATask(int[][] S, int[][] T, List<Integer> serverIndexes, int taskIndex){
int[] res = new int[2];
res[0] = -1; res[1] = -1;
int sI = 0;
while(sI < S.length){
if(S[sI][1] > 0 && !serverIndexes.contains(sI)){
res[0] = sI;
S[sI][1]--;
break;
}
sI++;
}
int tI = 0;
while(tI < T.length){
if(T[tI][1] > 0){
res[1] = tI;
T[tI][1]--;
break;
}
tI++;
}
return res;
}
}
- sudip.innovates October 18, 2017