guilhebl
BAN USERpublic class SolutionSameLevelXYTree {
public static boolean find(Node root, int x, int y) {
Map<Integer, Integer> allLevelsX = new HashMap<>();
Map<Integer, Integer> allLevelsY = new HashMap<>();
findAllLevelsOccurenceOfVal(root, x, 0, true, allLevelsX);
findAllLevelsOccurenceOfVal(root, y, 0, false, allLevelsY);
if (allLevelsX.isEmpty() || allLevelsY.isEmpty()) {
return false;
}
for (Entry<Integer, Integer> lX: allLevelsX.entrySet()) {
if (allLevelsY.get(lX.getKey()) != null) {
return true;
}
}
return false;
}
public static void findAllLevelsOccurenceOfVal(Node root, int v, int l, boolean isX, Map<Integer, Integer> levelCount) {
if (root == null) {
return;
}
if (isX && root.x == v || !isX && root.y == v) {
if (levelCount.get(l) == null) {
levelCount.put(l, 1);
} else {
int count = levelCount.get(l);
levelCount.put(l, count + 1);
}
}
if (root.children != null) {
for (Node n : root.children) {
findAllLevelsOccurenceOfVal(n, v, l+1, isX, levelCount);
}
}
}
public static void testSolution() {
Node n1 = new Node(1, 120);
Node n2 = new Node(5, 15);
Node n3 = new Node(30, 70);
Node n4 = new Node(80, 110);
Node n5 = new Node(35, 40);
Node n6 = new Node(45, 50);
Node n7 = new Node(55, 65);
Node n8 = new Node(90, 100);
List<Node> n1List = new ArrayList<>();
n1List.add(n2);
n1List.add(n3);
n1List.add(n4);
n1.children = n1List;
List<Node> n2List = new ArrayList<>();
n2List.add(n5);
n2List.add(n6);
n2.children = n2List;
List<Node> n3List = new ArrayList<>();
n3List.add(n7);
n3.children = n3List;
List<Node> n4List = new ArrayList<>();
n4List.add(n8);
n4.children = n4List;
System.out.println(find(n1, 45, 100));
System.out.println(find(n1, 30, 100));
System.out.println(find(n1, 30, 70));
System.out.println(find(n1, 70, 30));
}
}
class Node {
int x;
int y;
List<Node> children;
public Node(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
public static void printLongestSubstringLexBiggerV2(String str) {
if (str == null || str.length() <= 1) {
return;
}
boolean found = false;
int l = str.length();
int i = 0, j = 1;
while(j < l && !found) {
if (str.charAt(i) < str.charAt(j)) {
found = true;
} else {
j++;
}
}
if (found) {
System.out.println(str.substring(j));
}
}
}
1. Suppose the API is exposed via RESTful webservice, use a token based mechanism to detect callers, send the token along each call in the HTTP Header, callers which specific tokens have higher priority, after detecting the caller, interrupt any existing running threads to serve the Thread with highest priority, use an OS that supports preemptive task scheduling. After finishing work with thread of highest priority resume unfinished threads.
2. Use a load balancer and a stateless service model, where each request can be treated in isolation inside each server.
Use 2 B-Trees for storing the photo Node indexes based on their timestamp, one tree for favorites and other for non-favorites so search will be
O (Log N), you can search for first immediate node after Timestamp T, this will still be O (log N), insert and remove O(log N) each node of the tree would store a key value which would point to a HashMap<key, photo> which would store the actual photo data (or else retrieve it from a persistent storage).
public static void main(String[] args) {
solveSeries();
}
public static void solveSeries() {
for (int i = 1; i <= 6; i++) {
System.out.println(findSeries(i));
}
}
public static String findSeries(int n) {
String s = "1";
if (n == 1) {
return s;
}
for (int i = 2; i <= n; i++) {
s = buildOnPrevious(s);
}
return s;
}
public static String buildOnPrevious(String s) {
char[] c = s.toCharArray();
StringBuilder sb = new StringBuilder();
int cnt = 1;
char ci = c[0];
for (int i = 1; i < c.length; i++) {
if (c[i] == ci) {
cnt++;
} else {
sb.append(cnt + "" + ci);
cnt = 1;
ci = c[i];
}
}
sb.append(cnt + "" + ci);
return sb.toString();
}
// output:
1
11
21
1211
111221
312211
public static void main(String[] args) {
System.out.println(isPalindrome("A man, a plan, a canal, Panama! "));
// abbacabba
System.out.println(isPalindrome("#!@$% Ab !@%!@ B !%@!%!@% a 1%!@% C !@%!@% a 1%!@% B 1%!@% b @!#)(*) A "));
System.out.println(isPalindrome("TEST"));
}
public static boolean isPalindrome(String s) {
char a, b;
int valA = 0, valB = 0;
int i = 0, j = s.length() - 1;
while(i < j) {
a = Character.toLowerCase(s.charAt(i));
b = Character.toLowerCase(s.charAt(j));
valA = a - 'a';
valB = b - 'a';
if(valA < 0 || valA >= 26) {
i++;
}
if(valB < 0 || valB >= 26) {
j--;
}
if((valA >= 0 && valA < 26) && (valB >= 0 && valB < 26) && a != b) {
return false;
} else if((valA >= 0 && valA < 26) && (valB >= 0 && valB < 26) && a == b) {
i++;
j--;
}
}
return true;
}
// output:
true
true
false
You can think of the board as a graph, where each cell is connected by a 1 weight edge, you have starting x,y of the soldier which will be on a certain vertex, you have starting point of targets which will be on some vertexes, based on this you can use solution:
1. calculate shortest distance from origin to target using djikstra.
2. Let's call it N the distance from Origin to Target, Starting from O traverse through path from O to T stopping at Node (N - 8), return that node as nearest shooting point. If there are more than one path choose any bullet-proof one (although not implicit in the question I guess shooting from a bullet proof cell must be safer than a non bullet-proof one).
Obs1 : If path length is shorter than (N - 8) soldier can shoot target from Origin, so return O.
Obs2 : If target is in a bullet-proof cell, solider must walk over that same cell in order to shoot target, so in this case nearest distance would be N.
This is wrong and it has 2 errors: 1 it counts duplicates and 2 it only counts direct parents and childs, you need to consider all the parents above on that branch, for example suppose you have a case as:
1
\
3
\2
your solution would wrongly consider 2 as one such node, but it's higher than a parent above on his branch.
@Killedsteel when we generate a subset, each element has the “possibility” of either being in there or not. That is, for the first element, there are 2 choices. For the second, there are two, etc. So, doing 2 * 2 * ... * 2 n times gives us 2^n subsets. We will not be able to do better than this in time or space complexity.
- guilhebl April 28, 20151. generate int array A based on sample range from 1 ... N
2. generate all subsets of A of size K.
3. print results
complexity: O(2^n)
implementation:
public static void main(String[] args) {
int n = 4;
int k = 2;
int a[] = getArrayFromN(n);
List<List<Integer>> lists = generateSubsetsSizeM(a, k);
for (List<Integer> arrayList : lists) {
printList(arrayList);
System.out.println();
}
}
private static int[] getArrayFromN(int n) {
int j = 0;
int a[] = new int[n];
for(int i = 1; i <= n; i++) {
a[j] = i;
j++;
}
return a;
}
public static List<List<Integer>> generateSubsetsSizeM(int a[], int size) {
List<List<Integer>> result = new ArrayList<>();
int max = new Double(Math.pow(2, a.length)).intValue();
int k = 0, index = 0;
for(int i = 0; i < max; i++) {
k = i;
index = 0;
List<Integer> list = new ArrayList<>();
while(k > 0) {
if ((k & 1) > 0) {
list.add(a[index]);
}
k = k >> 1;
index++;
}
if (list.size() == size) {
result.add(list);
}
}
return result;
}
// output for N = 4 and K = 2:
1 2
1 3
2 3
1 4
2 4
3 4
Use Quickselect to select the Kth smallest element in array,
average: O(n)
worst case: O(n^2)
implementation:
public static void solveKthSmallest() {
Integer[] a = {12, 3, 17, 0, 9, 6, 100};
int k = 3;
System.out.println(quickSelect(a, k-1, 0, a.length-1));
}
private static <E extends Comparable<? super E>> int partition(E[] arr,
int left, int right, int pivot) {
E pivotVal = arr[pivot];
swap(arr, pivot, right);
int storeIndex = left;
for (int i = left; i < right; i++) {
if (arr[i].compareTo(pivotVal) < 0) {
swap(arr, i, storeIndex);
storeIndex++;
}
}
swap(arr, right, storeIndex);
return storeIndex;
}
private static <E extends Comparable<? super E>> E quickSelect(E[] arr,
int n, int left, int right) {
Random rand = new Random();
while (right >= left) {
int pivotIndex = partition(arr, left, right,
rand.nextInt(right - left + 1) + left);
if (pivotIndex == n) {
return arr[pivotIndex];
} else if (pivotIndex < n) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
return null;
}
private static void swap(Object[] arr, int i1, int i2) {
if (i1 != i2) {
Object temp = arr[i1];
arr[i1] = arr[i2];
arr[i2] = temp;
}
}
in the example above both Trees differ right from the root, and still they give the same inorder output, so correct me if I'm wrong but your solution fails on that case, a much simpler solution would be to output both inOrder traversals as a string and compare them.
- guilhebl April 27, 2015Imagine you want to search all nodes between range 4 - 6 , you start from Root of tree, it's value is 3, so now you know the only possible nodes between that range must be in the right side, if there are any, so return any counts you can find starting from the right child. The other case is the opposite, it's when the range is lower than the current root's value, so only possible nodes remains in the left side.
- guilhebl April 24, 2015public int countNodesBetweenRange(NodeB root, int l, int r) {
if (root == null) {
return 0;
} else if (root.val >= l && root.val =< r) {
return 1 + countNodesBetweenRange(root.left, l, r) +
countNodesBetweenRange(root.right, l, r);
} else if (root.val < l) {
return countNodesBetweenRange(root.right, l, r);
} else if (root.val > r) {
return countNodesBetweenRange(root.left, l, r);
}
return 0;
}
We can think of this problem as a sort of graph coloring problem, where each "island" of 1s should have it's unique color, and also each "oceans" of 0s should have it's unique color.
Based on that,:
1. calculate each group or "island" of elements(those clustered together) of 1s, tagging each country with a number starting from 1 (color), and 0s too.
2. after all groups are calculated retrieve size of largest cluster group of 1s.
public static void solveCountNumCountries() {
int m[][]= {{1,1,0,0,0},{1,1,0,0,0},{1,0,0,1,1},{0,0,0,0,0},{1,0,1,0,1}};
System.out.println(countNumCountries(m));
}
public static int countNumCountries(int[][] m) {
int[][] country = new int[m.length][m[0].length];
for (int i = 0; i < country.length; i++) {
for (int j = 0; j < country[0].length; j++) {
country[i][j] = -1;
}
}
int ctyCount = 1;
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[0].length; j++) {
if(country[i][j] == -1) {
expandBorders(m, country, i, j, m[i][j], ctyCount++);
}
}
}
int[] ctyCounts = new int[ctyCount];
for (int i = 0; i < ctyCounts.length; i++) {
ctyCounts[i] = 0;
}
int maxCount = 0;
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[0].length; j++) {
ctyCounts[country[i][j] - 1]++;
if(m[i][j] == 1) {
maxCount = Math.max(maxCount, ctyCounts[country[i][j] - 1]);
}
}
}
return maxCount;
}
private static void expandBorders(int[][] m, int[][] c, int i, int j, int elemVal, int ctyCount) {
if (i >= 0 && i < m.length && j >= 0 && j < m[0].length) {
if(c[i][j] == - 1 && m[i][j] == elemVal) {
c[i][j] = ctyCount;
// check borders clockwise rotation
if (i >= 0 && i < m.length && j > 0 && j < m[0].length) {
expandBorders(m, c, i, j - 1, elemVal, ctyCount);
}
if (i > 0 && i < m.length && j > 0 && j < m[0].length) {
expandBorders(m, c, i-1, j-1, elemVal, ctyCount);
}
if (i > 0 && i < m.length && j >= 0 && j < m[0].length) {
expandBorders(m, c, i-1, j, elemVal, ctyCount);
}
if (i > 0 && i < m.length && j >= 0 && j < m[0].length-1) {
expandBorders(m, c, i-1, j+1, elemVal, ctyCount);
}
if (i >= 0 && i < m.length && j >= 0 && j < m[0].length-1) {
expandBorders(m, c, i, j+1, elemVal, ctyCount);
}
if (i >= 0 && i < m.length-1 && j >= 0 && j < m[0].length-1) {
expandBorders(m, c, i+1, j+1, elemVal, ctyCount);
}
if (i >= 0 && i < m.length-1 && j >= 0 && j < m[0].length) {
expandBorders(m, c, i+1, j, elemVal, ctyCount);
}
if (i >= 0 && i < m.length-1 && j > 0 && j < m[0].length) {
expandBorders(m, c, i+1, j-1, elemVal, ctyCount);
}
}
}
}
// output: 5
- guilhebl April 22, 2015In a binary tree there can be any value on any node, so we need to keep track of the Min. value found so far for that depth branch and propagate it until you reach the leafs, be aware not to count duplicates in the way back, a HashSet would help to avoid that,
and the final HashSet will hold all Nodes which are lesser than all their possible parents.
public static int countNumLesserNodes(Node<Integer> root) {
if(root == null) {
return 0;
}
Set<Node<Integer>> set = new HashSet<>();
countNumLesserNodes(root.left, root.data, set);
countNumLesserNodes(root.right, root.data, set);
return set.size();
}
public static void countNumLesserNodes(Node<Integer> root, int pVal, Set<Node<Integer>> set) {
if(root == null) {
return;
}
if(root.data < pVal) {
set.add(root);
pVal = root.data;
}
countNumLesserNodes(root.left, pVal, set);
countNumLesserNodes(root.right, pVal, set);
}
swaps pairs one at a time and returns new Head of List.
public static NodeLinked switchPairs(NodeLinked head) {
NodeLinked t1, t2, h2 = null;
t1 = head;
while(t1 != null && t1.next != null) {
t2 = t1.next;
t1.next = t2.next;
if (t1.next != null) {
t1.next.prev = t1;
}
t2.prev = t1.prev;
if (t2.prev == null){
h2 = t2;
} else {
t2.prev.next = t2;
}
t1.prev = t2;
t2.next = t1;
t1 = t1.next;
}
return h2;
}
@hideki.ikeda to deal with that case and also for the case of duplicates there is this solution: instead of saving only the number in the Map, save the number and the index of it in the array, use some sort of class like:
class NumIndex {
int num;
int index;
}
then the map would be a map of Map<Integer, NumIndex> then you can put an if condition when you find a value that matches,
12 - arr[i] = res --> NumIndex nIndex = Map.get(res)
is it a valid combination ? If (nIndex.index != currentNumber.index) -> true;
this does the job without recursion but prints results in a different order:
public static void main(String[] args) {
String[] strs = {"red", "fox", "super"};
solveMultiPerms(strs);
}
public static void solveMultiPerms(String[] strs) {
String[][] sets = new String[strs.length][];
for (int i = 0; i < strs.length; i++) {
sets[i] = new String[strs[i].length()];
char[] chars = strs[i].toCharArray();
for (int j = 0; j < chars.length; j++) {
sets[i][j] = new Character(chars[j]).toString();
}
}
List<String> results = new ArrayList<>();
int[] state = new int[sets.length];
int p = 0;
boolean stillHasMore = true;
StringBuilder sb = null;
while (stillHasMore) {
sb = new StringBuilder();
for (int i = 0; i < state.length; i++) {
sb.append(sets[i][state[i]]);
}
results.add(sb.toString());
state[p]++;
while (stillHasMore && state[p] == sets[p].length) {
state[p] = 0;
p++;
if (p == sets.length) {
stillHasMore = false;
} else {
state[p]++;
}
}
p = 0;
}
for (String string : results) {
System.out.println(string);
}
}
calling this function in the entire array will always resolve to the same numbers so
If it would be possible to specify a starting index on each of these functions
Then you could sort the array only using findMin(int i).
// finds Min from index i to array.length.
pseudocode:
public static void sortArray(int a[]) {
for (int i - 0; i < a.length; i++) {
int min = findMin(a.length, i);
if (min != a[i]) {
swap(a, min, i);
}
}
}
*In your example you actually have 2 odd count numbers: 5 and 7
solution using a hashmap to store counts:
public class CountOddNumberOfTimesElement {
public static void main(String[] args) {
int a[] = {4,7,2,2,5,3,5,7,7,3,4,5,7};
System.out.println(findNumCountOddTimes(a));
}
public static int findNumCountOddTimes(int a[]) {
Map<Integer, Integer> mapCount = new HashMap<>();
for (int i = 0; i < a.length; i++) {
if (!mapCount.containsKey(a[i])) {
mapCount.put(a[i], 1);
} else {
Integer count = mapCount.get(a[i]);
count = count + 1;
mapCount.put(a[i], count);
}
}
for(Map.Entry<Integer, Integer> countEntry : mapCount.entrySet()) {
if (countEntry.getValue() % 2 != 0) {
return countEntry.getKey();
}
}
return -1;
}
}
// output: 5
public static boolean isPalindrome(String s) {
if (s == null || s.length() == 0) {
return false;
}
if (s.length() == 1) {
return true;
}
char[] c1 = s.toCharArray();
int mid = c1.length/2;
int i = mid - 1;
int j = c1.length % 2 == 0 ? mid : mid + 1;
while(i > 0 && j < c1.length && c1[i] == c1[j]) {
i--;
j++;
}
return (i == 0);
}
1. get the middle element of the array (mid element should be root),
2. partition left side and right side to new arrays aLeft and aRight,
from 0 - mid , mid + 1 - array.length
each array will represent a subtree of root, with their mid elements representing the root's left child (mid of aLeft) and right child (mid of aRight).
3. Call the function recursively until you reach an array size of 1. These will be the leaf elements
* If you wish to check if this is a balanced binary tree and elements are sorted properly, just check left child and right child while dividing the array using the rule:
if (ROOT > ROOT.LEFT && ROOT < ROOT.RIGHT)
public static void main(String[] args) {
Set<String> stringSet = new HashSet<String>();
getPermutationOfString("tree".toCharArray(), 0, stringSet);
printSets(stringSet);
}
public static void getPermutationOfString(char[] a, int i, Set<String> stringSet) {
if (i == a.length) {
stringSet.add(new String(a));
} else if (i < a.length) {
for (int j = i; j < a.length; j++) {
swap(a, i, j);
getPermutationOfString(a, i + 1, stringSet);
swap(a, i, j);
}
}
}
public static void swap(char[] a, int i, int j) {
char temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void printSets(Set<String> strs) {
for (String string : strs) {
System.out.println(string);
}
}
public static void main(String[] args) {
System.out.println("Match " + isMatchPattern("abcddd", "abcd*"));
System.out.println("Match " + isMatchPattern("ccca", "c*a"));
System.out.println("Match " + isMatchPattern("ab", ".*"));
System.out.println("Match " + isMatchPattern("abcdefffffffg", "a*c..f*"));
System.out.println("Match " + isMatchPattern("fffffffgcdeeeeeee", "f*g..e*"));
System.out.println("Match " + isMatchPattern("abc", "...e*"));
}
public static boolean isMatchPattern(String s, String p) {
char[] cs = s.toCharArray();
char[] cp = p.toCharArray();
boolean inRep = false;
int i = 0, j = 0;
while(i < cs.length && j < cp.length) {
if (j + 1 < cp.length) {
if (cp[j + 1] == '*') {
inRep = true;
}
}
if (cs[i] == cp[j] || cp[j] == '.') {
if (inRep && cp[j] != '.' && cp[j] != '*') {
while(i < cs.length && j < cp.length && cs[i] == cp[j]) {
i++;
}
j+=2;
inRep = false;
} else {
i++;
j++;
}
} else {
if (inRep) {
i++;
j++;
inRep = false;
} else {
return false;
}
}
}
if (i < cs.length) {
return false;
}
return true;
}
Based on Kadane's algorithm: O(n)
* one minor correction in given example: starting index is 7 and not 8
public static void findLongestPositiveSeq(int a[]) {
int currMax = 0, maxLongest = 0;
int maxStartIndex = 0, currStartIndex = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] > 0) {
currMax++;
} else {
maxStartIndex = i + 1;
if (currMax > maxLongest) {
maxLongest = currMax;
maxStartIndex = currStartIndex;
}
currMax = 0;
currStartIndex = i + 1;
}
}
System.out.println("max = " + maxLongest + " starting at: " + maxStartIndex);
}
public class CheckByteAtLeastNBitsSetToX {
public static void main(String[] args) {
System.out.println(hasAtLeastNBitsSetToX((byte)7, 3, true));
}
public static boolean hasAtLeastNBitsSetToX(byte n, int k, boolean isSet) {
int n1 = n;
int countOnes = 0, countZeros = 0;
while (n1 > 0) {
if ((n1 & 1) > 0) {
countOnes++;
} else {
countZeros++;
}
n1 = n1 >> 1;
}
return isSet? (countOnes >= k) : (countZeros >= k);
}
}
Yes it's possible to store the counts in each node like having vars such as:
directEmployeesCount and totalEmployeesCount (which represents total count under subtree), then it would be necessary to calculate only once the values (O n log n), after building tree, in subsequent calls it would be O(1).
And for any delete or update the total counts of the left or right branch(starting from direct manager of inserted or deleted employee) counts should be recalculated and cascaded from manager to manager until reaching the CEO, this should be O(L) where L = number of levels in the tree where that employee got inserted/deleted.
RepI am randy, 29 year old and I am doing a job. I am doing a job as a plant ...
traverse both arrays at the same time, when you find an element in array 1 which is different or non-existant in array 2, return array1[i]. treat edge cases.
- guilhebl May 06, 2016