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
For each person, store lists of everyone they beat.
Backtrack:
- Fill first position with people who have had wins (iterate over all these of course)
- Then: At every position thereafter: Fill every person who has lost to the person in the previous position of the filled array but is not in result array.
Typed this directly in here, so could be buggy
// denote the people by integers 0, 1, ...., N-1
//global for convenience
static i=0; //position of result[] current invocation fills
_function(prev) //function gets previous person (filled into result)
{
int j; //iterate over losers of 'prev'
if( i == N) { //do whatever with result[ ] as it is full }
//fill current spot of result array
for( j = every person 'prev' has beaten and not in result)
{
result[++i] = j;
_function(j); //fill next spot in result with people j beat
i--;
}
}
// fills first spot with winners (wrapper for _function)
function()
{
int j; //iterate over all people who have at least one win
for (j = every person that has a win)
{
result[0]=j;
_function(j)
}
}
// PRUNE this as you desire.
- S O U N D W A V E October 09, 2013+1
Short on detail and confusing, but correct when I read your mind.
Since you didn't say "simple path" we must consider a loop off of any simple path from src to dest and count the vertices in the loop too. And if such a loop exists, there are infinite paths from src to dest. So take care to make sure any algorithms that correctly add the vertices of such a loop doesn't run forever...
:)
That is to say your "considering all paths" should not be literally translated to "must traverse all paths."
What does "pair" mean? |p-q| = 2 ?
You can sieve out composites from [2,n], then print pairs.
UPDATE====
Oh wow down vote makes me cry so hard :)
Yeah it says p*q <=n, not p, q <=n , misread.
So you can save on the range [2,n].
And only consider [2, n/2] to sieve on.
Let the OP just do it on [2,n] as a first coding step (his/her final check on pq <=n will take care of correctness). Can someone explain to him why n/2, as I will now:
Because , the boundary/extreme case is:
------------------------------------------------------
(smallest possible prime)*(largest possible) <=n
And (smallest possible prime) = 2, so:
2*(largest possible prime) <=n
which implies (divide both sides by 2):
(largest possible prime) <= n/2
Anyone care to explain the complexity of this algorithm?
The articles might be an understatement.
And remember the discussion about "illusion" ? That includes mechanisms of "work transfer."
This one is a "few" liner in Python, thanks to dictionary.keys() .
Anyone care to post code?
And we (meaning, comp sci community) are totally abusing "O" notation. Someone needs to reset its use.
What's the pseudocode for recursive exponential algorithm?
- S O U N D W A V E October 08, 2013+1
But to cut things short...requirements 1, 2, 3 are the "usual" operations for sets/dictionaries/collections/whatever/datastructures.
So it's better if you take them together, and find the data structure(s) that satisfy 1/2/3....
Then try to satisfy 4 on top of that.
Some of these are the most ambiguous/ unrepresentative examples for the problems at hand.
#define ALPH_SIZE 256
bool seen[ALPH_SIZE];
/* put it in a function that returns int (so you can return -1 on no repeats): */
for(i=0; i< str.length ; i++) {
if( seen [ str[i] ] ) return str[i]; // <=== BINGO
seen[str[i]] = true;
}
return -1; // <== no repeats
For 2), I want to place the piece at (inf, inf)
and I want to know the hops for it to reach (-inf, inf).
I guess you are given N=string length, where n1+n2+n3 = N/2.
Solution is to backtrack-> modify a recent problem involving only n3 (yesterday).
Use requirements 1 to 3 -> What are some DSturctures that can do this?
Of the above, can you add operation 4 to any of them?
And just saying "O(1)" is a bit ambiguous..
search terms: Kadane / max subarray.
It's tricky to get the linear code correct.
My post is one big implication, with hypotheses I stated :)
Yes, I'd use quickselect under "general" conditions.
Your comment runs fairly orthogonal to my post, and doesn't contradict it.
And careful with "better solution in practice" generalities.
Let N be an even number (just double the n from the question), the size of the thing you are building.
Backtracking: left to right build your thing. Keep track of the number of ( and ) braces already in the filled part of the thing you are building.
Let numLeft be the tally of ( already built.
Let numRight be the tally of the ) already built.
Take care in what you allow to be added in any position.
- If you are the i-th position "filler" of the recursive backtracking function:
-> You can fill that position with a ) if the numLeft > numRight
[ Because, if numLeft <= numRight, adding a ) won't match a previous ( ]
-> You can fill that position with a ( if numLeft < (1/2)*N
[Because we will have (1/2)*N ( in final result, so can't add more than that ]
C:
#include <stdio.h>
#define N 6 //question would have given n=3
void filler()
{
static int i, numleft, numright;
static char result[N+1]; // all 0-initialized by compiler
if(i==N) { puts(result); return; }
if(numleft > numright) //can close earlier ( with a ) so do so
result[i++]=')' , numright++, filler(i), numright--, i--;
if(2*numleft < N) //have room to open a ( so do so
result[i++]='(' , numleft++, filler(i), numleft--, i--;
}
int main(void){
filler();
return 0;
}
^^^ Made N fixed compiled time constant and other things simple to make the algo. stand out as the star player.
Made the winding and unwinding of variables explicit on purpose also (otherwise they might be "hidden" for illustrative purposes).
Math problem.... cool...
I did two examples fully to get used to the problem,
1) Drawing from set S = {1, 2, 3, 4} sequences of length 2. Answer was 10.
2) Drawing from set S = {1, 2, 3, 4} sequences of length 3. Answer was 20.
I did both above manually (try it) but it's fast as you see a pattern.
I can see 10 and 20 come from Pascal's triangle in a neat way.
Let N be the size of S (number of characters in alphabet, whatever)
Let n be length of sequence.
Number we want is (N+n-1) choose (n).
Omitted the proof I did to verify this (think of "bars and stars").
So write an function to essentially find Pascal's triangle values bottom up DP style until it reaches N+n-1 choose n , then return that.
===============
Nevermind, the problem was much easier... find all the sequences :P (printing them).
This gives us the excuse not to find a counting formula.
C:
#include <stdio.h>
// all this will be calculated at compile time (efficient)
#define FIRST_CHAR 'a'
#define ALPH_SIZE 26
#define PAST_LIMIT (FIRST_CHAR + ALPH_SIZE) //1 past last char
#define SEQ_LEN 3
char result[SEQ_LEN +1]; //let's make it global for change
void print_them()
{
static i=0; //position of result[] current invocation fills
int p;
if(i==SEQ_LEN) { puts(result); return; } //seq. full, print
p = (i==0) ? FIRST_CHAR : result[i-1]; //grab previous char
while(p < PAST_LIMIT) //iterate forward from prev. char
{
result[i++] = p++;
print_them(i) , i--; //fill next then unwind i
}
}
int main(void)
{
print_them();
return 0;
}
Keeping local variables + parameters to a minimum will help prevent the hardware stack from blowing up if you are dealing with longer sequences.
- S O U N D W A V E October 07, 2013agree on cannot be predicted +1
don't agree on random
+1
but std output buffer might be nearly full...
it might flush before all the odd numbers in that for loop are dealt with
i don't think it can be predicted without knowing the rest of the program (before this bit of code is called)
Ohh this is an interesting one. Where do you guys dig these questions out?
Let tower[i] be your initial tower array.
Define the height of the tallest tower to the right of position i be right[i].
{Essentially the largest integer to the right of position i}
So build right[i] by scanning right to left O(n) time O(n) space.
We need left[i] also, similarly, but we can store this in O(1) by not keeping previous values as we scan from left to right. That is, continuously update a "left" type variable as you sweep left to right as you update the totalrain variable on the spot as you sweep left to right...
Here is my idea. Have a totalrain variable accumulate while you sweep from left to right the rain above each tower.
1) Sweep right to left, get right[i] filled up.
2) Sweep left to right, and for each i:
a) totalrain += max( min( left , right[i] ) - tower[i], 0 ) <==** key calculation. Accumulate rain above tower i.
b) update "left" variable if tower[i] > left , i.e., current tower is larger than all others to left
3) return totalrain
In above, take care in one of several ways (sentinel in left /right, or starting and stopping the linear sweep in 2) inside the limits of the tower[i], to make sure that rain[0]=rain[N-1] = 0 . Just pointing out a possible bug.
Looks like 2 linear passes, plus 1 linear array needed.
Time ~2n, space ~n
Key calculation explanation:
=============================
The rain above tower i is:
0 rain UNLESS <=== this explain the outter max( , 0 )
- The largest tower to the left and the largest tower to the right are both greater than tower[i]
- in which case, the rain above tower[i] is the difference in height between the {smaller of the two towers listed just above} and tower[i]
What are your ideas Rajesh
- S O U N D W A V E October 05, 2013_If_ the range of numbers, which are _integers_, is O(n) we can use:
int count[range]; //array of counts (or adjust range if lower limit isn't 0 )
Traverse your array whilst incrementing counts.
i.e., count[array[i]]++ for each index i from 0 to N-1.
Then linear sweep count array to find median in the obvious way.
accumulate=0;
for(i=0; i<range; i++)
if( 2*(accumulate += count[i] ) > N ) return i;
or maybe off by 1 errors above
O(n) guranteed, O(k) storage ( a priori ~ range is O(n) )
This is essentially bucket sort with bucket size=1 modified for finding medians (I just used the idea of quicksort -> quickselect). What would this be called? BucketOneSelect?
:) Careful
- S O U N D W A V E October 05, 2013+1
- S O U N D W A V E October 05, 2013Hmm.. ok....
Fix this code. That's your homework.
// { Warning: Brute Forcing below }
// substring function: will be used by this problem
// returns index of FIRST starting point of pattern[ ] inside text[ ]
// or returns -1 if pattern[ ] not found in text[ ]
int substring(char text[], char pattern[])
{
int s;
int i;
for(s=0; s<=strlen(text)-strlen(pattern); s++)
{
for(i=0; i<strlen(pattern); i++) //store these strlen's ahead of loops to optimize
{
if( pattern[i] != text[s+i] )
break;
if (i==strlen(pattern))
return s; //found starting at index s of text[ ] string
}
}
return -1; //not found
}
int main(void)
char *mainstring ="CSK lost to RR and Subhu is a loser";
char *sub="CSK";
int N = strlen(mainstring); //length of main string
int M = strlen(sub); //length of substring to find
int numsub=0; //number of substrings
int t=0; //index into mainstring[ ] ... t=0 at start because we want to start searching mainstring from start
int s; //position of found substring
while( (s = substring( &mainstring[t] , sub) ) != -1 ) //search mainstring[] from 't' index (so we don't hit earlier matches)
{
printf("A substring found at index %d\n", s);
numsub++
t=s+M; //increase t to s+M so the next "substring" call in while loop will only check past last found substring
}
printf("%d substrings founds\n", numsub);
return 0;
}
collabedit.com/rg7fx
- S O U N D W A V E October 05, 2013If the elements are allowed to be negative, I think optimal solution is:
O(n) space and time
If the elements are only nonnegative,
O(n) time, O(1) space solution seems possible
Can you mark these without company name? Because you are just practicing, this is not from a Google interview.
- S O U N D W A V E October 05, 2013if( node == nil) return nil; // empty tree, no minimum
while( 1 ) {
if(node.left == nil) return node; //has no left child, so we are at min.
node = node.left; //has left child, so min. is recursively in left tree
}
Are they looking to hire ex-Nvidia employees?
- S O U N D W A V E October 04, 2013Rough idea: O(1) space, linear time
a -> input array
N -> input length for moving average (assume N is valid size)
int sum=0;
int tail=0; //trail an index (behind "i" by N)
for(int i=0; i < a.length; i++)
{
sum += a[i] - (i < N ? 0 : a[tail++]);
result[i] = sum/min(i+1, N);
}
Someone compile and test it for me ?
- S O U N D W A V E October 04, 20131.1.0 < 1.2.0 < 1.10.0 < 1.20.0
- S O U N D W A V E October 04, 2013+1
I need to recruit you as a SDET.
4*first letter? That would have been 1 line of code.
printf ("%c%c%c%c\n", str[0],str[0], str[0], str[0]);
Yes. Finally one I can do !
printf("*\n\n**\n\n*\n");
Yes. Finally one I can do !
printf("*\n\n**\n\n*\n");
Performance testing?
Can't you measure response time during other testing to judge this.
Maybe scalability testing is missing but I doubt this is done for every scenario of every page / field / form when a company build a website.
+1
- S O U N D W A V E October 03, 2013Yes, I had essentially the same idea.
Radix sort usually using counting sort subroutine on each slot, but in this case we should allow for comparison sorts (stable) in case huge integers are allowed in each intermediate version number.
i.e.,
1.1020203030301.2.3040404.3.1.1
Would cause the usual counting sort (sub sort of radix sort) some troubles on two of the slots.
Names: non alpha numeric, leading amount of whitespace (large large amount too), looonggg string, hyphens, mixed upper lower case in weird positions, use non characters letters (character map? not sure how this works), make the last and first name the same (see if it messes up after you submit the form), leave one or both blank, ....
Upload photo: Click upload with nothing in field, upload different photo file formats, upload 0 file size file with correct extention for a photo type (or incorrect), upload text file, upload a large large valid/invalid photo, try manually typing in the photo field some random path, try back and forward slashes for directory path, try uploading a photo of Miley Cyrus
etc. etc. etc. just say a lot of positive and negative cases and border cases for everything
make sure to mention "integration" / "interaction" cases
collabedit.com/rg7fx
- S O U N D W A V E October 03, 2013Talked to her/authour, she didn't want want anything except strlen used (and wanted the logic to be easy just for her to learn to do brute force):
She dipped from collabedit session after I typed this mess so I'm going to post it here and give her the homework of fixing the 1000 bugs:
// substring function: will be used by this problem
// returns index of FIRST starting point of pattern[ ] inside text[ ]
// or returns -1 if pattern[ ] not found in text[ ]
int substring(char text[], char pattern[])
{
int s;
int i;
for(s=0; s<=strlen(text)-strlen(pattern); s++)
{
for(i=0; i<strlen(pattern); i++)
{
if( pattern[i] != text[s+i] )
break;
if (i==strlen(pattern))
return s; //found starting at index s of text[ ] string
}
}
return -1; //not found
}
//main function for replace string problem posed by Reena (she wants all "manual" work, so no library calls, except strlen)
int main(void)
char *mainstring ="ABCDADXYZDADABC";
char *fromstring ="DAD";
char *tostring ="REENA" //for our example, we will get "ABCREENAXYZREENAABC" as result, ok???
int N = strlen(mainstring); //length of main string
int M = strlen(fromstring); //length of substring to find
int T = strlen(tostring); //length of replacement string
int *positions = malloc(N); //store positions where "fromstring" is substring of "mainstring" (picked N size for convenience only)
char *result = malloc(N*10); //just create a result array 10 times larger than starting string (you can improve this later with calculation)
// above ^^^ you should really check return value of mallocs for errors too (excluded for now)
int numpos=0; //index into positions array
int t=0; //index into mainstring[ ] ... t=0 at start because we want to start searching mainstring from start
int s; //index of returned substring from every while loop iteration below
while( (s = substring( &mainstring[t] , fromstring) )!= -1 ) //search mainstring[] from 't' index (so we don't hit earlier matches)
{
positions[numpost++] = s; //storing the position of substring
t=s+M; //KEY POINT: we increase t to s+M so the next "substring" call in while loop will only check past the original position
}
/* NOW: after the above while loop we have
1) positions[] array will have the positions of all the substrings to be replaced
2) numpos will be the number of positions/substrings we found in the mainstring
*/
// REENA: you can calculate actual needed result[ ] array size at this point and improve code at your liking
// now to build the result array:
int i=0; // iterates over positions
int resultfill=0; //position of result array we are filling currently
int maingrab =0; //position of mainstring we are getting characters from currently
int k; //for repalcement copy for loop (dummy index variable)
while ( maingrab < N) //will keep going as long as there is more of the main string to grab
{
//grab positions of mainstring[] and place in result[]until next position where substring starts
for( ; maingrab < pos[i]; maingrab++)
result[resultfill++] = mainstring[maingrab];
//now maingrab is index of start of next position of substring
//increment position index (to next substring for next iteration of while loop)
i++;
//copy over replacement string into result string
for(k=0; k < T; k++)
result[resultfill++] = tostring[k];
//maingrab must now be pushed ahead by size of substring (we are skipping over it for next while loop iteration)
maingrab += M;
}
result[resultfill] = '\0'; // NUL terminate
printf("result is: %s\n", result);
return 0;
}
Reena, type a full example, please.
- S O U N D W A V E October 03, 2013On what? Computer? If so, what OS? What player?
Did you ask the interviewer all this?
C:
#include <stdio.h>
#include <string.h>
int main(void)
{
char *str="ABCDEFG"; //test subject
int N = strlen(str); //length of it
int resultN = 4*(N-1); //length result string (-1 excludes last char)
char *result = malloc( resultN + 1 ); //space for result string
//check malloc failure if you desire
//4 positions of result corresponding to every char of str
int a,b,c,d;
int i;
for( i=0; i < N-1; i++)
{
/* first two positions in first half of result array */
a=i << 1; // 2*i (first position)
b=a+1; // 2*i+1 (second)
/* last two positions in last half of result array */
c=resultN-1-a; //resultN - 2*i -1 (third)
d=c-1; //resultN - 2*i -2 (fourth)
/* fill the result positions in with current input character */
result[a]=result[b]=result[c]=result[d]= str[i];
}
result[resultN] = '\0'; //NUL terminate
printf("%s\n", result);
return 0;
}
What does string replace mean?
- S O U N D W A V E October 02, 2013For binary trees, yes.
- S O U N D W A V E October 02, 2013I once had sprained/dislocated ribs from Judo. They were pretty bad and my doctor's painkillers didn't really fix the root cause. So I fixed it by finding a chiropractor and getting treatment for a few months. He would use an activator to hit the displaced ribs to slowly push them back into place.
- S O U N D W A V E October 02, 2013So you get an array of such strings? Let's assume you do, say s[i] :
Ok, for each string, say string i:
1) Tokenize with separator .
2) Convert each token to an element of an int array a[i][j]
where i= denotes string , j= denotes token of string in order it appears
So say you have two strings: s[0]=3.1 , s[1]=3.1.3
This converts to a[0]={3, 1} , a[1]={3,1,3}
3) If some elements of a[i] have less "j" tokens, 0 fill them so the j-width is all the same
{You can precompute the largest j-width if needed}
4) Do necessary number of stable sorts of versions a[i] on j entries from "right to left"
{use > sort ordering, and you will get your answer as first element of a[i] }
Did they say the elements were nonnegative?
- S O U N D W A V E October 02, 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 ...
Yes you can model the situation with a directed graph (a, b) denoting a beat b.
- S O U N D W A V E October 09, 2013But it's not necessarily a DAG as, for example, 1 beat 2, 2 beat 3, 3 beat 1.
[1, 2, 3] would be a valid result. Maybe I'm missing something on first look.
But, backtracking is roughly equal to DFS on directed graphs...
Everything turns out slick if we keep a "I beat all these people" list for each person (adj list), and strip out the direct. graph model to the bare minimum. I think backtracking does this?
Maybe there is a more slick way.