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
Miguel's answer is the one I'd give for the "no trampling original array, n is huge."
n is huge sort of implies that k isn't.
lol hahahaha
that's technically correct actually
even if some randommethod() sorts the array and finds the largest k numbers in O(1) time {hypothetical}, we can always wrap it with:
newmethod( )
{
randomethod(), then save largest k;
swap two elements (so array isn't sorted anymore);
return largest k
}
:)
But assuming we can't trample the original array, let's fork off different answers based on that too.
It should handle W1W2, bit I read other posts and thought "hire" was invalid (because we needed more than 1 letter each).
Well if "hire" "hiiree" are valid, then it could be easier easier:
for(t = 0, i = 0; i < str.length ; i++)
if( str[i] == alpha[t %M]  str[i] == alpha[++t %M] ) continue;
return false;
return ( t%M == M1) ? true : false;

S O U N D W A V E
October 24, 2013 And for completeness, you might try to argue to erase balanced BSTs as a competitor.
They also have O(lgn) remove min. and insert.
So why not use them? These don't require an array that can fill up like your reply is worried above. So why not use them?
+1 @Chan.
TBH, when I know I can solve a problem I rush in solving/explaining it.
It works really well in general, because you can learn a lot and get things done faster, but it fails when you need to explain your thoughts. Gotta work on it.
O(n) is min. space complexity for the problem, since we might do n inserts then n removemin.s.
You can grow the array multiplicatively (e.g., double it, 3/2 it, etc.) and still get the same amortized running times as listed in your argument.
The only justification you are missing is whether there is anything that can beat the minheap in either push and pop.
Can you justify minheap over an ordered list (vectors/ArrayList/linkedlist) ?
O(1) remove min, O(n) insert. Beats minheap on remove min., but loses to it on on insert.
I can play devil's advocate, for the sake of debate, and say:
Wait, I can queue the stream if it's too fast for me, but if a user wants to know the min. now I better do it fast. Thus O(1) ordered list beats O(lgn) for remove min..
How would you argue the interviewer if (s)he said that? Are there any applications where you would use an ordered list?
And are there even other basic DSs to consider?
{Forget fancy ones. A semi fancy one does have O(1) insert, O(lgn) get min amortized yada yada. }
Stream left to right: 1 2 3 4 5 6 7 8 9 10 < pop> 11 12 13 14 15 <pop>
First pop answer? Second?
Krzysztof, let's calm down.
Your diagram above itself immediately gives the idea of how to insert duplicates just as easily as throwing them out or overwriting.
Just take the subtree rooted at 3, put it aside.
Put the new duplicate 5 where the 3 was.
Make the old subtree, the new left subtree of the new 5.
It is O(1) extra work over the regular insert and doesn't require you to "rebuild" all the tree below 5.
It seems (picture a tree), that everything works smoothly if we allow duplicates to to go on one side (like left).
That way when you search works fine still in lg(height).
And duplicates can be designed into most DSs and they are useful (Duplicate numbers in real data, same names "John Smith", etc. etc.).
Regular BST stuff seems perfectly easy to convert to add handling of duplicates.
For balanced BSTs, we could probably convert the rebalancing stuff for this to on our own. Or we google it. Wikipedia isn't the ultimate authority on everything possible and probable.
Now take you diagram above, change the 7 to a 11.
1) Is it still a BST?
2) What will your BSTcheck do for that test case?
Take care
Ughh careercup messed up alignments. Trying again:
public int doit(int b[],int s[],int r[], int i)
{
if(i == b.length) return 0;
sum = doit(b,s,r,i+i) + ( i==0 ? 0 :
b.lengtha.length >= i ? b[i1] :
b[i1] + a[i1a.length]);
r[i] = sum%10, return sum/10;
}
And:
i 4 5
res [ ][ ][ ][ ][ ][ ]
b [ ][ ][ ][ ][ ]
a [ ][ ]
b.lengtha.length=3

