CareerCup

Use a stack:

We loop through the string. If we encounter an open parenthesis, we put it on the stack. If we find a close parenthesis, we remove an open parenthesis of the stack- In this case, if we find that there is no open parenthesis on the stack, we know that we have invalid parentheses.
Likewise, If we find that by the end of the string, we still have open parentheses on the stack, it is invalid.

Some code:

boolean isValid(String s) {

     Stack stack = new Stack();

     for (int i = 0; i < s.length(); i++) {

          if (s[i] == '(') { stack.push("("); }

               else if (s[i] == ')') {

                    if ( stack.size() > 0) { stack.pop();}
                    else { return false; }
               }
     }

     return (stack.size() == 0);
}

This is like finding a sink in a directed acyclic graph which is O(n)

One way you can do this is make nodes for each number, then add connections in code.
Put all of these nodes into a List (L)

Now, run DFS on one node- All nodes in the visited list of this DFS will be part of a set (group), Now, remove all the nodes in the visited list from L. With whatever node is left in L,run DFS and repeat the same process until L is empty.

Not the most efficient code, but it's the easiest to implement and explain:

basically loop until you reach the integer that has k counts of the digit before it. record it as the beginning of your possible range. then, find the next integer that produces a count of digits before it that exceeds k, find the number right before that and set it as the ending of the possible range

public int[] range(int d, int k) {
		
		int[] range = new int[2];

		int count = 0;
		int i = 0;

		while (true) {

			int temp = numPresent(i, d);
		
			if (temp > 0 && count <= k ) {
				
				count += temp;
				range[0] == i;
			}
			
			if (temp > 0 && count > k ) {
				
				count += temp;
				range[1] == i-1;
				break;
			}

			i++;
		}
		
		return range;
	}

	int numPresent(int n, int digit) {
	
		//returns the number of digit in the integer n
	}

This is, indeed, the correct answer

This is 2n operations/comparisons

That's awesome. Great solution!

(5/6)^2

Almost.

Let's define ascii values:

A= 65
B = 66
C = 67
D = 68
E = 69
... etc.

If we have two strings "BE" and "DC", they both sum to the same value, but they have different characters.

I think instead of transforming based on the sum of characters, when you iterate over the list, the hash code should be the hashcode produced when the particular string is lexicographically ordered.

so if you have the following strings:

"BAC", "CAB"

we would first find the lexicographically sorted version of the string , (for both this is "ABC") and in the hash location for "ABC", we would add both of them

Something like the following:

public Node makeBST(Node head) {
		
		if (head == null) { return null; }

		Node mid = findCenter(head);
		mid.previous.next = null;
		
		mid.previous = makeBST(head);
		mid.next = makeBST(mid.next);
		
		return mid;
	}

	public Node findCenter(Node head) {
	
		//implement
	}

This sounds like unweighted interval scheduling (which is greedy):

Order all the events on the calendar by their ending time in a list. Then,
loop through all of the events. For each event, remove all events in the list that it intersects, then continue to the next event in the list and repeat the process.

If there are certain events that are more valuable (more weight), then do the weighted interval scheduling algorithm which uses dynamic programming

This sounds like unweighted interval scheduling (which is greedy):

Order all the events on the calendar by their ending time in a list. Then,
loop through all of the events. For each event, remove all events in the list that it intersects, then continue to the next event in the list and repeat the process.

If there are certain events that are more valuable (more weight), then do the weighted interval scheduling algorithm which uses dynamic programming

Bouncing off of this, i was thinking that maybe the following would optimize?

Sort list, from negative to positive. For each negative number, try all subsets of positive numbers that equal the negative number. For each positive number, try all subsets of negative numbers that equal the positive number.

Thus, instead of trying all possibilities, the run time becomes:

nlogn + m * 2^n + n * 2^m

such that:
n = # of negative numbers
m = # of positive numbers

assuming the list is balanced b/w positive and negative numbers, this can severely cut down running time to approximately peak at:

nlogn + 2^(n/2)/2 + 2^(n/2)/2 = nlogn + 2^(n/2), which is approximately 33millionish (bad for int, but good for long)

You can use a trie to represent the dictionary, then simply traverse the trie using the 4 characters?

I'm not entirely sure, but this seems like a valid approach.

Basically you can do an inorder traversal, but keep track of a global 'previous' node. on each node we visit in the traversal, set the previous node's next pointer to the current node we are on. the current node's previous pointer to the previous global node. then set the current node as the global node and continue the traversal

Node global;
public void linkedList(Node n) {

if (n == null) { return; }

linkedList(n.left);

if (global == null) { 
global = n;
return;
}

global.next = n;
n.previous = global;
global = n;
linkedList(n.right);

}

public char[] sort(char[] x) {

		char[] out = new char[x.length];
		int a, b;
		a =  0;
		b = x.length - 1;

		for (int i = 0; i < char.length[]; i++) {
			
			if (x[i] == 'h') { out[a++] = 'h'; }
			if (x[i] == 'l') { out[b--] = 'l'; }
		}

		while (b > a) {
			
			out[b--] = 'm';
		}
		
		return out;
	}

2 hash tables. 1 keeps track of Node addresses and the other keeps track of the number of duplicates of a certain value.

O(n) time complexity and O(2n) space complexity-

HashTable A <address, boolean (visited already?)>
HashTable B <value, number that this value has occurred in our traversal>

You can use a stack

public void reorder(Node head, int n) {

	Stack s = new Stack();
	Node curr = head;

	while( curr.next != null ) {
		
		s.push(curr);
		curr = curr.next;
	}

	curr.next = head;
	head = curr;

	for (int i = 0; i < n; i ++) {

		s.pop();
	}

	(s.pop()).next = null;
	
}

c ^ ( (b ^ c) & -(a) )