CareerCup

Bloom filter will work only for the false case, not the true case.

One other way to optimize for space could be to keep two levels of hashsets. One regular one, one for contiguous ranges. If in your regular hashset you find that you have hashed numbers in, say, a contiguous block of 10 (like 0-9 inclusive), you can remove them from regular hashshet and then add 1 to your range hashset. Now, as you are checking a new number n, check to see if n/10 exists in the range hashset. If not, check in the regular hashshet.

This can incredibly reduce your space usage.

One more thing, this seems more like an open ended question to see how many questions you can ask about details and come up with different solutions for it rather than one with one correct answer.

def diff_char(s1, s2, idx=0):
	if idx >= len(s1) or idx >= len(s2) or s1[idx] != s2[idx]:
		return "MISMATCH AT INDEX {}".format(idx)
	return diff_char(s1, s2, idx+1)

Assume 32 bit integer

bit_vector = vector<int>;

void setTrue(index) {
	int remainder = index % 32;
	bit_vector[index/32] |= 1 << remainder; 
}

void setFalse(index) {
	int remainder = index % 32;
	bit_vector[index/32] &= ~(1 << remainder); 
}

void setAllTrue() {
	for (int& i : bit_vector) {
		i |= 0xFFFF;
	}
}

void setAllFalse() {
	for (int& i : bit_vector) {
		i &= 0;
	}
}

bool getIndex(index) {
	int remainder = index % 32;
	return (bit_vector[index/32] >> remainder) & 1;  
}

def reverseString(theString):
	operatorList = ['*', '+', '-', '/']
	finalString = ""
	i = len(theString) - 1
	while (i >= 0):
		currentNum = ""
		while (i >= 0 and theString[i] not in operatorList):
			currentNum = theString[i] + currentNum
			i -= 1
		
		totalString += currentNum
		if (i >= 0):
			totalString += theString[i]
		i -= 1

Build a trie for the words. Traverse the trie and add words to each list depending on the root of the trie.

Let's look at the pattern of binary representations of consecutive ones vs. non-consecutive ones. Let's shift the number over by 1 bit (on the bottom):

01001
10010

01101
11010

011001
110010

We see that if we AND the numbers, consecutive-one numbers produce non-zero values, so our check if the binary representation has consecutive ones is this;

bool consecutiveOnes(int n) {

	return ((n << 1 & n) != 0);
}

Call Quick select, but bound it on indices a and b

dumb problem

just put a guard in front of wherever the shooter is pointing

Loop through checking the following condition:

