GekkoGordan
BAN USERI trade, trade and then trade.
1. Divide the array into two sets
2. sort the sets.
3. compute sum and find the closest number to the difference using binary search (lower bound) and move it to the other set.
4. Repeat until the difference remains constant
5. should converge really quick
Unless this is a linked list, I don't see a way of doing it in O(n) time and O(1) space
- GekkoGordan February 01, 2011NodePtr tmp,tmp1,tmp2;
tmp1 = ll1; tmp2 = ll2; //point to root initially
tmp = ll1;
while(tmp1!=NULL && tmp2!=NULL){
if(*tmp2<*tmp1){
tmp = tmp2
tmp2 = tmp->next;
tmp->next = tmp1;
continue;
}else{
tmp = tmp1;
tmp1 = tmp->next;
tmp->next = tmp2;
}
}
if(*ll2<*ll1)
ll1 = ll2;
else
ll2 = ll1;
//both lists should be merged and ll1 & ll2 point to the same list
@funny bone: there's no right answer for this question because it totally depends on the problem. min heap, splay trees, skip lists etc.. all of them can give O(logn) performance but if the frequency of numbers changes uniformly then that would affect the performance depending on the data structure.
- GekkoGordan January 31, 2011I prefer a skip list.
- GekkoGordan January 31, 2011ls
- GekkoGordan January 28, 2011indefinite loop? was it a copy constructor passed as a "pass by value"?
- GekkoGordan January 28, 2011if it is 7 it is lucky!!
- GekkoGordan January 28, 2011int count = 0;
-> for ever character c
if(c==' ' || c==';' || c=='-' /*include more delimiters*/)
++count;
-> cout<<"Total count"<<count;
let the lengths of the two arrays be m and n and m<n
create a hashmap from the smaller array --> O(m).
For every element in the larger array check if the element exists in the hashmap. if it does then push into a vector --> O(n)
Time Complexity: O(m) + O(n) ==> O(n) {since m<n}
Space Complexity: O(m) + O(m) ==> O(m)
-> Obtain a pointer to the begin, middle and end of the double linked list and store it.
-> For every new element to be inserted,
check if it is less than middle element or not {O(1)}
traverse to the left or right based on the comparison {O(n/2)}
-> worst case complexity: O(n/2)
space complexity: O(1)
well, going to the middle would take traversing n/2 elements because this is a doubly linked list not an array. so the complexity with this algo would be = n/2 + n/4 + n/8.... + n/n ==> O(n) for searching and O(1) for inserting.
Instead, why not just traverse through the array?
the complexity = O(position_Of_New_Element)
First, assuming that missing numbers are filled in by duplicates of other numbers.
Here's an inplace algorithm:
-> for every element in the array:
:swap elements into their corresponding positions.
->if an element already exists in the right position then it is a duplicate so set it to -1
:traverse the array for '-1's and those positions are missing numbers.
time complexity: O(2n) ==> O(n)
space complexity: O(1)
if next day's stock price is decreasing: sell all holdings and short it.
if next day's stock price is increasing: cover any shorts and buy all in.
you have an answer, post it dude. lets not play "Who's your daddy?"
- GekkoGordan January 28, 2011Isn't that how bitlord works? or any torrent downloader
- GekkoGordan January 28, 2011yep, right on the money
- GekkoGordan January 28, 2011Yep.. a slight modification, computing size of hash table for obtaining the count is not the optimal way.
Instead, use a count variable which is incremented if the element is inserted into hash table else dont increment.
1. use pointers when you know a variable might point to NULL, if your design does not allow for the possibility that the variable is null, you should probably make it a reference variable.
2. pointers can be reassigned but references cannot be. a reference, however, always refers to the object with which it is initialized.
- Item 1 : Basics: Pointers Vs References: from Scott Meyers book "More Effective C++"
@ac6241: Apply dijkstra's starting from A, and then from B. take the max.
- GekkoGordan January 27, 2011@Shyam: hashset definition on Java site "implements the Set interface, backed by a hash table (actually a HashMap instance)."
- GekkoGordan January 27, 2011@Sathya: yes, a divide and conquer strategy which i believe is being abused in this case. A couple of things you got wrong about the 'minmax' function that you provided:
1. It does 2 additional comparisons before calling recursively (the first 'if' and 'else if' conditions)
2. c(2) = 2 due to the same reason above.
3. c(1) = 1 because that's when the first 'if' condition is satisfied.
3. It will be really slow compared to basic looping strategy because the your function has overhead with every function call.
So basically c(n) = 2*c(n/2) + 4 and c(2) = 2,
--> c(n) = 3*n-4. Consider example, n=8, no. of comparisons = 20.
Consider a simpler approach as below:
int min=array[0],max=array[0],i=0;
for(;i<array.size();++i)
if(min>array[i]){
min=array[i];
continue; //no need to check for max
}else if(max<array[i]){
max=array[i];
continue;
}
//The worst case for this would be a ascending series of numbers
//which gives number of comparisons including the for loop condition checking for 'i' --> (2*n - 2 + n) --> 3*n - 2
//best case would be a descending series of numbers --> (n - 1 + n) --> 2*n-1 (includes the loop condition checking)
So compared to an algorithm that always takes 3*n-4 comparisons with space and stack overhead I prefer the above approach.
- GekkoGordan January 27, 2011prince goes down and calls 911 and in the mean time it's the king and queens problem to get out. no worries
- GekkoGordan January 26, 2011worst case total comparisons = (2n-2),
best case total comparisons = (n-1)
questions sound dumb,dude. u sure u wanna work for this company
// code showing basic software design
class ATM; class ReceiptInfo;
class ATMImpl{
friend class ATM;
private:
ATMImpl(){/*implementation*/}
public:
float getBalanceInfo(){/*implementation*/}
ReceiptInfo getReceiptInfo(){/*implementation*/}
bool deposit(float val){/*implementation*/}
bool withdraw(float val){/*implementation*/}
bool verifyPIN(int pinVal){/*implementation*/}
~ATMImpl(){/*implementation*/}
};
class ATM{
private:
ATMImpl *d; //pointer to ATM implementation
public:
inline float getBalance(){return d->getBalance();}
inline ReceiptInfo getReceiptInfo(){return d->getReceiptInfo();}
inline bool deposit(float val){return d->deposit(val);}
inline bool withdraw(float val){return d->withdraw(val);}
inline bool verifyPIN(int pinVal){return d->verifyPIN(pinVal);}
};
class ATM_GUI{
private:
ATM atmObj;
public:
ATM_GUI(){/*initialize GUI*/}
void printReceipt(){atmObj.getReceiptInfo();/*more implementation*/}
void printBalance(){atmObj.getBalance();/*more implementation*/}
inline bool verifyPIN(int pinVal){atmObj.verifyPIN(pinVal);}
inline bool withdraw(float amount){atmObj.withdraw(amount);}//Atomic operation
inline bool deposit(float amount){atmObj.deposit(amount);}//Atomic operation
//more methods (operations)
};
/* Algorithm: //assuming writer thread has the highest priority i.e. readers wont enter CS if writer is waiting for access to CS
* reader_func():
* if writer thread not waiting then proceed
* if less than max_readers atomically increment semaphoreVar
* enter CS
* acquire semaphoremutex.
* decrement, check if writer is waiting and semaphoreVar==0.
* if yes then notify writer
* release semaphoremutex
* else
* max_readers already in CS so try later
* else
* writer thread waiting so try after it is done
*
* writer_func():
* acquire semaphoremutex
* if semaphoreVar!=0 then requestFlag; [release semaphoremutex and wait on condition variable]
* when notified acquire semaphoremutex
* process CS
* release semaphoremutex
*/
int MAX_READERS = 10 /*max readers 10*/ , cSem = 0 /*counting semaphore*/;
volatile bool requestCS = false; //this flag is used by writer to request CS.
WaitCondition waitForReadersExit; //condition variable which is invoked when readers==0.
Mutex semMtx; //mutex for atomically operating on cSem variable
void reader_func()
{
if(!requestCS){ //if writer thread not waiting then proceed
if(testAndIncrement(cSem,MAX_READERS)){ //if cSem less than MAX_READERS then increment it atomically proceed
//Critical Section processing
semMtx.acquire();
--cSem;
if(requestCS && cSem==0) //if writer requested CS and no readers are in CS then
waitForReadersExit.notify(semMtx);//unlock semMtx and notify writer
else
semMtx.release();
}else{
//max readers in CS. Try later
}
}else{
//writer has placed request, wait till writer is done.
}
}
void writer_func()
{
semMtx.acquire();
if(cSem!=0){
requestCS = true;
waitForReadersExit.wait(semMtx) //unlocks 'semMtx' and waits on the condition variable
}
//critical section
requestCS = false;
semMtx.release();
}
//atomically test and increment semaphore variable
bool testAndIncrement(semVar,MAX_READERS){
semMtx.acquire();
if(MAX_READERS>semVar){
++semVar; semMtx.release(); return true;
}semMtx.release();
return false;
}
I prefer hash method. elegant and efficient
- GekkoGordan February 01, 2011