S O U N D W A V E
October 24, 2013 For fun because I wanted to act on a hunch that a few liner was possible. Though I expanded a line into multiple to make it clear that 3 possible cases of sum are being calculated.
Call this with b[] being bigger array, r[] having length b.length+1, and last argument 0
(use a wrapper if you like):
b stands for bigger, s for smaller, r for result
public int doit(int b[],int s[],int r[], int i)
{
if(i == b.length) return 0;
sum = doit(b,s,r,i+i) + ( i==0 ? 0 :
b.lengtha.length >= i ? b[i1] :
b[i1] + a[i1a.length]);
r[i] = sum%10, return sum/10;
}
I used this diagram (in notepad) to play with to scratch my itch (the hunch):
i 4 5
res [ ][ ][ ][ ][ ][ ] res.length = b.length+1
b [ ][ ][ ][ ][ ]
a [ ][ ]
b.lengtha.length=3
Yes, there are limitations to the design, but it looks cool (and different from the ones already posted). And probably has off by one errors.
Compiled on scrap paper, tested on that notepad diagram above.
Ok, that's interesting.
Let me try recursive for fun.
How's it stored and in what type of array?
 S O U N D W A V E October 24, 2013Someone report the >; bug to careercup please..
One more try:
for(t = 0, i = 0, count = 0; i < str.length ; i++)
if( str[i] == alpha[t %M] ) count++;
else if( str[i] == alpha[++t %M] && count > 1) count=1;
else return false;
return ( count > 1 && t%M == M1) ? true : false;

S O U N D W A V E
October 24, 2013 Uggh, where do the random ; come from after we click submit:
for(t=0,i = 0,count=0; i < str.length ; i++)
if( str[i] == alpha[t %M] ) count++;
else if( str[i] == alpha[++t %M] && count > 1) count=1;
else return false;
return ( count >;1 && t%M == M1) ? true : false;

