CareerCup

/**
Brute-force solution: Maintain disjoint sets. Compute Euclidean distance between each pair of points and update the parent of each point’s disjoint set (using union by rank and path compression). Time complexity: O(N^2). Space: O(N)
**/

/**Optimal Solution: Use closest points algorithm to solve this problem in O(NlogN) time and O(N) space**/

class Point {
	int x;
	int y;
}

float euclidDistance(Point a, Point b) {}

int find(int[] ds, int idx) {
	Stack<Integer> stack = new Stack<Integer>();
	while (ds[idx] != idx) {
			stack.push(idx);
			idx = ds[idx];
	}
	while (!stack.isEmpty()) {
		int top = stack.pop():
		ds[top] = idx;
	}
	return idx;
}

int pointGroups(Point[] pts, float k) {
	int[] sets = new int[pts.length]//disjoint sets
	for (int i = 0; i < sets.length; i++) {
		sets[i] = i;
	}

	// Sort points by ascending x coordinate
	pts.sort(new Comparator() {
		public int compare(Point first, Point sec) {
			return first.x - sec.x
		}

	}
	
	pointsGroupHelp(pts,0,pts.length - 1, k, ds);
	//Apply path compression and count the total number of groups
	int count = 0;
	boolean[] seenGroup = new boolean[ds.length];
	for (int i = 0; i < ds.length; i++) {
		int p = find(ds,i);
		if (!seenGroup[p]) {
			count++;
			seenGroup[p] = true;
		}
	}
	return count;	
}

void bruteForce(Point[] pts, int start, int end, int[] ds, float k) {
	for (int i = start; i <= end; i++) {

		for (int j = i + 1; j <= end, j++) {
				float d = euclidDistance(pts[i],pts[j]);
				if (d <= k) {

						int minParent = Math.min(ds[i],ds[j]);
						int maxParent = Math.max(ds[i],ds[j]);
						ds[maxParent] = minParent;
				}
		}
	}
}

void pointsGroupHelp(Point[] pts,int start,,int end, float k, int[] ds) {
	if ((end - start + 1) <= 3) {
			bruteForce(pts,start,end,ds,k);
			return;
	}

	int mid = start + (end - start) / 2;
	
	int midX = pts[mid].x; //mid line

	pointsGroupHelp(pts,start,mid,k,ds); // group together all points <= k distance that lie to the left of mid line
	pointsGroupHelp(pts,mid + 1, end, k, ds); // group together all points <= k distance that lie to the right of mid line

	// Find subarray of points that are within <=k units away from midline and group pairs whose distance is <= k
	int stripStart = -1;
	int stripEnd = stripStart;
	for (int i = start; i <= end; i++) {
		if (Math.abs(pts[i].x - midX) <= k) {
			stripStart = stripStart == -1 ? i : stripStart;
			stripEnd = i;
		}
	}
	bruteForce(pts,stripStart,stripEnd,k,ds);
}

O(N^3) solution

Boolean isPeriodic(String str) {
	if (isSameCharacters(str)) {
		return true;
	}
	
	int maxLength =. str.length() / 2 
	while (maxLength >= 1) {
		if (isMatch(maxLength, str.length() - maxLength, str.length(),str)) {
			boolean middleSegment = isMatch(maxLength, maxLength, str.length() - maxLength,str)
			if (middleSegment) {
				return true;
			}
		}
		maxLength -= 1;
	}
	return false;
}


Boolean isMatch( int patternEnd, int start, int end, String str) {
	if (start > end) {
		return true;
	}
	int lenRegion = end - start;
	if (patternEnd % lenRegion != 0) {
		return false;
	}

	for (int i = start; i+ patternEnd < end; i += patternEnd) {
		for (int j = 0; j < patternEnd; j++) {
			if (str.charAt(j) != str.charAt(I + j)) {
				return false;

			}
		}
	}
}

//BFS time complexity: O(V + E), space: O(V)

class Solution {
  public static void main(String[] args) {
    
    List<List<Integer>> adj = new ArrayList<List<Integer>>(9);
    
    for (int i = 0; i < 9; i++) {
      adj.add(new ArrayList<Integer>());
    }
    

    adj.get(4).add(5);
    
    adj.get(5).add(6);
    adj.get(5).add(7);
    
    adj.get(7).add(6);
    adj.get(7).add(8);
    

    
    System.out.println(longestCycle(adj,4));
}


public static int longestCycle(List<List<Integer>> adj, int node) {

  Deque<Integer> q = new LinkedList<Integer>();
  
  boolean[] visited = new boolean[adj.size()];
  int[] levels = new int[adj.size()];
  levels[node] = 1;
  
  q.addLast(node);
  visited[node] = true;
  
  while (!q.isEmpty()) {
    int top = q.pollFirst();
    
    for (Integer x: adj.get(top)) {
      if (visited[x]) {
         if (x == node) {
          return levels[top];
         }
      } else {
      
        levels[x] = levels[top] + 1;
        q.addLast(x);
      }
    }
  
  }
  
  return -1;
}


}

What if there's more than one node with the minimum degree, say in the same row or column? Your code seems to just take the first node with the minimum degree.

Time Complexity: O(C( n *m, Math.max(m,n)))
Space: O(n + m)

Approach: Iterate through each row and select an orb that will be chosen to stay in the final board. When selecting an orb in the row, make sure it’s not in the same column as another orb that was previously selected

int minOrbs(char[][] m) {
	boolean[] cols = new boolean[m[0].length];
	return minOrbsHelp(m, cols, 0);
}


int minOrbsHelp(char[][] m, boolean[] visited, int idx) {
	if (idx == m.length) {
		return 0;
	}

	boolean allChosen = true;
	int result = Integer.MAX_VALUE;
	for (int c = 0; c < m[0].length; c++ ) {
		if (m[r][c] == ‘O’ && !visited[c]) {
			allChosen = false;
			visited[c] = true;
			result = Math.min(result, 1 + minOrbsHelp(m, visited, idx + 1);
			visited[c] = false;

		}

	}

	if (allChosen) {
		return minOrbsHelp(m, visited, idx + 1);

	}

	return result;

}

printSums(int[] coins) {
	Arrays.sort(coins)
	int minCoin = coins[0];

	boolean[] sums = new boolean[1000 - coins[0] + 1];

	for (int i = 0; i < coins.length; i++) {
		fillSums(sums, coins[i], minCoin);
	}

	for (int i = 0; i < sums.length; i++) {
		if (sums[i]) {
			
			system.out.println(i + minCoin);
		}
	}
}

fillSums(boolean[] arr, int coin, int minCoin) {
	arr[coin - minCoin] = true;

	for (int i = coin + 1; i - minCoin < arr.length; i++ ) {
		if ( (i- coin - minCoin) >= 0 && arr[i - coin - minCoin] ) {
			arr[i - minCoin] = true 
		}

	}
}

int maxWater(int[] arr)
{
	if(arr == null || arr.length < 3) {
		return -1;
	}

	int leftKeep = 0;
	int maxWater = 0;
	int leftCol = 0;
	for (int i = 1; i < arr.length - 1; i++) {
		// left + curr removed
		
		int maxRmvCurr = Math.max(Math.min(leftCol, arr[i + 1]) * 2, leftKeep + Math.min(arr[i - 1], arr[i + 1]));
		maxWater = Math.max (maxRmvCurr, maxWater);
		leftKeep = Math.max(leftKeep,Math.min(arr[i],leftCol));
		leftCol = arr[ i - 1];
	}

	return maxWater;

}

/** I am not sure why the start and end points or width and height are needed. I think all we need is the list of points we need to encounter.  If the points are arranged so that every point is either below and or to the right of another point, then we're guaranteed that there's at least one path. Sort the points by ascending x-coordinate. If two points p1 and p2  have the same x-coordinate, the point with the larger y-coordinate should occur before the point with the lower y-coordinate. The total number of ways we can get from one point p1 to another p2 can be computed using the equation for permutation of objects with duplicate objects ( n! / r1! * r2!) where n is the total number of objects (in this case the total number of steps) and each r is the number of duplicate steps (in this case the number of vertical steps-r1! and number of horizontal steps r2!). Note n = r1 + r2. **/

public class Point implements Comparable<Point> {
	int xcoord;
	int ycoord;

	public Point(int x, int y) {
		xcoord = x;
		ycoord = y;
}

public int compare(Point p) {
	return xcoord == p.xcoord ? -1 * (ycoord - p.ycoord) : xcoord - p.xcoord
}
}


int[] factorials(int max) {
	int[] arr = new int[max + 1];
	arr[0] = 1;
	arr[1] = 1;
	for(int i = 2; i <= max; i++) {
	arr[i] = i * arr[i - 1];
}
}

public int countWays(Point[] pts) {
	if(pts == null || pts.length == 0) {
	return 0;
}
	Arrays.sort(pts);
	for(int i = 1; i < pts.length; i++) {
		if(pts[i].ycoord - pts[i - 1].ycoord >= 0) {
			return 0;
}
}

	int maxSteps = 0;
	for(int i = 1; i < pts.length; i++) {
		maxSteps = Math.max(maxSteps, pts[i].xcoord - pts[i -1].xcoord + pts[i - 1].ycoord - pts[i].ycoord)
}

int[] fArray = factorials(maxSteps);

int ways = 1;
for(int i = 1; i < pts.length; i++) {
	int horizSteps = pts[i].xcoord - pts[i - 1].xcoord + 1;
	int vertSteps = pts[i-1].ycoord - pts[i].ycoord + 1;//I am assuming pts[i - 1] is above pts[i] since vertically we have to move downwards on the grid.
	
if(horizSteps != 0 && vertSteps != 0) {
ways *= fArray[(horizSteps + vertSteps)]/ fArray[horizSteps] * factorials[verticalSteps];
	}
}
return ways;
}
	
}

/ **Time complexity: O(w*h log w*h + w + h) Space: O(w + h + wh) where w is the width of the grid and h is the height. **/

Solution Idea 1: Let's call the two trees n and m. Iterate over all of the nodes in tree n using a pre-order traversal and using a queue store the sequence of characters
from n (call this string qn). Perform a pre-order traversal of m, everytime you encounter a node with a text string, compare the characters of the text string with characters in qn.
Dequeue characters from qn as they match characters in text strings of m. If there's a character mismatch, or qn becomes empty before finishing traversal of text nodes in m, or
qn has nodes left but we've finished visiting all text nodes of m return false. Otherwise return true.
Time complexity: O(nm) where n is the number of nodes in the tree and m is the length of the longest text string. Space complexity: O(nm) from the queue.

Solution Idea 2: Do an iterative post order traversal with two stacks (s1 for nodes in n  and s2 for nodes in m). Also keep two index variables i (for indices in text strings from n)
and j (for indices in text strings from m). When the top entry of s1 and top entry of s2 are both
nodes with text strings, do a string comparison of these strings(text1 for s1's string and text2 for s2's string). In the string comparison, if text1.charAt(i) != text2.charAt(j)
return false. If i == text1.length && j < text2.length, pop off the top entry in s1 set i = 0 and continue post order traversal of both trees (do the same if j == text2.length but i < text1.length).
At the end of the post order traversal of both trees, if both s1 and s2 are empty return true. Otherwise, return false. This solution has the same worst case
time complexity and space complexity idea 1 but is more optimal in some cases. Consider cases where the string formed by n and m differ at the begining (ie.their starting character). We 
could avoid traversing n in its entirety to find this difference saving both time and space).

