CareerCup

Recursive Solution:

public int findDisc(String a, String b) {
	
	return findDiscHelper(a, b);
}

public int findDiscHelper(String a, String b) {
	
	int count = 0;

	for (int i = b.length() - 1; i >= 0; i--) {

		if (b.charAt(i) == a.charAt(a.length()- 1)) {

			count += (a.length() <= 1) ? 1 : findDiscHelper(a.substring(0, a.length() - 1), b.substring(0 , i) );
		}
	}

	return count;
}

}

public String compressString(String s) {
	
	
	String out;
	int currentCounter = 1;

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

		while (i < s.length && s.charAt(i) == s.charAt(i - 1)) {

			currentCounter++;
			i++;
		}

		out += s.charAt(i-1) + currentCounter; 
		currentCounter = 0;
	}

	return out;
}

We know that if we have a rectangle (width = x, height = y), that the number of ways to get from the top left corner of the rectangle to the bottom left corner of the rectangle with right and down movements will be C(x + y, x) [which is also C(x + y, y)], because this represents the way we can order R and D movements so that we end up at our destination.

Now, we can apply this to the grid by finding rectangles created by entry and exit points - such that these points represent opposite corners of a rectangle, plug in the width and height of the given rectangle into C(w + h, w), and then sum these values to get the total paths.

Runtime should be O(n^2)

I'm not sure if this is what you want, but I guess it is important to note that small bags can fit in small, medium, and large slots. Medium can fit in medium and large slots, but can't fit in small slots. And large bags can only fit in large slots (can't fit in small or medium slots). Here, we see that the token numbers should give the greatest flexibility to small bags, medium flexibility to the medium flexibility to the medium bags and low flexibility to the big bags. You can simply have 3 hashtables, one for each bag type. In the small bag hashtable, you have k slots. In the medium bag hashtable, you have 2k slots (for every possible k bags, there are 2 spots reserved- one for medium one for small). In the large bag hashtable, you have 3k slots ( 3 spots reserved - one small, one medium, one large). You can definitely set up the token number so that the token number used is flexible because of the space that is reserved for the different kinds of bag.

This is basically an application of BFS. We will keep 2 queues- one representing one level and the other representing another.

We start by putting the head in the first queue (Q1). Now, we BFS the head, and add all of its children to Q2 in order. We remove the contents of Q1 and make it a linked list. Now, we BFS Q2 and put all of the children of nodes in Q2 into Q1. Remove the contents of Q2 and make it a linked list. Continue this process of alternating BFS between queues until there are only null values in a queue.

Some Code:

ArrayList linkedListify(Node head) {
	

	Queue q1, q2; //assume these are initialized or whatever
	q1.enqueue(head);

	ArrayList<LinkedList> ANSWER;

	int counter = 0;
	while (true) {

		LinkedList x = (counter % 2 == 0) ? convertQueueToLinkedList(q1, q2) : convertQueueToLinkedList(q2, q1) ;

		if (x == null) { break; }
		counter++;
	}

	return ANSWER;


}

LinkedList convertQueueToLinkedList(Queue q1, Queue q2) {
	
	
	if (q1.size() == 0) { return null; }
	LinkedList list;//initialize
	Node current;

	Node listToAdd = q1.dequeue();
	q2.enqueue(listToAdd.left);
	q2.enqueue(listToAdd.right);
	current = list.head = listToAdd;
	

	while (q1.size() != 0) {

	 	listToAdd = q1.dequeue();
		q2.enqueue(listToAdd.left);
		q2.enqueue(listToAdd.right);

		current = list.head = listToAdd;
		current = current.next;
	}

	return list;
}

[1,2,2,3,3,3, 3, 5,6,7,8,9,10,11,12,13]

Arr[n/8] = Arr[2] = 2
Arr[n/4] = Arr[4] = 3
Arr[3n/8] = Arr[6] = 3

In this pathological case, n/8 != n/4, but there is indeed a majority element at 3

[1,2,3,3,3,4, 4, 5,6,7,8,9,10,11,12,13]

Arr[n/8] = 3
Arr[n/4] = 3
Arr[3n/8] = 4

It would see the 3, even though 3 doesn't happen n/4 times

If we assume we can't use regex. (Since that would somewhat trivialize this problem)

You could populate the hashtable by recursively running through all the strings and replacing * in the strings to make all combinations of letters and *.
If the length of the longest string is k, then the population of the hashtable runs in O(n * 2 ^k), but then lookup is just O(1).


You can populate the hashtable with something like the following code called on every string s with the following function call:

Example:

populateHashTable(hashtableObject, "ahmed", "", 0);

populateHashTable(HashTable h, String original, String edited, int currentCharIndex) {

	if (currentCharIndex >= s.length) {

		h.add(edited, true);
		return;
	}

	populateHashTable(h, original, edited + original.charAt(currentCharIndex), currentCharIndex + 1);
	populateHashTable(h, original, edited + "*", currentCharIndex + 1);
}

We can solve this by memoization. For the given array "a", we will create a 2d array called "val" which will tell us information about the corresponding index at a. For every index in val, there are 2 values- one is a pointer which points to the most previous value that is both lower than the current value we are looking at and has the most previous values in a subsequence. The second one tells us the number of values in the subsequence that the current element is in.

For example, given:

[1,10,4,5,6, 11]

vals[1][0] = 0 (10 points to 1) -> vals[1][1] = 2
vals[2][0] = 0 (4 points to 1) -> vals[2][1] = 2
vals[5][0] = 4 (11 points to 6 and not 10 because the subsequence at 6 is bigger than that of 10) vals[5][1] = 5

We just basically need to go through all of the indices in the array from left to right and populate vals.
Then, we can check which of the second values in vals is maximum. Here, we just unwind the sequence by following the pointers. Use a stack here to add to a String and the print out b.

getB(int[] a) {
	

	int[][] vals = new int[a.length][2]; //0 index is the pointer, 1 index is the number of previously visited

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

		vals[i][0] = -1;
	}

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

		checkBackwards(a, vals, i);
	}


	int maxValElement, maxValIndex;
	maxValElement = maxValIndex = 0;

	for (int j = 0; j < vals.length; j++ ) {

		if (vals[j][1] > maxValElement) {

			maxValIndex = j;
			maxValElement = vals[j][1];
		}
	}

	unWind(a, vals, maxValIndex);
}

