Skip to main content

Daily: Find missing array value

3 likes • Dec 24, 2021 • 18 views
C++
Loading...

More C++ Posts

C++ Range Slicer

0 likes • Oct 31, 2023 • 3 views
C++
//Leif Messinger
//Compile with C++ 20
#include <iostream>
#include <ranges>
#include <vector>
#include <functional>
#include <cctype> //toupper
#include <cxxabi.h>
template <typename T>
void printType(){
std::cout << abi::__cxa_demangle(typeid(T).name(), NULL, NULL, NULL) << std::endl;
}
template <typename T>
class Slicer{
public:
T begin_;
T end_;
T trueEnd;
Slicer(T begin, T end): begin_(begin), end_(begin), trueEnd(end){}
template<typename U>
Slicer(U&& vec) : begin_(vec.begin()), end_(vec.begin()), trueEnd(vec.end()){}
Slicer& finish(){
begin_ = end_;
end_ = trueEnd;
return (*this);
}
Slicer& to(long int index){
begin_ = end_;
if(index > 0){
end_ = (begin_ + index);
}else{
index *= -1;
end_ = (trueEnd - index);
}
return (*this);
}
Slicer& operator[](long int index){
return to(index);
}
T begin(){
return this->begin_;
}
T end(){
return this->end_;
}
Slicer& operator()(std::function<void(decltype(*begin_))> func) {
for(decltype(*begin_) thing : (*this)){
func(thing);
}
return (*this);
}
};
static_assert(std::ranges::range< Slicer<std::vector<int>::const_iterator> >);
int main(){
std::string vec = "abcdefghijklmnopqrstuvwxyz";
Slicer<std::string::const_iterator> bruh(vec);
//printType<decltype(bruh)>();
bruh.to(3)([](char yeet){
std::cout << yeet;
})
.to(-1)([](char yeet){
std::cout << char(std::toupper(yeet));
}).finish()([](char yeet){
std::cout << yeet << yeet << yeet << yeet << yeet;
});
std::cout << std::endl << std::endl;
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
Slicer<int*> arrSlicer(arr, arr + (sizeof(arr)/sizeof(int)));
std::cout << "[";
arrSlicer.to(-1)([](int yeet){
std::cout << yeet << ", ";
}).finish()([](int yeet){
std::cout << yeet << "]" << std::endl;
});
return 0;
}

Enumeration Basics

0 likes • Nov 18, 2022 • 0 views
C++
#include <iostream>
using namespace std;
/*
Description: uses switch case statements to determine whether it is hot or not outside.
Also uses toupper() function which forces user input char to be uppercase in order to work for the switch statement
*/
int main() {
char choice;
cout << "S = Summer, F = Fall, W = Winter, P = Spring" << endl;
cout << "Enter a character to represent a season: ";asdasdasdasd
cin >> choice;
enum Season {SUMMER='S', FALL='F', WINTER='W', SPRING='P'};
switch(toupper(choice)) // This switch statement compares a character entered with values stored inside of an enum
{
case SUMMER:
cout << "It's very hot outside." << endl;
break;
case FALL:
cout << "It's great weather outside." << endl;
break;
case WINTER:
cout << "It's fairly cold outside." << endl;
break;
case SPRING:
cout << "It's rather warm outside." << endl;
break;
default:
cout << "Wrong choice" << endl;
break;
}
return 0;
}

BFS/DFS/TopSort