Code for Idea 2:
Class Node{
	String tag;
	String text;
	boolean isText;
	List<Node> child;
}

public boolean isSame(Node n, Node m){

	Stack<Node> s1 = new Stack<Node>//n nodes
	Stack<Node> s2 = new Stack<Node>//m nodes
	s1.push(n);
	s2.push(m);
	int i = 0;
	int j = 0;
	while(!s1.isEmpty() && !s2.isEmpty()){
		
		Node top1 = s1.peek();
		Node top2 = s2.peek();
		if(top1.isText && top2.isText){
			while(i < top1.text.length() && j < top2.text.length()){
				if(top1.text.charAt(i) != top2.text.charAt(j)){
					return false;
				}
				i++;
				j++;
			}
			if(i == top1.text.length()){
				s1.pop();
				i = 0;
			}
			if(j == top2.text.length()){
				s2.pop();
				j = 0;
			}
		}else if (!top1.isText && top2.isText){
			fillStack(s1,s1.pop());
		}else if(top1.isText && !top2.isText){
			fillStack(s2,s2.pop());
		}else{
			fillStack(s1,s1.pop());
			fillStack(s2,s2.pop());
		}
	
	}
	return s1.isEmpty() && s2.isEmpty();
}

private void fillStack(Stack<Node> st, Node curr){
	for(int i = curr.child.size() - 1; i >= 0; i--){
		st.push(curr.child.get(i));
	}
}

//Assumptions: Object has a getId() method which generates a unique integer similar to hash code. All operations are O(1)
public class ObjectSvc{

	private static class Node{
		Object obj;
		Node prev;
		Node next;
		
		Node(Object ob){
			obj = ob;
		}
	}
	
	Map<Integer,Node> mp;
	Set<Integer> seen;
	Node head;
	Node tail;
	
	public ObjectSvc(){
		mp = new HashMap<Integer,Node>();
		seen = new HashSet<Integer>();
	}
	
	public Object getUnique(){
		if(head == null){
			return null;
		}
		return head;
	}
	
	public void addObject(Object obj){
		int id = obj.getId();//could be hash code.
		if(mp.containsKey(id)){
			Node n = mp.get(id);
			mp.remove(id);
			removeNode(n);
			seen.add(id);
		}else{
			if(!seen.contains(id)){
				Node n = new Node(obj);
				mp.put(id,n);
				addNode(n);
			}
		}
	}
	
	private void addNode(Node n){
		if(head == null){
			head = n;
			tail = n;
		}else{
			tail.next = n;
			n.prev = tail;
			tail = tail.next;
		
		
		}
	}
	
