guilhebl
BAN USER1. using a HashMap<Character, Integer> traverse String inserting each unique found chars and it's occurences in String. keep track of maxUniqueCount found.
2. if maxUniqueCount > (n/2) + 1 return false;O
else copy contents of Map to ArrayList and sort list by occurrence count.
3. after list is sorted start from highest count and pick one char of it and decrement counter, keep traversing list picking pairs with highest and second highest chars and place them one after another in sequence until both reach count 0.
4. If you reach count 0 for all Chars you reached the final solution String.
Complexity: O (n * log(n))
Based on the input data it would make it possible to build the tree in O(n) time, using a HashMap lets you jump directly to a node instead of traversing there from the tree's root node:
1. build tree of designated company hierarchy based on input map, use an auxiliary
Map of <String, TreeNodeEmp> representing each employee and also for adding the direct employees of a specific manager.
complexity: O(n)
2. Once tree is built, calculate counts of Direct employees and total employees under each employee.
Once calculated subsequent operations for read will be O(1) such as counting total direct and indirect employees for any given employee, whenever tree is changed (nodes inserted or deleted) subtree counts of left or right branch starting from root should be recalculated.
Solution in Java:
public class Solution {
public static void main(String[] args) {
printAllEmployeesOfAllManagers();
}
public static void printAllEmployeesOfAllManagers() {
Map<String, String> dataSet = new HashMap<>();
dataSet.put("A", "C");
dataSet.put("B", "C");
dataSet.put("C", "F");
dataSet.put("D", "E");
dataSet.put("E", "F");
dataSet.put("F", "F");
Map<String, TreeNodeEmp> empTreeNodeMap = new HashMap<>();
TreeNodeEmp root = buildHierarchyTreeOfCompany(dataSet, empTreeNodeMap);
calculateCountsOfTree(root);
Map<String, Integer> output = new HashMap<>();
for (Map.Entry<String, TreeNodeEmp> empEntry : empTreeNodeMap
.entrySet()) {
String empName = empEntry.getKey();
TreeNodeEmp emp = empEntry.getValue();
output.put(empName, emp.countTotalEmployees);
}
printResults(output);
}
public static void printResults(Map<String, Integer> results) {
for (Map.Entry<String, Integer> r : results.entrySet()) {
System.out.println(r.getKey() + "  " + r.getValue());
}
}
public static void calculateCountsOfTree(TreeNodeEmp root) {
if(root == null) {
return;
}
root.countDirectEmployees = root.children.size();
root.countTotalEmployees = getCountEmployeesOfManager(root)  1;
for (TreeNodeEmp emp : root.children) {
calculateCountsOfTree(emp);
}
}
public static Integer getCountEmployeesOfManager(TreeNodeEmp root) {
if(root == null) {
return 0;
}
int count = 1;
for (TreeNodeEmp emp : root.children) {
count += getCountEmployeesOfManager(emp);
}
return count;
}
public static TreeNodeEmp buildHierarchyTreeOfCompany(
Map<String, String> empMap, Map<String, TreeNodeEmp> empTreeNodeMap) {
Map<String, List<TreeNodeEmp>> auxMgrEmpList = new HashMap<>();
List<TreeNodeEmp> listEmps = null;
TreeNodeEmp emp = null, mgr = null, root = null;
String nameEmp, managerName;
for (Map.Entry<String, String> empMapEntry : empMap.entrySet()) {
nameEmp = empMapEntry.getKey();
managerName = empMapEntry.getValue();
if (!empTreeNodeMap.containsKey(nameEmp)) {
emp = new TreeNodeEmp(nameEmp, managerName);
// check for who was added before and have this as a manger
if(auxMgrEmpList.containsKey(nameEmp)) {
emp.children.addAll(auxMgrEmpList.get(nameEmp));
}
empTreeNodeMap.put(nameEmp, emp);
}
if (nameEmp.equals(managerName)) {
root = emp;
} else if (empTreeNodeMap.containsKey(managerName)) {
mgr = empTreeNodeMap.get(managerName);
mgr.children.add(emp);
} else if (!auxMgrEmpList.containsKey(managerName)){
listEmps = new ArrayList<>();
listEmps.add(emp);
auxMgrEmpList.put(managerName, listEmps);
} else {
listEmps = auxMgrEmpList.get(managerName);
listEmps.add(emp);
auxMgrEmpList.put(managerName, listEmps);
}
}
return root;
}
class TreeNodeEmp {
String name;
String managerName;
Integer countDirectEmployees;
Integer countTotalEmployees;
Set<TreeNodeEmp> children;
public TreeNodeEmp(String name, String managerName) {
this.name = name;
this.managerName = managerName;
children = new HashSet<>();
countDirectEmployees = 0;
countTotalEmployees = 0;
}
}
}

