GatorsRock
BAN USER#include <iostream>
#include <vector>
#include <cmath>
#include <list>
using namespace std;
list<int> findUnion(list<int> a, list<int> b){
list<int> ab;
while(!a.empty() && !b.empty()) {
if(a.front() <= b.front()) {
ab.push_back(a.front());
a.pop_front();
} else {
ab.push_back(b.front());
b.pop_front();
}
}
while(!a.empty()) {
ab.push_back(a.front());
a.pop_front();
}
a.swap(b);
while(!a.empty()) {
ab.push_back(a.front());
a.pop_front();
}
return ab;
}
list<int> findIntersection(list<int> a, list<int> b) {
list<int> ab;
while(!a.empty() && !b.empty()) {
if(a.front() == b.front()) {
ab.push_back(a.front());
a.pop_front();
b.pop_front();
} else if(a.front()<b.front()) {
a.pop_front();
} else {
b.pop_front();
}
}
return ab;
}
int main() {
list<int> a, b, ab;
for(int i=1; i<10; i++) {
if(i%2)
a.push_back(i);
else {
b.push_back(i);
if(i>5)
a.push_back(i);
}
}
ab = findUnion(a, b);
for(auto i: ab) {
cout<<i<<" ";
}
cout<<endl;
ab = findIntersection(a, b);
for(auto i: ab) {
cout<<i<<" ";
}
return 0;
}
stdout: Success time: 0 memory: 3472 signal:0
1 2 3 4 5 6 6 7 8 8 9
6 8
#include <iostream>
#include <vector>
#include <cmath>
#include <list>
using namespace std;
void interval(list<pair<int, int>> &I, pair<int, int> m) {
bool f = false;
list<pair<int, int>>::iterator it = I.begin();
while(it!= I.end())
{
if(m.second<(*it).first) {
I.insert(it, m); return;
} else if(m.first>(*it).second) {
++it; continue;
} else {
(*it).first = min((*it).first, m.first);
(*it).second = max((*it).second, m.second);
f = true; break;
}
}
if(f == false || it == I.end()) {
I.push_back(m); return;
}
list<pair<int, int>>::iterator it2 = it; ++it;
while(it!=I.end()) {
if((*it).first <= (*it2).second) {
(*it2).second = max((*it2).second, (*it).second);
it = I.erase(it);
} else {
return;
}
}
}
int main() {
std::list<std::pair<int, int>> a = {
std::pair<int, int>(-10, -1), std::pair<int, int>(0, 2), std::pair<int, int>(4, 10), std::pair<int, int>(14, 19), };
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\n Adding [-5,1]:\n";
interval(a, std::pair<int, int>(-5, 1));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [3,9]:\n";
interval(a, std::pair<int, int>(3, 9));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [1,3]:\n";
interval(a, std::pair<int, int>(1, 3));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [-15,13]:\n";
interval(a, std::pair<int, int>(-15, 13));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [-3,21]:\n";
interval(a, std::pair<int, int>(-3, 21));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [30, 50]:\n";
interval(a, std::pair<int, int>(30, 50));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << std::endl;
return 0;
}
Thanks to psycophantEve for test cases and driver program. Below is stdout
[-10, -1] [0, 2] [4, 10] [14, 19]
Adding [-5,1]:
[-10, 2] [4, 10] [14, 19]
Adding [3,9]:
[-10, 2] [3, 10] [14, 19]
Adding [1,3]:
[-10, 10] [14, 19]
Adding [-15,13]:
[-15, 13] [14, 19]
Adding [-3,21]:
[-15, 21]
Adding [30, 50]:
[-15, 21] [30, 50]
#include <iostream>
#include <vector>
#include <list>
using namespace std;
bool canPlace(list<bool> bed, int xFlowers) {
int m = 0, n = xFlowers;
if(xFlowers == 0) return true;
if(bed.size()==1) {
if(bed.front() == false && n ==1) {
return true;
}
return false;
}
list<bool>::iterator it1 = bed.begin(), it2 = bed.begin(), it3 = bed.begin();
++it2;
++it3; ++it3;
for( ;it3!=bed.end();) {
if(*it1 == false && *it2==false && *it3==false) {
++m;
*it2 = true;
}
++it1; ++it2; ++it3;
}
if(bed.size() > 1) {
//it3 = bed.back(); it2 = it3 - 1;
it3 = it2;
it2 = it1;
if(*it3 == false && *it2 == false) {
++m; *it3 = true;
}
it1 = bed.begin(); it2 = bed.begin(); ++it2;
if(*it1 == false && *it2 == false) {
++m; *it1 = true;
}
}
return m>=n;
}
int main() {
// your code goes here
int arr[] = {0,1,0,0,1,0,0 };
list<bool> bed;
//int array[2] = { 0, 0 };
for (int i = 0; i < sizeof(arr)/sizeof(int); i++) {
//scanf("%d", &f);
bed.push_back((bool)arr[i]);
}
cout<<canPlace(bed, 1);
return 0;
}
Below is a solution with runtime of O(N) and space of O(N). Idea is to use unordered_map<int, bool> to process array. Then result can be returned as an vector or array.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> once_int(int *arr, int size) {
unordered_map<int, bool> myMap;
for(int i=0; i<size; i++) {
if(myMap.find(arr[i]) == myMap.end()) {
myMap[arr[i]] = true;
} else {
myMap[arr[i]] = false;
}
}
vector<int> vec;
for(unordered_map<int, bool>::iterator it=myMap.begin(); it!=myMap.end(); ++it) {
if(it->second == true)
vec.push_back(it->first);
}
return vec;
}
int main() {
// your code goes here
int arr[] = {4, 3, 3, 1};
vector<int> vec = once_int(arr, 4);
for(vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it) {
cout<<*it<<" ";
}
return 0;
}
Please clarify question with more examples (negative ones)
- GatorsRock April 26, 2016The solution is that each node in BST needs to be in certain range [min, max]
Wikipedia has good solution for this:
public static boolean isBST(TreeNode node, int maxData, int minData) {
if (node == null)
return true;
if (node.getData() >= maxData || node.getData() <= minData)
return false;
return (isBST(node.left, node.getData(), minData) && isBST(node.right, maxData, node.getData()));
}
The initial call to this function can be something like this:
if (isBST(root, Integer.MAX_VALUE, Integer.MIN_VALUE))
System.out.println("This is a BST.");
else
System.out.println("This is NOT a BST!");
Essentially we keep creating a valid range (starting from [ MIN_VALUE, MAX_VALUE]) and keep shrinking it down for each node as we go down recursively.
- GatorsRock July 31, 2014
1. Authenticate
- GatorsRock December 14, 20162. Authorize
3. JsonObject getQuestions(surveyID, pageNum)
4. bool sendResponses()
5. saveSession ()
think about processing images, form data (unicode, maybe UTF-8), validation, processing needed ? hide PII, etc. expiry of survey ? use https to communicate.