0 likes • Apr 30, 2021 • 3 views
C++
#include <bits/stdc++.h>
#define MAXSIZE 50000
#define INF 100000
using namespace std;
vector<int> adj[MAXSIZE]; //Adjacency List
bool visited[MAXSIZE]; //Checks if a node is visited or not in BFS and DFS
bool isConnected = true; //Checks if the input graph is connected or not
int dist[MAXSIZE], discover[MAXSIZE], finish[MAXSIZE]; //Distance for BFS, in time and out time for DFS
int t = 1; //Time used for DFS
int u, v, i, j, k, N = 0;
stack<int> st; //Stack for TopSort
multiset<pair<int, int>> s; //collection of pairs to sort by distance
pair<int, int> current; //pointer variable to a position in the multiset
void BFS()
{
queue<int> q; //queue for BFS
q.push(1); //pushing the source
dist[1] = 0; //assign the distance of source as 0
visited[1] = 1; //marking as visited
while(!q.empty())
{
u = q.front();
q.pop();
for(i=0; i < adj[u].size(); i++)
{
v = adj[u][i]; //Adjacent vertex
if(!visited[v]) //if not visited, update the distance and push onto queue
{
visited[v] = 1;
dist[v] = dist[u]+1;
q.push(v);
}
}
}
for(i = 1; i <= N; i++)
{
s.insert(make_pair(dist[i], i)); //for sorted distance
}
cout << "BFS results:" << endl;
//prints BFS results and checks if the graph is connected
while(!s.empty())
{
current = *s.begin();
s.erase(s.begin());
i = current.second;
j = current.first;
if(j == INF) //if any infinite value, graph is not connected
{
cout << i << " INF" << endl;
isConnected = false;
}
else
{
cout << i << " " << j << endl;
}
}
//marks blocks of memory as visited
memset(visited, 0, sizeof visited);
}
void dfsSearch(int s)
{
visited[s] = 1; //marking it visited
discover[s] = t++; //assigning and incrementing time
int i, v;
for(i = 0; i < adj[s].size(); i++)
{
v = adj[s][i];
if(!visited[v]) //if vertex is not visited then visit, else continue
{
dfsSearch(v);
}
}
st.push(s); //pushed onto stack for TopSort if it was called
finish[s] = t++; //out time
}
void DFS()
{
for(i = 1; i <= N; i++)
{
if(visited[i]) //if visited continue, else visit it with DFS
{
continue;
}
dfsSearch(i); //embedded function to actually perform DFS
}
for(i=1;i<=N;i++)
{
s.insert(make_pair(discover[i], i)); //minheap for sorted discovery time
}
cout << "DFS results:" << endl;
while(!s.empty()) //Prints DFS results as long as the multiset is not empty
{
current = *s.begin(); //duplicates the pointer to first object in the multiset
s.erase(s.begin()); //erases the first object in multiset
i = current.second;
cout << i << " " << discover[i] << " " << finish[i] << endl; //prints discover times and finish times
}
}
void TopSort()
{
//call DFS so we can have a sorted stack to print
for(i=1;i<=N;i++)
{
if(visited[i])
{
continue;
}
dfsSearch(i);
}
cout<<"Topological Sort results:"<<endl;
//print sorted results from DFS
while(!st.empty())
{
i = st.top();
st.pop();
cout << i << endl;
}
//declare blocks of memory as visited
memset(visited, 0, sizeof visited);
}
int main()
{
string str, num, input;
int selection, connectedChoice = 0;
//get to input any file, more freedom than declaring file in command line
cout << "Enter the exact name of your input file [case sensitive]: ";
cin >> input;
ifstream inputFile(input); //Read the input file
//checks if the ifstream cannot open
if(inputFile.fail())
{
cout << endl << "No input files matching that name. Terminating..." << endl;
return 0;
}
//Read until the end of file
while(!inputFile.eof())
{
getline(inputFile, str); //read the current line
if(str == "")
{
continue;
}
if(!isdigit(str[0])) //checks to see if the first item in a line is a digit or not
{
cout << "Invalid file format. You have a line beginning with a non-digit. Terminating..." << endl;
return 0;
}
stringstream ss;
ss << str; //convert the line to stream of strings
ss >> num; //read the line num
stringstream(num) >> u;
while(!ss.eof())
{
ss>>num;
if(stringstream(num) >> v)
{
adj[u].push_back(v); //read the adjacent vertices
}
}
N++; //calculate the number of vertices
sort(adj[u].begin(), adj[u].end()); //sort the adjacency list in case it is not sorted
}
//creates arbitrary values for distance, will check later if INF remain
for(i = 1; i <= N; i++)
{
dist[i] = INF;
}
cout << endl << "Valid Input file loaded!" << endl;
while(selection != 4)
{
cout << "************************************************" << endl;
cout << "What type of analysis would you like to perform?" << endl;
cout << "1: Breadth-First Search" << endl;
cout << "2: Depth-First Search" << endl;
cout << "3: Topological Sort" << endl;
cout << "4: Quit" << endl;
cout << "************************************************" << endl;
//read user input and execute selection
cin >> selection;
switch(selection)
{
case 1:
cout << endl;
BFS();
cout << endl;
cout << "Would you like to know if the graph is connected?" << endl;
cout << "1: Yes" << endl;
cout << "Any other key: No" << endl;
cin >> connectedChoice;
switch(connectedChoice)
{
case 1:
if(!isConnected)
{
cout << "The graph is not connected." << endl << endl;
}
else
{
cout << "The graph is connected!" << endl << endl;
}
break;
default:
break;
}
break;
case 2:
cout << endl;
DFS();
cout << endl;
break;
case 3:
cout << endl;
TopSort();
cout << endl;
break;
case 4:
return 0;
default:
cout << endl << "Invalid selection." << endl; //loops the selection prompt until a valid selection is input.
}
}
}

Daily: Find missing array value

