Loading...
More C++ Posts
#include <iostream>#include <vector>using namespace std;void swap(int *a, int *b){int temp = *b;*b = *a;*a = temp;}void heapify(vector<int> &hT, int i){int size = hT.size();int largest = i;int l = 2 * i + 1;int r = 2 * i + 2;if (l < size && hT[l] > hT[largest])largest = l;if (r < size && hT[r] > hT[largest])largest = r;if (largest != i){swap(&hT[i], &hT[largest]);heapify(hT, largest);}}void insert(vector<int> &hT, int newNum){int size = hT.size();if (size == 0){hT.push_back(newNum);}else{hT.push_back(newNum);for (int i = size / 2 - 1; i >= 0; i--){heapify(hT, i);}}}void deleteNode(vector<int> &hT, int num){int size = hT.size();int i;for (i = 0; i < size; i++){if (num == hT[i])break;}swap(&hT[i], &hT[size - 1]);hT.pop_back();for (int i = size / 2 - 1; i >= 0; i--){heapify(hT, i);}}void printArray(vector<int> &hT){for (int i = 0; i < hT.size(); ++i)cout << hT[i] << " ";cout << "\n";}int main(){vector<int> heapTree;insert(heapTree, 3);insert(heapTree, 4);insert(heapTree, 9);insert(heapTree, 5);insert(heapTree, 2);cout << "Max-Heap array: ";printArray(heapTree);deleteNode(heapTree, 4);cout << "After deleting an element: ";printArray(heapTree);}
/*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 valuefor(int i = 0; i < size; i++){if(input[i] > 0){sum += input[i];n++;}}//If no numbers higher than 0, answer is 1if(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 numberscout << calcMissing(new int[1]{0}, 1) << endl;}
using namespace std;class Hash{int BUCKET; // No. of buckets// Pointer to an array containing bucketslist<int> *table;public:Hash(int V); // Constructor// inserts a key into hash tablevoid insertItem(int x);// deletes a key from hash tablevoid deleteItem(int key);// hash function to map values to keyint hashFunction(int x) {return (x % BUCKET);}void displayHash();};Hash::Hash(int b){this->BUCKET = b;table = new list<int>[BUCKET];}void Hash::insertItem(int key){int index = hashFunction(key);table[index].push_back(key);}void Hash::deleteItem(int key){// get the hash index of keyint index = hashFunction(key);// find the key in (inex)th listlist <int> :: iterator i;for (i = table[index].begin();i != table[index].end(); i++) {if (*i == key)break;}// if key is found in hash table, remove itif (i != table[index].end())table[index].erase(i);}// function to display hash tablevoid Hash::displayHash() {for (int i = 0; i < BUCKET; i++) {cout << i;for (auto x : table[i])cout << " --> " << x;cout << endl;}}// Driver programint main(){// array that contains keys to be mappedint a[] = {15, 11, 27, 8, 12};int n = sizeof(a)/sizeof(a[0]);// insert the keys into the hash tableHash h(7); // 7 is count of buckets in// hash tablefor (int i = 0; i < n; i++)h.insertItem(a[i]);// delete 12 from hash tableh.deleteItem(12);// display the Hash tableh.displayHash();return 0;}
#include <iostream>#include <vector>#include <utility>#include <algorithm>#include <chrono>using namespace std;#include <stdio.h>#include <Windows.h>int nScreenWidth = 120; // Console Screen Size X (columns)int nScreenHeight = 40; // Console Screen Size Y (rows)int nMapWidth = 16; // World Dimensionsint nMapHeight = 16;float fPlayerX = 14.7f; // Player Start Positionfloat fPlayerY = 5.09f;float fPlayerA = 0.0f; // Player Start Rotationfloat fFOV = 3.14159f / 4.0f; // Field of Viewfloat fDepth = 16.0f; // Maximum rendering distancefloat fSpeed = 5.0f; // Walking Speedint main(){// Create Screen Bufferwchar_t *screen = new wchar_t[nScreenWidth*nScreenHeight];HANDLE hConsole = CreateConsoleScreenBuffer(GENERIC_READ | GENERIC_WRITE, 0, NULL, CONSOLE_TEXTMODE_BUFFER, NULL);SetConsoleActiveScreenBuffer(hConsole);DWORD dwBytesWritten = 0;// Create Map of world space # = wall block, . = spacewstring map;map += L"#########.......";map += L"#...............";map += L"#.......########";map += L"#..............#";map += L"#......##......#";map += L"#......##......#";map += L"#..............#";map += L"###............#";map += L"##.............#";map += L"#......####..###";map += L"#......#.......#";map += L"#......#.......#";map += L"#..............#";map += L"#......#########";map += L"#..............#";map += L"################";auto tp1 = chrono::system_clock::now();auto tp2 = chrono::system_clock::now();while (1){// We'll need time differential per frame to calculate modification// to movement speeds, to ensure consistant movement, as ray-tracing// is non-deterministictp2 = chrono::system_clock::now();chrono::duration<float> elapsedTime = tp2 - tp1;tp1 = tp2;float fElapsedTime = elapsedTime.count();// Handle CCW Rotationif (GetAsyncKeyState((unsigned short)'A') & 0x8000)fPlayerA -= (fSpeed * 0.75f) * fElapsedTime;// Handle CW Rotationif (GetAsyncKeyState((unsigned short)'D') & 0x8000)fPlayerA += (fSpeed * 0.75f) * fElapsedTime;// Handle Forwards movement & collisionif (GetAsyncKeyState((unsigned short)'W') & 0x8000){fPlayerX += sinf(fPlayerA) * fSpeed * fElapsedTime;;fPlayerY += cosf(fPlayerA) * fSpeed * fElapsedTime;;if (map.c_str()[(int)fPlayerX * nMapWidth + (int)fPlayerY] == '#'){fPlayerX -= sinf(fPlayerA) * fSpeed * fElapsedTime;;fPlayerY -= cosf(fPlayerA) * fSpeed * fElapsedTime;;}}// Handle backwards movement & collisionif (GetAsyncKeyState((unsigned short)'S') & 0x8000){fPlayerX -= sinf(fPlayerA) * fSpeed * fElapsedTime;;fPlayerY -= cosf(fPlayerA) * fSpeed * fElapsedTime;;if (map.c_str()[(int)fPlayerX * nMapWidth + (int)fPlayerY] == '#'){fPlayerX += sinf(fPlayerA) * fSpeed * fElapsedTime;;fPlayerY += cosf(fPlayerA) * fSpeed * fElapsedTime;;}}for (int x = 0; x < nScreenWidth; x++){// For each column, calculate the projected ray angle into world spacefloat fRayAngle = (fPlayerA - fFOV/2.0f) + ((float)x / (float)nScreenWidth) * fFOV;// Find distance to wallfloat fStepSize = 0.1f; // Increment size for ray casting, decrease to increasefloat fDistanceToWall = 0.0f; // resolutionbool bHitWall = false; // Set when ray hits wall blockbool bBoundary = false; // Set when ray hits boundary between two wall blocksfloat fEyeX = sinf(fRayAngle); // Unit vector for ray in player spacefloat fEyeY = cosf(fRayAngle);// Incrementally cast ray from player, along ray angle, testing for// intersection with a blockwhile (!bHitWall && fDistanceToWall < fDepth){fDistanceToWall += fStepSize;int nTestX = (int)(fPlayerX + fEyeX * fDistanceToWall);int nTestY = (int)(fPlayerY + fEyeY * fDistanceToWall);// Test if ray is out of boundsif (nTestX < 0 || nTestX >= nMapWidth || nTestY < 0 || nTestY >= nMapHeight){bHitWall = true; // Just set distance to maximum depthfDistanceToWall = fDepth;}else{// Ray is inbounds so test to see if the ray cell is a wall blockif (map.c_str()[nTestX * nMapWidth + nTestY] == '#'){// Ray has hit wallbHitWall = true;// To highlight tile boundaries, cast a ray from each corner// of the tile, to the player. The more coincident this ray// is to the rendering ray, the closer we are to a tile// boundary, which we'll shade to add detail to the wallsvector<pair<float, float>> p;// Test each corner of hit tile, storing the distance from// the player, and the calculated dot product of the two raysfor (int tx = 0; tx < 2; tx++)for (int ty = 0; ty < 2; ty++){// Angle of corner to eyefloat vy = (float)nTestY + ty - fPlayerY;float vx = (float)nTestX + tx - fPlayerX;float d = sqrt(vx*vx + vy*vy);float dot = (fEyeX * vx / d) + (fEyeY * vy / d);p.push_back(make_pair(d, dot));}// Sort Pairs from closest to farthestsort(p.begin(), p.end(), [](const pair<float, float> &left, const pair<float, float> &right) {return left.first < right.first; });// First two/three are closest (we will never see all four)float fBound = 0.01;if (acos(p.at(0).second) < fBound) bBoundary = true;if (acos(p.at(1).second) < fBound) bBoundary = true;if (acos(p.at(2).second) < fBound) bBoundary = true;}}}// Calculate distance to ceiling and floorint nCeiling = (float)(nScreenHeight/2.0) - nScreenHeight / ((float)fDistanceToWall);int nFloor = nScreenHeight - nCeiling;// Shader walls based on distanceshort nShade = ' ';if (fDistanceToWall <= fDepth / 4.0f) nShade = 0x2588; // Very closeelse if (fDistanceToWall < fDepth / 3.0f) nShade = 0x2593;else if (fDistanceToWall < fDepth / 2.0f) nShade = 0x2592;else if (fDistanceToWall < fDepth) nShade = 0x2591;else nShade = ' '; // Too far awayif (bBoundary) nShade = ' '; // Black it outfor (int y = 0; y < nScreenHeight; y++){// Each Rowif(y <= nCeiling)screen[y*nScreenWidth + x] = ' ';else if(y > nCeiling && y <= nFloor)screen[y*nScreenWidth + x] = nShade;else // Floor{// Shade floor based on distancefloat b = 1.0f - (((float)y -nScreenHeight/2.0f) / ((float)nScreenHeight / 2.0f));if (b < 0.25) nShade = '#';else if (b < 0.5) nShade = 'x';else if (b < 0.75) nShade = '.';else if (b < 0.9) nShade = '-';else nShade = ' ';screen[y*nScreenWidth + x] = nShade;}}}// Display Statsswprintf_s(screen, 40, L"X=%3.2f, Y=%3.2f, A=%3.2f FPS=%3.2f ", fPlayerX, fPlayerY, fPlayerA, 1.0f/fElapsedTime);// Display Mapfor (int nx = 0; nx < nMapWidth; nx++)for (int ny = 0; ny < nMapWidth; ny++){screen[(ny+1)*nScreenWidth + nx] = map[ny * nMapWidth + nx];}screen[((int)fPlayerX+1) * nScreenWidth + (int)fPlayerY] = 'P';// Display Framescreen[nScreenWidth * nScreenHeight - 1] = '\0';WriteConsoleOutputCharacter(hConsole, screen, nScreenWidth * nScreenHeight, { 0,0 }, &dwBytesWritten);}return 0;}
#include <iostream>using namespace std;int main() {const int ROW_SIZE = 2;const int COLUMN_SIZE = 5; //establish all variablesint matrix[ROW_SIZE][COLUMN_SIZE];int minVal;for (int i = 0; i < ROW_SIZE; ++i) // for loop to ask user to enter data.{for (int h = 0; h < COLUMN_SIZE; ++h) {cout << "Enter data for row #" << i + 1 << " and column #" << h + 1 << ": ";cin >> matrix[i][h];}}cout << "You entered: " << endl;for (int i = 0; i < ROW_SIZE; ++i) //for statements to output the array neatly{for (int h = 0; h < COLUMN_SIZE; ++h) {cout << matrix[i][h] << "\t";}cout << endl;}cout << "Minimum for each row is: {";for (int i = 0; i < ROW_SIZE; i++) //for statements to find the minimum in each row{minVal = matrix[i][0];for (int h = 0; h < COLUMN_SIZE; h++) {if (matrix[i][h] < minVal) // if matrix[i][h] < minVal -> minVal = matrix[i][h];{minVal = matrix[i][h];}}cout << minVal << ", ";}cout << "}" << endl;cout << "Minimum for each column is: {";for (int i = 0; i < COLUMN_SIZE; i++) //for statements to find the minimum in each column{minVal = matrix[0][i];for (int h = 0; h < ROW_SIZE; h++) {if (matrix[h][i] < minVal) //replaces minVal with array index for that column that is lowest{minVal = matrix[h][i];}}cout << minVal << ", ";}cout << "}" << endl;return 0;}
#include <iostream>using namespace std;int main {cout << 1;}