checkBackwards(int[] a, int[][] vals, int currentElement) {
	
	
	int maxElement, maxIndex;
	maxElement = maxIndex = 0;

	for (int i = currentElement; i >= 0; i--) {

		if (a[i] < a[currentElement] && vals[i][1] > maxElement) { 

			maxElement = vals[i][1]
			maxIndex = i;
		}
	}

	vals[currentElement][0] = maxIndex;
	vals[currentElement][0] = vals[maxIndex][1] + 1;
}

public void unWind(int[] a, int[][] vals, int element) {
	
	Stack s = new Stack;
	int currentVal = element;

	while(vals[currentVal][0] != -1) {

		s.push(a[currentVal]);
		currentVal = vals[currentVal][0];
	}

	s.push(a[currentVal]);

	while (s.size() > 0) {

		System.out.print(s.pop()+", ");
	}

}

hey thanks! :)

Something like the following:

We modify an inorder traversal to keep track of pointers to the "current" Node we are on in the list. We can also keep track of the head and tail of the list and after the inorder traversal, we simply link up the ends of the lists to make it circular.

I wrote this quickly, so there may be some syntax bug with the pointer logic (haven't done C pointers in a while) but I think it is the correct logic:

makeCircularList(Node treeHead) {
	
	Node *head;
	Node *tail;
	Node *current; 
	
	modInorder(treeHead, current, head, tail);

	tail -> right = *head;
	head -> left = *tail;
}


modInorder(Node n, Node *current, Node * head, Node * tail) {
	
	if (n == NULL) {

		return;
	}

	Node previous;

	if (*head == NULL) {

		head = &n;
	}

	tail = &n;

	previous = modInorder(n.left, current);

	current -> right = n;
	current = &n;
	current -> left = previous;

	modInorder(n.right, current)

}

Some Code:

public void findMinAndMax(int[] arr) {
	
	
	for (int i = 0; (i + 1) < arr.length; i+=2) {

		if (arr[i] > arr[i + 1]) {

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

	int minIndex, maxIndex, minimum, maximum;

	minIndex = 0;
	maxIndex = 1;



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

		if (minIndex < arr.length && arr[minIndex] < minimum ) {

			minimum = arr[minIndex];
		}

		if (maxIndex < arr.length && arr[maxIndex] > maximum ) {

			maximum = arr[maxIndex];
		}

		minIndex++;
		maxIndex++:
	}

}

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

Regular way of doing this is basically find minimum and maximum values each in O(n) operations, but you can do both at the same time in 3n/2 operations.

First, compare all consecutive pairs of elements, order them, then check even elements to get the min and check the odd elements to get the max.

First, pass through the array and check how many 0s there are. If there is more than one zero, then all the array elements in the output array MUST be 0.

If there is only one 0, then replace it with a 1.

After our first pass through, we will go through the array and get the product of all the array elements. let's call this product x.

Finally, we go through the array and for each element "e" in the array, its corresponding value in the new array will be x/e.

This algorithm would, thus, run in O(3n) = O(n).

I'm pretty sure that it would also work with negative numbers.

You can probably weight the trie by most used for the prefix string. Whichever path on the trie has the most weight will be displayed

Trie data structure

Use a stack for recently visited sites. Pop off the stack to go back to the most recent site.

You can scan all rows, scan all columns, and scan diagonals, but instead of multiplying 4 numbers everytime, you can just do a kind of rolling multiplication - I think this is what the interviewer is looking for as far as optimization.

Say you have a row:

3,4,1,2,5,4,3

calculate x = 3*4*1*2
then when you roll, divide the first number and multiply the next number, so

x /=3
x *= 5

Of course, you can't divide by 0, so when the first number is a 0 and the new number isn't, you need to re-multiply

That way you only do 2 operations rather than 4 operations every step

Sure, (Also I made a mistake- should be left and downward, not right and downward)

Let's say our matrix is the following:

00011111
00001111
00111111
01111111
00001111

We know that the max 1 row will be the one where we reach a 0 the latest from the left. Start from the top right. Scan left until we reach a 0. When we reach a zero, record the column we are on- if this column is lower than the max row column, then we set it as the max row. When we reach 0, go down the column until we reach a 1, when we get to this scan left again until we reach 0, doing the same process. When we are at the last row and at a 0, we are done.
First row, we scan left until we get to the x
000x1111
00001111
00111111
01111111
00001111

Scan down to the first 1 we get:

00011111
00001111
001x1111
01111111
00001111

Scan left again:

00011111
00001111
00x11111
01111111
00001111

Scan down until we reach a 1:

00011111
00001111
00111111
01x11111
00001111

Left to get to zero:

00011111
00001111
00111111
0x111111
00001111

Down to the last row:

00011111
00001111
00111111
01111111
0x001111

We have seen that the row that had the smallest column was the 2nd to last one, so this is our answer. Because at worse cast we step down from top right to bottom left, we find the answer in at most 2n operations

Bucket sort. Set a hashtable of length 10.

Scan the array and increment the numbers in the array when that number is found in the array.Finally, overwrite the array with the information from the hashtable.

The idea here is to scan right until you reach a 1, then scan down until you reach a 0, then right until you reach a 1, continue this cycle and record when you reach a new 1. This will be your max row.

We just want the left view, so what we can do is keep an array to hold the nodes we encounter in a traversal. We will traverse the right side before the left, ultimately overwriting nodes that are right-most with ones that are left most.

void printLeftSide(Node head) {
		
		Node[] left = new Node[getTreeHeight(head)];
		traverse(head, 0, left);
		
		print(left.toString);

	}

	void traverse(Node curr, int depth, Node[] arr) {

		if (curr == null) { return; }

		traverse(curr.right, depth+1, arr);

		arr[depth] = curr;

		traverse(curr.left, depth+1, arr);
	}

	int getTreeHeight(Node head) {
		
		if (head == null) { return 0; }
		return Max(getTreeHeight(head.left), getTreeHeight(head.right)) + 1;
	}

Linear search is O(n).

Sort each input array by the first number in the array:
[4, 8], [3, 5], [-1 2], [10, 12] -> [-1 2], [3, 5], [4, 8], [10, 12]

Then compare the last number of an array (L) with the first number (F) of the next array. If L + 1 is strictly < than F, then output the range we have visited so far.

We know that any number that only has 1s an 0s can be interpreted as a bit string.
We know that since our maximum bitstring for long is 1111111111 that this is the bit representing 1023.

So we simply find a conversion from all integers from 1 to 1023 (inclusive) to their corresponding bitstring values then check if this bitstring can divide our given number.

It is possible to avoid the overhead of String to long conversion by simply writing your own method for the conversion from int to long directly.

The function convertDecToLong runs in 32 operations since it will bitshift at most 32 times. Running this operations something around 1023 times will give us an estimated ~32000 operations - much better than the brute force of 1111111111 operations.

public static long min(int n) {

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

                long possibility = convertDecFromBin(i);

                if (isDivisible(possibility, n)) {

                        return possibility;
                }
        }

        return -1;
}

public static long convertDecFromBin(int n) {
       
        long output = 0;
        int x = n;
        int currentDecPlace = 0;
        while (x != 0) {
 
                output = ((x & 1) == 1) ? (output + (long)Math.pow(10, currentDecPlace)) : output;
                currentDecPlace++;
                x >>= 1;
        }
 
        return output;
}

when i = 5, it will see that log(125)/log(5) = 3 which is an integer

what do you mean it doesn't work?

s = our string

Keep two pointers. p1 is always one element behind p2. Every iteration, both are incremented. We check if s[p2] == s[p1] or s[p1-1]. If so, we know that we have a palindrome in some form, so we start recording the string with 2 pointers- iterate outwards until the palindrome ends and record all of the "visited" strings into an output table.

For example with the String "4racecarses", p1 and p2 are incremented until p2 = 5 and p1 = 4, s[p2] = s[p1-1]. Now, we iterate outwards: cec -> aceca -> racecar -> stop at 4racecars since the outward pointers won't match.

Back to the original loop, p2 is then at 6. Until it gets to the final element, it won't find a potential palindrome

In the end, add all single characters to the list

Perfect powers in linear time?

boolean isPerfectPower(int n) {
	
		for (int i = 1; i < n; i++) { 
		
			double temp = Math.log(n)/Math.log(i);
			
			if (Math.ceiling(temp) == temp) { return true;}
		}

		return false;
	}

This is still O(n^2) with slight optimization

The algorithm is something like this:

You need to use two stacks. one for operator, one for numbers.

When you add two numbers onto the number stack and add an operator, you check if the previous operator (on the stack) is of higher precedence. if it does, then you calculate those numbers first.

I apologize, but I'm not sure what you do when you have parentheses though - it has higher operator precedence so I think you calculate everything in it until you get a close parenthesis?

Shunting yard algorithm is for converting from regular notation to reverse polish notation.

What information are you given? What if P1 beats P2, P2 beats P3, and P3 beats P1?

If we arrange our bookings in an array {b1, b2, b3, b4,...}, we can do interval scheduling multiple times for each cab. Arrange bookings by end time into an Array A. Perform interval scheduling on A, then assign these bookings to the first cab. remove these bookings from A, then perform interval scheduling again, assign bookings to the second cab...repeat this process until there are no more bookings left to process.

We loop throught and check each character with the one right before it in a while loop to see if a sequence is emerging. When the while loop is done (the streak ends), we see if we update the max value, and if we do, we also update the longest character.
Default returns the first character in the string.

char longestConsecChar(String s) {
	
	int k, cnt = 1;
	char longest = s[0];

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

		while (s[i] == s[i-1] && i < s) {

			cnt++;
			i++;
		}

		if (k < cnt) { 

			k = cnt;
			longest = s[i-1]; 
		}

		cnt = 0;
	}
}