	private void removeNode(Node x){
		if(head == x){
			Node tmp = head.next;
			if(tmp != null){
				tmp.prev = null;
				head.next = null;
				head = tmp;
			}else{
				head = null;
				tail = null;
			}
		}
		else if(tail == x){
			Node tmp = tail.prev;
			tmp.next = null;
			tail.prev = null;
			tail = tmp;
			
		}else{
			x.prev.next = x.next;
			x.next.prev = x.prev;
			x.prev = null;
			x.next = null;
			
		}
	
	}

}

//Assumptions: there may or may not be a famous person. Time Complexity: O(n). Space Complexity: O(1)

public int getFamous(int n){
	int i = 1;
	int j = 0;
	while(j < n){
			if(i == m.length){
				return j;
			}
			if(isKnow(i,j)&& !isKnow[j][i]){
				i++;
			}
			else{
				int tmp = j;
				j = Math.max(i, j + 1);
				i = j;
		
			}
	
	}
	return -1;
}

//Time Complexity: O(c(n,k)) Space: O(n + c(n,k)). Avoids dupicates.
public class Detail{
	int value;
	int count;
	
	public Detail(int v, int c){
		value = v;
		count = c;
	}
}

public List<List<Integer>> subset(int[] arr, int t,int k){
	List<List<Integer>> res = new ArrayList<List<Integer>>();
	Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
	for(int i = 0; i < arr.length; i++){
		int ct = 1;
		if(mp.containsKey(arr[i])){
			ct += mp.get(arr[i]);
		}
		mp.put(arr[i],ct);
	}
	Detail[] arr = new Detail[mp.size()];
	int idx = 0;
	for(Map.Entry<Integer,Integer> e: mp.entrySet()){
		arr[idx++] = new Detail(e.getKey(),e.getValue());
	}
	subsetHelp(0,arr,new ArrayList<Detail>(),res,t,k);
	return res;
}

