Dr. Andrew
BAN USER1. Find the n * 1/3 and n * 2/3 largest element using QuickSelect. In order for an element to occur more than 1/3 of the time in the array, it must be one of these two elements.
2. Do a linear pass through the array to see if the array contains these two elements.
I agree. 2111 should only be in there once, for instance.
- Dr. Andrew December 05, 2012Well, if asked in an interview, using the STL in this way would be my first response. I think it's legitimate since the STL is a part of ANSI C++. If they then said, "How would you do this if you didn't have std::next_permutation?", then I would need to implement something similar to next_permutation myself.
- Dr. Andrew December 05, 2012This is trivial to do in C++ with the STL since there's a built-in function that does exactly this.
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
void permute(const string &s) {
string my_string = s;
sort(my_string.begin(),my_string.end());
do {
cout << my_string << "\n";
} while (next_permutation(my_string.begin(),my_string.end()));
}
int main(int argc, const char * argv[])
{
std::cout << "Please enter a string to permute\n";
string perm_string;
std::cin >> perm_string;
permute(perm_string);
return 0;
}
This is tested code in C++, making use of the STL.
#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
struct sequence {
int start_num;
int sequence_length;
};
void sequencify(int *input,int length,list<sequence> &first_seq) {
list<sequence> retval;
if (input == NULL || length < 1) {
return;
}
sequence s;
s.start_num = *input;
s.sequence_length = 1;
first_seq.push_back(s);
for (int *i = input + 1;i < input + length;i++) {
if (*(i - 1) == (*i) - 1) {
first_seq.back().sequence_length++;
}
else {
sequence s;
s.start_num = *i;
s.sequence_length = 1;
first_seq.push_back(s);
}
}
}
int main(int argc, const char * argv[])
{
vector<int> vecint;
for (int i = 0;i < 100;i++) {
vecint.push_back((int) rand()%100);
}
sort(vecint.begin(),vecint.end());
for (int j : vecint) {
cout << j << " ";
}
cout << endl;
list<sequence> result;
sequencify( vecint.data(), vecint.size(), result);
for (auto j : result) {
cout << "Start: " << j.start_num << " Length " << j.sequence_length << "\n";
}
return 0;
}
I'm assuming that the digits come in from left to right and that you have no idea when the number ends.
This approach uses O(n) space and has a pretty clean implementation, I think.
#include <iostream>
#include <deque>
#include <string>
#include <assert.h>
using namespace std;
class Incrementer {
deque<int> number;
public:
void add_digit(int digit) {
assert(digit >= 0 && digit <= 9);
number.push_back(digit);
}
void increment() {
deque<int>::iterator cur = number.end() - 1;
while (cur >= number.begin() && (*cur == 9)) {
*cur = 0;
cur--;
}
if (cur < number.begin()) {
number.push_front(1);
}
else {
*cur = (*cur) + 1;
}
}
string getNumber() {
string retval;
for (auto j = number.begin();j < number.end();j++) {
assert(*j >= 0 && *j <= 9);
retval.push_back('0' + *j);
}
return retval;
}
};
int main(int argc, const char * argv[])
{
Incrementer inc;
std::cout << "Please enter the number to test\n";
string input;
cin >> input;
for (string::iterator j = input.begin();j != input.end();j++) {
inc.add_digit((*j) - '0');
}
inc.increment();
cout << "The incremented number is: " << "\n";
cout << inc.getNumber() << "\n";
return 0;
}
RepSpent several months writing about boyfriend ki shadi todne ke upay .Spent 2001-2007 donating carp in Las Vegas, NV. My ...
@alex: I haven't implemented it myself yet, but the QuickSelect algorithm (see Wikipedia), as I understand it, would give you the nth smallest element in an unordered list. So in your list of 6, I'm saying it would pick the 2nd and 4th largest elements, counting duplicate elements, so the 2nd largest is 1 and the 4th largest is 3. Any list longer than 1/3 of the list has to touch one or both of those ranks.
- Dr. Andrew December 10, 2012