boolean isIntersecting(float[] arr, int n) {
	
	if ((arr[n-1] < arr[n - 3]) && (arr[n] > arr[n-2])) {
		return true;
	}

	if (n < 5) {

		return false;
	}

	if ((arr[n-1] < arr[n - 3]) && (arr[n - 5] > arr[n - 1]) && (arr[n] > (arr[n-2] - arr[n-4])) {
		return true;
	}

	return false;
}

do malloc of size (sizeInBytes+sizeAlignment), then from the starting pointer, find the first address that %sizeAlignment gives you 0.

if size is 1000 and alignment is 64, and malloc gives you a pointer at location 129 for example, it will extend from address 129 to 1093. From 129, we need to find the first pointer that %64 is 0, so we do (129/64 + 1)*64 = 192. From 192, we mark this as the beginning of the allocated space, and we mark 192 + 1000 -> 1192 as the end of the block.
Not sure how to stop memory from being used though.

To delete, Keep track of this distance from the new pointer to the original malloc pointer address.

Unless you already have movie hashtag as a key to number of tweets for all the possible hashtags, you will need to hash all those key value pairs

Cumulative Multiplication from the left ( discounting at the point ):
{1, 2, 8, 24, 120}

Cumulative Multiplication from the right (discounting at the point):
{360,90,30,6,1}

Now multiply these 2 arrays together

So you need to hash it first

obviously. call it a bit vector that could be of any size and it would work.

brilliant

Fixed it. sorry haha

isOn(int lights, int i) {
		
	return ((lights >> i) & 1);
}

toggle(int lights, int start, int end) {
	
	int mask = 1 << (end - start + 1);
	mask -= 1;
	lights ^= mask << start;
}

Langford pairing uses set cover which is NP complete. Your interviewer sucked

Keep a stack, then iteratively, find the path from the head to the Node you are considering. Each node you visit, push onto the stack. Now, when u reach your target node, you will begin to pop from the stack. The first Node you pop from the stack that has a higher value than your target node is the inorder successor. If all of the nodes on the stack are smaller than the target node, your target node is the last Node in the inorder traversal so the next node after that must be null.

public Node findSuccessor(Node n, Node head, Stack s) {

		Node current = head;

		while (true) {

			if (current == null || current.value == n.value) {

				break;
			}

			if (current.value < n.value) {

				s.push(current);
				current = current.right;
			}

			else if (current.value > n.value) {

				s.push(current);
				current = current.right;
			}

		}

		while (s.size() > 0) {

			if (s.peek().value > n.value) {

				return s.peek();
			}

			s.pop();
		}

		return null;
	}

reservoir sampling

brilliant!

Assume
k = # of digits per number
n = # of numbers in file

Suffix Tree for the numbers. Assume O(k) suffix tree construction for each number. Then, we would perform this n time for a suffix tree construction of O(nk). Now, we can simply look up the number in the suffix tree in O(k) time.

boolean isPowOfTwo(int n) {
	
	return (n > 0 && (n & (n - 1) == 0)) 
}

be sure to check that n > 0 since negative numbers aren't powers of 2

We can keep nodes and connections between nodes represents friendship. Each Node can have a hash table of "Liked Things". Such that every time a person likes something, there will be an observer object for all friends. Then the observer checks to see if the "Liked Object" exists in the respective Node's hashtable.

Create a Node for each Entry with the following structure:

Node {

List<Strings> info
int index
boolean visited

}

For every string entry in "info", hash the Node into the Hashtable. Then, for each node, run DFS. Add all the Nodes to a visited list, and make a set out of these nodes. Next, run DFS for another Node. We know that if it is visited, then it already exists in the set. Keep running DFS until we exhaust all Nodes.

This can be written in a recursive fashion as such:

F(M, N) = F(M- 1, N) + F(M, N- 1)

Because we have to maintain the order of processes. If we started with Ma, next could either be Mb or Na (which is represented by F(M- 1, N)). Likewise, if we start with Na, next could either be Nb or Ma (which is represented by F(M, N - 1)).


In code, something like this could work:

public int num(int m, int n) {
	
	if (m <  0 || n < 0) {

		return 0;
	}

	if (m == 0) {

		return 1;
	}

	if (n == 0) {

		return 1;
	}

	return num(m , n-1) + num (m - 1, n);

}

We can then memoize to make it more efficient.

good point. fixed.

boolean isAPowerOfTwo(int n) {

return ((n > 0) && (n & (n - 1)) == 0);

}

If we have something like a1 > a2, a2 > a3, a3 > a1, we know that there is no ascneding order. So we can create a graph based on the comparisons. Create nodes for each element. and then if element x > element y, direct the graph from node y to x. Run some sort of graph algorithm like DFS with cycle detection. If we detect a cycle, we know that we can not order in ascending order.

You have to take into account the fact that cuboids might not fit directly into the bigger cuboid- the volumes might be divisible, but physically, it might not be viable.

For example, if we take rectangles of size 4x3, our area would be 12. If we try to fit squares of 2x2 into that area, at first we might think just to divide 12 by 4 to get 3 squares that fit, but if you actually draw it out, you can only really get 2 squares to fit.

So, we need to break this down based on how many ways we can divide each dimension by 2, and take the floor of that, since anything above that would just be extra space.

boolean canFit(int x, int a, int b, int c) {
	
		return (((a/2)* (b /2) * (c/2)) >= x);
	}

Keep k variables. Each variable represents a factor. Each iteration, output the min variable then increment it by the respective factor. If a variable is equal to the currently output value, increment it (to avoid duplicates). When you've outputed n numbers, you are done.

O(kn) time, O(k) space

public static void printFactors(int[] values, int n) {

		int[] variables = new int[values.length];
		int output = 0;
		int i = 0;

		int toIncrement = 0;

		while (i < n) {

			toIncrement = 0;

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

				if (variables[j] < variables[toIncrement]) {

					toIncrement = j;
				}
			}

			if (output < variables[toIncrement]) {
				
				output = variables[toIncrement];
				System.out.println(variables[toIncrement]);
				i++;		
			}

			variables[toIncrement] += values[toIncrement];
		}
	}

