S O U N D W A V E
BAN USER 3 Answers How to delete an account?
I've emailed careercup support 5+ times already (no response) about having this account deleted. Does anyone work actively on this site at all?
 S O U N D W A V E November 27, 2013
I occasionally get emails for recent comments to questions even though I'm not subscribed to this.
The unsubscribe link in this email leads to nothing useful (as I'm not subscribed to this service to begin with).
How do I contact the people who run careercup? How to stop the sporadic spam emails?
I just got this email (which is considered spam now) :
undefined has commented on a question.
You are given an array in which you’ve to find a subarray such that the sum of elements in it is equal to zero.
He algo is nice.
However, In java it is not easy using the hashMap to get the key of values if we use hashmap(index,value). And if we want to use hashtable(value,index), the array cannot have dup as it will have the same key and cover the previous value. We can use a biMap to handle it.
if we don't want to use biMap here is my solution using two hashMap.
static void sumEqZero()
{snip}
View »  To unsubscribe, login and click here. Flag  PURGE
codechamp, are you sure Zynga asked someone this exact question?
 S O U N D W A V E March 31, 2014because I'm stupid :)
 S O U N D W A V E March 26, 2014min*
 S O U N D W A V E March 26, 2014Selection sort does it in n1 swaps
Find max, append it to the end. Repeat n1 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

S O U N D W A V E
March 24, 2014 +10
 S O U N D W A V E March 24, 2014Who asked you?
 S O U N D W A V E March 24, 2014^^^ 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?
 S O U N D W A V E March 23, 2014^^^^
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.
 S O U N D W A V E March 23, 2014So you weren't satisfied with the explanations you read elsewhere?
 S O U N D W A V E March 23, 2014For 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).
 S O U N D W A V E March 21, 2014It "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);
}

S O U N D W A V E
March 21, 2014 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('!');
}

S O U N D W A V E
March 20, 2014 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('!');
}

S O U N D W A V E
March 20, 2014 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('!');
}

S O U N D W A V E
March 20, 2014 Yes.
 S O U N D W A V E March 18, 2014invariant: A[0...copyto1] 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++;
}
}

S O U N D W A V E
March 18, 2014 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 bruteforcish.
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 ranomizeoninsert 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 :'(
 S O U N D W A V E March 17, 2014If 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.
 S O U N D W A V E March 17, 2014I 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 nonnull 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).
 S O U N D W A V E March 17, 2014What does this have to do with Huffman encoding?
 S O U N D W A V E March 17, 2014I 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
 S O U N D W A V E March 13, 2014Nice!
 S O U N D W A V E March 13, 2014I like minheap 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/loop1000times 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 minheap) without locality of reference with the original array is much faster :)
It's unfortunate that I don't qualify for Random Idiot Inc. ^^^^
 S O U N D W A V E March 13, 2014Cool 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). Equilinear.
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).
minheap would be O(n*lgm) =...= O(n*lgn)
the =...= is used to denote "if n=theta(m)"
Another method is to use a maxheap 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)
}

S O U N D W A V E
March 12, 2014
RepLooking for the best child development center in Charlotte? Pal A Roos provide summer camp for children Charlotte. Our experienced ...
Open Chat in New Window
One optimization might be that it is unlikely that num dishes is large, so we can store it in possibly 1 integer (64 bits).
 S O U N D W A V E August 06, 2015Then 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 ith person's preference
3) memo using a hash from (i, partialSolSoFar) to min