guilhebl
April 09, 2015 Solution in Java based on recursion:
public static int countStrings( char[] s, int n )
{
if ( n < 2 ) {
return 1;
}
int number = (s[n1]'0') + (s[n2]'0')*10;
if ( ( number >= 10 ) && ( number <= 25 ) ) {
return 1 + countStrings( s, n1 ) + countStrings( s, n2 );
}
else {
return 1 + countStrings( s, n1 );
}
}

guilhebl
April 07, 2015 @madi.sagimbekov Thanks for your input, actually it's not a seq. of 3 zeros, but 2, we test by placing a 1 at first found zero, and keep iterating left to see if we still have adjacent ones, I updated the answer to handle this scenario now it works correctly please verify.
 guilhebl March 30, 2015There are 2 possible number types you are going to deal with:
1. already sparse number
2. nonsparse number
Algorithm for solution based on the 2 scenarios:
1. Check if binary representation of number is Sparse, if it is:
 Check if bin. number contains a sequence of at least 2 zeros: (i.e "xx1100xx" or "xx11001xx") this will enable for fitting a 1 just right at index of first 0 found and setting to 0 all the right remaining bits (i.e"1010010" to "1010100"). If index of first 2 zeros is 0, just return n+1, i.e"10100" to "10101").
If it doesn't contain a seq. of 2 zeros
shift N left of 1 and set all remaining bits to 0,
return 1 << n (n = length of integer). *This is same as returning next higher power of 2.
i.e"10101", "100000")
2. If number is not sparse:
 Check for highest index of a sequence of at least 2 ones (i.e "10011010001"  index 6) then we will see if we can put a 1 at starting index after sequence and set remaining bits to zero on the right side. (i.e: "10011010001" to "10100000000")
If we find out we created a new seq. of 2 one's on that index (i.e: "10110010001" to "11000000000") then we keep flipping bits to 0 until we get to a point where previous bit is 0 and next is 1 (i.e "101xx") which is sparse, or 0.
 If we get 0 then we just need to left shift 1 by the original number's length, example: "110010010" to "1000000000" (512).  Next power of 2.
Implementation:
public class Solution {
public static void main(String args[]) {
int n = 72;
System.out.println(convertToBinaryString(n));
int nextSparse = getNextBiggerSparseNumber(n);
System.out.println(nextSparse);
System.out.println(convertToBinaryString(nextSparse));
}
public static int getNextBiggerSparseNumber(int n) {
if(isSparseBinaryNumber(n)) {
int i = getFirstIndexSeqZeros(n);
if (i != 1) {
if (i  1 == 0) {
return n + 1;
}
return incrementToNextSparseFromZeroIndex(n, i  1);
} else {
return 1 << getLengthBits(n);
}
} else {
int i = getLastIndexSeqOnes(n);
return incrementToNextSparseFromIndex(n, i);
}
}
/**
* Sets the bit at index to 1 while setting all remaining bits on the right to 0, "1001101" index 4 > "1010000"
* @param n
* @param index
* @return
*/
public static int incrementToNextSparseFromZeroIndex(int n, int index) {
int i = index  1;
int n2 = n;
n2 = setBit(n2, index, true);
while(i >= 0) {
n2 = setBit(n2, i, false);
i;
}
return n2;
}
/**
* Sets all bits of n to 0 until index, from right to left, then sets next bit index+1 to 1 and checks next bit,
* if next is 1 or if number is lower than original n, keeps setting last bit to 0 and current to 1, from right
* to left until a valid condition for sparse number is reached, otherwise if it reaches 0 returns next power of
* 2. (1 << sizeOf(n))
*
* @param n
* @param index
* @return
*/
public static int incrementToNextSparseFromIndex(int n, int index) {
int i = 0;
int n2 = n;
boolean prev = false, current = false;
while(i <= index) {
n2 = setBit(n2, i, false);
i++;
}
n2 = setBit(n2, i, true);
prev = true;
i++;
current = getBit(n2, i);
while (current && prev && n2 > 0  (n2 < n && n2 > 0)) {
n2 = setBit(n2, i  1, false);
n2 = setBit(n2, i, true);
i++;
prev = current;
current = getBit(n2, i);
}
if (n2 == 0) {
return 1 << getLengthBits(n);
}
return n2;
}
/**
* Checks index of first seq. of 2 consecutive zeros. i.e: "1001 > index = 2"
* if no seq. found return 1
*
* @param n
* @return
*/
public static int getFirstIndexSeqZeros(int n) {
// current and previous bit if set to 0 then true
boolean cur, prev = false;
int i = 0;
while(n > 0) {
if ( (n & 1) == 0) {
cur = true;
} else {
cur = false;
}
if (cur && prev) {
return i;
}
prev = cur;
i++;
n = n >> 1;
}
return 1;
}
/**
* Checks index of last seq. of 2 consecutive 1. i.e: "1011001 > index 3"
* if no seq. found return 1
*
* @param n
* @return
*/
public static int getLastIndexSeqOnes(int n) {
// current and previous bit if set to 1 then true
boolean cur, prev = false;
int i = 0;
int highest = 1;
while(n > 0) {
if ( (n & 1) == 1) {
cur = true;
} else {
cur = false;
}
if (cur && prev) {
highest = i;
}
prev = cur;
i++;
n = n >> 1;
}
return highest;
}
/**
* Checks if number is sparse: if 2 consecutive 1 are present.
* @param n
* @return
*/
public static boolean isSparseBinaryNumber(int n) {
// current and previous bit if set to 1 then true
boolean cur, prev = false;
while(n > 0) {
if ( (n & 1) == 1) {
cur = true;
} else {
cur = false;
}
if (cur && prev) {
return false;
}
prev = cur;
n = n >> 1;
}
return true;
}
public static int getLengthBits(int n) {
int count = 0;
while (n > 0) {
count++;
n = n >> 1;
}
return count;
}
public static String convertToBinaryString(int n) {
StringBuilder sb = new StringBuilder();
while(n > 0) {
if ( (n & 1) == 1) {
sb.append("1");
} else {
sb.append("0");
}
n = n >> 1;
}
return sb.reverse().toString();
}
public static boolean getBit(int n, int index) {
return ((n & (1 << index)) > 0);
}
public static int setBit(int n, int index, boolean b) {
if (b) {
return n  (1 << index);
} else {
return n & ~(1 << index);
}
}
}