The longest consecutively repeating character repeats k times. Return all characters that repeat k times in the order that they appear left to right

public static void printASCII() {
	
	asciiHelper(0);
}

public static void asciiHelper(int x) {
	
	if (x < 256) {
	
		System.out.println((char) x);
		asciiHelper(x + 1);
	}
}

I'm not sure of an O(n) solution, but I'm pretty sure you can do this in O(nlogn) using modified merge sort.

On each merge you do in merge sort, you have a left subarray (L) and a right subarray (R).

Assume that L has a candidate difference (CDL) and R has a candidate difference (CDR). On the merge, find the min from L and the max from R to get a candidate difference between L and R (CDLR). Now, for the array that L and R merge into, we will take Max(CDL, CDR, and CDLR) to be the candidate difference for the merged array.

Recursively, the answer bubbles all the way to the top.

Not enough time to complete the code, but this is the basic idea. We modify merge sort, so that whenever we add in an element from "the left side", we will add the difference between the end of the right side and the right side iterator to a hashed stored value for the element's qez.

For example, if we merge:

[11, 10, 5, 12, 20]

Our steps look like this:

[11, 10] -> [10, 11], No QEZ
[5, 12] -> QEZ of 5 is 1
[5, 12], [20] -> QEZ of 5 increases by 1, QEZ of 12 becomes 1

