CareerCup

One optimization might be that it is unlikely that num dishes is large, so we can store it in possibly 1 integer (64 bits).

Then we can build up partial solutions using the same 64 bit field.

And for filling person i , we can check that person i ' s preference (i.e., row of input matrix would be another bit field) against the partial solution so far using:

if ( partialSolSoFar & personPreference[i ] ) // no need to add...

We can also have a memo... mapping combinations of "i" and partialSolutions
... but this would have to be a hash table of sorts.

So I see 3 possible optimizations

1) use integer bit magic
2) prune recursion by checking if a partial solution already satisfies i-th person's preference
3) memo using a hash from (i, partialSolSoFar) to min

codechamp, are you sure Zynga asked someone this exact question?

because I'm stupid :)

min*

Selection sort does it in n-1 swaps

Find max, append it to the end. Repeat n-1 times (but exclude the previously appended items from your scan for max)

@Snob, it's language independent pseudocode

The whole put of the "return S" is an excuse to point out, via a trailing comment, that it holds the absolute path at that point (i.e., extract that information as you deem necessary).

There isn't even a function or a function call in the above code.

//concatenate the two paths then..

stack<string> S;

//assume getNextLevel returns NULL after munging whole path
int i=0;
string x;
while(  x=getNextLevel(concatenatedFullPath, i++)  )  
{
	//we do nothing if "."  or ".." inside root (i.e., empty stack)
	if( !strcmp(x, ".") ||  ( !strcmp(x, "..") && S.empty() ) ) continue;

	if( !strcmp(x, "..") ) S.pop(), continue;

	S.push(x);
}

return S; //holds absolute path

+10

Who asked you?

^^^ Anagram doesn't mean "reverse of the word" :)
You maybe need more test cases. Try searching for "abc" inside "zzzzbaczzzz" (should return true)

So the input is fixed {4,5,6,4,5,6} ?

function(array[ ])   //O(1)
{
return {4,4,5,5,6,6};
}

Or can we please define the input instances in their fully generality, please?

^^^^
Memoize with one index i

@meh: Ops, 01 ... 09 are not valid as per question. Need to make adjustments.

@KidOfKop: You can memoize based on i,j indices that point into the overall string.

I should have given that question more of a quick look (I blame being conditioned by the usual CC questions where we are just forced to guess details and solve based on this).

For such a general question, I would implement selection sort.
Scan linked list for max (always keeping ref/ptr to previous element of current max), then place it in new linked list. Repeat until old linked list has 0 elements.

You posted a facebook interview question and a non facebook interview question both on this Sunday.

So you weren't satisfied with the explanations you read elsewhere?

For binary tree:

preorder traversal:
{
   if( i'm null ) return;
   
   add "me.data" to end of a vector/arrayList;

   if( my chilren are both null ) print out the vector/arrayList;

   recurse into left child;
   recurse into right child;

   delete last element of the vector/arrayList (e.g. removing me.data);
}

For graph do DFS with a check for visited flags (do the check before extending path there) using same idea above.

NOTE: preorder(tree) == DFS(graph) - (need for visited flags)

recursive...

function(str) {

If str.length < 1 return 0;

x=0; //number of ways IF we can map first two digits

//if first two characters have a valid mapping, then count the ways into 'x'
If str.length >= 2 and str[1 .. 2] is in range(1,26) {  
    x = 1 + function(str[2 ... n]);
}

//max of interpreting first 2 digits as valid map OR first digit as valid
return max( x, 1+function(str[1 ... n] );  

}

Because of overlapping subproblems, memoize to make it DP (top down DP).

If you are NOT that nervous in interview, do it bottom up using a table.

This is careercup: We have to guess what posters are trying to say and solve based on that interpretation... and move on (otherwise we might end up in infinite loops wasting time).

It "feels" like there is a better way. This might seem borderline brute forcish..

Let N be the largest such number you want.

MinHeap<unsigned int> h;
h.insert(1);  // I consider this as 2^0 * 3^0 * 5^0 

int temp;

while( ( temp = h.checkMin() ) < N )
{
	print( temp );
	h.extractMin();

	insert(temp*2);
	insert(temp*3);
	insert(temp*5);

}

Don't upvote this. Let it die.

Where is the edit feature :(

int col,row, prevcol=0, prevrow=0;
for(int i=0; i<s.length(); i++)
{
	col  = ( s[i]-'a' ) % ROW_LEN;
	row = ( s[i]-'a' )   / ROW_LEN;

	while(col>prevcol) { putchar('r'); prevcol++; }
	while(col<prevcol) { putchar('l'); prevcol--; }

	while(row>prevrow) { putchar('d'); prevrow++; }
	while(row<prevrow) { putchar('u'); prevrow--; }
	
	putchar('!');
}

for(int i=0; i<s.length(); i++)
{
	col  = ( s[i]-'a' ) % ROW_LEN;
	row = ( s[i]-'a' )   / ROW_LEN;

	while(col>prevcol) { putchar('r'); col--; }
	while(col<prevcol) { putchar('l'); col++; }

	while(row>prevrow) { putchar('d'); row--; }
	while(row<prevrow) { putchar('u'); row++; }
	
	putchar('!');
}

for(int i=0; i<s.length(); i++)
{
	col  = ( s[i]-'a' ) % ROW_LEN;
	row = ( s[i]-'a' )   / ROW_LEN;

	while(col>prevcol) { putchar('r'); col--; }
	while(col<prevcol) { putchar('l'); col++; }

	while(row>prevrow) { putchar('d'); col--; }
	while(row<prevrow) { putchar('u'); col++; }
	
	putchar('!');
}

Yes.

invariant: A[0...copyto-1] matches output :
----------------------------------------------------
int copyto=0; //next position that you are copying into A[ ]
		     //to keep the invariant valid 
		     //when copying into this spot, swap its current element to the 
		     //later spot that you are copying back from 
					

for(int copyfrom=0; copyfrom < N; copyfrom++)
{
	if( isLow(A[copyfrom]) )
	{
		swap(A, copyto, copfrom); //swap to keep invariant
		copyto++;
	}
}

for(int copyfrom=copyto; copyfrom < N; copyfrom++)
{
	if( isMed(A[copyfrom]) )
	{
		swap(A, copyto, copfrom);
		copyto++;
	}
}

There are two interpretations to this problem.

I suggest the OP edit the question.

The question is stupid the way it is posted ("in a reasonable amount of time" ??). The only answers possible with the current form of the question are brute-forcish.

A good engineer would know the predicates before hand and split off relevant streams into auxillary arrayLists/vectors, or without knowing the predicates, would have duplicated/stiphened off the whole stream into a ranomize-on-insert DS.

The OP should post the discussions he had with the interviewer or he should mention more details.

Don't support the current quality of postings on this website.

The way the question is posed has no interesting/optimal/"cool" answers.

Prove the above wrong and then talk.

I didn't say it was incorrect :'(

If you are totally in the dark in predicting possible predicates (even sets of them?), then make sure you place the elements into a data structure that randomizes on insertion.

I don't like this question.
1) Situation is stupid. Why would someone who wants this query allow such an array to be built?
2) We don't know what process created the 10million element array (i.e., if we can assume it was a uniform random process, then we can scan to the first non-null element an return it) How many such queries will be performed? This, along with other considerations, will determine if preprocessing makes sense or not.
3) Why would

Search by index in Array? That would make it a hashMap (with possibility the trivial hash h(i) = i).

What does this have to do with Huffman encoding?

I don't get it?
The answer is always sum of overall stick
It's independent of choices leading to the final sum.
It's not even a minimization problem.

for loop in any order over the sticks, and return the accumulated sum.

Oops. I my interpretation of the question was different :P

Nice!

I like min-heap solution (especially with streams , a.k.a., getting elements one by one from a socket or some external source).

But not sure about the linkedlist/array/loop-1000-times solutions.

minheap vs. maxheap vs. linear_selection(quickSelect or MoM) really depends on the situation. We can't even "try it out" because so many other variables need to be known.

Also, if the elements are integers in a tight range, there are solutions that destroy all above.

:) Healthy debate is good for the brain, agree?

