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
What?
If you have a case where all the numbers are occuring odd times, then you still need to "print/access" them in a final loop. This will be ~ N/3 = O(n) "second thing" as you say.
How would you get rid of "another second O(n) thing?"
Basically converting base-10 input to base-26 on symbols {A, B, ..., Z}
C++:
#include <iostream>
#include <stack>
using namespace std;
int main(void)
{
stack <char> S;
char c;
unsigned int input=27;
while(input) {
S.push(input%26 +'A'-1);
input = input/26;
}
while( !S.empty() ) {cout << S.top(); S.pop();}
return 0;
}
It is a tree IFF if both
1) it is connected
2) has no cycles
So use DFS from any node s:
[Assuming below that vertices are integer labelled from 0 to ... N-1. ]
bool isTree(Graph *G)
{
if(G->numVertices == 0) return true; /* empty tree ? :) */
/* Step 1: pick a random vertex and reset visit flags somehow */
// int v = PICK RANDOM INDEX NUMBER from 0 to G->numVertices-1
// for(int i=0; i < G->numVertices i++) G-vertices[i].visited = false;
Stack <int> S;
/* DFS to check for cycles - that is, if you meet a visited node ==> cycle found */
S.push(start);
while( !S.empty ) {
v = S.pop();
if( G->vertices[v].visited )
return false; //cycle found (not a tree)
G->vertices[v].visited = true;
for( all edges (v, u) from vertex v)
S.push(u);
}
/* Step 3: If any vertices are unvisited, graph is disconnected == not a true */
for(int i=0; i < G->numVertices i++)
if( ! G-vertices[i].visited )
return false;
return true; //passed both tests, so it is a tree
}
Define the terms/phrases used in the question please!
- S O U N D W A V E February 27, 2014Or are you missing parts ? Like creating links to remember state of paths.
There are tricky ways to do this, but you need some way to remember "state" of ancestors.
In a BST without any augmentation nor parent pointers, wouldn't this be O(n*h) time and O(h) space [implicity recursion stack] algorithm?
Once you get the min, you lose the information on the ancestors of the path to this min unless you have some sort of stack, right? Unless you have parent pointers that is.
Correct me if I'm wrong as I am not sure how you are going to implement the subroutines.
Selfish aren't we? You spent 10 seconds typing this, so as to save YOU time.
google.ca/search?q=stored+procedure+is+slow&rlz=1CAACAC_enCA562CA562&oq=stored+procedure+is+slow&aqs=chrome..69i57j0l5.3771j0j4&sourceid=chrome&espv=210&es_sm=122&ie=UTF-8#q=sql+stored+procedure+is+slow
1. Code quicksort
2. Code mergesort
3. Code heapsort
4. Code BST sort (drop elements in a BST, then inorder traverse)
5. Code bucket/counting/radix sorts
$1 to the person who finds the big bug in the code above :P
- S O U N D W A V E February 25, 2014Why not spend an extra 2 min. typing the question more clearly, with more details , and possibly an example? This might save hordes of people many minutes, don't you think?
- S O U N D W A V E February 25, 2014There are two broad types/variants of the partition subroutines used for Quick(sort/select):
1) One broad type only has pointers/indices going from left to right
pos=0;
for(i=0; i<n; i++)
if(A[i] < pivotVal ) swap(A[i], A[pos]), pos++;
swap(A[pivotPos], A[pos]); // assuming pivot was hiding on right edge
/* check code above for bugs */
2) The other type has 2 pointers/indices going inwards from both ends, until there is a mismatch (left indexed array element > right indexed array element), and then a swap is triggered. Then the pointers start moving inwards again....
THIS is the Partition Subroutine type that runs very fast and makes Quick___ even more blazingly fast in practice .... and it is only a few lines of slick code. So MOST quicksort/select code with arrays will have type 2) partition subroutines.
------
Moral of the story, if you want to do quickselect(or quicksort) on singly linked lists, just use the Type 1) partition subroutine. You also need to adjust it a little such that you are always pointing to the elements before the to-be-swapped elements (the usual gotchas with linked lists).
Correct.
- S O U N D W A V E February 25, 2014math=match*
- S O U N D W A V E February 25, 2014Don't know what GC_PENNY is dreaming, but the "best" solution if parent pointers are not available seems to be (to me):
2 stacks, one for each tree.
Iteratively in order traverse each tree using independent stacks but check intermittently after each iteration in the obvious way for equality (and break if a no math condition is detected).
GZ_Penny, where did you get the question from?
How would you traversal on a single tree without a O(h) space stack (implicity via recursion or explicity container) ??????
Bad question.
Question is ambiguous (as usualy for CC).
a < b > c < d <-expressions like this are not well defined nor used in math.
a < b < c is an idiom that has come to mean a < b && b < c
But since it's the same inequality < used in both places, it matters not whether we explicitly state that a < c also (because this is true by transitivity automatically).
We can extend this to a < b < c < d < e < f safely.
Note above implies 5 inequalities directly, and 6choose2 inequalities in total.
Now if you have something like a < b > c < d > e
What does this say about the relative ordering of a vs. d or b vs. e ?
Or does it say nothing about these?
Sorting => usually O(nlogn)
Then the swapping =>O(n)
Total =?
Wherease just swapping = O(n)
Sit down with pen and paper and trace code posted by people you trust, and find bugs OR learn from good code (whichever the case).
Zoli, it is essentially DFS(grid position).
Just try starting it at every grid position.
There are implicit arcs from every grid position to every adjacent grid position.
"return" if you meet a character on the grid that doesn't match the corresponding level of character in the given word to allow for a different path to be search
A match is hit when all characters in the given word are exhausted.
DFS
- S O U N D W A V E February 24, 2014+1
It's careercup, where the voting doesn't matter. It's almost a compliment if you get downvoted by the trolls lurking in the background.
[Language independent] Using a balanced binary search tree is a _good_ answer. logarithmic getMin , insert, delete, ...
We can even improve getMin by making it 2 suboperations
1) ReturnMin ( O(1) give it to user immediately)
2) Calculate next min + removeMin (do this in parallel even before 1) is completed)
The same can be said for BinaryHeaps ( return the root in O(1), and heapify after placing new root can be viewed as 2 _almost_ parallel operations).
Nobody wants to debate anything here though. This is careercup. Also known as: "Give me the question paper for company X please with exact answers that will get me the job"
It is not a compression algorithm because they still want a single character to map to <char>1.
If they had allowed single character to map to single character without a count 1 following it, then it would be a compression algorithm (not simply an encoding), and you would be able to do it inplace.
all these O(1) space, O(strlen) time solutions.... Wow!
Now waiting for O(1) time and space solutions to be posted :P
Looks like folks need to look up definition of subsequence
- S O U N D W A V E November 11, 2013Who cares about different companies. Solve it for one.
And no, simply saying "hash the data we need for quieries we need" is not an alg.
Cool name uruk !
- S O U N D W A V E November 11, 2013Some typos above, incl:
*num-internal-nodes is O(numbasecasebodes)
Having no comp. Access suxs.
So my main points scattered throughout this thread were
1) Ajeet and yoda were correct and their upperbound is easiest to prove
2) Using the fib math recurrence (whether u keep base cases from math definition directly or use C or O(1) matters little... This is what u call "fibonacci-like" recurrence as one of the intermediate improvements of your argument) DOES NOT become the running time recurrence for the naïve math-translated to programming recursive alg.
(In fact... The "math recurrence _like_" runnning time recurrence only gives the running times for the base cases only under normal assumptions)
This SHOULD be obvious (not the bits u claim to be obvious).
Changing f to T (whether u also change base case to C or not is of little relevance here as base cases will be only costs) does not give tight nor upperbound on running time. Should be obvious.
So... In general it will give an omega lower bound on the total running time only. As it only gathers cost from base case invocation.
But in the case of fib. There recusion tree spreads out exponentially (you can see this in one of many ways) in a way that there are theta(phi^n) base case invocations itself.
So simply counting the runtimes of base case code gives us omega(phi^n) runtime for naivefib(n). This is good enough for cc and interviews.
(Incidentally, to count all costs you can prove that the recursion tree has at most O(num base case nodes) as ivan "kind of" did to prove bigO 2^n
He did it (or meant to) by showing that a balanced binary recursion tree has basically the same number of internal nodes as base case nodes).
(Warning: Everything above needs adjustment if base case and internal functions aren't both constant running time)
Nothing is as obvious as changing f to T.
Lol so wait... We end with you giving me advice?
Your fancy and "obvious" conjecture (which came after two mathematical symbol chugging replies by you) was easily proven wrong in my last reply. And I just picked the very last thing you said.
You gave up too easily man...
@anon
Just read some of ur recent replies carefully and upvoted one (with the best iteration of mathematics... With G(n)"
Do note u are improving the reasoning not simplying "explaining things that were obvious at first"
And who has been mass downvoting ghost ajeet yoda anon etc. in this thread? A good debate is ongoing stop frucking downvoting for no reason.
Haha. You just popped up in this thread (well other characters went quiet and now an Anonymous handle is trying to prove a point).
Good troll.
Building turtles on turtles to make something more accurate does not justify accuracy of initial reasoning. I'm stranded without comp. Access so for now I'll just respond to your very last statement just above...
"More intuitively... " What you mean here?
Assume n power of 2 for conv.
F(n) = F(n/2) for n>1
F(1) = C
=> ?
Vs.
F(n) = F(n/2) + C_0
F(1) = C
=> ?
HMMMMmmmmm seems intuition has failed. We can go back and changr "what we meant" a few times though, right?
Lol genius question poster.... He cud hav meant many things£. Bb sux
- S O U N D W A V E November 10, 2013Worst case len^2 operations (when n is len)
- S O U N D W A V E November 10, 2013HINT: Modify regular binary search.
- S O U N D W A V E November 05, 2013Since the values are in a tight range you probably want to do either of :
1) If the items come with auxillary data and you want "stability" (which you might since the range is so small), use linear counting sort.
2) If you are just getting numbers then use bucket sort (tally counts).
---Optimization of either idea above----
Now optimize either idea above by stripping out the last sort-like step of both sorts if you care (that is you just grab the top k elements either from the prefix sums of counting sort or the first few buckets which have enough for k elements in bucket/tally sort).
@Anonymous, I know. But I make up for it with an 9.7/10 appearance/body.
- S O U N D W A V E November 04, 2013lol
you repeat the same pattern under all your aliases..... a dumb fuck who plays to people's egos to try to get them to drop code (or modify their code to your language/specifications)... who posts questions under company names to make people rush to try... and eventually pretends to take the "high road" at the end when he gets outted
I still remember your bullshit "#DONT SKIP THIS AMAZON WILL ASK## LET'S SEE WHO BEST LOGIC"
Your dumb homework's answer can be summarized as (or it might be easier if you are solving offline on an array):
"bool stateflag1, stageflag2, .... ; while(c=get_next_char()) { switch(c) { case p: /* chk flags, print outputs, set flags if needbe */ break; case f: ............... "
Hash/set/whatever <char*> h; //boolean hash/set
char buf[s.length/2 + 2]; //store centre, rightwards of such substrings
int num=0;
in i, cen;
for(cen=0; cen<s.length; cen++) //try all centres
{
//use s[cen] to expand out "odd length" palindromes
for(i=0; cen-i>= 0 && cen+i<s.length ; i++ ) { //expand out from cen
if( s[cen-i]!=s[cen+i] ) break;
buf[i]=s[cen+i]; //increase candidate substring
buf[i+1]='\0'
if( h.exists(buf) ) continue;
h.insert(buf), num++;
}
//use s[cen] to expand out "even length" palindromes
for(i=0; cen-i-1>= 0 && cen+i<s.length ; i++ ) { //expand out from cen
if( s[cen-i-1]!=s[cen+i] ) break;
buf[i]=s[cen+i]; //increase candidate substring
buf[i+1]='\0'
if( h.exists(buf) ) continue;
h.insert(buf), num++;
}
}
return num;
Can make both inner for loops above into a single one
But it would be harder to understand/read
Quick/dirty attempt only:
Hash/set/whatever <char*> h; //boolean hash/set
char buf[2][s.length/2 + 2]; //store centre, rightwards of such substrings
bool valid[2]; //valid[0] for odd length, valid[1] for even
int num=0;
int i, j, cen;
for(cen=0; cen<s.length; cen++) //try all centres
{
valid[0]=valid[1]=true;
for(i=0; cen-i>= 0 && cen+i<s.length ; i++ ) { //expand out from cen
if( s[cen-i]!=s[cen+i] ) valid[0]=false;
if( cen > 0 && s[cen-i-1]!=s[cen+i] ) valid[1]=false;
for(j=0; j<2; j++) //j==0 for odd type, ==1 for even type
if(valid[j]) {
if( j==1 && cen ==0) break; //even for cen==0 meaningless
buf[j][i]=s[cen+i]; //increase candidate substring
buf[j][i+1]='\0'
if( h.exists(buf[j]) ) continue;
h.insert(buf[j]), num++;
}
if(!valid[0] && !valid[1]) break;
}
}
return num;
Need to learn to compile/test...
- S O U N D W A V E November 03, 2013+1 Suffix tree beats N^2 expand from centre in time.
- S O U N D W A V E November 03, 2013^^^ Consecutive hash checks within each iteration of inner for loop can be optimized.
Anyways, there are better ideas out there.
typed it raw so bugs expected
-> Take expand from centre algorithm and add functionality for this problem
-> using nonnaive definition of substrings (with hashing)
Hash/set/whatever <char*> h; //boolean hash/set
char buf[s.length/2 + 2]; //store centre, rightwards of such substrings
int num=0;
in i, cen;
for(cen=0; cen<s.length; cen++) //try all centres
{
for(i=0; cen-i>= 0 && cen+i<s.length ; i++ ) { //expand out from cen
if( s[cen-i]!=s[cen+i] ) break;
buf[i]=s[cen+i]; //increase candidate substring
buf[i+1]='\0'
if( h.exists(buf) ) continue;
h.insert(buf), num++;
}
}
return num;
EEk. That should be:
n(n-1)/2 naive definition of total number of substrings
n(n-1)/2 - duplicates for the strict one
in parallel we get these for subsequences
2^n subsequences (naively)
(2^n - duplicates) for the strict variant
It would seem that some algorithms (like the one I suggested above with expansion from different centres) that solve this problem would need to boolean hash/set to handle strict variants of the definition
hmmm i'm a little confused on definition
what I said above would "include" duplicates if they come from different parts of the string
this is consistent with the definition that leads to the theorem that every string has 2^n substrings
but not consistent with ( 2^n - duplicates)
so cubic is best known?
Any proof of problem's lower bounds beyond more than N^2?
else if you meet difficulty,
modify the pre-manacher's optimization (i.e., expand from each possible centre) algorithm using the above structure (no need for the "longest_centred_here" you can work straight with num_centred_here.
(i.e., array of
struct { int length_longest_centred_here; int num_centred_here; } ).
^^^^^^^^ ^^^^^
part of Manac. added for this question
Modify Manacher's in the obvious way.
(i.e., array of struct { int length_longest_centred_here; int num_centred_here; } ).
^^^^^^^^ ^^^^^
part of Manac. added for this quest
Should work without added complexity in big-O
Haven't checked though.
Modify Manacher's in the obvious way.
(i.e., array of struct { int length_longest_centred_here; int num_centred_here; } ).
^^^^^^^^ ^^^^^
part of Manac. added for this quest
Should work without added complexity in big-O
Haven't checked though.
Nice.
I think this is basically the best way that doesn't require the slickness (i.e. trick) of Manacher's (which is either just "known" or needs "a bit of time to think of").
Manac. is basically an optimization on nothing's alg to cut out some redundancies.
Search term: Manacher's algorithm.
O(N).
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 ...
There are ways that involve trickery, which you want to avoid in interview settings. It might be fun to try these funky ways when you are home drinking coffee and chilling.
- S O U N D W A V E February 27, 2014A good linear way is to use a map.
1) Go through your linked list, and for each node v, create a new node u, such that u->data = v->data. Now store (v,u) in your map. {Note, doesn't matter where you set the u->next, just leave the new nodes dangling in the air}
2) Now go through your original linked list again, and visit every v.
Now do 3 lookups in the map for every in your original linked list....
Look up v to get u.
Look up v->next to get whatever, call it x
Look up v->random to get whatever, call it y
Now set u->next = x, u->random=y.