now when we merge

[10, 11] and [5, 12, 20]

[5] -> no QEZ change
[5,10] -> QEZ of 10 is now 2 because right pointer is pointing at 12
[5, 10, 11] -> QEZ of 11 is 2 because right pointer is pointing at 12
[5, 10, 11, 12, 20] -> No QEZ change for 12 and 20 since while loop ends the merge

Not enough time to complete the code, but the basic gist of the merge method is like this:
end refers to the location of the end of right pointer so in the case of [10, 11] and [5, 12, 20], right would be = to 2 and end would be equal to 2 + 2 = 4.
Sorry, again for incompleteness

merge(int[] arr, int[] new, int l, int r, int end, HashMap hm) {
  
  boolean done = false;
  int i = l;
  int j = r;
  int k = l;
  while(!done) {

    if (arr[left] >= arr[right]) {

      new[k++] = arr[j++];
      //handle ending case of merge here
    }

    else {

      new[k++] = arr[j++];
      hm.put(arr[k], hm.get(arr[k] + (end - j)) );
    }
  }

}

The Catalan sequence will give you the number of ways of arranging a binary tree, but binary search tree becomes more difficult because ordering matters there.

I'm not sure of any other way of doing this other than brute force...

You can use a hashtable with strings as a key and an inUse boolean as a value.

