CareerCup

public void printRange(int[] n) {
	
	int begIndex = 0;
	String toPrint = "":

	if (n.length == 1) {

		System.out.prinlnt(n[0]);
		return;
	}
	
	for (int i = 1; i < n; i++) {

		while (i < n.length && n[i] - n[i - 1] == 1) {

			i++;
		}

		if (i-1 == begIndex) {

			toPrint += ", " + n[begIndex];//handle first parenthesis
		}

		else {

			toPrint += ", " + n[begIndex] +" - " + n[i-1];
		}

		begIndex = i;
	}

	System.out.prinlnt(toPrint);

}

Could you provide reasoning for it?

Agreed. This can definitely be done in O(logn), but I see no way of doing this in O(1) time.

But insertion is logn for each element, so nlogn in total....

I feel like this is not possible

XOR the numbers, then see how many 1s there are in this value

Reasoning:
We know that a ^ a = 0 , so 1 ^ 1 = 0 and 0 ^ 0 = 0
But, 1 ^ 0 = 1 and 0 ^1 = 1, so we see that we can find differences by xoring


Some code:

int numSwaps(int a, int b) {
	
	int c = a ^ b;
	int output = 0;

	while (c != 0) {

		out += c & 1;
		c =>> 1;
	}

	return out;
}

For non sparse numbers, there's not really way to generalize getting a bigger sparse number, so here you just have to increment the number, check if sparse, increment, check (so on and so forth in the brute force approach. Now, let's look at sparse bitstrings:

Assuming they have greater than or equal to 4 bit positions, we can see something:

If it ends in:

1000, we can keep it sparse by adding 1

x1000 -> x1001

If it ends in:

1010, we keep it sparse by adding a 0,

x1010 -> x10100

If it ends in 1001:

x1001 -> 1010


For all other combinations of sparse bitstring, we will do the brute force approach, but this is a quick optimization

It should print out "1"

The thread is started when you call thread.start().
Now there are 2 threads running - the original one that called start, and t.
t will wait until the boolean is set to true in the original thread, then print out "1". Thread t then ends.

public void getSeeds(int n) {
	
	for (int i = 1; i <= n; i++) {

		if (isSeed(n, i)) {

			System.out.println(i);
		}
	}

}

public boolean isSeed(int target, int num) {
	
	return (getDigitProduct(num) * num == target);
}


public int getDigitProduct(int n) {
	
	if (n == 0) {

		return 0;
	}

	return (n / 10 == 0) ? n : getDigitProduct(n/10) * (n % 10);
}

We know that

WWW would be wrong because this violates 2
We know that

BWW would be unfair because the person who sees both whites would win.

The only way this would be generalized to all 3 is if all 3 wore blue hats.

So,
BBB

Node mergeList(Node a, Node b) {
	

	Node currA, currB, currC, cHead;

	currA = a;
	currB = b;
	cHead = null;

	//add first- address edge cases

	if (a == null && b == null) {

		return null;
	}

	if (a == null && b != null) {

		return b;
	}

	if (a != null && b == null) {

		return a;
	}

	if (currA.value <= currB.value) {

		cHead = currC = currA;
		currA = currA.next;
	}

	else {

		cHead = currC = currB;
		currB = currB.next;
	}




	while (true) {

		if (currA == null) {

			while (currB != null) {

				currC.next = currB;
				currB = currB.next;
				currC = currC.next;
			}

			break;
		}

		if (currB == null) {

			while (currA != null) {

				currC.next = currA;
				currA = currA.next;
				currC = currC.next;
			}

			break;
		}

		if (currA.value <= currB.value) {

			currC.next = currA;
			currA = currA.next;
			currC = currC.next;
		}

		else {

			currC.next = currB;
			currB = currB.next;
			currC = currC.next;
		}


	}

	return cHead;

}

edge case:

two intervals that are on different days but would intersect if they were on the same day.

example: 2-5pm on monday, 3-4 pm on tuesday

First, sort the times by end time in a list L. Now, start from the first interval, do interval scheduling to see how many intervals are valid with the first interval.

Remove such intervals and put into one bucket.
Now with the first interval left in L, do the same thing. repeat this process until there are no intervals left in L. The number of buckets generated is the number of rooms needed.

With preorder, we know the first element would be the head, and the second element would be the left child. When we find this head in the inorder, we will know that the node directly to the right of the head in inorder will be the right subchild.

