CareerCup

1. 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))

the largest group can be at max N/2 + 1

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;
	}

}	

}

I updated the solution to use an aux. HashSet which stores values already calculated, so it won't keep repeated values.

Solution in Java based on recursion:

public static int countStrings( char[] s, int n )
{
	if ( n < 2 ) 	{
		return 1;
	}
	
	int number = (s[n-1]-'0') + (s[n-2]-'0')*10;
	if ( ( number >= 10 ) && ( number <= 25 ) )	{
		return 1 + countStrings( s, n-1 ) + countStrings( s, n-2 );
	}
	else 	{
		return 1 + countStrings( s, n-1 );
	}
}

@koosha.nejad I guess your solution is missing a 1 + before the recurrence please see my solution in java.

Tested with a very basic sample: "123" your solution returns 3, but shouldn't it be: 5? - 1 = B, 2 = C, 3 = D, 12 = M and 23 = X ?

@ninhnnsoc updated the answer with comments on each important method and wrote a better explanation of each scenario.

please check my answer

@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.

There are 2 possible number types you are going to deal with:
1. already sparse number
2. non-sparse 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);
	}
}

}

@Ernesto I added the explanation of my code above, it works, please verify and remove down-vote if you don't find any other issues, thanks.

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;
	}	
	
}

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 (n-1), (n-2), (n-3), (n-k) elements.

@g233007 your method CheckOccurrence fails for finding occurrences of 3 in 33, it returns 8 while count should be 7:
3,13,23,30,31,32,33

Thanks for pointing it out, I've updated my solution using quickSelect instead of sorting the whole array.

use 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;
	}
}

how do you know when to discard a sequence when another better sequence might come upfront? for example: for 3 unique chars: aaabbccppxxzzaaaabkkkkzz

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.

The idea is to keep using candles until all of them reach size 1, then you're left with the only option of extinguishing one by one.

Yes, but how do you know which node goes on the left and right of a given parent? How about single long branches on the left or right in unbalanced trees ? Can you describe how your algorithm would tackle those scenarios?

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;
	}
}

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;
	}
}

this is O(n!) right ? it might work for smaller values of N but something above 100 will take a long time...

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;
	}

}

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

First 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.

I implemented a version of your described algorithm and it seems to work

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.length-1; 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;
}

I guess you're right, updated accordingly thanks for pointing it out.

How about the subtrees inside the unival subtrees ? Like for example the trees below derived from your example:

/**
		 *              
		 *         2         3
		 *        /            \
		 *       2             3
		 *                      / \
		 *                     3  3
		 */

These are also unival trees as well.

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 N-ary 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();
}

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;
	}
	
}

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.

@Skor correct me if I'm wrong, but instead of height of the tree, it's the sum of the height of the 2 longest subtrees of root, if there are 2 or more children of root, otherwise it's the tree height.

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);
}

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[j-squared]+1);
}
}

I was mistaking one thing here, your results are right I'm getting the same now

tested with 13 and it gives 1 do you get the same result ?

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 bottom-right 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 bottom-right do the same process to sweep upper-right, then upper-left and finally bottom-left.

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;
}

I believe this question is related to the Minimum Spanning Tree using Prim's algorithm for maze creation

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.length-1; 	
	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.length-1; 
				while (a[top] == 0 && top > 0) {
					top--;	
				}					 
				if (top == 0) {
					stillCandles = false;
				}
				currentIndex = top;
			}
							
			days++;
		}			
	}
	
	return days;		
}

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;				
	}

You are right, definitely missed that detail, your solution would cover that issue.

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

public static int distance(List<String> words, String word1, String word2) {
		if (words == null || words.isEmpty()) {
			return -1;
		}

		String[] strArr = (String[]) words.toArray();
    	List<Integer> indexesWord1 = new ArrayList<Integer>();
    	List<Integer> indexesWord2 = new ArrayList<Integer>();		

		// build all indexes of word 1 and 2.		
		for (int j = 0; j < strArr.length; j++) {
			if (strArr[j].equals(word1)) {
				indexesWord1.add(j);
			} else if (strArr[j].equals(word2)) {
				indexesWord2.add(j);
			}
		}				
		
		if(indexesWord1.isEmpty() || indexesWord2.isEmpty()) {
			return -1;
		}
		
		// check from indexes the min distance
		int minFoundSoFar = Integer.MAX_VALUE;
		for (Integer i : indexesWord1) {
			for (Integer j : indexesWord2) {
				if (i < j) {
					int dist = (j - i);
					if (dist < minFoundSoFar) {
						minFoundSoFar = dist;
					}
				} else if (i > j) {
					int dist = (i - j);
					if (dist < minFoundSoFar) {
						minFoundSoFar = dist;
					}					
				}		
			}			
		}
				
		if (minFoundSoFar != Integer.MAX_VALUE) {
			return minFoundSoFar;
		}
			
		return -1;
	}