When clients request a string, they are put in a queue to use the string if its inUse value is found to be "true".

It's basically a kind of manual implementation of mutex in multithreading

@soup:

yes, you make a valid point.
In this case, I am not sure that there is really a way to do Mode in O(1) - I can only think of changing the stack to a priority queue, in which case it would work, but wouldn't be O(1)

Even indices = stack 1
Odd indices = stack 2

Keep 2 pointers - one for top of each stack

This is, I think easier to implement than the stacks starting from the ends and meeting inwards, but it will not work very well if one stack if being underutilized

If gems are not less than 1 then the value will never be able to decrease, so simply keep updating the value in one loop, assuming we have already passed even number of Reds

I think you would need a double for loop. In the outer loop, you iterate through all the houses to find one to begin at, then in the inner loop with the starting house defined in the outer loop, you will go through the rest of the houses and check to see what the best values you can make are, by continuously multiplying by the gems you encounter and only updating the values if you have visited an even number of red houses. I make an assumption that you can't have negative gems but that you can encounter a house with 0 gems, in which case your range will mess up, so you break out of the inner loop since there's nothing more you can do if you continue (since you will just multiply by 0).

int[] rangeHouse(char[] house, int[] houseGem) {

	int[] optRange = new int[2];
	int bestVal = 0;

	int currentStart = 0;
	int currentEnd = 0;
	int currVal = 1;

	int redCount = 0;

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

		redCount = 0;
		currVal = 1;

		currentStart = i;
		currentEnd = i;

		for (int j = i; j < house.length; j++) {

			if (houseGem[j] == 0) { 

				break;
			}

			else {

				currVal *= houseGem[j];
				if (house[j] == 'R') { redCount++; }

				if (redCount % 2 == 0 && currVal > bestVal) {

					optRange[0] = currentStart;
					optRange[1] = currentEnd;
					bestVal = currVal;
				}
			}
		}
	}

	return optRange;
}