private void subsetHelp(int idx,Detail[] arr, List<Detail> tmp, List<List<Integer>> res, int t, int k){
	if(k == 0){
		if(t == 0){
			res.add(expand(tmp));
		}
		return;
	}
	if(k < 0 || idx == arr.length){
		return;
	}
	subsetHelp(idx + 1, arr, tmp, res, t , k);
	for(int j = 1; j <= arr[idx].count; j++){
		tmp.add(new Detail(arr[idx].value,arr[idx].count);
		subsetHelp(idx + 1, arr, tmp, res, t - (j * arr[idx].value), k - j);
		tmp.remove(tmp.size() - 1);
	}

}

private List<Integer> expand(List<Detail> ls){
	List<Integer> r = new ArrayList<Integer>();
	for(Detail d: ls){
		for(int c = d.count; c > 0; c--){
			r.add(d.value);
		}
	}
	return r;
}

/**
	Approach 1: O(n) time and O(n) space. Iterate through the array and find the indices containing the maximum value. Store these indices in a
	separate array list. Inside the run function, choose a random value in the array list.
	
	Approach 2: O(n) time and O(1) space. Iterate through the array (A) and find the maximum value (max).Create an 
	index variable (i-initialized to 0) and a counter variable (count-initialized to 0). Iterate through the array again,
	everytime you encounter max at an index j, set A[i++] = j and increment count (count ++). Inside the run function, 
	choose a random integer (idx) between 0(inclusive) and count - 1 (inclusive), return A[idx]-this will be an index
	which contained the maximum value.
**/

public class RandMaxSvc{
	private int[] vals;
	private int count;
	
	public RandMaxSvc(int[] arr){
		vals = arr;
		count = 0;
		initialize()
	}
	
	private void initialize(){
		int max = vals[0];
		for(int i = 1; i < vals.length; i++){
			max = Math.max(max,vals[i]);
		}
		int idx = 0;
		for(int i = 0; i < vals.length; i++){
			if(vals[i] == max){
				vals[idx++] = i;
				count++;
			}
		}
	}
	
	public int run(){
		Random rnd = new Random();
		int idx = rnd.nextInt(count);
		return vals[idx];
	}
}

//O(n) time
public void print(int n){
	if(n <= 0 || n % 2 != 0){
		throw new IllegalArgumentException();
	}
	for(int i = 1; i < n; i += 2){
		printStars(i);
		System.out.print('\n');
	}
	printStars(n);
	for(int i = n - 2; i >= 1; i -= 2){
		System.out.print('\n');
		printStars(i);
	}
}

private void printStars(int n){
	while(n > 0){
		System.out.print('*');
		n--;
	}
}

//Time: O(N), Space: O(N)
public int maxSum(int[] arr, int k){
	for(int i = 1; i < arr.length; i++){
		arr[i] += arr[i - 1];
	}
	Deque<Integer> q = new LinkedList<Integer>();
	int maxSum = arr[0];
	q.addLast(0);
	for(int i = 1; i < k; i++){
		maxSum = Math.max(maxSum, Math.max(arr[i], arr[i] - arr[q.peekFirst()]);
		while(!q.isEmpty()){
			if(arr[i] < arr[q.peekFirst()]){
				q.pollFirst();
			}
		}
		q.addLast(i);
		
	}
	for(int i = k; i < arr.length; i++){
		while(q.peekFirst() < i - k){
			q.pollFirst();
		}
		maxSum = Math.max(maxSum,arr[i] - arr[q.peekFirst()]);
		while(!q.isEmpty()){
			if(arr[i] < arr[q.peekFirst()]){
				q.pollFirst();
			}
		}
		q.addLast(i);
	}
	return maxSum;
}

public int maxSubarray(int[] arr,int k){
	int max = 0;
	int diff = 0;//num zeros
	int totalOnes = 0;
	for(int i = 0; i < arr.length; i++){
		if(arr[i] == 1){
			totalOnes++;
		}
	}
	int j = 0;
	int i = 0;
	while(j < arr.length){
		if(arr[j]  == 0){
			diff++;
		}else{
		totalOnes--;
			diff--;
		}
		while(diff > k){
			if(arr[i] == 1){
				diff++;
				totalOnes++;
			}else{
				diff--;
			}
		}
		if(totalOnes >= k){
			max = Math.max(max,j - i + 1);
			
		}
		j++;
		
	}
	return max;

}

class Data{
	Map<Character,Integer> elems;
	int idx;
	int mult;
	
	Data(Map<Character,Integer> mp, int i, int m){
		elems = mp;
		idx = i;
		mult = m;
	}
}

public Map<Character,Integer> elemCounts(String str){

	Data d = elemHelp(str, 0);
	if(d.mult != 1){
		for(Map.Entry<Character,Integer> e: d.elems.entrySet()){
			e.getValue() *= d.mult;
		}
	
	}
	return d.elems;
}

private Data elemHelp(String str, int i){
	Map<Character,Integer> mp = new HashMap<Character,Integer>();
	int mult = 1;
	while(i< str.length()){
		if(str.charAt(i) >= 'A' && str.charAt(i) <= 'Z'){
			char elem = str.charAt(i);
			int ct = 1;
			if(i + 1 < str.length() && str.charAt(i + 1) >= '0' && str.charAt(i + 1) <= '9'){
				int j = i + 1;
				while(j < str.length() && str.charAt(j) >= '0' && str.charAt(j) <= '9'){
					j++;
				}
				ct = Integer.parseInt(str.substring(i + 1, j));
				i = j;
			}else{
				i++;
			}
			if(mp.containsKey(elem)){
				ct += mp.get(elem);
			}
			mp.put(elem,ct);
		}else if(str.charAt(i) == '('){
			Data d = elemHelp(str, i + 1);
			for(Map.Entry<Character,Integer> e : d.elems.entrySet()){
				e.getValue() *= d.mult;
				if(mp.containsKey(e.getKey())){
					e.getValue() += mp.get(e.getKey());
				}
				mp.put(e.getKey(),e.getValue());
			}
			i = d.idx;
		}else{
			if(i + 1 < str.length() && str.charAt(i + 1) >= '0' && str.charAt(i + 1) <= '9'){
				int j = i + 1;
				while(j < str.length() && str.charAt(j) >= '0' && str.charAt(j) <= '9'){
					j++;
				}
				mult = Integer.parseInt(str.substring(i + 1, j));
				i = j;
			}else{
				i++;
			}
			break;
		}
		
	}
	return new Data(mp,mult,i);
}

//Worst case Time Complexity: O(nlogn) where n is the number of log entries in the stream.
public class Event{
	long time;
	int tag;
}

public class Node{
	int time;
	int tag;
	Node prev;
	Node next;
	
	public Node(int tagVal,int timeVal){
		time = timeVal;
		tag = tagVal;
	}
}

public class StreamSvc{
	private TreeMap<Integer,Node> bst;
	private Set<Integer> tags;
	private int interval;
	
	
	public StreamSvc(int intervalSize){
		bst = new TreeMap<Integer,Node>();
		tagToTime = new HashSet<Integer>();
		interval = intervalSize;
	}
	
	public void readStream(Iterator<Event> it){
		while(it.hasNext()){
			Event e = it.next();
			Integer val = bst.lowerKey(e.time - interval);
			while(val != null){
				Node n = bst.get(val);
				while(n != null){
					if(n.next != null){
						n.next.prev = null;
						n.next = null;
					}
					tags.remove(n.tag);
					n = n.prev;
				}
				Integer next = bst.lowerKey(val);
				bst.remove(val);
				val = next;
			}
			if(!tags.contains(e.tag)){
				Node x = new Node(e.time,e.tag);
				if(bst.containsKey(x.time)){
					Node v= bst.get(x.time);
					v.next = x;
					x.prev = v;
				}
				bst.put(x.time,x);
				tags.add(x.tag);
			}
		}
		
		
	}

}

public class Server{
	private int units;
	
	public Server(int u){
		units = u;
	}
}

public boolean canAssign(int[] tasks, int[] servers){
	Stack<Server> st = new Stack<Server>();
	for(int i = 0; i < servers.length; i++){
		st.push(new Server(servers[i]));
	}
	for(int i = 0; i < tasks.length; i++){
		if(tasks[i] > st.size()){
			return false;
		}
		while(tasks[i] > 0){
			Server s = st.pop();
			s.units--;
			if(s.units != 0){
				st.push(s);
			}
			tasks[i]--;
		}
		
	}
	return true;
}

/**
	If the size of A is even, partition the array about the lower value that makes up the median (ie the value which occurs at index A.length/2 - 1 if A is sorted in ascending order). If the size of A is odd,
	partition the array about the median (ie. the value which occurs at index A.length/2 if A is sorted in ascending order). Call this pivot value mA.
	Parititon array A so that values greater than mA are placed towards the right end of the array and elements less than or equal to mA
	occurr towards the left half of the array. Parititon array b such that elements in B less than mA are placed towards the right end of B and
	elements less than or equal to mA are placed towards the left end of the array.  After this partitioning the right half of array A( A[A.length/2 - 1: A.length -1] if A is even size
	A[A.length/2: A.length - 1] if A is odd sized) will contain values greater than values in array B at the same positions. The number of elements in this region is 1 + (A.length / 2),
	hence countA will be > countB
	Time Complexity: Average case: O(N), Worst case O(N^2)
**/
public void shuffle(int[] a, int[] b){
	int k = a.length % 2 == 0 ? a.length / 2 - 1: a.length /2;
	partitionAsc(a,k);
	int i = 0;
	int j = b.length - 1;
	while(i < j){
		if(b[i] < a[k]){
			swap(b,i,j);
			j--;
		}
		i++;
	}
	
}

private void partitionAsc(int[] a,int k){
	int i = 0;
	int j = a.length - 1;
	Random rnd = new Random();
	while(i < j){
		int piv = i + rnd.nextInt(j - i + 1);
		piv = partitionHelp(a,piv,i,j);
		if(piv == k){
			break;
		}
		if(piv < k){
			i = piv + 1;
		}else{
			j = piv - 1;
		}
	
	}
}

private int partitionHelp(int[] a, int piv, int i, int j){
	swap(a,piv,j);
	piv = j--;
	while(i <= j){
		if(a[i] > a[piv]){
		
			swap(a,i,j);
			j--;
		}
		i++;
	}
	swap(a,piv,i);
	return i;

}

//Time: O(N) Space: O(1)
public int[] shiftElems(int[] arr){
	if(arr == null || arr.length == 0){
		throw new IllegalArgumentException();
	}
	if(arr.length == 1){
		return(arr[0] == 0? 0: 1);
	
	}
	boolean allNonZeros = true;
	for(int i = 0; i < arr.length; i++){
		if(arr[i] == 0){
			break;
			allNonZeros = false;
			break;
		}
	
	}
	if(allNonZeros){
		return 0;
	}
	boolean arrangedOkay = true;
	i = 1;
	while(i < arr.length){
		if(arr[i -1] == 0 && arr[i] != 0){
			arrangedOkay = false;
			break;
		}
		i++;
	}
	if(arrangedOkay){
	 for(int j = 0; j < arr.length; j++){
		if(arr[j] ==0){
			return j + 1;
		}
	 }
	
	}
	
	int i = 0;
	int j = arr.length - 1;
	while(i <= j){
		if(arr[i] == 0){
			swap(i,j,arr);
			j--;
		}
	
	}
	return i + 1;

//Iterative Time Complexity:O(N)
public int countEncodings(String str){
	if(str == null || str.length() == 0 || str.charAt(0) == 0){
		return 0;
	}
	int n_1 = 1;
	int n_2 = 1;
	for(int i = 1; i < str.length(); i++){
		int oneDigit = Integer.parseInt(str.substring(i,i+1));
		int twoDigit = Integer.parseInt(str.substring(i - 1, i + 1));
		if(oneDigit == 0 && twoDigit == 0){
			return 0;
		}
		int nextTotal = 0;
		if(oneDigit >= 1 && oneDigit < 10){
			nextTotal += n _ 1;
		}
		if(twoDigit >= 10 && twoDigit <= 26){
			nextTotal += n _2;
		}
		n_2 = n_1;
		n_1=nextTotal;
	}
	return n_1;
}

public class Data{
	int sumSoFar;
	
	public Data(int s){
		sumSoFar = s;
	}
}

class Node{
	int value;
	Node left;
	Node right;
}

public Node updateSum(Node n){
	updateHelp(n,new Data(0));
}

private void updateHelp(Node n, Data d){
	if(n == null){
		return;
	}
	updateHelp(n.right,d);
	n.val += d.sumSoFar;
	d.sumSoFar = val;
	updateHelp(n.left, d);
}

//Time Complexity : O(N) Space: O(N)
public List<Integer> leaves(int[] arr){
	if(arr == null || arr.length == 0){
		return Collections.<Integer>emptyList();
	}
	List<Integer> result = new ArrayList<Integer>();
	Stack<Integer> st = new Stack<Integer>();
	for(int i = 0; i < arr.length; i++){
		Integer l = null;
		boolean leafFound = false;
		while(!st.isEmpty() && arr[i] > st.peek()){
			if(l != null && !leafFound){
				result.add(l);
				leafFound = true;
			}
			l = st.pop();
		}
		st.push(arr[i]);
		
	}
	result.add(st.pop());
	return result;
}

class ResultIterator{
	private List<String> wrds;
	ResultIterator(Iterator it1, Iterator it2){
		wrds = new ArrayList<String>();
		fillWords();
	}
	
	public boolean hasNext(){
		return !wrds.isEmpty();
	}
	
	public String next(){
		if(wrds.isEmpty()){
			return null;
		}
		String ret = wrds.remove(0);
		fillWords();
		return ret;
	}
	
	private void fillWords(){
		if(it1.hasNext()){
			wrds.add(it1.next());
		}
		if(it2.hasNext()){
			String s = it.next();
			if(wrds.isEmpty() || !s.equals(wrds.get(wrds.size() - 1))){
				wrds.add(s);
			}
		}
	}
}

There are three approaches: 1) Trie of words in the dictionary + dfs on the query string. Time complexity: O(max(w*m,n^2)) Space is O(w*m) where n is the length of the query string w is the length of the longest word and m is the length o the dictionary. 2) Find the lcs between each word in the dictionary and the query string.Time: O(w*m*n) Space:O(min(w,n)) 3)Using a single while loop and two pointers (i-characters in a word, j-characters in query string) determine if word occurs in query string. Time: O(w*m*n) Space:O(1)

