nikolay.dimitrov
BAN USERConsidering rand50() is defined, then rand75() would be
char rand75() {
return !(rand50() && rand50());
}
I still like my approach above but yours makes sense too!
A couple of notes:
- It won't work if you pick the same ball multiple times
- Change the average/2 to average*2 as you have it in your explanation ;)
I think you should be prepared quite well! :))
- nikolay.dimitrov May 20, 2015You take the maximum number from the picked ones, subtract 1, and divide by K = the average gap between elements.
Then simply add this gap to the found maximal one and that's your answer:
vector<int> a = {2,1,6,9,7,10};
int max = 0;
for (int x : a) {
if (max < x)
max = x;
}
cout << max + round((float)(max-1)/a.size()) << endl;
bool compare(Node *a, Node *b) {
stack<Node*> x, y;
// Find the first elements
while (a) {
x.push(a);
a = a->left;
}
while (b) {
y.push(b);
b = b->left;
}
// Walk the trees
while (!x.empty() && !y.empty()) {
a = x.top(); x.pop();
b = y.top(); y.pop();
if (a->value != b->value) {
return false;
}
// Find next node on tree a
if (a->right) x.push(a = a->right);
while (a->left) {
x.push(a = a->left);
}
// Find next node on tree b
if (b->right) y.push(b = b->right);
while (b->left) {
y.push(b = b->left);
}
}
return x.empty() && y.empty();
}
bool match(char *pattern, char *st) {
if (*pattern == 0) return *st == 0;
switch (*pattern) {
case '?' :
return *st ? match(pattern+1, st+1) : false;
case '*' :
if (pattern[1] == 0) return true;
while (*st)
if (match(pattern+1, st++))
return true;
return false;
default: return *st
? *pattern == *st && match(pattern+1, st+1)
: false;
}
}
Yes, not bad. You just have to consider that if 6 is there, your solution always returns true
- nikolay.dimitrov April 16, 2015Nice idea!
- nikolay.dimitrov April 16, 2015The complexity is about (n+1)*logn which is ok
- nikolay.dimitrov April 14, 2015This is my solution using modified binary search to find the closest possible cut that is in the middle of the log:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int find_price(vector<int> &cuts, int from, int to) {
if (from >= to-1) return 0;
int dist=cuts[to]-cuts[from], m=(from+to)/2, cut = -1;
int target=cuts[from]+dist/2, curdiff = dist, tmpdiff = abs(target - cuts[m]);
while (m>from && m<to && curdiff>tmpdiff) {
curdiff = tmpdiff;
cut = m;
// Left or right?
if (abs(target-cuts[m-1]) < abs(target-cuts[m+1])) {
tmpdiff = abs(target-cuts[--m]);
} else {
tmpdiff = abs(target-cuts[++m]);
}
}
if (cut > -1) {
dist += find_price(cuts, from, cut),
dist += find_price(cuts, cut, to);
}
return dist;
}
int main() {
const int len = 80;
vector<int> cuts = {30,41,67,5,10,15,20,25};
cuts.push_back(0);
cuts.push_back(len);
sort(cuts.begin(), cuts.end());
cout << find_price(cuts, 0, cuts.size()-1);
return 0;
}
Yep, I did the same thing without the optimisations:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct {
bool operator() (const int& a, const int& b) {
return abs(a)<abs(b);
}
} comparator;
int main() {
vector<int> a = {-23, -21, 12, 123, 11, 23, 1, -111, 44};
sort(a.begin(), a.end(), comparator);
int min = 100000;
for (int i=0; i<a.size()-1; ++i) {
if (min > abs(a[i]+a[i+1]))
min = abs(a[i]+a[i+1]);
}
cout << min;
return 0;
}
Yep, that's my solution too. Except for 5 the check is against (n+1)/2
- nikolay.dimitrov April 13, 2015Obviously you don't need 3 indexes, as it's same as k-2, k-1 and k.
Good solution!
I reckon there's no way to make it in O(n). The only way is to sort it and keep the indexes... So best case would be O(n*logn)
- nikolay.dimitrov April 06, 2015Yeah, that was a bit naive. That's why you shouldn't be allowed to post late at night! :))
- nikolay.dimitrov April 06, 2015O(n) complexity, simple for loop:
#include <cstdlib>
#include <iostream>
using namespace std;
int main() {
int a[] = {7,6,10,5,2,8,1,9,3,4};
int n = 10, index = 0, win = 0;
for (int i=1; i<n; ++i) {
if (a[i] > a[index])
index = i;
if (win < i-index)
win = i-index;
}
cout << win << endl;
return 0;
}
#include <cstdlib>
#include <iostream>
using namespace std;
struct Node;
typedef pair<Node*, Node*> bounds;
struct Node {
Node *l, *r;
int data;
Node(int d) : data(d) { }
bounds flatten() {
bounds t, b(this, this);
if (l) {
t = l->flatten();
b.first = t.first;
t.second->r = this;
l = t.second;
}
if (r) {
t = r->flatten();
b.second = t.second;
t.first->l = this;
r = t.first;
}
return b;
}
};
int main() {
Node *root = new Node(1);
...
bounds b = root->flatten();
return 0;
}
It will work either way.
Before seeing the answers, I wrote something similar with one additional variable:
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
int main() {
vector<int> a = {10,345,4545,454,542,23,1356,5565,0};
int min=10000, max=-10000, maxDiff = -1;
for (int i=0; i<a.size(); ++i) {
if (min > a[i]) {
min = a[i];
max = a[i];
}
if (max < a[i]) {
max = a[i];
}
if (maxDiff < max - min) {
maxDiff = max - min;
}
}
cout << maxDiff << endl;
return 0;
}
Whenever you are adding to the PriorityQueue, it does sorting behind the scenes, probably at O(n*logn). It is just a sorted linked list, which is the same solution I've posted yesterday
- nikolay.dimitrov March 26, 2015- Keep a sorted list with the chars in frequency order and the number of occurrences
- Generate a random number between 0 and total number of characters
- Go through the list by decrementing the number above with the number of occurrences
- When negative - the current characters is the randomly generated one
C++:
#include <iostream>
#include <cstdlib>
using namespace std;
struct Node {
Node *next;
int data, count;
Node(int d, int c = 1) : data(d), count(c) {}
};
Node* addData(Node *list, int data) {
if (!list) {
return new Node(data);
}
Node *cur = list, *last = 0, *l=0;
while (cur) {
if (cur->data == data) {
cur->count++;
if (last && last->count < cur->count) {
int v = last->data; last->data = cur->data; cur->data = v;
v = last->count; last->count = cur->count; cur->count = v;
}
return list;
}
if (!last || last->count != cur->count) {
last = cur;
}
l = cur;
cur = cur->next;
}
// Not found - append
l->next = new Node(data);
return list;
}
char getRandChar(Node *list, int total) {
int r = rand()%total;
while (r >= list->count) {
r -= list->count;
list = list->next;
}
return (char)list->data;
}
int main() {
int n = 10, count = 0;
Node *list = 0;
string strings[] = {"akdjfsfdf", "sdfsdfsdf", "sdfsdfsdfdsf", "aaaasasasaa"};
for (string s : strings) {
for (char c : s) {
list = addData(list, c);
count++;
}
}
srand (time(NULL));
while (n--) {
cout << getRandChar(list, count);
}
}
#include <iostream>
#include <cstdlib>
using namespace std;
struct Node {
Node *next;
int data, count;
Node(int d, int c = 1) : data(d), count(c) {}
};
Node* addNode(Node *list, int data) {
if (!list) {
return new Node(data);
}
Node *cur = list, *last = 0, *l=0;
while (cur) {
if (cur->data == data) {
cur->count++;
if (last && last->count < cur->count) {
int v = last->data; last->data = cur->data; cur->data = v;
v = last->count; last->count = cur->count; cur->count = v;
}
return list;
}
if (!last || last->count != cur->count) {
last = cur;
}
l = cur;
cur = cur->next;
}
l->next = new Node(data);
return list;
}
int main() {
int k = 2;
int a[] = {0, 0, 100, 3, 5, 4, 6, 4, 2, 100, 2, 100};
Node *list = 0;
for (int i : a) {
list = addNode(list, i);
}
while (--k) {
cout << list->data << ", ";
list = list->next;
}
cout << list->data;
}
#include <iostream>
#include <cstdlib>
using namespace std;
int main() {
float rooms[] = {0.2, 0.3, 0.5};
int full[] = {0, 0, 0};
int total = 0;
// Add 100 test people
for (int i=0; i<100; ++i) {
total++;
for (int j=0; j<3; ++j) {
if (full[j]/(float)total < rooms[j]) {
full[j]++;
break;
}
}
}
for (float i : full) {
cout << i << " ";
}
}
What about O(N) solution with a simple walkthrough of a copy of the array and swapping elements with mirror index values whenever they don't follow a normal sort order.
We can do that as all the sub-elements between the swapped ones can be put in the same order with another reverse operation.
If a is a copy of the original array, then in C++:
- nikolay.dimitrov August 22, 2016