CareerCup

Solution with heap implemented in C++

#include <iostream>
#include <fstream>
#include <queue>

int main() {
	std::priority_queue<int, std::vector<int>, std::greater<int>> queue;
	std::vector<int> vec{10, 20, 30, 40, 50};

	for(auto value: vec) {
		queue.push(value);

		if(queue.size() > 2)
			queue.pop();		
	}

	while(queue.size() > 0) { 
		std::cout << queue.top() << std::endl;
		queue.pop();
	}

	return 0;
}

Quicksort in this case won't be a good option as data is almost sorted and this is the worst case for quick sort (n square).
An merge sort (require additional space) and a insert sort (no additional space) could be a nice option.

The solution above is mine. Forgot to loggin before posting.

The related problem is about format strings. If the user can control de string used as first argument of printf() could dump memory regions or even execute arbitrary code.

My proposal starts with setting the bit of worker in his own bipmap. Ex: worker 0 has bit 0 = 1.

After that, gonna iterate forward doing binary OR with all other workers presented in the bitmap.

As I have to iterate through array changing the bit set, I'm not sure about running complexity.

Follow my code:

/*
Output:

Before:

0011
0010
1100
1000

After:
0011
0011
1100
1100

*/

#include <iostream>
#include <vector>
#include <bitset>

int main() {
	const int bits = 4;
	const int elements = 4;

	std::vector<std::bitset<bits>> workers(elements);
	
	workers[0].set(0, 1).set(1, 1);
	workers[1].set(1, 1);
	workers[2].set(2, 1).set(3, 1);
	workers[3].set(3, 1);
	
	std::cout << "before:" << std::endl;
	for(auto worker: workers)
		std::cout << worker << std::endl;
	std::cout << std::endl << std::endl;
	
	for(int i = 0; i < workers.size(); i++) {
		if(workers[i].any() == false) {
			// Working alone			
			continue;
		}
		
		// Looking for partners
		for(int b = 0; b < workers[i].size(); ++b) {
			if(workers[i].test(b)) {
				// Bit b of worker [i] is set
				workers[i] |= workers[b];
				workers[b] = workers[i];
			}
		}
	}

	std::cout << "after:" << std::endl;
	for(auto worker: workers)
		std::cout << worker << std::endl;

	return 0;
}

30

O(n) complexity with no additional space

/*
  Given a sorted array of integers, write a function that will return the number with the biggest number of repetitions.

  (Asked to refine the solution to be more efficient)
*/

#include <iostream>
#include <vector>

static int max_rep(const std::vector<int>& vec) {
	int big_cnt = 0;
	int saved_int;
	int cnt;

	saved_int = vec[0];
	cnt = 1;
	big_cnt = 1;
	
	for(int i = 1; i < vec.size(); i++) {
		if(saved_int == vec[i]) {
			++cnt;
			continue;
		}

		// Different
		if(cnt > big_cnt) {
			big_cnt = cnt;
		}

		saved_int = vec[i];
		cnt = 1;
	}

	if(cnt > big_cnt)
		big_cnt = cnt;

	return big_cnt;
}

int main() {
	std::vector<int> vec{1, 1, 1, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5};
	std::cout << max_rep(vec) << std::endl;
	return 0;
}

1 0 0 1 0 0 1 0
flip17
1 1 1 0 1 1 0 1
max(1):6
0 0 0 0 1 1 1 0 0 0 0
flip010
1 1 1 1 0 0 0 1 1 1 1
max(1):8

#include <iostream>
#include <vector>

int check_begin(const std::vector<int>& vec) {
	int cnt_zero;
	int cnt_one;
	
	int bigger = 0;
	int saved_i;

	for(int i = 0; i < vec.size(); i++) {
		cnt_one = 0;
		cnt_zero = 0;

		for(int j = i; j < vec.size(); j++) {
			if(vec[j] == 0) {
				++cnt_zero;
			} else {
				++cnt_one;
			}
		}

		int delta = cnt_zero - cnt_one;
		if(delta > bigger || bigger == 0) {
			bigger = delta;
			saved_i = i;
		}
	}

	return saved_i;
}

