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
I allowed above diagonal connections as part of blobbing more area.
We can change this bit to be more restrictive otherwise
8 directions:
for(i=-1; i<=1; i++)
for(j=-1; j<=1; j++)
if(!(i==0 && j==0) && A[r+i][c+j]==0) //checks 8 directions
The other obvious blob extending case is to only allow 4 directions. It becomes easier to code....
//helper recursive function
unsigned int tallyarea(A, r, c) <-- assume knows about R,C or whatever
{
int d;
unsigned int areaaround=0;
//if out of bounds or not a unseen zero cell, no area to add
if( !(0<=r && r<C && 0<=c && c<C ) || A[r][c] != 0) return 0;
A[r][c]= -1; //mark this cell as already counted as part of some area
for(d=-1; d<=1; d+=2)
areaaround += tallyarea(A,r+d, c) + tallyarea(A,r, c+d);
return areaaround + 1;
}
Yes, sorry I'm a lazy coder, reflected in my style.
- S O U N D W A V E October 22, 2013This was fun and interesting, thanks.
Typing idea raw here (pseudocode + with bugs):
// assume RxC array, R : number of rows, C: number of columns
unsigned int maxarea=0;
for(r=0; r<R; r++)
for(c=0; c<C; c++)
if(A[r][c] == 0)
maxarea = max( tallyarea(A, r, c, R, C) , maxarea ); //inline func.
//recreate array:
for(r=0; r<R; r++)
for(c=0; c<C; c++)
if(A[r][c] == -1)
A[r][c]= 0;
//return max area:
return max area;
//helper recursive function
unsigned int tallyarea(A, r, c, R, C)
{
int i,j;
int areaaround=0;
if( ! (0<=r && r<C && 0<=c && c<C ) ) return 0; //if out of bounds
A[r][c]= -1; //mark this cell as already counted as part of some area
for(i=-1; i<=1; i++)
for(j=-1; j<=1; j++)
if(!(i==0 && j==0) && A[r+i][c+j]==0) //if a nonzero cell is around us
arearound += tallyarea(A,r+i,c+j); //accumulate any unseen area
return areaaround + 1; //unseen area around this cell plus area cell
}
This should be runtime O(RC), the theoretical min. for this problem.
There might be a better way to do this, but I haven't bothered googling.
What would someone call such an algorithm? Blob area something (like Adnan says)?
It's basically DFS, the way I saw it.
//assuming integers (modify as desired), and input array is A[ ]
int zeropos= -1;
long product=1;
int result[A.length] = {0}; //begins life as all 0's
// assume your function can modify result[ ] on behalf of calling function
for(i=0; i < A.length ; i++) {
if( A[i] == 0 ) {
if( zeropos != -1 ) return; //saw 2 zeros, result[ ] all zeros is valid
else zeropos=i, continue; //position of zero
}
product *= A[i]; // accumulate product of nonzero elements
}
//if we had 1 zero in A[ ], result[ ] is all zeroes except at zeropos:
if(zeropos != -1) A[zeropos]=product, return;
//we had no zeroes in A[]
for(i=0; i < A.length ; i++)
result[i] = prod/A[i];
return;
height is usually defined as max depth of any node
h( Node x )
{
if( x == nil ) return 0; //tree rooted at nil has 0 height
//tree rooted here is 1+ height of tallest subtree
return max( h(x.left) , h(x.right) ) +1 ;
}
Haha that's cool!!! Everyone should +1.
That might let 0 through, so you might need to do it like this:
bool isPowerof4(unsigned int n) {
return ( n !=0U && (n & 0xAAAAAAAAU) == 0 && (n&(n-1)) == 0);
}
If they wanted THETA(lglgn) then we have to know what n is.
We can guess that n is the number (or max int).
Then lgn is ~ b where b is number of bites in max int.
Then THETA(lg(b)) suggests binary search in the "bit" space.
Or since LUT is "sparse" you can turn it into a quick function too.
bool LUT[1U << 8]; //look up: is a byte sized integer a power of 4?
//initialize: LUT[1U] = LUT[1U<<2] = LUT[1U<<4] = LUT[1U<<6] = true;
bool ispower4 ( uint x )
{
union {
uint whole;
unsigned char part[sizeof(uint)];
} var;
bool bytecheck = false; //whether we've seen a powerof4 byte
int zerobytes = 0; //count number of all-0 bytes in integer
int i;
var.whole=x;
for(i=0; i < sizeof(uint); i++)
{
if( LUT[var.part[i]] ) bytecheck=true; //i-th byte is a power of 4
else if (var.part[i] == 0x0 ) zerobytes++; //i-th byte is all 0s
}
//all bytes are totally 0s, except 1 byte that is power of 4
return ( zerobytes == sizeof(uint)-1 && bytecheck );
}
or use this instead of LUT (calling it LUT(x) for convenience ) if you don't mind the extra time:
bool LUT(unsigned char b) //returns true if byte "b" is a power of 4
return( b== 1U ||b == 1U<<2 || b==1U<<4 || b==1U<<6 );
Oh this one looked cool.
Write a multibyte example on paper, then you get the idea to use a lookup table:
Note: 4^i = (2^2)^i = 2^(2i)
Also, on paper you see that any integer is a power of 4 precisely when:
1) One of it's bytes is a power of 4
2) All other bytes are fully 0
bool LUT[1U<<8]; //look up: is a byte sized integer a power of 4?
//initialize: LUT[1U] = LUT[1U<<2] = LUT[1U<<4] = LUT[1U<<6] = true;
bool ispower4 ( uint x )
{
union {
uint whole;
unsigned char part[sizeof(uint)];
} var;
bool bytecheck = false; //whether we've seen a byte in the integer that's power of 4
int zerobytes = 0; //count number of all-0 bytes in integer
int i;
var.whole=x;
for(i=0; i < sizeof(uint); i++)
{
if( LUT[var.part[i]] ) bytecheck=true; //i-th byte is a power of 4
else if (var.part[i] == 0x0 ) zerobytes++; //i-th byte is all 0s
}
//all bytes are totally 0s, except 1 byte that is power of 4
return ( zerobytes == sizeof(uint)-1 && bytecheck );
}
typedef unsigned int uint;
#define ALPH_SIZE 26 //for English alphabet
//so long as lower, upper case parts live in contiguous
//ranges of any underlying encoding (ascii, etc.)
uint count[2*ALPH_SIZE + 1]; //lower, upper case & other junk
uint h( char x )
{
return (x >= 'a' && x <='z' ? x-'a' : //lower case
x >= 'A' && x <='Z' ? x-'A'+ALPH_SIZE : //upper case
2*ALPH_SIZE) //all other characters
}
/* precondition: you supply it with strings on English alphabet
that is, the rest of the code in your program
should not create junk strings/characters if you want proper results */
if( s1.length != s2.length ) return false;
for(i=0; i < s1.length ; i++) count[h(s1[i])]++, count[h(s2[i])]--;
for(i=0; i < 2*ALPH_SIZE ; i++) if ( count[i] ) return false;
return true;
typedef unsigned int uint;
#define ALPH_SIZE 26 //for English alphabet
//so long as lower, upper case parts live in contiguous
//ranges of any underlying encoding (ascii, etc.)
uint count[2*ALPH_SIZE + 1]; //lower, upper case & other junk
uint h( char x )
{
return (x >= 'a' && x <='z' ? x-'a' : //lower case
x >= 'A' && x <='Z' ? x-'A'+ALPH_SIZE : //upper case
2*ALPH_SIZE) //all other characters
}
/* precondition: you supply it with strings on English alphabet
that is, the rest of the code in your program
should not create junk strings/characters if you want proper results */
if( s1.length != s2.length ) return false;
for(i=0; i < s1.length ; i++) count[h(s1[i])]++, count[h(s2[i])]--;
for(i=0; i < 2*ALPH_SIZE ; i++) if ( count[i] ) return false;
return true;
+1 @Ajeet.
And QA will always test empty string as first test case, so any developer should mentally check that too.
1) "If we can manage to linear sort the strings, this preprocessing step is free since we have to check every letter regardless"
2) "Keep a count of characters we've seen as we sweep each string from left to right"
Above are two such ways to explain how to get an idea for the solution:
"Use a hash" off the bat is not the way to go.
Ok I'm biased to a single language alphabet in my answer above ^^^^
Hasing, I feel, is not a "algorithm." Some DSs have natural algorithms coming with them, but "use hash" seems like it's not explaning much. In this problem, I think it's better to think of Hash as a final optimization step to get memory size and/or runtime down for specific applications. And there are many hashing techniques... here is one such idea for a specific application niche (probably best application for this question: 1 language, strings on the alphabet compared) ....
One interesting way to hash to get memory size and runtime O(s) down is to strip out all parts of the encoding that are irrelevant to the problem (that is, anagrams usually refer to strings on the actual alphabet characters).
We can make due without even 256 sized count array (even if we are living in ASCII) with a one-to-one hash that maps 'a' to 'z' into integers 0 to 25, and also characters 'A' to 'Z' into 26 to 51 , irrespective of the underlying encoding size.
#define ALPH_SIZE 26 //size of real alphabet
unsigned count int[2*ALPH_SIZE + 1]; //lower, upper case & other
//shifted hash (this is one-to-one on the actual alphabets)
unsigned int alphahash( char x )
{
return ( x >= 'a' && x <='z' ? x-'a' : //lower case
x >= 'A' && x <='Z' ? x-'A'+ALPH_SIZE : //upper case
2*ALPH_SIZE); //all other characters (junk)
//or add other ranges (numbers?)
}
Since the above hash is invertible on the alphabets, we can do the final anagram for-loop just as easily in ~C*52 fixed checks regardless of encoding size (note, this is for this special 1 language anagram niche application).
So O(s=encoding size) become C*52.
Yeah, we can optimize and modify solutions to make them super amazing, but we shouldn't simply post the most fancy one without any explanation. Rather _maybe_ we should show how to "develop" a solution.
Idea => Idea2 => Idea3 => Idea4 => Idea5 => {Optimize/improve/use tricks}
This problem has a "non-trick" chain of ideas that can lead to a good solution for even someone who has never done such a problem.
Anyways time to take a giant break from this place because I'm tired of the way people post questions and how people post responses. People are doing things to save themselves time (like rushing a question post with lack of details or posting a response hoping for validation or a code check) and causing the whole system to become extremely inefficient.
Most people post their code as a response to questions simply as a way to get other people to find bugs in their code.
That is, having a DS that is fixed O(s=encoding size), is better than having one that is O(m=stringsize) for this problem, IMO.
- S O U N D W A V E October 21, 2013@Eugene, Yes correct. I have commented on the O(s) fixed being too large in a reply somewhere else on this thread.
@Siva, In this problem, getting a workable algorithm comes first, the rest is something easily _designable_ with the interviewer (or engineering team), like you say.
for(int i=0, j=strlen(s)-1; i < j; s[i++]^=s[j--]^=s[i]^=s[j] ) ;
That might.
- S O U N D W A V E October 21, 2013For fun only
One liner (C++ maybe) for maximum ugliness:
for(int i=0; int j=strlen(s)-1; i < j; s[i++]^=s[j--]^=s[i]^=s[j] ) ;
Wonder if that works....
- S O U N D W A V E October 21, 2013or if you insist
char[] A = str.toCharArray();
for(int i = 0, j = str.length() - 1; i < j ; i++, j-- )
{
A[i] = A[j];
A[j] = str.charAt(i);
}
str=String.valueOf(A);
No need for your l and c.
- S O U N D W A V E October 21, 2013QA will make that throw an "Array Index Bounds Exception"
Your second line, LENGTH -1, <-- this "can" be 0 - 1 = -1
And no need to charAt insidethe loop. And you need to copy back to str.
Your method should be something like this:
char[] A = str.toCharArray();
for(int i = 0, j = str.length() - 1; i < j ; i++, j-- )
swap( A[i] , A[j] );
str=String.valueOf(A);
or collabedit.com/b386g/history
- S O U N D W A V E October 21, 2013Wow, above had perfect alignment when I pasted it, but it looks like garbage after I clicked Submit.
ideone.com/9jo6Kw , collabedit.com/b386g
Wow, above had perfect alignment when I pasted it, but it looks like garbage after I clicked Submit.
ideone.com/9jo6Kw , collabedit.com/b386g
/* for Yogi.rulzz */
#include <stdio.h>
#include <stdlib.h>
typedef enum {false, true} bool;
char input[]={'a','b','c','z'};
#define N sizeof(input)/sizeof(*input) //size of input array & num. decisions to make
void function()
{
static int decisions = 0; //number of decisions (either fill a letter, or blank decision)
static bool used[N]; //track characters we've used
static char result[N+1]; //result array that will be printed after N decisions
static int respos = 0; //position of result[] each invocation has an option to fill
int i;
if(decisions == N) { //we've made all N decisions in creating result
result[respos]='\0';
if(respos !=0 ) printf("%s\n", result); //print non-empty results
return;
}
//if there is nothing in result array, we can make an empty decision
if( respos == 0 ) decisions++, function(), decisions--;
//try filling result[] with characters from input[]
for(i=0; i < N; i++) {
if( used[i] ) continue; //if i-th character already used, skip it
/* fill result[] with i-th char and recurse */
used[i] = true; //mark i-th character as used
decisions++; //we've made another decision
result[respos++]=input[i]; //place i-th character of input[]
function(), decisions--, respos--; //recurse; unwind variables
used[i] = false; //mark i-th character as unused
}
}
int main (void)
{
function();
return 0;
}
Design decisions like calling the function "function" or using static variables (without passing variables recursively) were made for pedagogical and/or to limit sizes of stack frames.
In real code you'd want to:
1) For variables that don't unwind fully (e.g., used array), you need a wrapper that resets them before each call to the function.
2) You would decide against static variables if you are going to multi-thread into the function.
3) You would call "function" something else (but I find when talking about recursion, and this is only true for a recursive function, people sometimes function better looking at a bland name like "function" ).
4) For deep recursive use, you would might need to change the recursive function (hardware stack) to a software stack based solution to prevent stack overflow.
Please feel free to let me know of bugs in replies or here collabedit.com/b386g
Thank you Yogi, as this was fun and new for me.
Follow-up question to people:
=========================
If Input has a size of N.
How many output strings will there be?
{Counting formula + reasoning for it}
wipes out any polynomial or power function (even fractional) *
- S O U N D W A V E October 21, 2013shinsetsu,
You cannot do this in an effort to justify use of N=num elements: => "So total complexity is O(N log(sqrt(N)))"
Because, log(sqrt(N)) = log(N) inside big O/theta
log wipes out any polynomial.
Even for a 1D array mergesort we can say merge sort's runtime is T(N) = O(N log(any_polynomial(N))) and we would be correct, but we lose precision.
We have to work with the "X" from your post directly.
I still do not get it, what are you correcting with your reply? Any objections?
Count array method above is basically a hash table with trivial hash h(x) = x, that keeps counts of keys seen instead of storing satellite data (i.e., keeps information about duplicate keys). We all know this.
The count array comes naturally from thinking of the abstract solution using linear sorts. To call it a hash table right off the bat is not the right way to go here. We can call "any" array with some meaning given to the index a hash table, since h(index) = index is used to index into the array (implicitly, without a hash function). That's like calling a cherry bomb a WMD.
If someone says "use a hash table of size O(stringsize)" then that is pulling a rabbit out of a hat.
I have explained the process of developing the solution, which is roughly: try to match. theoretical min. => pre-process by linear sort => bucket sort is one such type of sort => strip out unnecessary bits => keep a tally of letters
If character encoding range is too big for your app., then the logical adjustment is another => hash the character counts (to get smaller memory usage). e.g., if you don't want to use a sizeof(int)x64kB count array for unicode in Java, then the adjustment is minor. For one you can use "byte" or "char" then it's only 64kBytes memory, else you can map onto a smaller chunk of memory (e.g., a type of hashing).
And you are incorrect, there is no problem at runtime. The size of the tally array (or tally hash array if you want to go that route) is a matter of design, not a runtime problem. Encoding is fixed at compile time.
swap first with last
....
then?
#define ALPH_SIZE 256
unsigned int count[ALPH_SIZE], i;
if( s1.length != s2.length ) return false;
for(i=0; i < s1.length ; i++) count[ s1[i] ]++, count[ s2[i] ]--;
for(i=0; i < ALPH_SIZE ; i++) if ( count[i] ) return false;
return true;
There is a small bug there (which when coding people will catch); I'll leave it in there as an exercise.
- S O U N D W A V E October 21, 2013Use unsigned int or another "rollover/under" save integer type above.
unsigned int count[ALPH_SIZE]; //or keep it as "int" if roll-under is "safe"
Or modify as necessary for your "more strict" platform.
- S O U N D W A V E October 21, 2013Use unsigned int or another "rollover/under" save integer type above.
unsigned int count[ALPH_SIZE]; //or keep it as "int" if roll-under is "safe"
#define ALPH_SIZE 256 //change as desired based on encoding
int count[ALPH_SIZE], i;
if( s1.length != s2.length ) return false;
for(i=0; i < s1.length ; i++) count[ s1[i] ]++, count[ s2[i] ]--;
for(i=0; i < ALPH_SIZE ) if ( count[i] ) return false;
return true;
RC, nlgn is only a minimum on < comparison sorting.
And no need for hash table or any storage that grows with string size.
Below uses fixed O(encoding size) storage regardless of strings.
Try,
// put in a function returning true if s1, s2 are anagrams
#define ALPH_SIZE 256 //change as desired based on encoding
int count[ALPH_SIZE], i;
if( s1.length != s2.length ) return false;
for(i=0; i < s1.length ; i++) count[ s1[i] ]++, count[ s2[i] ]--;
for(i=0; i < ALPH_SIZE ) if ( count[i] ) return false;
return true;
//please fix bugs too
Note: Above is essentially optimized bucket sort (stripping out the parts not needed from it).
That is, optimized form of abstract solution below(m= string length):
1) t1 = linearsort(s1), t2 = linearsort(s2) <=== O(m) work
2) now compare t1 and t2 letter by letter <=== O(m) work
Any linear sort followed by step through comparing strings works optimally.
The optimized form above came to me after thinking in abstract about linear sorts (then optimizing by "strip out"). The linear sort came to me because I wanted to match the theoretical minimum for the problem as best as possible.
No magic rabbit out of a hat needed. Can we start explaining how we are "thinking" of solutions? Of course, to some people that answer is "I remember this question like the 1000 other questions I remember" but .... and least reverse engineer what you remember as a solution into a thought out process?
Problem solving process:
- You see "sorted array"
- You see lg(n)
Above suggest you try some modified binary search.
Then on paper you work with examples (check middle elements) and decide two things:
1) For this specific problem, which half would I choose and how would I choose it
2) What is the ending condition
sqrt(num)
{
// evaluate the special polynomial at x= num -1
// above can be done with O(K) operations. K is fixed.
return whatever you got ;
}
Can be done in O(1) me thinks (for a range of inputs numbers for our application).
Use Taylor's polynomial theorem.
Find polynomial expansion of sqrt(1+x) about x=0.
For the required range of inputs, design the expansion to have degree K such that the error is within required precision for the range of inputs.
Now you have a polynomial p(x) of degree K to use for your application.
{{
sqrt(num)
{
// evaluate the special polynomial at x= num -1
// above can be done with O(K) operations. K is fixed.
return whatever you got ;
}
}}}
Do you require uniform distribution at the start?
After every deletion ?
Also,
rand(b)%a+rand(b-a) <=== off by one error?
Also, the above might not be very uniform (it is close to uniform if and only if the length of the sequence given by rand() is "long" relative to the b-a ... assuming the C type rand() ).
The question as stated is not clear. After all numbers are are deleted , then what do your function return?
Your example suggests duplicates are allowed.
So jaingok, what would the answer be if I hand you this array:
{1,1,1,1,1,..., 1,1,1,1,1,1,1}
?
I haven't checked the details above no paper yet either.
- S O U N D W A V E October 20, 20131 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
^^^ One one type of extreme case it should run in N^2 :)
Because the axillary mean heap will never have more than 2 elements.
One the other type of extreme case (you know what it is right?), the auxillary min heap will grow from size 1 to N then back down to 1 (roughly)
So it will be roughly ~ C*N * lg(H(N)) where H(N) is the hyperfactorial function
This should be theta bound N^2 *lg(N)
{But not as TIGHT a bound to N^2(lg(N)) as the merge K sorted list thing idea people are using, because in that idea the min heap is almost always having N elements}
So if someone with time can
1) Try to make this idea work (fill in details)
2) Calculate the "expected" runtime based on a reasonable probability distribution on the valid matrix inputs of size NxN.
Maybe expected is closer to ~C*N^2 (best case) than ~C*N*lg(H(N)) (worst)
and it pops out to be some nonsense like N^2 lg(lg(N)) ?
There is hope because:
1) the "worst" case type of input matrix is not going to happen all the time
{Is seems less likely than the best case type of input above}
2) even in the worst case, the min heap grows to size N and back down (doesn't stay at size N for most of the running of algorithm like the merging N lists alg.).
{ Above is my first idea from other thread. Haven't refined it because the other thread got bogged down. }
This was my first idea, re-posted from the other thread:
Treat the matrix has a (quasi) min heap:
LEFT(i, j ) = A[i+1,j] //left child
RIGHT(i, j ) = A[i, j+1] //right child
Note, 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 //descendent check is easy O(1)
of elements already in aux.min heap );
}
return result array
@Michael, yes the problem has an NxN.
So someone responding reasonably has two options:
1) use N without any definition, so the reason know he/she means the N defined in the problem
2) or redefine a new letter and not muddle it up with N from the problem definition
NxN means N rows and N columns.
It makes a big difference in using #rows (or columns) instead of number of elements. How about the fact the question was worded that way? Also think of "log" for one example. log wipes out the effect of squaring and pushes any effect into the bigO hidden constant, and this information is best brought to light by working with N=width.
For another, we are working with a square matrix, so do you think it's good enough to simple state theorems that were "stated" for linear arrays?
See:
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
If the two nonanagram strings are different lengths and we know the lengths ahead of time, we're done ( O(1) ) but ignore that case.
Let m be length of a string (note, they are both equal in length in interesting case).
{Note: Since the problem had no "letters" I, myself, define a letter instead of bringing "historical reasons" as a hidden assumption for what they mean}
Theoretical MIN. for solving the problem is clearly O(m) - you have to check every letter of the strings. Note, O(m) + O(m) = O(m) so I do mean checking both strings.
Can we find a solution that meets the theoretical min.?
Sure, in the abstract, let s1, s2 be our strings.
1) t1 = linearsort(s1), t2 = linearsort(s2) <=== O(m) work
2) now compare t1 and t2 letter by letter <=== O(m) work
Total O(m). We win.
=================
Details: What linear sort you use is a detail that changes the constants hidden in the big O. We can optimize step by step:
1) Counting sort works fine, but we don't need the stability, so maybe it's enough to...
2) BucketSort or basically count number of letters of each string. {Good enough I think}
{Now you can optimize 2) even further with a trick, of counting UP with one string, then DOWN with the other on the same tally array ... this saves some space and time... big deal who cares }
Ok, this whole thread got swamped out by
1) incorrect use of bigO and letters and stating theorems
2) claiming solutions broke the theoretical minimum possible for the problem
and comparing theorems incorrectly
3) not enough discussion of the problem itself....
Time to bail, me thinks.
Michael and Sung:
Letters don't matter. We try to measure the size of the input with the most "independent" and "fundamental" measure possible.
Ok say we are using n or N for measuring things.
If we let n (N) be the numbers of elements, fine.
But this is equal to the square of the width of the matrix. Does it not make sense to use the width instead?
Let's see:
1) If we used number of elements, then sure we can regurgitate formulas (nlgn for mergesort, klgn or whatever for merging k lists), but does it really give insight into this specific problem?
For one, think about O(nlgn) (if we used # elem.) vs. O(n^2 lg n) (if we used width) to describe the runtime of mergesort.
Which is more useful to this problem?
2) n or N or K are irrelevant and can be interchanged for y, u, p, cats, dogs, blah in big-O.
These are "dummy variables" just like the x in f(x) or y in integral(f(y)dy).
Don't commit too many dummy variables to memory. When you study something, don't burn "n is used for this problem" , "K is used for merge lists" into your ROM.
We need to stop memorizing letters along with theorems and matching them to historical studies and problems.
This is like first year physics when people got confused because the diff. equation for the spring based harmonic oscillator is x ' = something.
"Professor, but isn't it dy/dx with x independent variable? it's always f(x) = something in calculus books"
There is an N in the problem, nothing more nothing less.
some other n, some other K , redefining N=all elements .... no
@Ajeet. No need for reference or comp. analysis. or book chapter bro. Work from first principles.
See above my earlier reply. I am fairly certain it is O(N^2 lgN)
Doubt it's O( NlgN )
You have to push N^2 elements in and out of an _up to_ N element min heap.
That's O(N^2) * O(lgN)
You keep editing your initial post making it look more accurate. Why not just comment reply?
Looks O(N^2 lg N).
- S O U N D W A V E October 19, 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 ...
It is O(lglgn) n=the number
- S O U N D W A V E October 22, 2013Constant time function is element of O(lglgn) class of functions.
Do we want theta( lglgn ) ?
Just do two level tower of powers 4^(2^i) <--- that's 2 levels of left shifting
Loop on i until some 4^(2^i) is greater than your number (you can make this platform independent, and even work on mythical infinite sized integers)
.
Then you know the number is between 4^(2^(i-1)) and 4^(2^i) for last seen i
{Except some boundary case(s)}
Now binary search on that range. Lower = 2^(i-1), Upper= 2^i
We don't have to keep calculating powers throughout all this, as we can adjust previous powers whenever we have a loop.
And every ^ you see above is some kind of shifting.