Keep 2 stacks, s1 and s2.

For node 1, traverse down to the root while push Nodes onto the s1 until the root is on top of the stack.

For node 2, traverse down to the root while push Nodes onto the s2 until the root is on top of the stack

Now, pop from both stacks and compare ancestors. If the Nodes popped are the same, it is a common ancestor, so record this as the current ancestor. when it comes to nodes popped that are not the same, we have a reached a non-ancestor. Return the current ancestor to get the least one.

Yes.
Another way you can do this is utilize the k select algorithm on the list, and when the kth element is found, return all distances less than it in the list.

O(n) time

Seems pretty straightforward:

public void outputPairs(int n) {
	

	int prev, curr, temp;
	prev = curr = 1;

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

		printPair(prev % 10, curr % 10);

		temp = curr;
		curr += prev;
		prev = temp;
	}
}

public void printPair(int a, int b) {
	
	System.out.println("["+a+", "+b+"]");
}

Congratulations! :)

This sounds like a type of bucketsort.
Create a hashtable mapping characters in O to a number counting its occurences in t
append characters that don't exist in o to the beginning of the output string.
Finally go through and add the number of a character corresponding to o

public String reorder(String t, String o) {
	
	HashMap<String, Integer> H = new HashMap();

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

		h.put(o.charAt(i), 0);//put o chars in hashmnap
	}

	StringBuffer output = new StringBuffer();

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

		if (h.keyExists(t.charAt(i))) {

			h.put(t.charAt(i), h.get(t.charAt(i)) + 1);//increment the value here
		}

		else {

			output.append(t.charAt(i));
		}
	}


	int copyNum = 0;

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

		copyNum = h.get(o.charAt(i));//get number of times this character occured

		for (int j = 0; j < copyNum; j++) {

			output.append(o.charAt(i));
		}
	}

	returnt output.toString()

}

Recursively check all unique combinations

public List sumOfNumber(int n) {
	
	Hashtable h = new Hashtable();

	sumOfNumberHelper(n, h, "");

	List output = newList<String>();

	for (String s : h.values()) {

		output.add(s);
	}

	return output;
}


public List sumOfNumberHelper(int n, Hashtable h, String prev) {
	
	if (n < 0) {

		return;
	}

	if (n == 0) {

		h.add(prev.hashCode(), prev);
	}

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

		sumOfNumberHelper(n - i, h, prev.append(i))
	}
}

I'll admit I couldn't figure this out on my own and had to look it up.

This is what I found:
Algorithm:

First swap elements in the middle pair
Next swap elements in the middle two pairs
Next swap elements in the middle three pairs
iterate n-1 steps.

Ex: with n = 4.
a1 a2 a3 a4 b1 b2 b3 b4
a1 a2 a3 b1 a4 b2 b3 b4
a1 a2 b1 a3 b2 a4 b3 b4
a1 b1 a2 b2 a3 b3 a4 b4

I'm not really sure, conceptually how it works, so if someone has some insight on that, that would be great. Nevertheless, here is some code implementation of it:

public void fixArray(int[] arr) {
	
	int pairStart, numPairs;

	pairStart = x.length/2;
	numPairs = 1;

	for (int i = 0; i < x.length/2 - 1; i++) {

		swapPair(arr, pairStart--, numPairs++);
	}
}

public void swapPair(int[] arr, int startIndex, int numPairs) {
	
	for (int i = startIndex; i < arr.length && i < startIndex + numPairs*2; i += 2) {

		swap(arr, i, i + 1);
	}
}

public void swap(int[] arr, int e1, int e2) {
	
	int temp = arr[e1];
	arr[e1] = arr[e2];
	arr[e2] = temp;
}

I would assume that the short URL points to a redirection page to the actual website.

This would work, but the bottleneck would be adding numbers to the BST. This would be O(n^2) complexity, worse than just plain sorting the numbers in the first place.

Keep a hashtable (Call it h)
Keep a sum which represents the dot product value (Call it s)

Now, the idea is that we will add to h whatever mapping we encounter when reading the lines. If there is no such mapping for the vector position, we will add the mapping. if there is, then we simply multiply the value by the mapped value and then add it to the sum (s)

Return s.

