/*
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;
}

#include <iostream>
int main(){
    const char* const hello = "Hello, world!";
    
    const char* bruh = hello;
    
    char* const yeet = hello;
    
    std::cout << bruh << std::endl;
    
    std::cout << yeet << std::endl;
    
    return 0;
}

/*
    Place your bets!
    
    Will the program:
    a.) Print "Hello, world!" twice?
    b.) Compile error on line 5 (bruh initialize line) because the pointer gets implicit cast to non-const?
    c.) Compile error on line 7 (yeet initialize line) because the char gets implicit cast to non-const?
    d.) Both b and c?
    e.) Compile error line 11 (print yeet) because the pointer is constant and can't be incremented
    f.) Print "Hello, world!" then print the pointer address in hexadecimal
    g.) Both b and e?
    h.) Both c and e?
    i.) B, c, and e?
    
*/

// The answer is in this base 64 string:
// T25seSBjLikKVGhlIGNvbXBpbGVyIGRvZXNuJ3QgYXBwcmVjaWF0ZSB5b3UgbWFraW5nIHRoZSBjaGFyYWN0ZXJzIHRoZSBwb2ludGVyIHJlZmVycyB0byBub24tY29uc3QsIGJ1dCBpdCdzIGZpbmUgd2l0aCB5b3UgY29weWluZyBhIGNvbnN0YW50IHZhbHVlLCBpLmUuIHRoZSBwb2ludGVyLCB0byBhIG5vbi1jb25zdGFudCB2YXJpYWJsZS4KSWYgeW91IHJlcGxhY2UgdGhhdCBsaW5lIHdpdGggY2hhciogY29uc3QgeWVldCA9IGNvbnN0X2Nhc3Q8Y2hhciogY29uc3Q+KGhlbGxvKTsgSXQnbGwgcHJpbnQgIkhlbGxvLCB3b3JsZCEiIHR3aWNlLCB3aGljaCBpcyB2ZXJ5IHN0cmFuZ2UgY29uc2lkZXJpbmcgdGhhdCB5ZWV0IGlzIGEgY29uc3QgcG9pbnRlciwgc28geW91J2QgdGhpbmsgaXQgd291bGQgcHJpbnQgYXMgYSBoZXhhZGVjaW1hbCBiZWNhdXNlIGlmIHlvdSB0cnkgdG8gKCsreWVldCkgd2hpbGUgbG9vcGluZyB0aHJvdWdoIHRoZSBzdHJpbmcsIHlvdSdkIGdldCBhbiBlcnJvciwgYmVjYXVzZSBpdCdzIGNvbnN0IGFuZCBjYW4ndCBiZSBjaGFuZ2VkLgpJbnN0ZWFkIG9mIHVzaW5nIGEgdGVtcGxhdGUgZnVuY3Rpb24gZm9yIG9zdHJlYW06Om9wZXJhdG9yPDwsIHRoZXkgbWFrZSBpdCBhIGZ1bmN0aW9uIHRoYXQgdGFrZXMgdHlwZSBjb25zdCBjaGFyKiwgYW5kIEMrKyBoYXMgbm8gcHJvYmxlbXMgcHJvbW90aW5nIGEgdmFyaWFibGUgdG8gY29uc3RhbnQgd2hlbiBpbXBsaWNpdCBjYXN0aW5nLCBhbmQgaXQgaGFzIG5vIHByb2JsZW1zIGltcGxpY2l0IGNhc3RpbmcgdGhlIGNvbnN0IHBvaW50ZXIgdG8gYSBub3JtYWwgcG9pbnRlciBiZWNhdXNlIGl0J3MgbWFraW5nIGEgY29weS4gVGhlIHBvaW50ZXIgZ2V0cyBjb3BpZWQgYmVjYXVzZSB0aGUgcG9pbnRlciBpcyBwYXNzZWQgYnkgdmFsdWUsIG5vdCByZWZlcmVuY2Uu

#include <iostream>
using namespace std;

/* Function: get_coeff
Parameters: double& coeff, int pos passed from bb_4ac
Return: type is void so no return, but does ask for user to input data that establishes what a b and c are.
*/
void get_coeff(double& coeff, int pos) {
  char position;
  if(pos == 1) {
    position = 'a';
  } else if(pos == 2) {   //a simple system to determine what coefficient the program is asking for.
    position = 'b';
  } else {
    position = 'c';
  }
  cout << "Enter the co-efficient " << position << ":"; //prompt to input coeff
  coeff = 5; //input coeff
}

/* Function: bb_4ac
Parameters: no parameters passed from main, but 3 params established in function, double a, b, c.
Return: b * b - 4 * a * c
*/
double bb_4ac() {
  double a, b, c; //coefficients of a quadratic equation
  get_coeff(a, 1); // call function 1st time
  get_coeff(b, 2); // call function 2nd time
  get_coeff(c, 3); // call function 3rd time
  return b * b - 4 * a * c; //return b * b - 4 * a * c
}

int main() {
  cout << "Function to calculate the discriminant of the equation. . . " << endl;
  double determinate = bb_4ac(); //assign double determinate to bb_4ac function
  cout << "The discriminant for given values is: " << determinate << endl;  //output the determinate!
}

#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.
	}

	}
	
}

#include "stdio.h"
#include <stdlib.h>

int main (int argCount, char** args) {
    int a = atoi(args[1]);
    int b = atoi(args[2]);

    unsigned int sum = 0;

    unsigned int p = 1;
    for (unsigned int i = 1; i < b; i++) {
        p = p * i;
    }

    // (b!, (1 + b)!, (2 + b)!, ..., (n + b)!)
    for (unsigned int i = 0; i < a; i++) {
        p = p * (i + b);
        sum = sum + p;
    }
    printf("y: %u\n", sum);
    return 0;
}

#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();
      }
   }
}