y = a ^ ((a ^ b) & (x))

Find max element with binary search. Then do binary search on the subarray of all numbers to the left of the max, then do another binary search on subarray on all numbers to the right of the max.

log(n) for max
log(n/2) for left subarray
log(n/2) for right subarray

-> 3log(n) time -> O(logn)

C(M + N, N) or C(M + N, M)

Hash the values of all elements. Then go through, and for each element x, check if x + 1 or x -1 exist in the hashtable. If so, add such elements to a specific set. With all the sets, go through and check which set has the greatest number of elements. Return that set.

topological sort to get the graph detailing prerequisite, then dfs from starting nodes, to get the number of semesters needed

Binary search to find the key, then look to the left and to the right of it until the number changes

Heap gives answer in N*log(K) which is slightly better.

keep a heap. add elements to the heap until it reaches k elements. when this happens, keep adding elements, but for every element added, remove the min from the heap and output it. when there are no more elements, remove and output all the heap elements.

good work.

Find the max and set it as the first element (whatever rotation results in that) seems to be the greedy approach and can give a good approximation, but I don't know if this works all the time.

The goal is to get the biggest cluster of big numbers at the left side of the rotated array, but I am not sure of an algorithm to do this

I had this idea too, but i'm not sure if it's better than brute force- mainly because for every combination you try, you have to see if adding digit 0,1,2,3,4,5,6,7,8,9 are in the hashtable. This means, you will (at worst case) test 10 digits each time, and do this 100,000 times, which is worse than brute force of 500,000 checks

That ends up being worse than brute force though...

this is a mean question to ask.

i think the approach is to give a stream of numbers such that every 5 consecutive numbers gives you a unique number. I don't know how to do this though.

There is another option which is to keep a hashtable of all numbers from 0 to 10000, then when you add another number to the stream, you check which digit you can add and see if this new digit with the last 4 numbers in stream are already in the hashtable? This ends up being more cumbersome than brute force though...

k select algorithm

Say k = size of each sequence. Check all subsequences length k from k = 1 to n/2. Keep track of the min/max of subsequences. If subsequences are non intersecting and the max of one is smaller than a min of the other, you've found your answer. This is expected to be an O(n^3) algorithm

public static void main(String[] args) {

	String s = "careercup";

		generateAll18(s, 1, s.length() - 1);
	}

	public static void generateAll18(String s, int i, int j) {

		if (i >= j) {

			return;
		}

		String s1, s2, s3;

		s1 = s.substring(0, i + 1)+(j- i - 1)+""+s.substring(j, s.length());
		s2 = s.substring(0, i)+(j - i)+""+s.substring(j, s.length());
		s3 = s.substring(0, i+1)+(j - i)+""+s.substring(j + 1, s.length());
		System.out.println(s1);
		System.out.println(s2);
		System.out.println(s3);

		generateAll18(s, i+ 1, j-1);
		generateAll18(s, i + 1, j);
		generateAll18(s, i, j - 1);
	}

Modify this by adding a hashtable to remove duplicates

Yes. See my answer

This is a case of using bitwise dark magic

public int bitsSet(char[] arr) {
	
	int currentRep;
	int count = 0;

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


		currentRep = hammingWeight[i] << 24 | hammingWeight[i + 1] << 16 | hammingWeight[i + 2] << 8 | hammingWeight[i + 3];  
		count += hammingWeight(currentRep);
	}
}

public int hammingWeight(int i) {
	
	//bit magic here- there is a way to do this in O(1)

     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

do as many interview questions from this site as you can before your interview...