ninhnnsoc
BAN USERThis relevant problem may interest you:
What if the array is NOT sorted, and the "popularity" is defined as repeated more than n/2 times?
We can find that popular element in linear time and constant extra space. The idea is similar to "majority voting".
Code illustrates majority voting:
int candidate = A[0];
int vote = 1;
for(int k = 1; k<N; k++){
if (candidate == A[k]){
vote ++;
continue;
};
if (vote > 0){
vote --;
continue;
}else{
candidate = A[k];
vote = 1;
}
};
//double check for candidate:
vote = 0;
for(int k = 0; k<N; k++) vote += (candidate == A[k]);
if (vote > N/2) cout <<"Popular element is: "<<candidate<<endl;
This link gives details: capacode.com/?p=496
- ninhnnsoc February 28, 2015The hard part is how to make sure the rand7() gives equally random probability.
The easiest way is to create a look-up table, where the table stores numbers from 1 to 7 with equal probability. And then think of a way to map rand5() results into the look-up table, with equal chance of mapping to any entry.
Thus, we can design a look-up table of size 5x5 as follow, where each number from 1 to 7 appears 3 times each:
Table = { 1, 1, 1, 2, 2,
2, 3, 3, 3, 4,
4, 4, 5, 5, 5,
6, 6, 6, 7, 7,
7, 8, 8, 8, 8
}
Rand7() can be following:
rand7(){
do{
row = rand5() -1;
col = rand5() -1;
r7 = Table[row][col];
} while (r7 > 7);
return r7;
}
We can see that row, col are equally likely between 0 to 4. Thus, each entry of the Table is chosen equally likely.
The loop condition while(r7>7) make sure that we only generate numbers from 1 to 7.
Use Sliding Window to slides along the sequence, watching the sum of numbers inside the window:
If sum less than T: expand the window to the right;
If sum = T: report true, finish;
If sum > T: shrink the window from left.
EDIT:
This algorithm works for positive numbers.
It takes O(N) time, O(1) space, where N is the size of array.
Pseudo code (which is almost code!):
checkSum(){
wL = 0, wR = 0, sum = A[0]; // fixed by phantomlord, thanks!
while(wR<N){
if (sum < T){
wR++; //expand to the right
sum += A[wR]; //update sum
};
if (sum==T) return true;
if (sum > T){
sum -= A[wL]; //update sum
wL++; //shrink from left
};
};
return false;
}
EDIT2:
For input of both NEGATIVE and positive numbers: we can store cumulative sum at each position in a hash table and check for the sum of T along the way.
If we see Sum at current position i, and saw Sum-T at some previous position j, then all numbers between j and i will sum up to T.
Remember to check the case Sum-T = Sum. To avoid that case, need to check the hash table before inserting current Sum into it.
Still O(N) time, but O(N) space needed.
Credit to eugene.varovoi!
Pseudo code:
checkSum(){
Sum = 0;
HashSet = {};
for i = 0..N-1
Sum += A[i];
//if see a value of (Sum-T) previously, report true, else insert current Sum in:
if HashSet contains (Sum-T) then return true;
else HashSet.insert(Sum);
};
return false;
}
This is minimum set cover problem, I think.
Each seller can "cover" a set of products.
We have to find the minimum number of sellers to cover all required products.
Minimum Set Cover is a NP-hard problem.
Thus, if we want to find optimal solution, heuristic should be used. Or transform it into an integer linear programming instance, then use ILP solver to solve.
If we want to find some approximated solution, greedy may work fine.
Suppose we have only 3 balls, 1 of them is heavier. This is 3-ball problem.
Then, we take 2 balls, leave 1 ball alone. Weight 2 chosen balls by a balance scale. We can easily identify which ball is heavier: one of the two chosen balls (if the scale is not balanced) or the one that left alone (if the scale is balanced).
So for 3 balls we can solve using 1 operation.
Now instead one ball, we put 3 balls into a bag. Thus, we have 3 bags, one of them is heavier. It becomes 3-bag problem. Using 1 operation we can identify which bag is heavier.
Then it reduces problem to the 3-ball problem above.
Totally, 2 operations are enough to find the heavier ball.
This problem can be solved by dynamic programming, with O(L.M) time and O(L) space, where L is the length of the input string, and M is the length of the longest word in the dictionary.
The dynamic programming idea is the same/similar to this Valid String problem, described in this link capacode.com/?p=285
My friend gives DP solution for checking valid string at the above link. Using the computed DP table, we can easily output the sentence itself.
@hiuhchan: The relative order of numbers must be preserved. Sorting violates that.
@Explain: Hi, explanation can be found by this link: capacode.com/?p=419
That link also gives how to reconstruct the sub-sequence itself.
I am just lazy to copy-paste :D.
The code is in C++ and it's working fine. LEOS is built on the fly, no need to initialize, *it = A[k] means change the position pointing by iterator it to A[k].
Probably you may want to look at the link for details.
This is longest increasing sub-sequence. It can be solved using dynamic programming.
The best implementation I know so far runs in O(nlogn) time.
If we are only required to find the length of the longest increasing sub-sequence, code can be short as following:
#include <iostream>
#include <algorithm>
using namespace std;
int A[] = {10, 8, 6, 10, 2, 10, 6, 14, 4, 9, 5, 13, 3, 11, 7, 15, 80, 9, 10, 10,10,10};
int N = sizeof(A)/sizeof(int);
vector<int> LEOS;
vector<int>::iterator it;
//-----------------------------------------------
// Change upper_bound() into lower_bound() to get strictly increasing subsquence!
void LISS(){
for(int k=0; k<N; k++){
it = upper_bound(LEOS.begin(), LEOS.end(), A[k]);
if (it == LEOS.end()) LEOS.push_back(A[k]);
else *it = A[k];
};
cout <<"Length of the LIS is: "<<LEOS.size()<<endl;
};
//-----------------------------------------------
int main(){
LISS();
return 0;
}
Follow this link for more details: http www capacode.com/?p=419
Seems like the 3n/2-comparison algorithm beats 2n-comparison algorithm for data type of double and string. This is reasonable since comparing double/string is costlier than comparing int.
Statistic:
Generated 1000000 numbers/(strings of length 2): 116 [ms]
3n/2 comparisons: 37.73 [ms]
2n comparisons: 47.64 [ms]
Code (again):
#include <iostream>
#include <sys/time.h>
#include <stdlib.h> /* srand, rand */
using namespace std;
long int milisecond(struct timeval tp){
long int ms = tp.tv_sec * 1000 + tp.tv_usec / 1000;
return ms;
};
typedef string myType;
//typedef double myType;
//typedef int myType;
const int N = 1000000;
const int LEN = 2;
myType A[N+10];
myType MIN, MAX;
void generateRandom(){
srand (time(NULL));
for(int i=0;i<N; i++){
//string:
for(int j=0;j<LEN;j++)
A[i] += (rand()%26) + 'A';
//double:
//A[i] = rand()%N /N;
//int:
//A[i] = rand()%N;
};
};
void FindMinimunMax(){
myType max = A[0];
myType min = A[0];
for(int i = 0; i < N; i++){
if (max < A[i] ){
max = A[i];
}else if(min > A[i]){
min = A[i];
}
}
MIN = min, MAX = max;
}
void findMinMax3n2(){
if (N%2) A[N] = A[N-1];
myType mi = A[0];
myType ma = A[0];
int i = 0;
for(; i<N; i+=2){
if (A[i]<A[i+1]){
if (mi>A[i]) mi = A[i];
if (ma<A[i+1]) ma = A[i+1];
}else{
if (mi>A[i+1]) mi = A[i+1];
if (ma<A[i]) ma = A[i];
};
}
MIN = mi, MAX = ma;
}
int main()
{
struct timeval start, end;
gettimeofday(&start,NULL);
generateRandom();
gettimeofday(&end,NULL);
cout<<"Generated "<<N<<" numbers/(strings of length "<<LEN<<"): "<<milisecond(end)-milisecond(start)<<" [ms]"<<endl;
int nRuns = 100;
gettimeofday(&start,NULL);
for(int i=0;i<nRuns;i++)
findMinMax3n2();
gettimeofday(&end,NULL);
cout<<"3n/2 comparisons: "<<(0.0+milisecond(end)-milisecond(start)) / nRuns<<" [ms]"<<endl;
gettimeofday(&start,NULL);
for(int i=0;i<nRuns;i++)
FindMinimunMax();
gettimeofday(&end,NULL);
cout<<"2n comparisons: "<<(0.0+milisecond(end)-milisecond(start)) / nRuns<<" [ms]"<<endl;
return 0;
}
Sorry, there's typo in the above code.
Wrong one:
A[i] = (rand()%26) + 'A';
Correct one:
A[i] += (rand()%26) + 'A';
Statistics:
Generated 1000000 strings of length 2: 116 [ms]
3n/2 comparisons: 40.14 [ms]
2n comparisons: 47.61 [ms]
(I would like to request careercup to bring back the edit button)
- ninhnnsoc February 23, 2015@Perez: You assume all operations are equally fast.
How about comparing strings?
Statistic on my machine over 100 runs:
Generated 1000000 strings of length 2: 87 [ms]
3n/2 comparisons: 40.44 [ms]
2n comparisons: 47.92 [ms]
Code for benchmarking in C++:
#include <iostream>
#include <sys/time.h>
#include <stdlib.h> /* srand, rand */
using namespace std;
long int milisecond(struct timeval tp){
long int ms = tp.tv_sec * 1000 + tp.tv_usec / 1000;
return ms;
};
const int N = 1000000;
const int LEN = 2;
string A[N+10];
string MIN, MAX;
void generateRandom(){
srand (time(NULL));
for(int i=0;i<N; i++){
for(int j=0;j<LEN;j++)
A[i] = (rand()%26) + 'A';
};
};
void FindMinimunMax(){
string max = A[0];
string min = A[0];
for(int i = 0; i < N; i++){
if (max < A[i] ){
max = A[i];
}else if(min > A[i]){
min = A[i];
}
}
MIN = min, MAX = max;
}
void findMinMax3n2(){
if (N%2) A[N] = A[N-1];
string mi = A[0];
string ma = A[0];
int i = 0;
for(; i<N; i+=2){
if (A[i]<A[i+1]){
mi = mi>A[i]?A[i]:mi;
ma = ma<A[i+1]?A[i+1]:ma;
}else{
mi = mi>A[i+1]?A[i+1]:mi;
ma = ma<A[i]?A[i]:ma;
};
}
MIN = mi, MAX = ma;
}
int main()
{
struct timeval start, end;
gettimeofday(&start,NULL);
generateRandom();
gettimeofday(&end,NULL);
cout<<"Generated "<<N<<" strings of length "<<LEN<<": "<<milisecond(end)-milisecond(start)<<" [ms]"<<endl;
int nRuns = 100;
gettimeofday(&start,NULL);
for(int i=0;i<nRuns;i++)
findMinMax3n2();
gettimeofday(&end,NULL);
cout<<"3n/2 comparisons: "<<(0.0+milisecond(end)-milisecond(start)) / nRuns<<" [ms]"<<endl;
gettimeofday(&start,NULL);
for(int i=0;i<nRuns;i++)
FindMinimunMax();
gettimeofday(&end,NULL);
cout<<"2n comparisons: "<<(0.0+milisecond(end)-milisecond(start)) / nRuns<<" [ms]"<<endl;
return 0;
}
Sorry, the increment of for-loop must be 2 each time:
if (n%2) A[n] = A[n-1];
mi = INF;
ma = -INF;
for(int i = 0; i<n; i+=2){
if (A[i]<A[i+1]){
mi = min (mi, A[i]);
ma = max (ma, A[i+1]);
}else{
mi = min (mi, A[i+1]);
ma = max (ma, A[i]);
};
}
(Just realized that the edit function of career cup is off now)
- ninhnnsoc February 22, 2015Some code:
if (n%2) A[n] = A[n-1];
mi = INF;
ma = -INF;
for(int i = 0; i<n; i++){
if (A[i]<A[i+1]){
mi = min (mi, A[i]);
ma = max (ma, A[i+1]);
}else{
mi = min (mi, A[i+1]);
ma = max (ma, A[i]);
};
}
This take about 3n/2 comparisons because for each 2 elements, it takes 3 comparisons.
- ninhnnsoc February 22, 2015Seems like there is a confusion in the wording of the question:
K-th largest element
vs.
K largest elements
For "K-th largest element":
--------------------------
Use quick select algorithm with linear time complexity.
For "K largest elements":
--------------------------
There are 4 solutions worth discussing:
Solution #1. Min-Heap solution with O(N log K) time, O(K) extra space:
Use a min heap of size at most K to store elements. Keep inserting element into the min heap. When the size is K+1, we know that the minimum element in the heap will always smaller than at least K other elements (also in the min heap now). Thus, that minimum element must be extracted from the heap, maintaining the heap size of at most K.
Solution #2. Max Heap solution, with O(K log N) time, O(N) space:
Use a max heap of size N. Making a heap (e.g., max heap) from an array of size N can be done in O(N) time, no extra space. After making such a max heap of size N, just extract K elements from it to get K largest elements, in O(K log N) time.
Note, when K<<N, K log N is also << N log K. Therefore, the max-heap solution has better time complexity than the min-heap solution.
Solution #3. Algorithm via quick select idea:
- Find the K-th largest element X using quick select, in O(N) time.
- Partition the array into 2 parts, using X as the pivot, in O(N) time. Suppose the left part contains all K numbers >= X.
- Sort the left part, using most efficient sorting algorithm, which takes f(K) time.
Time complexity: O(N + f(K)). Where f(K) = K if using linear time sorting algorithm, or f(K) = K log K if use comparison-based sorting algorithm, like merge sort.
Solution #4. Algorithm via sorting:
- Sort the array;
- Print first K largest elements.
Complexity of sorting algorithms can be:
- O(N log N), if use best comparison-based sorting algorithm like merge short;
- O(N*L) if use radix sort, where L = length of the largest element, can consider L = O(1);
- O(N + M) if use counting sort, where M = value of the largest element.
My order of preference (based on time complexity and easiness of implementation):
1. radix sort, if O(N) extra space is allowed;
2. max-heap, if modification on original array is allowed (for make_heap()), or O(N) extra space is allowed;
3. min-heap, if O(K) space is allowed;
4. partitioning via quick select (not trivial implementation).
@Phoenix: your output comes from a wrong algorithm, isn't it?
UPDATED:
O(N+M) time algorithm:
- Merge two sorted interval lists into one sorted list, sorted by start time
- Consider the begin of each interval as a time-point;
- For each time-point, keep track of the latest time of any busy period we see so far.
- If this latest time is still before the next time-point, that will be the free period.
Code is quite short:
#include <iostream>
#include <algorithm>
using namespace std;
int N=5;
pair<int,int> Person1[] = { {1,5}, {10, 14}, {19,20}, {21,24}, {27,30} };
int M=4;
pair<int,int> Person2[] = { {3,5}, {12, 15}, {18,21}, {23,24} };
pair<int,int> TimePoints[100];
int C=N+M;
int main()
{
//merge two sorted lists into a list sorted by start time
int p1=0, p2=0, k=0;
while(k<C){
if (Person1[p1].first < Person2[p2].first
||( Person1[p1].first == Person2[p2].first &&
Person1[p1].second < Person2[p2].second ))
TimePoints[k++] = Person1[p1++];
else
TimePoints[k++] = Person2[p2++];
if (p1 >=N) while(p2<M) TimePoints[k++] = Person2[p2++];
if (p2 >=M) while(p1<N) TimePoints[k++] = Person1[p1++];
};
//mark latest time so far and print free period
int latestSoFar = 0;
for(int i = 0; i < C-1; i++){
latestSoFar = max(latestSoFar, TimePoints[i].second);
if (TimePoints[i+1].first > latestSoFar) // next start time is after the latest
cout <<latestSoFar<<" "<<TimePoints[i+1].first<<endl;
}
return 0;
}
@Victor: we have to count number of people for EACH age, isn't it?
So, just count all the ages into a counter with O(n+MaxAge) time, O(MaxAge) space.
Can't do better than O(n) time!
int AgeCnt[150], MaxAge= -1;
for(int i = 0; i<n; i++){
MaxAge= max(MaxAge, Input[i]);
AgeCnt [Input[i]]++;
};
for(int i = 0; i<MaxAge; i++)
cout <<"There are "<<AgeCnt[i] <<" people have age "<<i<<endl;
O(length(A) + length(B)) time solution:
#include <iostream>
using namespace std;
int charSet[256];
int main()
{
string A = "Picture";
string B = "Epic";
for(int i = 0; i<A.length(); i++) A[i] = toupper(A[i]);
for(int i = 0; i<B.length(); i++) B[i] = toupper(B[i]);
for(int i = 0; i<A.length(); i++) charSet[A[i]] =1;
int bull = 0, cow = 0;
for(int i = 0; i<B.length(); i++){
if (i<A.length())
bull += A[i] == B[i];
cow += charSet[B[i]];
};
cow -= bull;
cout <<"bull = "<<bull<<endl<<"cow = "<<cow<<endl;
return 0;
}
Good try! It's dynamic programming.
Your implemtation is recursive, and it's much worse than O(n^2). Should use recursive with memorization, then can improve to O(n^2).
However, recursive memorization doesn't improve over bottom-up and it has costly overhead. Bottom-up is better in this problem.
Dynamic programming approach:
Define OPT function
OPT(i,j) be the maximum length of palindromes considering in the input array A from i to j.
Recursive formula is:
OPT(i,j) = 2 + OPT(i+1, j-1) if A[i] = A[j],
= max (OPT(i,j-1), OPT(i+1,j), otherwise.
Initial values:
OPT(i,i) =1 for all i.
The final answer is OPT(1,n).
How to calculate the table OPT:
Consider each length k of a range, k = 2..n
For each length k, calculate all OPT(i, i+k) entries using the previously calculated entries with shorter length.
This bottom-up implementation is O(n^2).
I think time complexity of this implementation is O(logN * logN), where N is the value of the desired sum, assuming adding/comparison two (big) integers is O(1). (In fact, adding/comparison of two big numbers N and M is O(max(logN, logM)).
Why it is O(logN * logN) time? Well, we have at most O(logN) number of Fibonacci numbers that are not larger than N.
The minimum number of Fibonacci needed is also of O(logN).
In the OP implementation, the split() function is called O(logN) times. For each call, the function getHighestFibNumber() takes about O(logN) to loop through the list of "cached" Fibonacci numbers. Thus, overall running time is O(logN * logN).
So, if using binary search for getHighestFibNumber(), the overall complexity can be reduced to O(logN * log(logN)).
Even better, if we process the Fibonacci list from back to front, we can get average O(1) for getHighestFibNumber(), thus improving to O(logN) overall.
Keshav's implementation below achieves O(logN) time complexity.
Note that, we can't do better than O(logN), which is= number of Fibonacci numbers less than N. Thus, O(logN) time algorithm is optimally efficient for this problem.
@Vishnu: did you mean n = number of Fibonacci numbers = log N? Then you're correct!
We should have to mention that this greedy works fine for Fibonacci series.
Your implementation using stack is really nice!
By the way, you state that your algorithm is O(log(sqrt(N)), which indeed is = O(log N) (where N is the value of the desired sum).
The number of Fibonacci numbers that less than N is of O(log(N)) already. How did you get the sqrt()?
Hi all,
Seems like we don't have a consensus definition on the "relative position".
For example, is NE exactly northeast or "approximately" northeast?
So, what is your opinion on this example: Is it possible or impossible?:
p1 SE p2; p3 NE p2; p3 NE p1; p4 SW p1; p5 SE p4; p5 SE p1; p3 NE p5.
(First 3 points are in my previous example).
This example is a W-shape, where p3 and p5 run to infinity. But the last pair "p3 NE p5" may or may not be possible, depends on how NE direction is defined.
Thanks!
Yes, this is "coin change" or "change-making" problem, the only minor difference is that the given coin system is not finite.
Fibonacci is a canonical coin system, i.e., a coin system for which a greedy algorithm can give result as good as the optimal result.
Greedy algorithm for this problem is efficient enough.
Great job!
Rep
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
RepLoler, Employee at Google
RepNelson Perez, Software Engineer
Repaliciagreene771, Vashikaran mantra for get my love back at None
Hello! How are you,My name is Alicia Greene I am from London (UK). I am a Business English, Math ...
RepNoahTaylor, abc at A9
Accomplished software developer with many years of experience in development of applications. Excels in every stage of the life cycle ...
RepEarned praise for analyzing acne for the government. Earned praised for my work implementing mantra to get desired husband in ...
Replamisobbeya45, Student at None
Hello there, My name is Lamis Obbeya I am from Brooklyn, New York . I am 29 years of age. I ...
RepAugment is a mobile app that lets you and your customers visualize your 3D models in Augmented Reality. If you ...
RepNellieWheeler212, None at Service Now
Hey Everyone! My name is Nellie Wheeler and I live in the constantly radiant and wonderful San Francisco, CA, and ...
RepA real dynamo when it comes to buying and selling carnival rides in Fort Lauderdale, FL. Spend several years working ...
Repmorganweiler771, Employee at None
Hello Everyone, I am Morgan Weiler I am from Mumbai, (India).I enjoy Watching TV, playing guitar, Yoga and reading ...
RepAre you looking a solution for marry your love? Islamic dua to marry someone you love is the effective solution ...
RepPandit Ji is the best vashikaran expert for vashikaran mantra for girlfriend in Mumbai.It is the strongest method to ...
RepAre you looking for strong dua for husband love?Astrology is the perfect way to get your lost love back ...
RepAmber Van is registered and fully insured cheap removal company in Bristol.Our featured services includes domestic moves,commercial moves ...
Rep
RepAre you wasting time for to search a professional astrologer and specialist to get rid of black magic?Black Magic ...
Repaalvinbrowne, Android Engineer at ASAPInfosystemsPvtLtd
Working as an Agricultural laborer at Mars Music I maintain yields like natural products, vegetables, grains, and nuts, or take ...
RepLeonaDWilliams, Analyst at CCN
At the moment I'm building banjos in Deltona, FL. Once had a dream of analyzing easy-bake-ovens in Fort Walton ...
RepDo you want to marry with your desired person? The Islamic dua for marriage with a loved one has great ...
RepCeliaParker, teacher at Illinoisstate
Experienced teacher with a background in education who is looking to complement graduate studies with the opportunity to teach at ...
Very interesting problem!
Optimally we need log2(52!) = 226 bits to send 52 cards.
I have other approach, as following:
Send first K cards.
Then, send 52-K cards recursively.
To send first K cards: there are K-permutations of 52 cards, which is P(K,52). This must take ceil(log2(P(K,52)) bits. After sending K cards, the receiver decodes these K cards, and now both sides know exactly which are 52-K cards remaining.
We can compute optimal K by dynamic programming (see my code for details).
An example for sending N = 6 cards:
I can get a result of 227 bits for sending 52 cards, with following sequences, which is easy for encode/decode (less than 32bits each time):
One of optimal sequences is (but quite hard to encode/decode):
Following program gives above result:
- ninhnnsoc February 28, 2015