Other than if multithreading occurs, what benefit does this have over just having 1 large hashtable for the whole thing?

Could you elaborate on what you mean by "unique"?
For example, I can look at the first URL in the list and see that there are no duplicates thus far and it will be considered unique...

I don't know if you are allowed to use complementary data structures, but I guess this works - we use a queue for insert and FIFO removal. We use a hashtable to keep track of modes of nodes, and finally we keep chronological track of modes with a stack (if we remove a mode, it will take us O(n) to search for the next one in the hash table, but we want this to be O(1)).

class DS {
		
		HashTable<Node, Integer> ht;
		Queue q;
		Stack modeStack;
		Node currentMode;
		int modeNum;
		
		insert(int element) {
			
			Node curr = Node(element);
			q.enqueue(curr);
			int checkMode =  ht.getValue(curr) + 1;
			ht.put(Node, ht.getValue(Node) + 1);
			
			if (checkMode > modeNum) {
				
				curr = currentMode;
				modeNum = checkMode;
				modeStack.push(curr);
			}
		}


		remove() {

			Node curr = q.dequeue;
			ht.put(curr, curr.getValue() - 1);
			
			Node modeTop = modeStack.pop();
			Node modeSecond = modeStack.peek();

			if (ht.getValue(modeTop) < ht.getValue(modeSecond)) {
				
				currentMode = modeSecond;	
				modeNum = ht.getValue(modeSecond);
				return;
			}
	
			modeStack.push(modeTop);
		}

		findMode() {

			Node mode = modeStack.pop();
			
			currentMode = modeStack.peek();
			modeNum = ht.getValue(currentMode);

			return mode;
		}

	}

String reverseSentence(String s) {
			
		char temp;

		for (int i = 0; i < s.length / 2; i ++) {
			
			temp = s[s.length - 1 - i];
			s[s.length - 1 - i] = s[i];
			s[i] = temp;
		}
		
		int p1, p2;
		p1 = p2 = 0;

		for (int i = 0; i < s.length(); i++) {
			
			if (s[i] == ' ') { 
	
				reverseChar(s, p1, p2); 
				p1 = p2 = i + 1;
				continue;
			}

                        p2++;
		}	
			
		return s;	
	}

	void reverseChar(char[] c, int a, int b) {

		//implement a reverse of char array at specific range here...
	}

We can exploit a post-order traversal for our needs

public void mirror(Node n) {
		
		if (n == null) { return; }
		
		Node left = n.left;
		Node right = n.right;

		mirror(n.left);
		mirror(n.right);
		
		n.right = left;
		n.left = right;
	}

In that case, then we can simply keep a second stack and add closing brackets if it is unable to pop from the first stack. Then at the end, return the sum of the sizes of both stacks