guilhebl
March 30, 2015 Just use same approach as mergesort merge phase:
public class Solution {
public static void main(String[] args) {
List<Integer> list1 = new ArrayList<Integer>();
list1.add(3);
list1.add(5);
list1.add(9);
list1.add(11);
List<Integer> list2 = new ArrayList<Integer>();
list2.add(1);
list2.add(2);
list2.add(6);
list2.add(8);
list2.add(12);
List<Integer> result = mergeList(list1, list2);
for (Integer integer : result) {
System.out.print(integer + " ");
}
}
public static List<Integer> mergeList(List<Integer> list1, List<Integer> list2) {
if (list1 == null  list2 == null  list1.size() == 0  list2.size() == 0) {
return null;
}
List<Integer> result = new ArrayList<Integer>();
int n = list1.size();
int m = list2.size();
int i = 0, j = 0, elem1 = 0, elem2 = 0;
while (i < n && j < m) {
elem1 = list1.get(i);
elem2 = list2.get(j);
if (elem1 < elem2) {
result.add(elem1);
i++;
} else {
result.add(elem2);
j++;
}
}
// add remaining of i
while (i < n) {
elem1 = list1.get(i);
result.add(elem1);
i++;
}
// add remaining of j
while (j < m) {
elem2 = list2.get(j);
result.add(elem2);
j++;
}
return result;
}
}

guilhebl
March 28, 2015 These are valid points, I agree the complexity is O(n*k), and if k is ~ n then it's better to just sort the array, perhaps if the K is >= n/2  n/4 would be a limit to decide to sort or not? Notice also that for each round of quickselect it partially sorts the array and once we pick one max K we can reduce the size of the next partition to be searched by one, so each time it will target (n1), (n2), (n3), (nk) elements.
 guilhebl March 27, 2015use a hashmap to count occurrences of a number and then do quickselect to pick K biggest counts.
O(n * k) time, O(n) space
public class Solution {
public static void main(String[] args) {
int a[] = { 0, 0, 100, 3, 5, 4, 6, 2, 100, 2, 7, 7, 7, 100 };
printArray(findNumHighestKFrequent(a, 8));
}
public static int[] findNumHighestKFrequent(int[] a, int k) {
if (a == null  a.length == 0  k <= 0  k > a.length) {
return null;
}
Map<Integer, Integer> numCount = new HashMap<>();
int num;
int count;
for (int i = 0; i < a.length; i++) {
num = a[i];
if (!numCount.containsKey(num)) {
numCount.put(num, 1);
} else {
count = numCount.get(num);
count++;
numCount.put(num, count);
}
}
NumCount[] numCountArr = new NumCount[numCount.size()];
int i = 0;
for (Map.Entry<Integer, Integer> entry : numCount.entrySet()) {
numCountArr[i] = new NumCount(entry.getKey(), entry.getValue());
i++;
}
HashSet<Integer> resultSet = new HashSet<Integer>();
int[] result = new int[k];
int number = 1, counted = 0;
for (int j = numCountArr.length  1; j >= 0 && counted < k; j) {
number = quickSelect(numCountArr, j, 0, j).num;
if (!resultSet.contains(number)) {
resultSet.add(number);
result[counted] = number;
counted++;
}
}
return result;
}
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;
}
}
private static void printArray(int[] ar) {
for (int n : ar) {
System.out.print(n + " ");
}
System.out.println("");
}
}
class NumCount implements Comparable<NumCount> {
int num;
int count;
public NumCount(int num, int count) {
this.num = num;
this.count = count;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
NumCount other = (NumCount) obj;
if (num != other.num)
return false;
return true;
}
@Override
public int compareTo(NumCount o) {
if (this.count < o.count) {
return 1;
} else if (this.count > o.count) {
return 1;
}
return 0;
}
}

