randomtech

 Following is the code for string builder: /******************************************************************************                               Online C++ Compiler.                Code, Compile, Run and Debug C++ program online. Write your code in this editor and press "Run" button to compile and execute it. *******************************************************************************/ #include <iostream> #include "bits/stdc++.h" using namespace std; class stringbuilder{ private:     vector<string> words;     vector<char> complete_string;     string concatenate_string() public:     void insert_words(string s);     string get_string(); }; void stringbuilder::insert_word...

Problem Statement:     Given a tree, task is to find out the path with maximum sum of the elements along the path.  The path can be anywhere in the tree and need not go along the root and the nodes shouldn't be skipped in the path. Example 1: Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2: Input: [-10,9,20,null,null,15,7]   -10    / \   9   20     /  \     15   7 Output: 42  Approach to the solution:   Approach here is simple, first traverse the tree in post order manner. Keep track of maximum values of left and right. Keep track of maximum values of left side and right side. Compare and keep track of maximum values between maximum side max and sub tree. Keep track of global maximum sum of the path in one variable Compare global maximum sum with the sum which got from the above process. Return that maximum sum. This maximum sum is the maximum path of the sum ...

  Problem Statement: Given a binary search tree. Program should return Kth Smallest element in the binary search tree. Suppose if the binary tree is represented as: 3,1,4,null, 2 Then 1st smallest element is 1, second smallest element is 2 and 3rd smallest element is 3.   Solution with Explanation: The binary tree consists of elements in sorted order. The easiest way of finding solution is insert the elements in the priority queue and then  pop out k-1 elements, then top element of the priority queue is the kth smallest element of the tree. Optimized solution is doing in-order traversal and keeping track of the count of number of elements visited.  After visiting the left most element of the binary tree, increase the count to 1 and traverse back in in-order manner and increase the count. Whenever the count is reached to k return that element. Complexity Explanation: As the traversal is in-order, each node is visited only once. The traversal continues till the Kth el...

Problem Statement: Given an array which consists of daily temperatures, find out what is the warmth upcoming day in the list. If there is no such day exist return 0. Suppose the array of temperature is: 60, 70, 80, 77, 73, 79, 81, 75 Answer should be 1, 1, 4, 2, 1, 1, 0, 0. Explanation: Immediate warmth day after 60 is 70 which is next day, so 1. Same for 70 as well. But for 80 next warmth day is 81 which is after 4 days, for 77 it is 79 which is the second day, for 73 it is 79 which is next day. But there is no day in the list where temperature is greater than 81 so insert 0 same for 75 as well. Solution with Explanation: The idea is to use stack data structure to keep track of which we didn't find the warmth temperature in next day. First day temperature is pushed into the stack On second day we check the top value of stack is less than the current day temperature. If yes, then we found the immediate warmth day for the day which is on top of the stack. We pop that and check wheth...

Problem Statement: Given a tree return inorder traversal of a binary tree. Note: Solve it using both recursion and iterative approach. Approach - 1(Recursive approach): Recursive approach is very simple. Inorder traversal is traversing left sub tree first Then visiting root and finally visiting right sub tree. Break the recursion whenever there is no node available. Code in C++: class Solution {         void traverse(TreeNode* node, vector<int> &res){             if(!node)                 return;             traverse(node->left, res);                        res.push_back(node->val);           ...

LeetCode Problem #687 Given a binary tree find the longest possible path with same node values. The length of the path is determined the number of edges between the node. Example 1: Input: 5 / \ 4 5 / \ \ 1 1 5 Output:  2   Example 2: Input: 1 / \ 4 5 / \ \ 4 4 5 Output:  2 Solution in C++: /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}  * };  */ class Solution ...

Problem Statement: Validate whether given three set of combination leads to valid Tic-Tac-Toe  pattern or not. Given strings consists of 'x', 'o' or ' '. Assume that game starts from 'x'. So, first players1 puts 'x' in the game then player2 takes the turn and inserts 'o'. The game will continue until one of the players win. Our task is to find out whether given pattern is possible at any point of time of play. Return true if the given pattern is possible else return false. Example 1: Input: ['XXX', '   ', 'OOO'] Output:   false Explanation: The given pattern is not possible because once the player 1 put three X in a row which is in the first row game is over, player 2 doesn't get a chance to put thrid O. So, this pattern is not possible. Example 2: Input: ['XOX', 'OOX ', 'XO '] Output:   true Explanation: The given pattern is possible. Example 3: Input: ['OXX', 'XOX', ...