S O U N D W A V E
October 24, 2013 Let's make it an "ordered" alphabet array
by letting (compile time fixed or get from somewhere at runtime):
alpha[]={ your ordered list of characters in your alphabet }
M be size of your ordered alphabet (i.e., size of alphabet array above)
idea:
for(t=0,i = 0,count=0; i < str.length ; i++)
if( str[i] == alpha[t %M] ) count++;
else if( str[i] == alpha[++t %M] && count > 1) count=1;
else return false;
return ( count >1 && t==M1) ? true : false;
Untested. Fix the bugs please.
Maybe I'm missing something, but why do we need fancy stuff?
hmmm....................................
VMware?
time to learn the basic DSs
Why would there be a standard answer for this? The way Ajeet coded it looked very clean.
But true on the second point, any algorithm to check the invariant of a basic data structure isn't worth a "invented by Dr. ______" label.
:)
Not good boss.
Too many issues to comment.
#1 advice: Look at how to design Java programs and design well encapsulated DSs/ADTs in Java.
Ajeet, that's very nice.
 S O U N D W A V E October 23, 2013You sure that works?
 S O U N D W A V E October 23, 2013it only compiles on one platform: back of envelope
 S O U N D W A V E October 23, 2013Will the answers to 2 and 3 in your list after the code always be compatible (i.e, two paths that don't cross on white squares) ?
What's the memory usage like in the worst case grid for a very large N?
Also, folks,
There are some more obvious O(nlogn) solutions that you can work out on paper too that can be a second iteration on design/optimization of runtime over N^2 worst case brute force.
N^2>NlgN >N
Try some cases brute force on paper, then when you try this case you get the idea
: 4 3 2 1 2 3 4
And it it clear from question itself that the alg. you should scan from right to left.
DS needed is a stack..
And also, as I'm coding I realize we should have sentinel value like INF (you can replace with whatever, maybe even replace with a[i] at that point) when no result exists (especially the rightmost answer):
call invocation of this stack, S:
for( i = N1; i>=0; i )
{
while( !S.isEmpty && a[i] >= S.checkTop() ) //try to find > a[i] element
S.pop();
if( S.isEmpty )
result[i]= INF; //nothing > a[i] to right (or use a[i] instead of INF)
else
result[i]= S.checkTop(); //this was > a[i] to right
S.push(a[i]);
}
Find the bugs.
Please double test the code.
runtime O(n)
worstcase aux space O(n)
Assume all of the above is not there.
Original poster sunshihaosd can modify his question properly, or fork another thread for "the other" interpretation. Sheesh.
Look at the example.
It said "areas"
And the input grid has more blobby shapes and barely and real rectangles.
m*n is meaningless and can mean "input is a rectangle, not just a square"
Why do you and I have to guess?
This place has serious issues. Efficiency is garbage here.
People spend 1 min. speed typing their questions because they want to save 1 min. of their time, and cause havoc. Selfish idiots.
Got it I think.
We can pass up some interesting data from the recursive calls to the caller to actually calculate the middle max area in O(N). Try it out. This actually came while thinking about optimizing the 2) D and Q algorithm.
T(N) = 4*T(N/2) + O(N) < optimized middle calculation
T(N) = O(N ^(log_base2(4)) ) = O(N^2)
I'll code it up tomorrow. For now, this proves writing down ideas can lead to iterative improvements in solutions (or attempts) very fast.
Wait,
The recursive calls can return more information that can aid the caller.
Ouch, many possibilities abound, still let's leave it as abstract O(N^2) as the combine middlecheck step.
I apologize, I read blob throughout the thread and took it as "blob" (fits in any space).
Thanks pxe for "flood fill" (label given for DFS on these things).
For the rectangular problem, let's consider a square matrix of width N (simply so that solving recurrences and comparing becomes easier in one variable). We can modify the algorithms back to MxN after we compare runtimes (with some faith).
1) Worst Possible Brute force:
Pick two points in the grid (topleft and bottomright corners), and check if it encloses a valid area.
Looks O(N^4)*O(N^2) = O(N^6) or something horrible like that (might be a loose upper bound).
2) How about divide and conquer? (As usual, assume N is power of 2 to make recurrence easier to solve):
Divide the grid up into 4 smaller squares, and recurse into each to find max area of any valid blob in each.
We must also consider any blob that spans more than 1 of the subsquares. We can fill this out starting from the centre to find the max such rectange. This is upperbound O(N^2). We then return the max of the centre blob, and the 4 recursive call return values up the call chain.
So recurrence looks T(N) = 4*T(N/2) + O(N^2)
T(N) = O(N^2 lgN) , should be easy to code
correct me if I'm wrong please
3) Theoretical minimum for problem: T(N) = O(N^2) , gotta touch them all.
You should probably try first to get this theoretical minimum by making use of the heavy dose of overlapping subproblems (and opt. sub. structure) in 1) brute force above. We can modify that into a tableed bottom up approach I think, and try to get O(N^2).
No time to code, a movie is coming up :)
Compile and run defeats this MCQ.
This is not out of the realm of reality for Google SRE interviews.
Thanks to Archit Thawaria for finding a case that broke the no parent pointer code :)
In fact, we need to track 'prev' even for noparent pointer cases (only for a small part of downward DFS)
/* collabedit.com/w57qp for further updates, anyone can do it */
//without parent pointers (similar if you are searching for a target key)
find_kth(Node x, Node target, k, *prev) <= better to have a wrapper
{
if( x == nil ) return INF; //treat it like infinity in remaining stuff
if( x == target ) {
DFS_down(x, k);
*prev=target; //set prev node as target node
return 0; //0 hops above target node
}
//calculate number of hops away from target node
int away1 = find_kth(x.left, target, k, &prev1);
int away2 = find_kth(x.right, target, k, &prev2);
if( away1 < INF ) prev = prev1, away=away1;
elif( away2 < INF ) prev = prev2, away=away2;
if( ++away <= k ) DFS_down(x, kaway, prev); //DFS down if hops to spare
*prev=x; //set prev. node as current node
return away;
}
DFS_down(Node x, Node *prev, k) //prev!=nil => dont BFS down there
{
if( x == nil ) return;
if( k == 0 ) { cout << x or x.val << " is found as desired"; return; }
if(x.right != *prev) DFS_down(x.right, nil, k1);
if(x.left != *prev) DFS_down(x.left, nil, k1); //remaining dont need prev
}