public static void printSums(int[] coins){
	boolean[] b = new boolean[1001];
	b[0] = true;
	Arrays.sort(coins);
	for(int i = 0; i < coins.length; i++){
		for(int j = coins[i]; j < b.length; j++){
			if(b[j - coins[i]]){
				b[j] = true;
			}
		}
	}
	for(int i = coins[0]; i < b.length; i++){
		if(b[i]){
			System.out.println(i);
		}
	}
}

public class Pair{
	char first;
	char last;
}
//Using Disjoint sets.
public boolean isValid(Pair[] pairs, Pair[] unequals){
	
	Map<Character,Character> ds = new HashMap<Character,Character>();
	for(char x = 'A'; x <= 'Z'; x++){
		ds.put(x,x);
	}
	for(Pair p: pairs){
		char parent1 = find(ds,p.first);
		char parent2 = find(ds,p.sec);
		if(parent1 != parent2){
			if(parent1 < parent2){
				ds.put(parent2, parent1);
			}else{
				ds.put(parent1, parent2);
			}
		}
	}
	for(Pair p: unequals){
		char parent1 = find(ds,p.first);
		char parent2 = find(ds,p.sec);
		if(parent1 == parent2){
			return false;
		}
	}
	return true;
}

private char find(Map<Character,Character> ds, char x){
	char r = ds.get(x);
	if(r == x){
		return r;
	}
	r = find(ds,x);
	ds.put(x,r);
	return r;
}

Time Complexity: O(n) where n is the size of the input array. Space: O(n)
public class FindNumSvc {
	
	public static int findNum(int[] arr){
		if(arr == null || arr.length < 2){
			throw new IllegalArgumentException();
		}
		int[][] minMax = new int[2][arr.length];
		int max = arr[0];
		for(int i = 1; i < arr.length; i++){
			minMax[0][i] = max;
			max = Math.max(arr[i], max);
		}
		int min = arr[arr.length - 1];
		for(int i = arr.length - 2; i >= 0; i--){
			minMax[1][i] = min;
			min = Math.min(arr[i], min);
		}
		for(int i = 1; i < arr.length - 1; i ++){
			if(minMax[0][i] < arr[i] && minMax[1][i] > arr[i]){
				return i;
			}
		}
		if(minMax[0][arr.length - 1] < arr[arr.length - 1]){
			return arr.length - 1;
		}
		return minMax[1][0] > arr[0]? 0:-1;
	}

	public static void main(String[] args) {
		int[] arr = {-1,4,-3,6,-2,5,8,9};
		System.out.println(findNum(arr));

	}

}

//Time Complexity: O(N) where N is the length of the string. Space Complexity: O(RN) where R is the number of repititions.
private static class Data{
	int count;
	String strVal;
	
	private Data(int c){
		count = c;
		strVal ="";

	}
}

public String decode(String str){
	if(str == null || str.length() == 0){
		throw new IllegalArgumentException();
	}
	Stack<Data> stk = new Stack<Data>();
	int count = 0;
	int strStart = -1;
	for(int i = 0; i < str.length(); i++){
		if((str.charAt(i) >= '0' && str.charAt(i) <= '9') || str.charAt(i) == ']'){
			if(strStart != -1){
				stk.peek().strVal = str.substring(strStart,i+1);
				strStart = -1;
			}
			if(str.charAt(i) == ']'){
				Data top = stk.pop();
				String rep = applyRepition(top);
				if(!stk.isEmpty()){
					stk.peek().strVal += rep;
				}else{
					top.count = 1;
					top.strVal = rep;
					stk.push(top);
				}
			}else{
				count *= 10;
				count += ((int)(str.charAt(i) - '0'));
			}
		}
		if (str.charAt(i) == '['){
			stk.add(new Data());
			stk.peek().count = count;
			count = 0;
		}
	}
	return applyReptition(stk.pop());
}

private String applyRepitition(Data d){
	if(d.count == 1){
		return d.strVal;
	}
	StringBuilder bldr = new StringBuilder(d.count * d.strVal.length());
	int ct = d.count;
	while(ct > 0){
		bldr.append(d.strVal());
		ct--;
	}
	return bldr.toString();
}

//Time Complexity: O(NL) where N is the number of words in the dictionary and L is the length of the longest word. Space: O(NL)

private static class Node{
	private Node[] child;
	boolean isWord;
	
	private Node(){
		child = new Node[26];
		isWord = false;
	}
}
public static List<String> words(String str, String[] dict){
	if(str == null || str.length() == 0 || dict == null || dict.length == 0){
		throw new IllegalArgumentException();
	}
	Set<String> result = new HashSet<String>();
	Node rt = new Node();
	makeTree(dict,rt);
	search(0,str,new List<Character>(),rt,results);
	
}
private static void search(int i, String str, List<Character> wrd, Node rt,Set<String> result){
	if(i == str.length()){
		if(rt.isWord){
			result.add(buildString(wrd));
		}
		return;
	}
	int curr = (int)str.charAt(i);
	for(int j = i; j < str.length(); j++){
		if(rt.child[curr] != null){
			wrd.add(str.charAt(i));
			search(i + 1,str,wrd,rt.child[curr],result);
			wrd.remove(str.charAt(i));
		}
	}
}


