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
Children of a node in the matrix would be defined as:
LEFT(i, j ) = A[i+1,j]
RIGHT(i, j ) = A[i, j+1]
Node, the matrix is a kind of quasi-min-heap to begin with:
1) A[0,0] - top left - is the minimum of all elements
2) Every node A[i,j] is < LEFT, RIGHT children (as defined above)
So we can create an aux. min. heap,
store (0,0) in there, then:
while( aux.min.heap not empty)
{
x=extractMinAux;
storeInResultArray(x);
insertMinAux( children of x THAT are not descendents of elements already in aux.min heap <--- this bit is special for this quasi min heap );
}
return result array
collabedit.com/fqaax <= I meant this.
- S O U N D W A V E October 19, 2013collabedit.com/fqaax <= I meant this.
- S O U N D W A V E October 19, 2013@JonG
collabedit.com/4k9d4
Add and fix things in there as you please.
@JonG
collabedit.com/4k9d4
Add and fix things in there as you please.
loop in MIN-extracts*
- S O U N D W A V E October 19, 2013@EOF
True. I can see a solution that might be N^2 with high probability (or avg. case N^2 maybe, or at the very least N^2 best case) but can't think of an N^2 worst case.
The matrix is already (from top left) in a min-heap form (but with a stronger rep. invariant property, with subtrees overlapping unlike a usual min-heap).
We can create a separate min-heap, put the (0,0) element then loop on max_extract's and inserting children of everything we extracted (but we can also use the extra overlapping properly to exclude certain children from needing to be inserted into the min. heap).
The size of the aux. min. heap is "usually" rather small on the average case (and in the best case it should be small and independent of N, making the whole alg. N^2 in best case).
Another comment for you to downvote :)
ender, you can downvote each comment separately
ender, your original post with strong opinions and N^2 code has disappeared, now the replies are just floating...
- S O U N D W A V E October 19, 2013The updates on the right show this activity:
ender said Hi Urik, yes, I have rephrased some sentences to make ...
ender up-voted EOF's comment: Since the matrix has ...
ender up-voted URIK LAGNES's comment: 1) O(N ...
You edited your original post :) Cool.
- S O U N D W A V E October 19, 20131) O(N*N) worst case for any solution? Huh? You mean OMEGA(N*N) ?
2) Merge sort which runs in O(N* Log N)
-> In this problem N is a dimension of the square matrix. So M.Sort is O(N^2 lgN)
3) With this approach, the space efficiency is O(1) and the time efficiency is O(1/4 * N*N).
-> What does this mean? What is the "1/4" for? You break the square matrix up into 4 element blocks (with two outer for loops). But then you have inner for loops to work on each for 4 elements per block. You aren't magically touching only 1/4 the elements.
4) Have you tested this? How could this possibly work? Looks like you'd have to sort "sorted_array" at the end for it to be really sorted (correct me if I'm wrong).
For the problem itself, we have global upper and lower bounds on any optimal solution in terms of time complexity:
1) Upperbound O(N^2 lgN) <--- Because the original poster's mergesort does this
2) Lowerbound Omega(N^2) <-- Gotta touch them all. In fact, it can't be C <1 constant within the O either.
@JonG, too late I already upvoted this one hehe :P
- S O U N D W A V E October 19, 2013"Letter counts" on a string is roughly equal to linear sort == bucket sort (bucket size = 1)
So in the abstract, any linear sort on strings works.
I think the key idea is we hash on the key== anylinearsort(string) and keep the original string as data.
Roughly (you can optimize, tweak this in obvious ways).
A string-key based hash table that "keeps" duplicates (doesn't overwrite).
One can think of how to design this, but since anagram equivalence classes are rarely large... who cares.
Simply hash these: < key=linearsort(string), data=string> into the hash table.
Then you are basically done.
How you design the details is boring....
O(strlen)
- S O U N D W A V E October 18, 2013nice
- S O U N D W A V E October 18, 2013On first thought, it would seem THE PROBLEM itself has an OMEGA(N^2) runtime (lower bound N^2).
The number of pairs that meet the conditions of the question seems to be ( as N-> inf ) quadratic in N. So you have to access all results.
Or am I missing anything?
nice
- S O U N D W A V E October 17, 2013Nikhil,
"main" is not the only functions that can/does call other functions.
So your function signature is something like this it seems [you should have maybe said it in original question :) ]:
typedef unsigned int uint;
void removeit(uint a[], uint remelem, uint *size)
{
for( i=0; i<(*size); i++)
if( a[i] == remelem )
a[i] = a[(*size)-- -1];
}
Psycho, he doesn't mention "stable" in the requirements.
Move onto next Q man.
Yeah, nvm.
I think it's O(infinite)
How does the second loop break?
I dunno boss. Questions that are typed in a rush deserve 2 min. thought before answer, me think.
- S O U N D W A V E October 17, 2013or rotate other way :P
- S O U N D W A V E October 17, 2013Actually his code should be worst case N*lgN.
+1 for using distance^2 instead of distance (no sqrt used, cool)
Also, if you have all N elements up front, you shouldn't do N heap inserts, but rather you should use a slick O(N) build heap algo. (heapify from lowest internal nodes up to roof).
The building of heap alone you are using is O(N*lgN) worst case. Then add the removes, which are worst case O(k*lgN) and you get a total runtime of O(NlgN). So you are better off actually just doing heapsort on the array (same runtime, but the internal constants will be smaller).
My thoughts:
1) Never use distance, but rather use the square on distance.
We don't want to get caught up in the ugliness of sqrt.
2) We can do this in place (and in most apps. this should be allowed because the set of points is just a "bag" of points):
3) Modify QuickSelect or MedianOfMedians to use a distance^2 comparison function "on the fly" on the original array itself.
This gets the k closest points into the first k elements of _original_ array of points.
Should be O(n)
nice
- S O U N D W A V E October 17, 2013This also should be "nondestructive" on the array.
* O(n) time
* O(1) space
* array left untouched after result returned
collabedit.com/bbptb
Again, no compiling/testing done.
#define ABS(x) ((x)< 0 ? -(x) : (x))
/* put this in a function that return true if duplicate is found in array a[] of size N */
int zeropos = -1; //position of any 0 found in array
for(i=0; i<N; i++)
if(a[i] == 0)
if(zeropos != -1) return true; //duplicate 0 found (and array is untouched, so return immediately )
else
zeropos = i //position of 0
a[zeropos] = 1; //set to 1 so the next for loop works for dup="zeropos"
bool dupfound; // true means we found duplicate
for(int i=0; i<N; i++)
{
// this means abs(a[i]) was used as an index into a[ ] already
if( a[ abs(a[i]) ] < 0 ) { dupfound = true; break; }
// first time abs(a[i]) used to index a[ ], change sign below to trap second time
a[ abs(a[i]) ] *= -1;
}
/* next part "recreates" the original array */
for(int i=0; i<N; i++)
if( a[i] < 0 ) a[i] *=-1;
a[zeropos]=0; //recreate the zero element
return dupfound;
Sorry, but above I was talking "out loud" and building the solution by iteration (and explaining).
It's better if I drop a clean almalgamation of it.
This also should be "nondestructive" on the array.
collabedit.com/bbptb
Again, no compiling/testing done.
#define ABS(x) ((x)<0 ? -(x) : (x))
/* put this in a function that return true if duplicate is found in array a[] of size N */
int zeropos = -1; //position of any 0 found in array
for(i=0; i<N; i++)
if(a[i] == 0)
if(zeropos != -1) return true; //duplicate 0 found (and array is untouched, so return immediately )
else
zeropos = i //position of 0
a[zeropos] = 1; //set to 1 so the next for loop works for dup="zeropos"
bool dupfound; // true means we found duplicate
for(int i=0; i<N; i++)
{
// this means abs(a[i]) was used as an index into a[ ] already
if( a[ abs(a[i]) ] < 0 ) { dupfound = true; break; }
// first time abs(a[i]) used to index a[ ], change sign below to trap second time
a[ abs(a[i]) ] *= -1;
}
/* next part "recreates" the original array */
for(int i=0; i<N; i++)
if( a[i] < 0 ) a[i] *=-1;
a[zeropos]=0; //recreate the zero element
return dupfound;
rehash
careercup.com/question?id=6318635089920000
collabedit.com/4pmvt
Small adjustment:
On the first pass (zero check), keep the position of the zero:
int zeropos = -1;
for(i=0; i<N; i++)
{
if(a[i] == 0)
if(zeropos != -1) return true; //duplicate 0
else
zeropos = i //position of 0
}
Then add an extra check (either as part of the sign flipping for loop, or as an extra pass before hand, to see if there are duplicate "zeropos" values in the array:
Here I show the extra pass pre-signflipcode:
bool extracheck
for(i=0; i<N; i++)
{
if( a[i] == zeropos )
if( extracheck ) return true; //duplicate "zeropos" values in a[ ]
else
extracheck = true;
}
Again, I need to compile and test.
- S O U N D W A V E October 16, 2013the post had the formatting messed up in a few places (some extra ;'s appear, like in abs macro):
Redo:
#define ABS(x) ( (x) < 0 ? -(x) : (x) )
Assume all this is in a function that returns true if a duplicate is found:
0) Needed is an abs. value function or macro:
#define ABS(x) ( (x)<0?-(x):(x) )
1) Have a boolean flag to check if you have duplicate 0's.
bool seenzero;
for(i=0; i<N; i++)
if( a[i] == 0 )
if( seenzero ) return true; //zero was seen before
else
seenzero=true;
So the zero check is ~1n single pass, plus 1 boolean var. space.
Now we can assume the array has values in the range 1 to n-1 only.
This means a few things:
1) We can flip any value in the array from positive to negative and not "lose" information, because abs(a[i]) == original(a[i]) regardless if we flipped the sign.
So we can flip signs as we desire.
2) Since 0 can no longer be a value, we "know" if a[i] < 0, that "we" are the ones that had flipped it's sign. ( 0 would mess this up because -0 == 0 ).
3) Since the values are in the range 1 to n-1 and len(a)==n, all the original values of the array can index the array itself.
Now comes the code that someone has to do on paper to get it the first time:
for(int i=0; i<N; i++)
{
// this means abs(a[i]) was used as an index into a[ ] already
if( a[ abs(a[i]) ] < 0 ) return true;
// first time abs(a[i]) used to index a[ ], change sign below to trap second time
a[ abs(a[i]) ] *= -1;
}
return false; //neither the zerocheck or the self-indexing-sign-flipping caught the error
Type this raw, so hope it's okay.
Runtime O(n) , two passes with constant effort on each element during each pass
Aux. storage O(1) ... just the index i, and boolean seenzero (1 stack frame, registers)
Add 1 more pass if you need the array back to it's original form (take abs of each element).
Hmm.. ok.
Best done if underlying data structure is a pointer linked data structure with a head and tail pointer available.
Then a rotate by 1 char is O(1).
If you want to go with an array,
temp=a[0];
for(int i=0; i<N-2; i++) a[i]=a[i+1];
a[N-1] = temp;
_Map_ into node addresses of a self organizing (e.g. "Move to Front") doubly linked list.
- S O U N D W A V E October 16, 2013roughly
for(i=0; i<N; i++)
if(you hate a[i])
a[i] = a[(N--) -1];
return N; //new array size
Try it and fix the bugs?
- S O U N D W A V E October 15, 2013Static problem (the way you posed it).
So, PRINT(" < pre process the answers and put them here> ");
?
#define yourfavouritenumber 14
#define yourmosthatednumber 30
(y=(x=(y=x^y)^x)^y ) ? yourfavouritenumber : yourmosthatednumber ;
And fix any bugs found :)
- S O U N D W A V E October 15, 2013I was asked this recently, and it all boiled down to "how would a human do it?"
You can sort of reason that O(1) space is impossible. That is, a "max" variable augmented on the stack is insufficient.
Think of two extreme cases.
{As a human}
Pushing these in this order: 7 6 5 4 3 2 1 <=== O(1) unchanging max variable would work only (fluke)
Pushing these in this order: 1 2 3 4 5 6 7 <=== Ouch, after every pop we need to recalculated the max "below" the thing we popped.
So take the 2nd extreme case... after every pop, what "would" you need to recalculate the new_max in O(1) time?
After I pop the 7, I kind of need the max "below the 7" for any further min queries.
After I pop the 6, I kind of need the max "below the 6" for any further min. queries.
So it would seem on every push() we should push with it the new max "at that point in time (I use time loosely here)."
That is, push: < new_elem, new_max>
What is new_max ? It would seem to be, MAXVAL( new_elem, max_stored_with_old_top )
Try it on paper.
//for every possible key on the keypad (i.e., numbers 0, ..., NUM_DIGITS-1 )
above comment should be deleted
But what if the user wants to press less than all the keys...
Introduce NUM_PRESS <= NUM_DIGITS:
#include <stdio.h>
#include <string.h>
typedef enum {false,true} bool;
#define NUM_DIGITS 4 // {0, 1, ..., NUM_DIGITS-1} will be the digits of pad
char *keypad[NUM_DIGITS]={"ab","cd","efgh","xyz"}; //defining the keypad: e.g., 0-key has 'a' and 'b'
bool used[NUM_DIGITS]; //boolean "hash" (kind of) that keeps track of the keys already touched
int num[]={0, 2, 1}; //the input number
#define NUM_PRESS (sizeof(num)/sizeof(*num)) //size of input (number of keys we'll press)
char result[NUM_PRESS+1]; //result (global for convenience)
/* note: NUM_PRESS <= NUM_DIGITS allowing for less than all keys pressed */
void function()
{
int k;
char *letptr;
static int i=0; //index of result we're filling now
if (i==NUM_PRESS) { puts(result); return; } //result full, print
for(k=0; k<NUM_PRESS; k++) //for every possible key on the keypad (i.e., numbers 0, ..., NUM_DIGITS-1 )
{
if( used[ num[k] ] ) continue; //if the key was touched already, skip it
used[ num[k] ] = true; //mark key as touched
letptr=keypad[ num[k] ]; //point to first letter corresp. to this key
while(*letptr) //iterate over all letters corresp. to this key
{
result[i++]=*letptr; //fill letter, inc. i in prep. for recursive call
function(); //recursively fill next position of result[]
i--, letptr++; //unwind i and point to next letter
}
used[ num[k] ]=false; //tried all letters of current key, mark untouched
}
}
int main(void)
{
function();
return 0;
}
I comment heavily on purpose (and use globals heavily too) to keep the idea clear. Which also allows people to see any bad ideas, logic I have :)
In C:
#include <stdio.h>
#include <string.h>
typedef enum {false,true} bool;
#define NUM_DIGITS 4 // {0, 1, ..., NUM_DIGITS-1} will be the digits of pad
int num[NUM_DIGITS]={0, 2, 1, 3}; //the input number
bool used[NUM_DIGITS]; //boolean "hash" (kind of) that keeps track of the keys already touched
char result[NUM_DIGITS+1]; //result (global for convenience)
char *keypad[NUM_DIGITS]={"ab","cd","efgh","xyz"}; //defining the keypad: e.g., 0-key has 'a' and 'b'
void function()
{
int j;
char *letptr;
static int i=0; //index of result we're filling now
if (i==N) { puts(result); return; } //result full, print
for(j=0; j<NUM_DIGITS; j++) //for every possible key on keypad
{
if( used[ num[j] ] ) continue; //if the key was touched already, skip it
used[ num[j] ] = true; //mark key as touched
letptr=keypad[ num[j] ]; //point to first letter corresponding to this key
while(*letptr != '\0') //iterate over all letters corresp. to key
{
result[i++]=*letptr; //fill letter; inc. i in prep. for recursive call
function(); //recursively fill next position of result[]
i--, letptr++; //unwind i, point to next letter corresp. to this key
}
used[ num[j] ]=false; //tried all letters of key, so mark it as untouched
}
}
int main(void)
{
function();
return 0;
}
No need. If you have an array 1, 2, 3, 4, ..., n , you can find out if/where some k is in O(1). It's only slightly harder in a 2D array.
- S O U N D W A V E October 12, 2013+1 because you put DFS ( or BFS) instead of the other way around
I assume you compiled and tested (based on what you said in another thread) it so no need to read
@LinhHA05, I said it's not necessarily a DAG == "no top. sort."
@OP
A lot of these "graph like" problems really should state clearly if the underlying query structure is adjList like or adjMatrix like.
Java?
I would hope the compiler converts this to bytecode roughly equal to
String temp = "ABC";
It's all known at compile time.
Cheer up
+1 :)
O(1) usually means inplace
He meant one of the loops in EratSiev need only go upto sqrt(largest prime you are trying to find)
- S O U N D W A V E October 10, 2013Yeah. I wouldn't bother worrying if someone included 1 as a prime.
A lot of mathematicians in the past included 1, and some still do.
1 is excluded to make theorems like uniqueness of prime factorization "easier" to state.
Then change question to "simple path" please :)
- S O U N D W A V E October 09, 2013
Repmylakleinm, Quality Assurance Engineer at Coupon Dunia
Articulate and accomplished admin executive experience at keeping an office running smoothly. A communicator and collaborator who is efficient in ...
Repherminanmuller87, Animator at 247quickbookshelp
Hello,I am a literacy teacher. I completed my degree from Chicago and now am a literacy teacher in a ...
Repjanistbennett, Blockchain Developer at AMD
I am JanisBennett working as a journalist, having years of experience in my career. I have covered various stories.Great ...
Repgarlandkrebs, Animator at ADP
Highly focused and seasoned magazine editor with vast experience in all stages of weekly and monthly magazine production. My aim ...
Repannawellson007, Area Sales Manager at 8x8
Hey my name is anna And i am working as a content writer in Search engine optimization company.My component ...
Repneshujaha, Member Technical Staff at BMO Harris Bank
I am Neshu, a Camera Operator with a creative eye for detail and dedication to quality work. I am always ...
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
Reprafaeltanner210, Associate at 247quickbookshelp
I am Labor relations directors, oversee employment policies in union and nonunion settings. I draw up, negotiate, and administer labor ...
Repcolettehenna, OOPS Freshers at Bosch
I am Colette , policy analyst at Sunflower Market , with 3 years of experience building and maintaining relationships with elected officials ...
RepIndianastrologyguru, Data Scientist at ABC TECH SUPPORT
Hey I'm Shelly Renee and I'm working as a system developer. Currently working part time on a project ...
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 ...
Reptaylamowll, Analyst at AMD
Aspire to work in a challenging environment, where my exceptional skills and abilities are completely explored, and I can easily ...
Repamayalopez800, Accountant at A9
I am Amaya ,working in the field of training and development coordinator for three years, focusing on teaching English as ...
Reploragurrero, Research Scientist at Absolute Softech Ltd
I am Lora , an empathetic and dedicated Community Organizer with a deep passion for helping others and a strong determination ...
RepKellyLabbe, Animator at Future Advisor
My name is Kelly and I am currently a freshman Fitness trainer in Vibrant Man company .I have learned a ...
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 ...
RepTimothyAYocum1, Android Engineer at ABC TECH SUPPORT
I am a medical or osteopathic doctor who specializes in eye and vision care. My work Ophthalmologists differ from optometrists ...
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 ...
RepDonnaArvin, Analyst at Apple
Hii am from the United States. I work as a computer control programmer at Dynatronics Accessories. I am a social ...
Reppamilarbowman, Animator at ABC TECH SUPPORT
Je travaille en tant que Web Manager dans la société Forum Cafeterias. Je veux tout savoir sur le marketing numérique ...
How is that obvious bro? There isn't even a K in the question/problem, and the absolute minimum is N^2.
- S O U N D W A V E October 19, 2013