guilhebl
March 25, 2015 The idea is to read chunks of 256 bytes from the file using ReadFromDisk():
create 2 buffers: one that will hold the final file result, and other that will read temp results from call to ReadFromDisk
1. Calculate numbers of chunks necessary to read entire file: N/256 where N is the size of file in bytes. Let's call this value S.
2. for i to S call ReadFromDisk and store result in temp buffer[] (256 bytes)
3. Read contents and transfer to bigger buffer until you hit End of File.
 sort the timeslots from in ascending order
 create an empty array int[24] representing 24 hours of the day
 iterate over timeslots filling the array for that hour with [1] if only 1 timeslot has that hour inside it's interval otherwise fill with N if N timeslots intersects on that hour
at the end pick MAX value of array.
 max value will be your min. number of rooms.
Using Java 8 solution:
1. keep a field in Point class called distanceFromOrigin, which will be calculated when the point is created. The formula is based on Euclidian distance formula for distance between points in a 2d Map.
2. Create a Comparator class that compares points based on their distance from origin.
3. Create a list that will store the points of the sample.
4. Use Java 8 Stream api on List to sort by PointDistanceToOrigin Comparator and limit max results as K and print the results to System.out
public class Solution {
public static void main(String args[]) {
Point p1 = new Point(1, 3, findDistanceOfPoints(1, 3, 0, 0));
Point p2 = new Point(3, 4, findDistanceOfPoints(3, 4, 0, 0));
Point p3 = new Point(1, 5, findDistanceOfPoints(1, 5, 0, 0));
Point p4 = new Point(2, 2, findDistanceOfPoints(2, 2, 0, 0));
Point p5 = new Point(2, 3, findDistanceOfPoints(2, 3, 0, 0));
List<Point> ptList = new ArrayList<Point>();
ptList.add(p1);
ptList.add(p2);
ptList.add(p3);
ptList.add(p4);
ptList.add(p5);
int k = 3;
printClosestPointsToOrigin(ptList, k);
}
public static void printClosestPointsToOrigin(List<Point> ptList, int k) {
// sort by distance from origin and print
ptList.stream().sorted(PointDistanceFromOriginComparator.INSTANCE)
.limit(k).forEach(System.out::println);
}
public static int findDistanceOfPoints(int x1, int x2, int y1, int y2) {
Double dist = Math.sqrt(Math.pow(x1  x2, 2) + Math.pow(y1  y2, 2));
return dist.intValue();
}
}
class Point {
Integer x, y;
Integer distanceFromOrigin;
public Point(Integer x, Integer y, Integer distO) {
this.x = x;
this.y = y;
this.distanceFromOrigin = distO;
}
@Override
public String toString() {
return "Point [x=" + x + ", y=" + y + ", distanceFromOrigin="
+ distanceFromOrigin + "]";
}
}
class PointDistanceFromOriginComparator implements Comparator<Point> {
public static final PointDistanceFromOriginComparator INSTANCE = new PointDistanceFromOriginComparator();
public int compare(Point p1, Point p2) {
if (p1.distanceFromOrigin < p2.distanceFromOrigin) {
return 1;
} else if (p1.distanceFromOrigin > p2.distanceFromOrigin) {
return 1;
}
return 0;
}
}

guilhebl
March 23, 2015 public class Solution {
public static void main(String[] args) {
String t = "water";
String o = "zealot";
System.out.println(orderStringByRef(t, o));
}
public static String orderStringByRef(String t, String o) {
StringBuilder sb = new StringBuilder();
char c;
int indexOfChar = 1;
List<CharSeq> list = new ArrayList<>();
for (int i = 0; i < t.length(); i++) {
c = t.charAt(i);
indexOfChar = o.indexOf(c);
if (indexOfChar >= 0) {
CharSeq cs = new CharSeq();
cs.c = c;
cs.i = indexOfChar;
list.add(cs);
} else {
sb.append(c);
}
}
list.sort(new CharSeqComparator());
for (CharSeq cs : list) {
sb.append(cs.c);
}
return sb.toString();
}
}
class CharSeq {
char c;
int i;
}
class CharSeqComparator implements Comparator<CharSeq> {
@Override
public int compare(CharSeq a, CharSeq b) {
if (a.i < b.i) {
return 1;
} else if (a.i == b.i) {
return 0;
} else if (a.i > b.i) {
return 1;
}
return 1;
}
}