0 likes • Aug 5, 2023 • 5 views
C++
/*
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[4]{3, 4, -1, 1}, 4) << endl;
cout << calcMissing(new int[3]{1, 2, 0}, 3) << endl;
//No positive numbers
cout << calcMissing(new int[1]{0}, 1) << endl;
}

Critques

0 likes • Feb 4, 2021 • 0 views
C++
#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.";
}

PlaylistNode.cpp (lab 9)

0 likes • Nov 18, 2022 • 0 views
C++
#include <string>
#include <iostream>
#include "PlaylistNode.h"
using namespace std;
PlaylistNode::PlaylistNode() {
uniqueID = "none";
songName = "none";
artistName = "none";
songLength = 0;
nextNodePtr = 0;
}
PlaylistNode::PlaylistNode(string uniqueID_, string songName_, string artistName_, int songLength_) {
uniqueID = uniqueID_;
songName = songName_;
artistName = artistName_;
songLength = songLength_;
nextNodePtr = 0;
}
void PlaylistNode::InsertAfter(PlaylistNode* ptr) {
this->SetNext(ptr->GetNext());
ptr->SetNext(this);
}
void PlaylistNode::SetNext(PlaylistNode* ptr) {
nextNodePtr = ptr;
}
string PlaylistNode::GetID() {
return uniqueID;
}
string PlaylistNode::GetSongName() {
return songName;
}
string PlaylistNode::GetArtistName() {
return artistName;
}
int PlaylistNode::GetSongLength() {
return songLength;
}
PlaylistNode* PlaylistNode::GetNext() {
return nextNodePtr;
}
void PlaylistNode::PrintPlaylistNode() {
cout << "Unique ID: " << uniqueID << endl;
cout << "Song Name: " << songName << endl;
cout << "Artist Name: " << artistName << endl;
cout << "Song Length (in seconds): " << songLength << endl;
}
Playlist::Playlist() {
head = tail = 0;
}
void Playlist::AddSong(string id, string songname, string artistname, int length) {
PlaylistNode* n = new PlaylistNode(id, songname, artistname, length);
if (head == 0) {
head = tail = n;
}
else {
n->InsertAfter(tail);
tail = n;
}
}
bool Playlist::RemoveSong(string id) {
if (head == NULL) {
cout << "Playlist is empty" << endl;
return false;
}
PlaylistNode* curr = head;
PlaylistNode* prev = NULL;
while (curr != NULL) {
if (curr->GetID() == id) {
break;
}
prev = curr;
curr = curr->GetNext();
}
if (curr == NULL) {
cout << "\"" << curr->GetSongName() << "\" is not found" << endl;
return false;
}
else {
if (prev != NULL) {
prev ->SetNext(curr->GetNext());
}
else {
head = curr->GetNext();
}
if (tail == curr) {
tail = prev;
}
cout << "\"" << curr->GetSongName() << "\" removed." << endl;
delete curr;
return true;
}
}
bool Playlist::ChangePosition(int oldPos, int newPos) {
if (head == NULL) {
cout << "Playlist is empty" << endl;
return false;
}
PlaylistNode* prev = NULL;
PlaylistNode* curr = head;
int pos;
if (head == NULL || head == tail) {
return false;
}
for (pos = 1; curr != NULL && pos < oldPos; pos++) {
prev = curr;
curr = curr->GetNext();
}
if (curr != NULL) {
string currentSong = curr->GetSongName();
if (prev == NULL) {
head = curr->GetNext();
}
else {
prev->SetNext(curr->GetNext());
}
if (curr == tail) {
tail = prev;
}
PlaylistNode* curr1 = curr;
prev = NULL;
curr = head;
for (pos = 1; curr != NULL && pos < newPos; pos++) {
prev = curr;
curr = curr->GetNext();
}
if (prev == NULL) {
curr1->SetNext(head);
head = curr1;
}
else {
curr1->InsertAfter(prev);
}
if (curr == NULL) {
tail = curr1;
}
cout << "\"" << currentSong << "\" moved to position " << newPos << endl;
return true;
}
else {
cout << "Song's current position is invalid" << endl;
return false;
}
}
void Playlist::SongsByArtist(string artist) {
if (head == NULL) {
cout << "Playlist is empty" << endl;
}
else {
PlaylistNode* curr = head;
int i = 1;
while (curr != NULL) {
if (curr->GetArtistName() == artist) {
cout << endl << i << "." << endl;
curr->PrintPlaylistNode();
}
curr = curr->GetNext();
i++;
}
}
}
int Playlist::TotalTime() {
int total = 0;
PlaylistNode* curr = head;
while (curr != NULL) {
total += curr->GetSongLength();
curr = curr->GetNext();
}
return total;
}
void Playlist::PrintList() {
if (head == NULL) {
cout << "Playlist is empty" << endl;
}
else {
PlaylistNode* curr = head;
int i = 1;
while (curr != NULL) {
cout << endl << i++ << "." << endl;
curr->PrintPlaylistNode();
curr = curr->GetNext();
}
}
}