For example, we first add the key value pair <1, 4>
When we encounter <1, 7>, we see that there already exists a mapping for the key <1>
So we look at the value to that key (4) and multply it by our current value (7) and add to the sum. Same thing happens when <5, 3> is originally added - nothing happens, but when we see that we can add <5, 1>, we multply 3 and 1 and add to the sum.

I assume you said either mergesort or quicksort but backwards, so it sorts from large to smallest.

I don't think there is any real optimization for these.

Yeah this is the algorithm I'm thinking. but it would be O(n) because you check left and right at most twice.

So it would still be O(2n) -> O(n)

public boolean isBST(Node n) {
	
	if (n == null) {

		return true;
	}

	boolean checkRight = (n.right == null) ? true : (n.right.value > n.value) ? true : false;
	boolean checkLeft = (n.left == null) ? true : (n.left.value < n.value) ? true : false;

	return checkRight && checkLeft && isBST(n.left) && isBST(n.right);
}

Agreed. Its a terrible technical interview question and demonstrates an interviewer's incompetence. Something you'd more likely see in a childrens riddle book. Still its a cute little question

First, it might be helpful to use string split here since it saves room.
Two tricky things are just going to be knowing how many days are in each month. secondly, we need to take into account leap years (the formula for which is annoying to remember).
It is a good idea to split up the code when writing this, and you will see that it is not so bad.

public int dayFromDate(String date) {
	
	String[] info = date.split("-");//split the string up so we can retrieve data more easily
	int d, m, y;

	d = Integer.parseInt(info[2]);//parse this info
	m = Integer.parseInt(info[1]);
	y = Integer.parseInt(info[0]);

	int output = 0;

	for (int i = 1; i < m; i++ ) {//go through all of the months starting from january and add the number of days for each month into a sum

		output += numDays(i, y);
	}

	return output + d;
}


public int numDays(int month, int year) {// given a month and a year, return how many days are in that month
	
	int[] days = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

	if (month == 1 && isLeapYear(year)) {// if we encounter a leapyear, and the month we check is february, return 29 instead of 28

		return 29;
	}

	return days[month - 1];
}

public boolean isLeapYear(int year) {// check if a year is a leapyear
	
	return (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0));
}

Good point.

Then basically, I'd arrange it in this way instead.
We are looking for local maxima in the array and then compare the distance between them.

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

	if (bargraph[i-1] < bargraph[i] && bargraph[i] > bargraph[i+1]) {

		//check this local max with the previous local max and find the water between them and add
	}
}

I think this modification should work

I think the intuition is that you know that 2 peaks will either be the same, the first one will be bigger than the other or the second will be bigger than the first. Keep one variable for peak1, one variable for highestPeakSoFar (hpsf)

We will iterate through the bar graph, starting with peak1 = element 0. If we encounter a peak p that ends up being greater than or equal to peak1, we will calculate the amount of water sumOfWater += (Min(peak1, p) - element). Then, we set p as peak1 and repeat the process from there. If we don't encounter a higher peak, we simply set hpsf as the highest peak we've encountered so far that is smaller than peak1. This is because this smaller peak wouldn't affect the water unless it is the final peak.

Finally, if we can't find anymore high peaks, we do the calculation with hpsf,

sumOfWater += (Min(peak1, hpsf) - element)

We are guaranteed To be done with this in 2n operations, which runs in O(n)

first:

{6, 5, 4,3,2,1}

then

{5,6,4,3,2,1}

then

{5,6,3,4,2,1}

then

{5,6,3,4, 1, 2}

I see nothing wrong

It may seem like it's overcomplicating things at first, but the standard way of doing these kinds of problems involve the stack method as it gives a better range of possibilities if we want to expand the problem to take into account, for instance, order of ops, or even parenthetical expressions.

Your solution is definitely more simple, be more space efficient, and just as correct, don't get me wrong, but the stack method gives us more to discuss with a potential interviewer and serves as a good model to understand for a lot of problems similar to this (see checking balanced parentheses problem for example).

Final List should look like:

A: 12
B: 30
C: 40
D: 20

Then you can organize however it needs to be empirically

Hey anon, let's consider the following:

A2((AB3)2(C2D)4)5

First, we know that this is equivalent to:

A2((A1B3)2(C2D1)4)5, so let's work from this one for ease of the algorithm.

Stack: 1

We start out with this.