Ok if you say so.
Creating and playing with another array (for the min-heap) without locality of reference with the original array is much faster :)

It's unfortunate that I don't qualify for Random Idiot Inc. ^^^^

Cool idea. +1

You saved space O(1) by sacrificing time O(n^2). It is a legitimate, possible use case.

Ok.
So if you tell me to find the biggest K elements of an array of size N, I can just say well K doen't count because it is given, and I'll give a O(K^K * N) algorithm, then I'll make K disappear into O(N). Equi-linear.

QuickSelect is blazingly fast in practice (works well with cache), and will drop the result in the first 1000 elements of your original array ready for your bidding.

Or you can build a min heap of size 1000, then do all that other stuff if you like...

I am from the Vedic bloodline, and I came up with above, thus that is Vedic :)

If there is another Vedic multiplication method, then whoever asks me to do this will have to explain how that works, and then I'll translate their psuedocode to code line for line :P

n is array size
m is the "1000"

[Forgot to define the variables above]

Ok, so you keep track of the index and value of the lowest number. Fine.
Say you replaced it, fine.
Now... how do you get the index of the "new" lowest number?
This is what makes it quadratic.

Worst case analysis:

All three solutions you mention above would be supralinear in time.
Array/linkedList would be O(nm)=...= O(n^2).
min-heap would be O(n*lgm) =...= O(n*lgn)

the =...= is used to denote "if n=theta(m)"

Another method is to use a max-heap which would be:
O(n + m*lgn) = ...= O(n*lgn)

assumes b >= 0

a*b = (a+a+ .. + a) <-- add 'a' to itself b times (with a loop)

if b<0, do above loop (-b) times then negate result

use median of medians, O(n), to get 1000th largest
then scan array picking out all numbers >= the one you got from above
Runtime: O(n) worst case
------------------------
or you can use QuickSelect for 1000th largest (expected linear, but worst case with low probability to be quadratic)

+1 @cptjack

Yes, I missed that :P

You sure your code works ?
You might want to loop over letters before looping over s.

Or better yet (optimization), you should do the loop over letters once in the outter function, and reuse it in the inner function:

public String getLongest(Set<String> dict, String letters) {

	// get letter counts for the input/letters string
	Map<Character, Integer> letocc = new HashMap<Character, Integer>();
	for (char c : letters.toCharArray())
		if (!letocc.containsKey(c))
			letocc.put(c, 1);
		else
			letocc.put(c, letocc.get(c) + 1);

	// check if each word is longer than previous longest valid word 
	String result = "";
	for (String s : dict)
		if (s.length() > result.length() && isWordOfLetters(s, letters, letocc))
			result = s;

	return result.length() == 0 ? null : result;
}

private boolean isWordOfLetters(String s, String letters, Map<Character, Integer> letocc) {
	Map<Character, Integer> occ = new HashMap<Character, Integer>();

	//count occurrences of letters in word 's' from dictionary
	for (char c : s.toCharArray())
		if (!occ.containsKey(c))
			occ.put(c, 1);
		else
			occ.put(c, occ.get(c) + 1);

	//if any letter in input string doesn't exist or exists in less number
	//in the word s, then the word doesn't pass our test
	for (char c : letters.toCharArray())
		if (!occ.containsKey(c) || occ.get(c)<letocc.get(c))
			return false;

	return true;  //word has all the characters of input string (letters)
}