S O U N D W A V E
October 22, 2013 Ok you want to find shortest path.
Then ok.
Actually, see responses to your 2 direction code.
It is not at all obvious how to extend that to the 8 direction (cycling Dir. graph) model.
Because the paths from (0,0) to grey, and paths from grey to (N1,N1) will depend on each other, so you can't use "the product rule" from combinatorics.
And the product rule bit is assuming you meant that (which is the way to make your idea for 2 direction case work).
^^^ I am referring to his original "2 direction" scenario.
The product rule paths1 * paths2 (as stated) will not work in 8 direction case (because of "visited flags" interaction between the two journeys).
DFS.
Main reason against BFS is that it won't work.
It works "layer by layer" and the first vertex to be seen by some path will not be allowed to be part of another path (because of the visited flag being set already).
For example if your code does down before right.
down then right might reserve a vertex even though
right then down could also have a path going through there
And there are other reasons.
@Varun
He has some loose ends in his explanation, but it should work if he calculates total paths as:
DFS_countpaths( (0,0), (a,b) ) * DFS_countpaths( (a,b), (n1,n1) );
findit(Node x, Node target)
{
if(x==nil) return 1; //target not down this path
if(x==target) return 0; //target found, return 0 as dist. above it
// else check for target down all paths (children)
distanceabove = 1;
for(temp=x.children; temp!=nil ; temp=temp.nextchild)
{
distabove=findit(temp, target);
if( distabove >= 2 ) return 2; //helps prune tree (optimization .. I hope!)
if( distabove != 1 ) break; //target was along this path
}
if(distabove == 1) return 1; //target is nowhere in our subtree
distabove++; //add 1 to distance (for extra hop up to us)
if(distabove == 2) { //we are 2 hops above target, thus grandma
for(temp=x.children; temp && temp.next; ) //find rightmost aunt of target
temp=temp.nextchild;
for(temp=temp.children, prev=nil; temp && temp.next; ) //aunt's 2 r.m. daughters
prev=temp, temp=temp.nextchild;
if(temp && temp != target)
cout << temp << " is rightmost cousin\n"; //rightmost daughter if not me
elif(temp && prev )
cout << prev<< " is rightmost cousin\n"; //else try second rightmost
}
return distabove;
}
Typed it raw, expect the unexpected.
 S O U N D W A V E October 22, 2013Another way for two directions.
You should be able to:
Recolour some "blocking lines" outwardling from the grey point to black (to block paths that go around the grep point).
Then recolour the grey point to white.
Now we just have to find paths through the white points.
Because these two directions prevent cycles, the model is a DAG.
So we can compute number of paths to any white square from any possible previous white square and fill out a table.
[*nix OS specific]
a process calls fork() (call it this process 1 which dives into fork)
This causes OS, via a system call, to create a copy of process 1, call it process 2, with some PID
then fork call returns into both processes as if they had executed that bit of code
so 1 process dives in, 2 dive back out... how to differentiate in the two different programs that are now executing the same code from thereon?
in process1: fork returns a positive integer (PID of process 2)
in process2: fork returns 0
There on each independently executes the rest of the code assuming on that line, and for that call, fork returned what it did for them.
// 1 process
if(fork() && fork()) // creates 2 more
{
fork(); //very first process will get here and create 1 more
}
//4 processes reach here
=== assume 1 process reached here though ===
if(fork()  fork()) //creates 3 more (even first child will try second fork)
{
fork(); // 2 processes reach here (original plus 1st child that tried 2nd fork above)
}
// Thus above sequence will create 5 more processes
4 x 5 = 20 ?????
This should cover the two other combinations (i.e, "with parent pointers"):
//with parent pointers and given key to find (must search for Node)
find_kth(Node x, Key val, k)
{
if( x == nil ) return;
if( x.val == val ) { //at Node x, DFS down for kth distance nodes
DFS(x, nil, k);
return 0; //current node is "0" links above target node
}
find_kth(x.right, val, k);
find_kth(x.left, val, k);
}
//called by above OR called directly in the "Parent Pointers + Node Ref." case;
DFS(Node x, Node prev, k)
{
if( x == nil ) return;
if( k == 0 ) { cout << x << " is one such Node" << endl; return; }
if( x.right != prev) DFS(x.right, x, k1);
if( x.left != prev) DFS(x.left, x, k1);
if( x.parent != prev) DFS(x.parent, x, k1);
}
With a macro, we can hide some of the ugliness in the last part above
( C/C++/pseudocde style marcos)
#define safeDFS(t) if( x.t != prev ) {DFS(x.t, x, k1);}
DFS(Node x, Node prev, k)
{
if( x == nil ) return;
if( k == 0 ) { cout << x << " is one such Node" << endl; return; }
safeDFS(right);
safeDFS(left);
safeDFS(parent);
}