private static void makeTree(String[] dict, Node rt){
	for(String s: dict){
		addWrd(s,rt);
	}

} 
private static void addWrd(String str, Node rt){
	Node v = rt;
	for(int i = 0; i < str.length(); i++){
		int idx = (int)str.charAt(i) - 'a';
		if(v.child[idx] == null){
			v.child[idx] = new Node();
		}
		v = v.child[idx];
	}
	v.isWord = true;

}

//Time Complexity: O(n^2) where n is the number of nodes in the tree. Space complexity: O(n)
 //Modified your Node class as I couldn't figure out how to accomodate deleting a single node with the structure that was given.
private class TreeNode{
	int val;
	List<TreeNode> child;
	
	private TreeNode(int v){
		val = v;
	}

}
//Assumption: List of nodes returned should be the root node (if it's not one of the deletion candidates) otherwise the children of the root node.
 private List<TreeNode> delete(TreeNode rt, HashSet<TreeNode> set){
	if(rt == null || set == null || set.isEmpty()){
		throw new IllegalArgumentException();
	}
	List<TreeNode> result = new ArrayList<TreeNode>();

	for(TreeNode n: set){
		if(n == rt){
			result.addAll(rt.child);
			return result;
		}
		boolean result = deleteNode(rt,n);
		if(!result){
			throw new IllegalArgumentException();//if target node isn't present in the tree.
		}
	}
	result.add(rt);
	return result;
 }
 private boolean deleteNode(TreeNode rt, TreeNode t){
 
	int targetIdx = -1;
	for(int i = 0; i < rt.child; i++){
		if(rt.get(i) == t){
			targetIdx = i;
			break;
		}
	}
	if(targetIdx != -1){
		rt.child.remove (targetIdx);
		rt.child.addAll(t.child);
		return true;
	}else{
	
		for(TreeNode n: rt.child){
			boolean r = deleteNode(n,t);
			if(r){
				return true;
			}
		}
		return false;
	}	
}

//Time: O(N) space: O(N)
//Test cases to try: "aaa"=> 3, mkmk=>2, akem=>1
public int countChunks(String str){
	if(str == null || str.length() == 0){
		throw new IllegalArgumentException();
	}
	int s = 0;
	int e = str.length();
	int i = 1;
	int j = e - 1;
	int chunks = 0;
	while(i <= j){
		String left = str.substring(s,i);
		String right = str.substring(j,e);
		if(left.equals(right)){
			chunks += 2;
			s = i++;
			e = j--;
		}else{
			i++;
			j--;
		}
	}
	if(s != e){
		chunks++;
	}
	return chunks;
}

Taking a shot at this. We need to have a lookup table where they key is userId and value is a list of the websites that user is subscribed to. Let's assume we assign each user a 32-bit(4 byte) int user iD. Let's also assign 4 byte int iDs to the websites. If in the worst case a user is subscribed to all websites, a single key-value pair will take up 16Kb of space we have a total of 16Kb * 10^9 users = 1.6 * 10^12 bytes of data (1.6TB). Assume that a single server can store 8GB of data then 1.6 * 10^12 / 8 * 10^9 = 2 * 10^3 servers ( which is what we have). This allows us to store data on 500K users per server. Each server can store a range of User IDs (ex. server 1 stores IDs from 1...499 999). When a user unsubscribes based on his userId we can navigate to the correct server containing the corresponding look-up table. In the look up table delete the ID of the website he wishes to unsubscribe from.

camiloni42 what are we expected to optimize for in the solution. Are we trying to find the solution that leaves the character with the maximum money or maximum strength? Please clarify

private class Counts{
	int above;
	int down;
	int left;
	int right;
	private Counts(){
		above = 0;
		down = 0;
		left = 0;
		right = 0;
	}
}
// Time Complexity: O(N*M) where N is the number of rows, M is the number of columns. Space: O(N * M).
public int maxPlus(int[][] mat){
	if(mat == null || mat.length == 0 || mat[0].length == 0){
		throw new IllegalArgumentException();
	}
	
	Counts[][] countData = new Counts[mat.length][mat[0].length];
	for(int r = 0; r < countData.length; r++){
		for( int c = 0; c< countData[0].length; c++){
		
			countData[r][c] = new CountData();
		}
	}
	
	//across first and last row
	for(int c = 1; c < mat[0].length; c++){
		countData[0][c] = countData[0][c - 1] == 1? countData[0][c - 1].left + 1: 0;
		countData[mat.length][mat[0].length - c - 1] = countData[mat.length][mat[0].length - c] == 1? countData[mat.length][mat[0].length - c].right + 1: 0;
	}
	//across first and last columns
	for(int r = 1; r < mat.length; r++){
		countData[r][0] = countData[r - 1][0]==1?countData[r - 1][0].above + 1: 0;
		countData[mat.length - r - 1][mat[0].length - 1] = countData[mat.length - r][mat[0].length - 1] == 1? countData[mat.length - r][mat[0].length - 1] + 1: 0;
	}
	
	// start from (1,1)
	for(int r = 1; r < mat.length; r++){
		for(int c = 1; c< mat[0].length; c++){
			if(mat[r - 1][c] == 1){
				countData[r][c].above = countData[r - 1][c].above + 1;
			}
			if(mat[r][c - 1] == 1){
				countData[r][c - 1].left = countData[r][c - 1].left + 1;
			}
		}
	}
	for(int r = mat.length - 2; r >= 0; r--){
		for(int c = mat[0].length - 2; c >= 0; c--){
			if(mat[r + 1][c] == 1){
				countData[r][c].down = countData[r + 1][c].down + 1;
			}
			if(mat[r][c + 1] == 1){
				countData[r][c].right = countData[r][c + 1].right + 1;
			}	
		}
	}
	int maxLen = 0;
	for(int r = 0; r < mat.length; r++){
		for(int c = 0; c < mat[0].length; c++){
			
			if(mat[r][c] == 1){
				int minPlus = Math.min(countData[r][c].above,countData[r][c].down);
				minPlus = Math.min(countData[r][c].left, countData[r][c].right);
				maxLen = math.max(maxLen,minPlus);
			}
		}
	}
	return maxLen;
}