guilhebl
March 22, 2015 the problem is to print all numbers i < N where i can be expressed by the sum of 2 different cubes in 2 different ways, The right way would be to iterate for all the i < N and check for each number i if it has at least 2 different distinct cubic pairs which sum up to N.
The algorithm below follows this aproach:
package tempProject2;
public class Solution {
public static void main(String[] args) {
System.out.println(printAllNumbersSmallerThanNCubeSum(1730, 2));
}
public static final int printAllNumbersSmallerThanNCubeSum(int n, int k) {
if (n <= 1  k <= 0) {
return 0;
}
Double cb = new Double(n);
cb = Math.cbrt(cb);
int cbroot = cb.intValue();
int count = 0;
int[] cubes = new int[cbroot];
for (int i = 0; i < cubes.length; i++) {
cubes[i] = (i + 1) * (i + 1) * (i + 1);
}
int lowerBound = cubes.length > 1 ? 1 + cubes[1] : 1;
for (int i = 1; i < n; i++) {
if (i >= lowerBound) {
if (countPossiblePairSums(i, cubes) >= k) {
count++;
}
}
}
return count;
}
public static int countPossiblePairSums(int sum, int[] cubes) {
int count = 0;
int i = 0;
int j = cubes.length  1;
while (i < j) {
if (cubes[i] + cubes[j] == sum) {
count++;
i++;
j;
} else if (cubes[i] + cubes[j] > sum) {
j;
} else if (cubes[i] + cubes[j] < sum) {
i++;
}
}
return count;
}
}

guilhebl
March 20, 2015 Great solution! But I guess you still have an extra step, as I believe your solution is not accomplishing fully what the question asks for, the problem is to print all numbers i < N where i can be expressed by the sum of 2 different cubes in 2 different ways, yours is only checking for pairs that sum up to N. The right way would be to iterate for all the i < N and check for each number i if it has at least 2 different distinct pairs which sum up to N. Please check my solution
 guilhebl March 20, 2015First of all in a real world scenario would have to analyze historical usage data:
 are the elevators requested more frequently during certain times ?
 are the elevators requested more frequently for certain floors ?
 what's the average weight of load for each elevator on peak times ?
Let's say the peak times are around 07:30AM  09:30AM , 11:30 AM  1:30 PM and 4:30 PM  6:30PM (lunch time and rush hours).
Now let's analyze the number of people on each floor of the building if this data is available, we can distribute weights to each section of the building, let's say bottom half and upper half.
Now let's think how each elevator should operate, usually it works under a FIFO model, sweeping people through requested floors up, and then going down the way, while there's still space available the elevator would be attending new requests, otherwise if fully occupied(weight max or near max) just ignore (no preemptive interruptions allowed).
Usual default start location for elevators are ground floor, but given historical data if we realize that this would benefit more people from the lower levels on certain times like lunch time and leaving time, then we can program the elevators according to the following rules:
 Default start location: for all elevators always go back to ground floor and stay there waiting for the next request.
 Default start location for peak times: only during lunch and leave peak times (11:30AM  1:30 PM and 4:30PM  6:30 PM), half of the elevators available (n/2) should start from the top floor, sweeping it's way down collecting passengers till full. This would prevent passengers from the upper half to wait more than usual as compared to the ones for the bottom half.
Again this will all depend on historical data modelling and planning, this is just a given example scenario.
2 different implementations based on the ideas of the author and the idea of swapping adjacent elements:
/**
* based on sorting and iterative approach using aux. array:
*
* O(n*log(n)) time, O(n) space
*
* @param a
* @return
*/
public static int[] getOrderedArrayDecIncSequence(int[] a) {
if (a == null  a.length == 1) {
return a;
}
Arrays.sort(a);
int[] b = new int[a.length];
int k = 0;
for (int i = 0, j = a.length1; i < a.length && j >= i; i++, j) {
b[k] = a[i];
if (j > i) {
b[k + 1] = a[j];
}
k+=2;
}
return b;
}
/**
* Based on swapping adjacent positions: O(n) time, O(1) space
* @param a
* @return
*/
public static int[] getOrderedArrayDecIncSequenceSwapping(int[] a) {
if (a == null  a.length == 1) {
return a;
}
boolean odd = true;
int temp;
for (int i = 1; i < a.length; i++) {
if (odd) {
if (a[i  1] > a[i]) {
temp = a[i];
a[i] = a[i  1];
a[i  1] = temp;
}
} else {
if (a[i  1] < a[i]) {
temp = a[i];
a[i] = a[i  1];
a[i  1] = temp;
}
}
odd = !odd;
}
return a;
}