S O U N D W A V E
October 22, 2013 Sounds cool.
Pseudocode?
+1, that's a good start.
 S O U N D W A V E October 22, 2013Here is my idea for "no parent pointers"
(I would search for the Node first regardless of key vs. node ref.)"
//without parent pointers (similar if you are searching for a target key)
find_kth(Node x, Node target, k)
{
if( x == nil ) return INF; //treat it like infinity in remaining stuff
if( x == target ) {
DFS_down(x, k);
return 0; //0 hops above target node
}
//calculate number of hops away from target node
int away= MIN( find_kth(x.left, target, k), find_kth(x.right, target, k) ) + 1;
if( away<= k ) DFS_down(x, kaway); //DFS down if hops to spare
return away;
}
DFS_down(Node x, k)
{
if( x == nil ) return;
if( k == 0 ) { cout << x or x.val << " is found as desired"; return; }
DFS_down(x.right, k1); DFS_down(x.left, k1);
}
I tend to think of pseudocode with infinity or other sentinels (to shorten required thinking) so left it in there (my style). Fix the bugs as you desire.
Drawing a tree (not a symmetric perfect case) on paper (or your mind) makes almost all tree questions very tractable.
2 times 2 variations == 4 combinations exist for this problem.
2 choices
========
You can be given a key (must find the node) or given reference to the node (can access the node in question directly).
2 choices
========
Parent pointers available or not.
What does the original poster want code for?
Is this really O(lglgn)?
"Do zero check on both parts" ? Except for the case when the parts are perfectly aligned and CPU accessible objects (e.g., int, short, char), how would you do that part when you are dealing with parts that are < 1byte in size?
Pseudocode please?
Why not (for sizeof(int) independent alg.) just sweep through the bytes and do "zero check" and "odd 1 set check" byte by byte?
Yeah, sorry about typos, I am lazy and and abusing careercup lately to see if I can speed code solve a bunch of problems (yeah, I admit it).
1) I know. It's because of the nature of the problem, you can always throw out solution ideas for this.
2) Easy to alter if you are allowed to trample A[] without affecting the O( ) of time and space.
Whether you are using a result[] array or A[] trampled with result, we can still measure AUX space as being outside either, and "num passes" the same way.
I assure you, the simple change to "destruct and store results back in A[]" code keeps it
~2 passes
O(1) aux. space
I took the liberty of commenting your idea in return.
You could have picked better notation , because idx, three letters just get in the way.
Your recursion would be O(N^2) I think, just like the iterative brute force.
But there would be overlapping subproblems and optimal substructure (because, the PI(something) and PI(otherthing) in your post above overlaps for other idx positions) , so you can memoize your recursive function to give O(N).
And neither naive recursion nor memoized are O(1) aux. space.
Or you can bottom up DP for the same idea and fill out a suffixproduct[] array, then sweep from left to right, and at each position i
1) Calculate result[i] = prefixproduct * suffixproduct[i]
2) Update prefixproduct with A[i]
~2 linear passes, ~1 linear aux. space (suffix product[])
....
But all this can be beaten with ~2 passes, and O(1) aux. space
without any recursion, nor memoization, nor DP.
I guess it would be more appropriate to call these funcitons num_levels.
 S O U N D W A V E October 22, 2013
RepLooking for the best child development center in Charlotte? Pal A Roos provide summer camp for children Charlotte. Our experienced ...
RepRobertBaumbach, Administrative Manager at Meridian Mechanical Services
Repelisahbuff, Apple Phone Number available 24/7 for our Customers at Altera
I have previous work experience in a customer focused environment. I like to Enjoy my Free Time Playing football.I ...
Repkarinkwalton, Backend Developer at Broadsoft
I am working as a Support clerk in an MVP Sports company. I love traveling and exploring facts about technology ...
RepGinaSanchez, Computer Scientist at Autoportal.com
Ginna from New York.Successfully managing a high volume of work assignments without compromising quality to exceed client expectations.Apart ...
Open Chat in New Window
These points are dumb.
 S O U N D W A V E October 26, 2013Can't even trade it in for free McDonalds burgers.
Going to create a new account just to get back down to 0.
+1 for good debate.