//Assuming that the rest of the question is --when checking a query, all lights that are adjacent or on the same diagonal as a query position will turn off.
//Time O(N^2). Space O (N^2).
public void checkLights(Point[] lamps, int n, Point[] queries){
	if(lamps == null || queries == null || lamps.length == 0 || queries.length == 0 || n <= 0){
		throw new IllegalArgumentException();
	}
	
	boolean[][] board = new boolean[n][n];
	int[][][] visited = new int[n][n][8];
	for(int i = 0; i < lamps.length; i++){
	
		board[lamps[i].x][lamps[i].y] = true;
	}
	for(int i = 0; i < queries.length; i++){
		System.outprintln(board[queries[i].x][queries[i].y]?"Yes":"No");
		for(int i = 0; i < 8; i ++){
			dfs(quries[i],m,i,visited);
		}
		
		
	}
	
	
}
private boolean dfs(Point q, boolean[][] m, int dir,int[][][] visited){
	if(q.x < 0 || q.x == m.length || q.y < 0 || q.y == m[0].length){
		return false;
	}
	if(visited[q.x][q.y][dir] != 0){
		return;
	}
	m[q.x][q.y] = false;
	visited[q.x][q.y][dir] = 1;
	switch(dir){
	
		case 0:
			dfs(new Point(q.x -1, q.y),m,dir,visited);
		case 1: 
			dfs(new Point(q.x + 1, q.y),m,dir,visited);
		case 2:
			dfs(new Point(q.x,q.y -1),m,dir,visited);
		case 3:
			dfs(new Point(q.x,q.y + 1),m,dir,visited);
		case 4:
			dfs(new Point(q.x -1, q.y -1),m,dir,visited);
		case 5:
			dfs(new Point(q.x - 1, q.y + 1),m, dir,visited);
		case 6:
			dfs(new Point(q.x + 1, q.y - 1),m, dir, visited);
		case 7:
			dfs(new Point(q.x + 1, q.y + 1),m,dir,visited));
	}
}

public int missing(int[] arr){
	if(arr == null || arr.length == 0){
		throw new IllegalArgumentException();
	}
	
	for(int i = 0; i < arr.length; i++){
	
		while(arr[i] != i){
		
			int dest = arr[i];
			if( dest < arr.length && arr[dest] != dest){
				swap(i,dest,arr);
			}else{
				break;
			}
		}
	}
	for(int i = 0; i < arr.length; i++){
	
		if(arr[i] != i){
			return i;
		}
	}
}

private void swap(int a, int b, int[] arr){
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}

O(min(n,m)) where n is the length of s1 and m is the length of s2.
public int compare(String s1,String s2){
	if(s1 == null || s2 == null){
		throw new IllegalArgumentException();
	}
	
	Map<String, Integer> lookUp = new HashMap<String, Integer>();
	int idx = 0;
	for(char c = 'a'; c <= 'z'; c++){
		lookUp.put(""+c,idx);
		idx++;
		if(c == 'c'){
			idx++;
		}
	}
	lookUp.put("ch",3);
	
	int i = 0;
	int j = 0;
	while(i < s1.length() && j < s2.length()){
		int p1;
		int p2;
		if(s1.charAt(i)== 'c' && ( (i + 1 < s1.length()) && s1.charAt(i + 1) == 'h')){
			p1 = lookUp.get("ch");
		}else{
			p1 = lookUp.get(s1.subString(i,i+1));
		}
		if(s2.charAt(i) == 'c' &&((j + 1 < s2.length() && s2.charAt(j + 1)== 'h')){
			p2 = lookUp.get("ch");
		}else{
			p2 = lookUp.get(s2.subString(j,j+1));
		}
		if(p1 != p2){
			return p1 < p2? -1: 1;
		}
		i++;
		j++;
	}
	if(i < s1.length()){
		return 1;
	}
	if(j < s2.length()){
		return -1;
	}
	return 0;
	
}

//Time Complexity: O(N^2) where N is the size of the matrix. Space: O(N).
public int[][] fillMatrix(int[][] m){
	if(m == null || m.length == 0 || m[0].length == 0){
		throw new IllegalArgumentException();
	}
	boolean[][] rowData = new boolean[m.length][10];
	boolean[][] colData = new boolean[m.length][10];
	for(int i = 0; i < m.length; i++){
		for(int c = 0; c < m[0].length; c++){
			if(m[i][c] != 0){
				rowData[i][m[i][c]] = true;
				colData[c][m[i][c]] = true;
			}
		}
	}
	
	boolean r =fillHelp(m,0,0,rowData,colData);
}

private boolean fillHelp(int[][] m, int r, int c, boolean[][] rowDetail, boolean[][] colDetail){
	while(r < m.length){
		while(c < m.length){
			if(m[r][c] == 0){
				for(int i = 1; i <= 9; i ++){
					if(!rowDetail[r][i] && !colDetail[c][i])
					{
						m[r][c] = i;
						rowDetail[r][i] = true;
						colDetail[c][i] = true;
						result = fillHelp(m,r,c+1,rowDetail,colDetail)
						if(result){
							return true;
						}
						rowDetail[r][i] = false;
						colDetail[c][i] = false;
						m[r][c] = 0;
					}
				}
				return false;
			
			}else{
				c++;
			}
		}
		c = 0;
		r++;
	}
	return true;
}

//Time: O(NlogN) Space: O(N).
class Circle{
	double x;
	double y;
	double rad;
	
}

class Interval implements Comparable<Interval>{
	double start;
	double end;
	int id;
	
	public Interval(double s, double e, int idx){
		start = s;
		end = e;
		id = idx;
	}
	
	public int compareTo(Interval i){
		if(start == i.start){
			return end - i.end;
		}
		return start - i.start;
	}
}

public boolean hasIntersect(Circle[] c){

	if(c == null || c.length == 0){
		throw new IllegalArgumentException();
	}
	
	Interval[] xRange = new Interval[c.length];
	Interval[] yRange = new Interval[c.length];
	
	for(int i = 0; i < c.length; i++){
		xRange[i] = new Interval(c[i].x - c[i].r,c[i].x + c[i].r,i);
		yRange[i] = new Interval(c[i].y - c[i].r, c[i].y + c[i].r, i);
		
	}
	Arrays.sort(xRange);
	Arrays.sort(yRange);
	
	Set<String> overlaps = new HashSet<String>();
	for(int i = 1; i < xRange.length; i++){
		if(xRange[i].start <= xRange[i -1].end){
			int minId = Math.min(xRange[i-1].id, xRange[i].id);
			int maxId = Math.max(xRange[i - 1].id, xRange[i].id);
			overlaps.add(minId +", " + maxId);
		}
	}
	
	for(int i = 1; i < yRange.length; i++){
		if(yRange[i].start <= yRange[i - 1].end){
			int minId = Math.min(yRange[i -1]. id, yRange[i].id);
			int maxId = Math.max(yRange[i - 1].id, yRange[i].id);
			if(overlaps.contains(minId + ", " + maxId)){
				return true;
			}
		}
	}
	return false;
}

public int pivotIndex(int[] arr){
	if(arr == null || arr.length < 2){
		throw new IllegalArgumentException();
	}=
	reint cumSum = 0;
	for(int i = 0; i < arr.length; i++){
		cumSum += arr[i];
	}
	
	int s = arr[0];
	for(int i = 1; i < arr.length; i++){
		s += arr[i];
		if(s == (cumSum - arr[s])){
			return i;
		}
	}
	return -1;
}

//Time Complexity: O(N) where N is the size of the array.

public String reformat(String str, int k){
	if(str == null || str.length() == 0 || k <= 0 || k > str.length()){
		return null;
	}
	if(k == str.length()){
	return str;
	}
	
	int len = 0;
	for(int i = 0; i < str.length(); i++){
		if(str.charAt(i) != '-'){
			len++;
		}
	}
	int rem = len % k;//0
	StringBuilder bldr = new StringBuilder(str.length());
	int i = 0;
	while(i < rem){
		
			if(str.charAt(i) != '-'){
				bldr.append(str.charAt(i))
			}
		
		i++;
	}
	if(i != 0){
		bldr.append('-');
	}
	while(i < str.length()){
		int count = 0;
		while(count < k){
			if(str.charAt(i) != '-'){
				bldr.append(str.charAt(i))
				count++;
			}
			i++;
		}
		if(i < str.length()){
			bldr.append('-');
		}
	}
	return bldr.toString();

}
//O(N) time where N is the length of the input string. O(N) Space.

/**
	 * 
	 * Using BFS compute the weight of the shortest path from the starting vtx(s) to the
	 * destination vtx(e). Use a HashMap to keep track of which verticies have already been visited
	 * and update the minimum cost of reaching each vertex from s. For each vtx removed from the queue (t) check if it  has a direct
	 * edge to e. If no direct edge exists, take the minimum cost of travelling to t(just do a lookup in the hash map) and add w to this value-
	 * this will be the minimum cost of going from t to e, update the hash map with the minimum cost
	 * of going to e from each vertex.
	 * Time: O(v + e) where v is the number of vertices and e is the number of edges.
	 * Space: O(v + e) due to hash map and bfs queue.
	 * 
	 * 
	 *
	 */
	
	private static class Edge
	{
		int vtx;
		int cost;
	}
	public int minCost(List<Edge>[] adj, int w,int s, int e)
	{
		return minCostHelper(adj,w,s,e);
		
		
	}
	
	private int minCostHelper(List<Edge>[] adj, int w, int s, int e){
		Map<Integer,Integer> lookUp = new HashMap<Integer,Integer>();
		lookUp.put(s,0);
		Deque<Integer> q = new LinkedList<Integer>();
		q.addLast(s);
		int minCost = Integer.MAX_VALUE;
		while(!q.isEmpty()){
			boolean hasDirect = false;
			Integer top = q.pollFirst();
			int initial = lookUp.get(top);
			int cost;
			for(Edge vtx:adj[top]){
				cost = initial + vtx.cost;
				if(!lookUp.containsKey(vtx.vtx) || cost < lookUp.get(vtx.vtx)){
					if(!lookUp.containsKey(vtx.vtx)){
						q.addLast(vtx.vtx);
					}
				
					lookUp.put(vtx.vtx,cost);
				
				}
				if(vtx.vtx == e){
					hasDirect = true;
				}
			}
			if(!hasDirect){
				cost = initial + w;
				if(!lookUp.containsKey(e) || cost < lookUp.get(e)){
					lookUp.put(e,cost);
				}
			}
		}
		return lookUp.get(e);
	}
}