guilhebl
March 18, 2015 1. for 1st scenario :
For binary tree:
public static boolean isTreeUnivalRoot(Node root) {
if (root == null) {
return true;
}
return isTreeUnival(root.left, root.val) && isTreeUnival(root.right, root.val);
}
public static boolean isTreeUnival(Node n, int val) {
if (n == null) {
return true;
}
if (n.val != val) {
return false;
}
return isTreeUnival(n.left, val) && isTreeUnival(n.right, val);
}
In case for an Nary tree
public static boolean isTreeUnivalRoot(Node root) {
if (root == null) {
return true;
}
boolean isUnival = true;
if (root.children != null && !root.children.isEmpty()) {
for (Node c : root.children) {
isUnival = isTreeUnival(c, root.val);
}
}
return isUnival;
}
public static boolean isTreeUnival(Node n, int val) {
if (n == null) {
return true;
}
if (n.val != val) {
return false;
}
boolean unival = true;
if (n.children != null && !n.children.isEmpty()) {
for (Node c : n.children) {
unival = isTreeUnival(c, val);
}
}
return unival;
}
2. for 2nd on a binary tree count the number of unival subtrees:
There will be at least N subtrees of size 1 unival trees.
Then again inside a bigger unival subtree there will be several smaller unival subtrees, each from a possible combination of the nodes of the bigger tree.
public static String findLowestPossibleNumberFromNumericString(String s, int n) {
if (n <= 0  s == null  s.length() == 0  n > s.length()) {
return null;
}
if (s.length() == n) {
return s;
}
int[] indexKeep = new int[s.length()];
int[] numbers = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
numbers[i] = Integer.parseInt(s.substring(i,i+1));
indexKeep[i] = 0;
}
int localMin = Integer.MAX_VALUE;
int localMinIndex = 0;
int indexStart = 0;
int totalCharsToKeep = s.length()  n;
int indexEnd = s.length()  totalCharsToKeep;
while (totalCharsToKeep > 0 && indexStart < s.length()) {
for (int i = indexStart; i < indexEnd; i++) {
if (localMin > numbers[i]) {
localMin = numbers[i];
localMinIndex = i;
}
}
indexKeep[localMinIndex] = 1;
totalCharsToKeep;
indexStart = localMinIndex + 1;
indexEnd = s.length()  totalCharsToKeep + 1;
localMin = Integer.MAX_VALUE;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indexKeep.length; i++) {
if (indexKeep[i] == 1) {
sb.append(numbers[i]);
}
}
return sb.toString();
}