Now, we begin from the right. We will push a (1 * 5) onto the stack. We do this because we know that whatever is to the left of the 5, there will be 5 of it. We encounter a ")" which means that this multiple will affect everything within some parenthesis, so we won't pop it just yet.

Stack : 1/5

Next, we encounter a 4. We know that whatever is left of the 4 will be multiplied by 4, but also , since we have a 5 on top of the stack, multiplied by 5 because of the outside multiple.

Stack: 1/5/20

We encounter a ")" which means to continue since this multiple will apply to whatever is in the parenthesis.

Encounter a 1, so push (20 * 1) on the stack.

Stack: 1/5/20/20

Now, we encounter our first Element (D), and we know that there will be 20 Ds so far. So in our list of Elements, add 20 to D. Since we encountered an element, we can pop off the stack

Stack : 1/5/20


Encounter a 2, so push (2*20) on the stack.

Stack: 1/5/20/40

Now, we see we have Element C, so add 40 to C in the list and pop off the stack:

Stack : 1/5/20

Since we encounter an open parenthesis "(", we pop off the stack signaling that we are done with an encounter of some in parenthesis expression:

Stack : 1/5

Now, we begin on a new parenthesis set, which is succeeded by a "2":

Stack : 1/5/10

Push (3*10),

Stack : 1/5/10/30

Add 30 to B

Pop 30

Stack : 1/5/10

Push(1 * 10)

Stack : 1/5/10/10

Add 10 to A

Pop 10

Stack : 1/5/10

Encounter a "(", pop 10

Stack : 1/5

Encounter another "(", pop 5

Stack : 1

We see a 2, so push (2*1)

Stack : 1/2

Add 2 to A, pop off 2

Stack : 1

We are done.

I've considered this problem more today and I think it's even more simple than what I had originally explained.

We will keep one stack, call it s. We first begin by pushing a "1" onto s.

Now, we will start reading the string from the end to the beginning. If we encounter a number, we will multiply this number with the number currently on top of the stack and then push this product onto the stack. When we encounter a close parenthesis ")", we will copy whats on the stack and push on top of the stack. When we encounter an open parenthesis "(", we will pop whatever is on the stack. Finally, when we encounter an element, the number that is currently on top of the stack will be the number of atoms of that element is described by that specific portion of the string.

Pretty Straight forward:

public String modify(String orig) {
	
	String[] toModify = orig.split(" ");
	StringBuffer out = new StringBuffer();

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

		out.append( (stringIsOdd(toModify[i])) ? capitalize(toModify[i]) : reverse(toModify[i]) );
		out.append(" ");
	}

	return out.toString();
}

public String capitalize(String s) {
	
	return s.toUpperCase();
}

public String reverse(String s) {
	
	StringBuffer out = new StringBuffer();

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

		out.append(s.charAt(out.length() - i - 1));
	}

	return out.toString();
}

public boolean stringIsOdd(String s) {
	
	return (s.length() % 2 == 1);
}

We know the head will have a null parent. Now that we have a head, we will know the 2nd level of the tree will be the nodes that have the head as a parent, so organize the tree by how those nodes are organized.

You can keep a queue- put 50 into it first, then search the list for nodes that attach to 50. add those to the queue. dequeue 50. search the list for nodes that attach to the nodes in the queue, add to the queue and dequeue the lists you found nodes for. continue this process until both the list and the queue are empty.

Some very loose pseudocode:

buildTree(list) {
	
	Node head;
	Queue treeQueue = ;// initializeQueue

	for (info in list) {

		head = node who's parent is null;
	}

	list.remove(head);
	treeQueue.enqueue(head);

	Node current;
	while(list != empty) {

		current = treeQueue.dequeue();

		for (node in list) {

			if (node's parent is current) {
				
				enqueue(node);
				
				if (node.isLeft) {	current.left = node;} else {	current.right = node}
			}
		}

	}


	return head;
}

For the first:

isSame(Node n) {

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

	Node l = n.left;
	Node r = n.right;

	boolean a, b, c;

	a = (l == null) ? true : (l.value == n.value) ? true : false;
	b = (r == null) ? true : (r.value == n.value) ? true : false;
	c = (l == null) ? true : (r.value == l.value) ? true : false;

	return (a && b && c && isSame(l) && isSame(r));
}

Oh. I see now. I misread and assumed you were incrementing by one.

anon is correct. By the third iteration, the array would look like this:

