nikolay.dimitrov
BAN USERConsidering rand50() is defined, then rand75() would be
char rand75() {
return !(rand50() && rand50());
}

nikolay.dimitrov
July 23, 2016 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)(max1)/a.size()) << endl;

nikolay.dimitrov
May 20, 2015 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();
}

nikolay.dimitrov
April 30, 2015 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;
}
}

nikolay.dimitrov
April 17, 2015 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 >= to1) 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(targetcuts[m1]) < abs(targetcuts[m+1])) {
tmpdiff = abs(targetcuts[m]);
} else {
tmpdiff = abs(targetcuts[++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;
}

nikolay.dimitrov
April 14, 2015 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;
}

nikolay.dimitrov
April 13, 2015 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 k2, k1 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 < iindex)
win = iindex;
}
cout << win << endl;
return 0;
}

nikolay.dimitrov
April 05, 2015 #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;
}

nikolay.dimitrov
April 05, 2015 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;
}

nikolay.dimitrov
March 31, 2015 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);
}
}

nikolay.dimitrov
March 26, 2015 #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;
}

nikolay.dimitrov
March 25, 2015 #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 << " ";
}
}

nikolay.dimitrov
March 24, 2015 Open Chat in New Window
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 subelements 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