guilhebl
March 16, 2015 The problem can be solved using the following approach:
1. pick a person as a pivot, let's say the first friend let's call him A. If there are common timeslots, then at least 1 timeslot of A is in common with all others.
2. Iterate over A's timeslots and compare them with all others, if A's current timeslot has no match with any of the next person's timeslots, flag it as not a candidate. interrupt iteration and pick next slot of A.
3. Timeslots will either match or be inside or intersect another person timeslot calculate the intersection of both timeslots.
4. If A's current timeslot matches (or intersects) all others include it as part of the final result. Keep this in a Hashset to avoid duplicates. Do this until there's no more timeslots for A or if already found K target timeslots.
*Obs: using time as int range from 0  23, so 1PM will be 13, while 1AM will be 1. This is to facilitate timeslot calculation.
Solution: Time: O(m*(log(n))  where m is the number of slots of Person chosen as pivot, memory: O(1).
Implementation in Java:
public class Solution {
public static void main(String[] args) {
List<List<TimeSlot>> timeslots = new ArrayList<List<TimeSlot>>();
// friend 1
List<TimeSlot> timeSlotList = new ArrayList<TimeSlot>();
timeSlotList.add(new TimeSlot(6, 9));
timeSlotList.add(new TimeSlot(10, 14));
timeSlotList.add(new TimeSlot(16, 17));
timeSlotList.add(new TimeSlot(19, 20));
timeSlotList.add(new TimeSlot(21, 22));
timeslots.add(timeSlotList);
// friend 2
timeSlotList = new ArrayList<TimeSlot>();
timeSlotList.add(new TimeSlot(7, 8));
timeSlotList.add(new TimeSlot(13, 14));
timeSlotList.add(new TimeSlot(17, 18));
timeSlotList.add(new TimeSlot(20, 23));
timeslots.add(timeSlotList);
// friend 3
timeSlotList = new ArrayList<TimeSlot>();
timeSlotList.add(new TimeSlot(5, 8));
timeSlotList.add(new TimeSlot(13, 15));
timeSlotList.add(new TimeSlot(19, 20));
timeSlotList.add(new TimeSlot(21, 23));
timeslots.add(timeSlotList);
// friend 4
timeSlotList = new ArrayList<TimeSlot>();
timeSlotList.add(new TimeSlot(6, 8));
timeSlotList.add(new TimeSlot(13, 16));
timeSlotList.add(new TimeSlot(19, 20));
timeSlotList.add(new TimeSlot(21, 22));
timeslots.add(timeSlotList);
printFirstNCommonTimeslots(timeslots, 3);
}
public static void printFirstNCommonTimeslots(List<List<TimeSlot>> timeslots, int n) {
if (n <= 0  timeslots == null  timeslots.isEmpty()) {
return;
}
Set<TimeSlot> commonTimeSlots = new HashSet<>();
TimeSlot candidate = null;
int i = 0;
int candidatesFound = 0;
int listsAnalyzed = 0;
boolean stillCandidate = false;
boolean candidateFound = false;
// get timeslots from first person and check if it matches with all others
List<TimeSlot> firstPersonTimeslots = timeslots.get(0);
for (TimeSlot timeSlot : firstPersonTimeslots) {
candidate = timeSlot;
stillCandidate = true;
i = 1;
while(i < timeslots.size() && stillCandidate) {
List<TimeSlot> listT = timeslots.get(i);
for (int j = 0; j < listT.size() && !candidateFound; j++) {
TimeSlot timeSlot2 = listT.get(j);
int initTimeA = candidate.init;
int endTimeA = candidate.end;
int initTimeB = timeSlot2.init;
int endTimeB = timeSlot2.end;
if (initTimeA == initTimeB  endTimeB == endTimeA 
(initTimeA < endTimeB && initTimeA > initTimeB) 
(initTimeB < endTimeA && initTimeB > initTimeA)) {
while (initTimeA != initTimeB) {
if (initTimeA < initTimeB) {
initTimeA++;
} else if (initTimeA > initTimeB) {
initTimeB++;
}
}
while (endTimeA != endTimeB) {
if (endTimeA < endTimeB) {
endTimeB;
} else if (endTimeA > endTimeB) {
endTimeA;
}
}
candidate = new TimeSlot(initTimeA, endTimeA);
candidateFound = true;
}
}
if (candidateFound) {
listsAnalyzed++;
candidateFound = false;
} else {
stillCandidate = false;
listsAnalyzed = 0;
}
i++;
}
if (listsAnalyzed == timeslots.size()  1) {
commonTimeSlots.add(candidate);
candidatesFound++;
listsAnalyzed = 0;
if (candidatesFound == n) {
break;
}
}
}
if (candidatesFound > 0) {
Iterator<TimeSlot> timeSlots = commonTimeSlots.iterator();
while(timeSlots.hasNext()) {
System.out.println(timeSlots.next());
}
}
}
}
class TimeSlot {
int init;
int end;
public TimeSlot(int init, int end) {
super();
this.init = init;
this.end = end;
}
@Override
public String toString() {
return init + " " + end;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
TimeSlot other = (TimeSlot) obj;
if (end != other.end)
return false;
if (init != other.init)
return false;
return true;
}
}

guilhebl
March 16, 2015 1. Keep a int distanceFromNode for all Nodes indicating it's distance from Root.
2. Keep track of the of longest and 2nd longest. 1st and 2nd Longest must be in 2 different branches starting from root. One way to check this is keeping track of the 1st and 2nd longest paths using 2 Lists or HashSets.
3. Sum of Longest and second Longest will give you the current tree diameter.
4. While adding nodes to the tree, calculate it's distance from root getting Parent distance + 1
5. If node added has distance > longest or distance > 2nd longest  Node added is 1st or 2nd new longest, update diameter. Update 1st and 2nd Max paths node sets.
Sliding window solution in java below:
public static String findLongestSubstringMUniqueChars(String s, int maxUniques) {
if (s == null  s.length() == 0  s.length() < maxUniques) {
return null;
}
if (s.length() == maxUniques) {
return s;
}
int currentCharCount = 0;
int currentUniqueCharCount = 0;
int longestCharCount = 0;
int longestIndexInit = 0;
int longestIndexEnd = 0;
Set<Character> currentSet = new HashSet<>();
Set<Character> longestSet = new HashSet<>();
char[] chars = s.toCharArray();
int i = 0;
while (i < chars.length) {
Character c = chars[i];
if (currentUniqueCharCount < maxUniques) {
if (!currentSet.contains(c)) {
currentSet.add(c);
currentUniqueCharCount++;
}
currentCharCount++;
} else if (currentUniqueCharCount == maxUniques) {
if (!currentSet.contains(c)) {
if (longestCharCount < currentCharCount) {
longestCharCount = currentCharCount;
longestIndexInit = i  currentCharCount;
longestIndexEnd = i;
longestSet = currentSet;
}
currentSet = new HashSet<>();
i = i  currentCharCount;
currentCharCount = 0;
currentUniqueCharCount = 0;
} else {
currentCharCount++;
}
}
i++;
}
if (longestCharCount < currentCharCount) {
longestCharCount = currentCharCount;
longestIndexInit = i  currentCharCount;
longestIndexEnd = s.length()1;
longestSet = currentSet;
}
return s.substring(longestIndexInit, longestIndexEnd);
}

guilhebl
March 13, 2015 Your solution looks good, only thing I would change is switch the squared = pow(i,2); to outside the for j loop, to avoid recalculating this value if not needed:
for (int i=2; i<=max; i++){
squared = pow(i,2);
for (int j=0; j<=n; j++){
if (squared <= j)
table[j] = min(table[j], table[jsquared]+1);
}
}
Since you don't know the exact location of the apple, then only option is to 'sweep' the whole grid until you eventually find it, trying to minimize the number of revisited cells.
1. Find 'boundaries' for Grid:
Try to build a "rectangle" on bottomright area and sweep it
1a. keep going down while you find a boundary.
after reaching end mark length from your initial spot, new limit D.
1b. keep going right while you find a boundary.
after reaching end mark length from your D as new spot R.
1c. Now you have a rectangle base on your known boundaries from your original spot.
1d. sweep inside of rectangle getting your way back to your initial position.
After sweeping bottomright do the same process to sweep upperright, then upperleft and finally bottomleft.
on any of these if you find apple stop.
what if you have a case like N = 12
A[] = {1,2, 4, 4,4,7,7,8,9,9,10,10} checking only the elements of n/4  n/2  n/4*3 will not suffice, besides that it is necessary to expand the window starting from one of these positions n/4, n/2 3*n/4 until you fit a window of size n/4... Since you don't know exactly if that element is the popular one or not until you counted a n/4 window.
private static boolean isBalanced(String s1) {
if (s1 == null  s1.length() == 0) {
return false;
}
char[] chars = s1.toCharArray();
Stack<Character> stack1 = new Stack<>(); // { e {
Stack<Character> stack2 = new Stack<>(); // [ e ]
Stack<Character> stack3 = new Stack<>(); // ( e )
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '{') {
if (!stack2.isEmpty()  !stack3.isEmpty()) {
return false;
}
stack1.push(chars[i]);
} else if (chars[i] == '[') {
if (!stack3.isEmpty()) {
return false;
}
stack2.push(chars[i]);
} else if (chars[i] == '(') {
stack3.push(chars[i]);
} else if (chars[i] == '}') {
if (!stack2.isEmpty()  !stack3.isEmpty()) {
return false;
}
if (stack1.isEmpty()) {
return false;
}
stack1.pop();
} else if (chars[i] == ']') {
if (!stack3.isEmpty()) {
return false;
}
if (stack2.isEmpty()) {
return false;
}
stack2.pop();
} else if (chars[i] == ')') {
if (stack3.isEmpty()) {
return false;
}
stack3.pop();
}
}
return true;
}