[10, 12, 20, 80, 100]

since we have already looked an index 1 we can't change it.
This algorithm is a bit too localized.

You can merge/quick sort, then add to the array like the following:

index i = 0
index j = 2

loop:
add arr[i]
add arr[j]
i++
j++
add arr[i]
add arr[j]
i+=3
i+=3

We know that we will have encountered a sentence by the time we have reached a period in a string. So, what we can do is create a queue, enqueue all strings until a period is reached. Then we create a new queue and repeat the process. There should be one queue for each sentence. Finally, starting from the first queue until the last queue, dequeue and print, then start from the first queue again until the last queue- dequeue and print. Continue this process until all queues are empty

Usually with this, we'd use the shunting yard algorithm to evaluate this with order of operations- convert to RPN then use 2 stacks. Since order of ops is being ignored here, this makes our lives a lot easier.

Keep one stack for numbers and another for operators. Start from the end of the string, pushing numbers on top of the number stack and operators on top of the operator stack.

Now that every number is pushed on the number stack and every operator is pushed on the operator stack we begin.
With whatever operator is on top of the operator stack, pop the top number, use the operator on the popped number and the currently top of the number stack number, then place this resulting number on top of the number stack. Pop the operator from the operator stack.

Repeat this process until there is one number on the number stack and no operators on the operator stack. If this isn't the result, then the string is invalid.

Assume you have k processors/cores.
We will now create k queues of Messages, one for each processor. The idea is now that each core will process Messages in its respective queue.

Now, when publisher sends a message to the broker, the broker will put the message in the queue with the least number of Messages currently in it, which would be in O(k) time. If k is a small number, like 4 or 8, this would be trivial. However to scale up with many different processors, you could use a min heap to keep track of the queues that have the least number of messages.

If we assume that the MessageBroker is what contains the mapping between publisher and subscriber, then simply keep a hashtable that holds this mapping. Because processors would only read the hashtable for mappings, without changing it, then this would be threadsafe and there would be no need for mutex in the general case. However, if subscribers needs to be updated by the broker, processing can be stalled to do updates with the mutex.

If we want to scale up, the hashtable could be split, so that updates in one partition of the hashtable wouldn't affect performance of reading other partitions.

The idea here is that given some node N, if it is a left child of node M, we want to find the fixed value of M, then add this value to N since M will be bigger than N.

Then, we want to find the fixed value of N by adding the sum of every right child of N.

public int fixBST(Node current, int parentValue) {

	if (current == null) {
		
		return 0;
	}

	current.value += fixBST(current.right, 0) + parentValue;
	fixBST(current.left, current.value);
	
}

Assume that we start out with 2 people in A, 3 people in B, and 5 people in C. We are currently maintaining the ideal percentage. Now, if we decide to add a person to a room, there is no way we can maintain this ideal percentage because we will have 11 people, so we can't get the exact percentages since you can't put a fraction of a person into a room. The best place to add a person would be in the room with the highest percentage since this would lead to the smallest difference of ideal percentages over all of the rooms.

So we know that in the case that we have an ideal percentage, we should add a person to the room with the highest ideal percentage (in this case, room C).

Now, we can see that the percentages of the rooms will be lower for A and B, but higher for C. Since we can't take people out of rooms, we can only add people. Adding to C would be unwise, since it is already over the ideal percentage, so we will look at A and B. whichever has a greater difference that is lower that the average, we will add a person to the room.

We continue this heuristic to get the best case percentages at any given time...

With this heuristic, we add in this order to each room:

CBACBCACBC

If you go through it, you will see how stable the percentages are throughout

You can keep a secondary 2D array with each element keeping 2 boolean values P and A.
Pass through the perimeter elements of the continent and check to see if these values have direct access to P or A. Then Pass through again checking to see if they have direct access to P or A, again through neighbors with smaller heights.

Now that we have checked the outer perimeter, we will check the first inner perimeter twice again- Check all outward neighbors of elements- if any of these outward elements are smaller in height, OR the current element's A and P boolean values with that of the neighbors.

Continue this until you get to the middle element.

Finally, pass through all of the elements and return those that have both boolean values set to true.

Assuming rectangle with height of m and width of n,

Runtime: 3m*n
Space: m*n

Basically, find the height of the tree

I did the same thing, except i compare the last characters instead of the first. Good solution.