## aedrarian

User since Oct 28, 2022
5 Posts
C++
Plaintext

### Recent Posts

```/*Good morning! Here's your coding interview problem for today.
This problem was asked by Stripe.
Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.
For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.
You can modify the input array in-place.*/#include <iostream>using namespace std;
int calcMissing(int* input, int size){	int sum = 0;	int n = 1; //add one to account for missing value	for(int i = 0; i < size; i++)	{	if(input[i] > 0)	{	sum += input[i];	n++;	}	}
//If no numbers higher than 0, answer is 1	if(sum == 0)	return 1;
return (n*(n+1)/2) - sum; //Formula is expectedSum - actualSum	/* expectedSum = n*(n+1)/2, the formula for sum(1, n) */}
int main(){
cout << calcMissing(new int{3, 4, -1, 1}, 4) << endl;	cout << calcMissing(new int{1, 2, 0}, 3) << endl;
//No positive numbers	cout << calcMissing(new int{0}, 1) << endl;}```
```/*Good morning! Here's your coding interview problem for today.
A wall consists of several rows of bricks of various integer lengths and uniform height. Your goal is to find a vertical line going from the top to the bottom of the wall that cuts through the fewest number of bricks. If the line goes through the edge between two bricks, this does not count as a cut.
For example, suppose the input is as follows, where values in each row represent the lengths of bricks in that row:
[[3, 5, 1, 1],	[2, 3, 3, 2],	[5, 5],	[4, 4, 2],	[1, 3, 3, 3],	[1, 1, 6, 1, 1]]
The best we can we do here is to draw a line after the eighth brick, which will only require cutting through the bricks in the third and fifth row.
Given an input consisting of brick lengths for each row such as the one above, return the fewest number of bricks that must be cut to create a vertical line.
AUTHORS NOTE:Makes following assumptions:- Each row is same length- Data is in file called "data.dat" and formatted in space-separated rows- The cuts at the beginning and end of the wall are not solutions
This requires the following file named data.dat that is a space separated file, or similar formatted file:----START FILE----3 5 1 12 3 3 25 54 4 21 3 3 31 1 6 1 1----END FILE----*/
#include <algorithm>#include <iostream>#include <fstream>#include <map>#include <sstream>#include <string>#include <vector>using namespace std;
int main(){	vector<vector<int>> wall;
ifstream in;	in.open("data.dat");	if(!in.good())	{	cout << "ERROR: File failed to open properly.\n";	}
/* Get input from space separated file */	string line;	while(!in.eof())	{	getline(in, line);
int i;	vector<int> currv;	stringstream strs(line);	while(strs >> i)	currv.push_back(i);	wall.push_back(currv);	}

/* Convert each value from "length of brick" to "position at end of brick" */	for(int y = 0; y < wall.size(); y++)	{	wall.at(y).pop_back(); //Delet last val	for(int x = 1; x < wall.at(y).size(); x++) //Skip the first bc data doesn't need change	wall.at(y).at(x) += wall.at(y).at(x-1);	}
/* Check output. COMMENT OUT */	// for(auto row : wall)	// {	// for(int pos : row)	// cout << pos << " ";	// cout << endl;	// }
/* Determine which ending position is most common, and cut there */	//Exclude final position, which will be the size of the wall
int mode = -1;	int amt = -1;	vector<int> tried;	for(auto row : wall)	{	for(int pos : row) //For each pos in the wall	{	//Guard. If pos is contained in the list, skip pos	if(find(tried.begin(), tried.end(), pos) != tried.end())	continue;	tried.push_back(pos);
/* Cycle through each row to see if it contains the pos */	int curramt = 0;	for(auto currrow : wall)	{	if( find( currrow.begin(), currrow.end(), pos ) != currrow.end() )	curramt++;	}	//cout << pos << " " << curramt << endl;
if(curramt > amt)	{	amt = curramt;	mode = pos;	}	}	}
cout << "Please cut at position " << mode << endl;	cout << "This will cut through " << (wall.size() - amt) << " bricks." << endl;
return 0;}```
```//Get data file at https://codecatch.net/post.php?postID=91e87d73//Iteration 1 of Wing Project. Solution breaks down around n=35
#include <iostream>#include <fstream>#include <string>#include <vector>#include <map>using namespace std;
int getSum(map<int, int> list);void readData(map<int, float>* data);void lowestPrice();void findSums(int n, vector<map<int, int>>* sumsList, map<int, float>* data);//void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList);void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList, map<int, float>* data);float getPrice(map<int, int> set, map<int, float>* data);
template <typename S>ostream& operator<<(ostream& os, const vector<S>& vector){	// Printing all the elements using <<	for (auto element : vector) {	os << element << " ";	}	return os;}
bool operator==(map<int, int> m1, map<int, int> m2){	if(m1.size() != m2.size())	return false;
bool ret = true;
for(auto it = m1.begin(); it !=m1.end() && ret; it++)	{	if(ret && m1.count(it->first) != m2.count(it->first))	ret = false;
if(ret && m1.count(it->first) == 1)	{	if(m1.at(it->first) != m2.at(it->first))	ret = false;	}	}
return ret;}

int main(){	map<int, float> data;	readData(&data);
vector<map<int, int>> *sumsList;	sumsList = new vector<map<int, int>>;	findSums(40, sumsList, &data);
for(auto el : *sumsList)	{	for(auto it = el.begin(); it != el.end(); it++)	{	cout << it->first << "->" << it->second << " ";	}	cout << getPrice(el, &data) << endl;	}
return 0;}
/* Returns the price of wings given a set of numbers of wings to buy.	* Returns -1 if the set contains a number that is not possible to buy.	*/float getPrice(map<int, int> set, map<int, float>* data){	float price = 0;	for(auto it = set.begin(); it != set.end(); it++)	{	//If data doesn't contain an element of set, return -1	if(data->count(it->first) == 0)	return -1;		price += data->at(it->first) * it->second; //pricePerPacket * qtyOfPackets	}
return price;}
/* Adds the elements of list.	* Suppose mapping is <num, qty>.	* Returns sum(num*qty)	*/int getSum(map<int, int> list){	int sum = 0;	for(auto it = list.begin(); it != list.end(); it++)	sum += it->first * it->second;	return sum;}
void findSums(int n, vector<map<int, int>>* sumsList, map<int, float>* data){	map<int, int> currList;
//Recur when currSum < n	auto it = data->begin();	while(it->first <= n && it != data->end())	{	findSum(currList, it->first, n, sumsList, data);	it++;	}}
void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList, map<int, float>* data){	//Append x to currList	if(currList.count(x) == 0)	currList.emplace(x, 1);	else	{	int val = 1+ currList.at(x);	currList.erase(x);	currList.emplace(x, val);	}
//Determine current sum, check for return cases	int currSum = getSum(currList);
if(currSum > n)	return;	else if(currSum == n)	{
//Check to make sure no duplicates	for(auto list : *sumsList)	{	if(list == currList)	return;	}
sumsList->push_back(currList);	return;	}
//Recur when currSum < n	auto it = data->begin();	while(it->first <= n-x && it != data->end())	{	findSum(currList, it->first, n, sumsList, data);	it++;	}}
void readData(map<int, float>* data){	ifstream file ("./data", ifstream::in);
if(file.is_open())	{	int i = 0;	while(!file.eof())	{	float wings, price;	string skipnl;	file >> wings;	file >> price;
data->emplace(wings, price);
getline(file, skipnl);	i++;	}	}}```

### Wing Data

aedrarian
0 likes • Oct 31, 2021
Plaintext
`##README: Rename file to "data" (no extension) and delete this line4 4.555 5.706 6.807 7.958 9.109 10.2010 11.3511 12.5012 13.6013 14.7514 15.9015 1716 18.1517 19.3018 20.4019 21.5520 22.7021 23.8022 24.9523 26.1024 27.2525 27.8026 28.9527 30.1028 31.2029 32.3530 33.5035 39.1540 44.8045 50.5050 55.6060 6770 78.3075 83.4580 89.1090 100.45100 111.25125 139150 166.85200 222.50`
```#include <iostream>using namespace std;
main{	cout << "No tabbing. That's very sad :(\n";	cout << "No in-editor highlighting either :(((\n";	cout << "Descriptions might be niice too.";}```

### Posts

#### No Posts Found

It looks like aedrarian hasn't uploaded a post yet

### Likes

You must be authenticated to view a user's likes