guilhebl
March 11, 2015 Solution using:
1. sorting  tallest candles will be last
2. decrease sequentially the candles according to each days number.
approach, time: O(N*log(K)) where K is the number of days per cycle, space O(1):
public static int daysFromCandles(int[] a, int daysMax) {
if(a == null  a.length == 0) {
// Error
return 1;
}
int limit = daysMax;
int candles = 0;
int days = 0;
Arrays.sort(a);
int currentIndex = a.length1;
boolean stillCandles = true;
while (stillCandles) {
// day cycle
for (int i = 0; i < limit && stillCandles; i++) {
candles = i + 1;
// starting lit from highest
int j = currentIndex;
for (;candles>0 && j>0 && stillCandles; j,candles) {
if (a[j] > 0) {
a[j];
}
if (j == 0) {
if (a[j] > 0) {
currentIndex;
} else if (a[j] == 0) {
stillCandles = false;
}
}
}
currentIndex = j;
if (currentIndex == 0) {
int top = a.length1;
while (a[top] == 0 && top > 0) {
top;
}
if (top == 0) {
stillCandles = false;
}
currentIndex = top;
}
days++;
}
}
return days;
}

guilhebl
March 11, 2015 Here is my solution, simple and concise O(n) time, O(1) space, the basic idea is to iterate the array comparing for difference of 1 values and treating the special case diff 2, in a sliding window fashion:
public static int[] findLongestSubsetDiff1(int[] a){
int i = 0, j = 0, diff = 0;
int longest = 1, minLongestIndex = 0, min = a[0], max = a[0], minIndex = 0, maxIndex = 0, newLongest = 0;
for(i=1; i < a.length; i++) {
max = Math.max(a[i], max);
min = Math.min(min, a[i]);
diff = Math.abs(max  min);
if (diff == 1  diff == 0) {
maxIndex = i;
newLongest = (maxIndex  minIndex) + 1;
if (longest < newLongest) {
longest = newLongest;
minLongestIndex = minIndex;
}
} else if (diff == 2) {
minIndex = minLongestIndex + 1;
min = a[minIndex];
maxIndex = i;
max = a[i];
diff = Math.abs(max  min);
while (diff == 2 && minIndex < maxIndex) {
minIndex++;
min = a[minIndex];
diff = Math.abs(a[i]  min);
}
max = Math.max(max, min);
}
else {
min = max = a[i];
minIndex = maxIndex = i;
}
}
int[] r = new int[longest];
for(j=0, i = minLongestIndex; i < a.length && j < longest; i++, j++) {
r[j] = a[i];
}
return r;
}

guilhebl
March 11, 2015 1. Create a HashMap<Integer, List<String>> that will hold every String from your array of strings using as Key the sum of each char Integer value.
2. Iterate over your list and insert each string using as key a transformation function that will calculate the sum of every char on that string, thus strings with same chars will have exact same sum. Append the Strings with same sum into the List of Strings for that particular sum.
3. for your String as input, just get it's sum value using the same transformation function, once you have the sum use it as key to print the resulting List<String> of the HashMap, that will print all Strings with same chars.
 O(n * n) to build list, O(1) to print String list
 O(n) space
RepI am randy, 29 year old and I am doing a job. I am doing a job as a plant ...
Open Chat in New Window
Yes it's possible to store the counts in each node like having vars such as:
 guilhebl April 13, 2015directEmployeesCount 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.