int check_end(const std::vector<int>& vec, int begin) {
	int cnt_zero;
	int cnt_one;
	
	int bigger = 0;
	int saved_i;

	for(int i = vec.size() - 1; i > begin; i--) {
		for(int j = begin; j <= i; j++) {
			cnt_one = 0;
			cnt_zero = 0;
			
			if(vec[j] == 0) {
				++cnt_zero;
			} else {
				++cnt_one;
			}
		}

		int delta = cnt_zero - cnt_one;

		if(delta > bigger || bigger == 0) {
			bigger = delta;
			saved_i = i;
		}
	}

	return saved_i;
}

static void flip(std::vector<int>& vec, int begin, int end) {
	std::cout << "flip" << begin << end << std::endl;
	for(int i = begin; i <= end; i++) {
		if(vec[i] == 0) {
			vec[i] = 1;
		} else {
			vec[i] = 0;
		}
	}
}

static int count_one(const std::vector<int>& vec) {
	int cnt = 0;
	for(auto c: vec) {
		if(c == 1)
			++cnt;
	}

	return cnt;
}

static void print_vec(const std::vector<int>& vec) {
	for(auto c: vec) std::cout << c << " ";
	std::cout << std::endl;
}

int main() {
	std::vector<int> binvec{1, 0, 0, 1, 0, 0, 1, 0};
	std::vector<int> binvec_test{0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0};
	int begin, end;
	
	print_vec(binvec);
	begin = check_begin(binvec);
	end = check_end(binvec, begin);
	flip(binvec, begin, end);
	print_vec(binvec);
	std::cout << "max(1):" << count_one(binvec) << std::endl;
	

	print_vec(binvec_test);
	begin = check_begin(binvec_test);
	end = check_end(binvec_test, begin);
	flip(binvec_test, begin, end);
	print_vec(binvec_test);
	std::cout << "max(1):" << count_one(binvec_test) << std::endl;

	return 0;
}

#include <iostream>

template <typename T>
struct node {
	node(T value) : value{value}, next{nullptr} {}
	~node() { if(next != nullptr) delete(next); }

	T value;
	node* next;
};

template <typename T>
node<T> * merge_list(node<T> * head1, node<T> * head2) {	
	node<T>* ptr1 = head1;
	node<T>* ptr2 = head2;

	node<T>* merged_list = nullptr;
	node<T>* out;

	while(ptr1 != nullptr && ptr2 != nullptr) {
		if(ptr1->value > ptr2->value) {
			//std::cout << ptr2->value << std::endl;

			if(merged_list == nullptr) {
				merged_list = new node<T>(ptr2->value);
				out = merged_list;
			} else {
				out->next = new node<T>(ptr2->value);
				out = out->next;
			}

			ptr2 = ptr2->next;
		} else {
			//std::cout << ptr1->value << std::endl;
			
			if(merged_list == nullptr) {
				merged_list = new node<T>(ptr1->value);
				out = merged_list;
			} else {
				out->next = new node<T>(ptr1->value);
				out = out->next;
			}

			ptr1 = ptr1->next;
		}
	}

	while(ptr1 != nullptr) {
		//std::cout << ptr1->value << std::endl;
		out->next = new node<T>(ptr1->value);
		out = out->next;

		ptr1 = ptr1->next;
	}

	while(ptr2 != nullptr) {
		//std::cout << ptr2->value << std::endl;
		out->next = new node<T>(ptr2->value);
		out = out->next;

		ptr2 = ptr2->next;
	}

	return merged_list;
}

int main() {
	node<int>* head1 = new node<int>(2);
	head1->next = new node<int>(2);
	head1->next->next = new node<int>(4);
	head1->next->next->next = new node<int>(6);

	node<int>* head2 = new node<int>(1);
	head2->next = new node<int>(3);
	head2->next->next = new node<int>(5);

	node<int>* merged_list = merge_list<int>(head1, head2);

	delete head1;
	delete head2;
	
	node<int>* ptr = merged_list;
	while(ptr != nullptr) {
		std::cout << ptr->value << std::endl;
		ptr = ptr->next;
	}

	delete merged_list;

	return 0;
}