//O(nlogn) with AVL tree.

private static class Node
{
	int value;
	int idx;
	public Node(int v, int i){
	value = v;
	idx = i;
	}
}

public static int countPairs(int[] arr){
	if(arr == null || arr.length <= 1){
	return -1;
	}
	
	Node h = new Node(arr[0],0);
	int ct = 0;
	for(int i = 1; i < arr.length; i++){
		int lo = arr[i] - i;
		int hi = arr[i] + i;
		//count values
		ct += (count(lo,hi,h,arr[i],i))*2;
		h = insertAvl(h,arr[i],i);
		
	}
	return ct;
}

private static int count(int lo, int hi, Node h, int x, int idx){
	if(h == null|| h.value < lo || h.value > hi){
		return 0;
	}
	int total = count(lo,hi,h.left,x,idx);
	if(Math.abs(x - h.value) <= Math.abs(idx - h.idx))
	{
		total++;
	}
	return total;
}

do the nodes have prent pointers

public class Dictionary{
	public boolean containsWord(String str){...}
}
public String getValidSentence(String str, Dictionary d){

ArrayList<String> ls = new ArrayList<String>();

boolean r = getSentence(0, str, ls, d);
return makeSentence(ls);
}
private boolean getSentence(int i, String s, ArrayList<String> ls, Dictionary d){
	if(i == s.length()){
		return true;
	}
	boolean r = false;
	for(int idx = i+1; idx < s.length(); i++){
		String sub = s.subtring(i, idx);
		if(d.containsWord(sub))
		{
			ls.add(sub);
			r = getSentence(idx, s, ls, d);
			if(r){
				break;
			}else{
				ls.remove(ls.size()-1);
			}
		}
	}
	return r;
}

//O(N^2)

public class Solution{
	
private static Node rt=new Node();//Reference to root node of trie.
public static boolean searchWord(String wrd){
	if(wrd==null||wrd.length()==0){
		return false;
	}
	for(int i=0;i<wrd.length();i++){
		int idx=(int)wrd.charAt(i)-'a';
		Node v=rt;
		if(v.nextLetters[idx]==null){
			return false;
		}
		v=v.nextLetters[idx];
	}
	return true;
	
}

public static boolean searchPhrase(String[] phrase){
	
	Node v=rt;
	for(int i=0;i<phrase[0].length();i++){
		int idx=(int)phrase[0].charAt(i)-'a';
		if(v.nextLetters[idx]==null){
			return false;
		}
		v=v.nextLetters[idx];
	}
	for(int i=1;i<phrase.length;i++){
		String wrd=phrase[i];
		
		//check if the node corresponding to the last letter of the previous word has a pointer to the first letter of the current word
		int currChar=(int)wrd.charAt(0)-'a';
		if(r.c[currChar]==null || v.nextWordStart[currChar]==null){
			return false;
		}
		v=r.c[currChar];
		for(int j=1;j<wrd.length();j++){
			currChar=wrd.charAt(j)-'a';
			if(v.nextLetter[currChar]==null){
				return false;
			}
			v=v.nextLetter[currChar];
		}
	}
	return true;
}



//represents a letter.
private static class Node{
	Node[] nextLetters;//Points to the next character of current word
	Node[] nextWordStart;//Points to starting character of next word (if node is the last letter of a word in a phrase).
	
	public Node(){
		nextLetters=new Node[26];
		nextWordStart=new Node[26];
	}
}

}

public int countWays(int n, int[] last,int bFreq, int cFreq){
		if(n==0){
			return 1;
		}
		int total=0;
		if(bFreq<1){
			
			total+=countWays(n-1,last,1,0);
			
		}
		if(cFreq<2){
			
			total+=countWays(n-1,last,bFreq,cFreq+1);
			
		}
		total+=countWays(n-1,last,bFreq,0);
		return total;
	}

//Time complexity: O(N^2) I think. Space: O(1). Using cyclic swaps.
	public int[] sortArray(int[] arr){
		if(arr==null||arr.length<=1){
			return arr;
		}
		int empty=arr.length-1;
		for(int i=0;i<arr.length;i++){
			int next=i;
			while(arr[next]!=next+1 && arr[next]!=0){
				arr[empty]=arr[arr[next]-1];
				int next_i=empty;
				arr[arr[next]-1]=arr[next];
				empty=next;
				arr[empty]=0;
				next=next_i;
			}
		}
		return arr;
	}