Solution to Leetcode 406. Queue Reconstruction by Height

Problem statement could be found @https://leetcode.com/problems/queue-reconstruction-by-height/


Input -
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Approach -


Arrange the inputs first in decreasing order of height, so it would start looking like
[7,0],,[7,1]
[6,1],
[5,0],[5,2]
[4,4]

Now pick one element at a time and put it at index  k

First we pick [7,0] since this is the only element O/P vector is [7,0]
Next we pick [7,1] since its index is 1 we will put it at index 1 in O/P vector [7,0],[7,1]
Next we pick  [6,1] and place it index 1 so O/P vector is [7,0],[6,1],[7,1]
Next we pick  [5,0] and place it index 0 so O/P vector is [5,0],[7,0],[6,1],[7,1]
Next we pick  [5,2] and place it index 2 so O/P vector is [5,0],[7,0],[5,2],[6,1],[7,1]
Next we pick  [4,4] and place it index 4 so O/P vector is [5,0],[7,0],[5,2],[6,1],[4,4],[7,1]

Following is the code for above logic in C++

class Solution {
    private:
    struct compare
    {
        bool operator()(const pair<int, int> &p1,const pair<int, int> &p2) const{
          // ensures greater height comes first
            if (p1.first > p2.first)
                return true;
           // if there is tiebreak in height, then put smaller k index first
            if ( (p1.first == p2.first ) && (p1.second < p2.second))  
                return true;
            return false;  
           
        }
    };
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
       
        vector<pair<int, int>> retVal;
        if (people.size() == 0)
            return retVal;
        std::sort(people.begin(), people.end(), compare());
     
     
        retVal.push_back(people[0]);
     
        for(int i=1;i<people.size();i++){
            pair<int, int> px = people[i];
            retVal.insert(retVal.begin() + px.second, px);
         
        }
        return retVal;
    }
};

Solution to Leetcode 404 Sum of Left Leaves

Problem Description could be found @https://leetcode.com/problems/sum-of-left-leaves/

Solution

class Solution {

public:
    int helper(TreeNode* root, TreeNode *parent){
        if (root->left == NULL && root->right  == NULL && root == parent->left ){
            return root->val;
        }
       
        int rightVal = 0;
        int leftVal = 0;
       
        if (root->left != NULL)
            leftVal = helper(root->left, root);
     
       if ( root->right != NULL)
            rightVal = helper(root->right, root);
       
        return (leftVal + rightVal);
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL )
            return 0;
        if (root->left == NULL && root->right == NULL)
            return 0;
           
     
        int num = helper(root, NULL);
        return num;
     
    }
};

Solution to Leetcode 402 Remove K Digits

Problem Statement could be found @https://leetcode.com/problems/remove-k-digits/

Approach - Idea is to start from first character of string and compare it with next character, if current character is smaller then next then it can be removed. If the very first  character is larger than second then remove it. All the while take care of zeros at the start

Following is the code
class Solution {
public:
    string truncZero(string num){
         while (num.size() > 1 && num.at(0) == '0'){
                num = num.substr(1);
         }
        return num;  
    }
    string removeKdigits(string num, int k) {
     
       
        while ( k >0){
            while (num.size() !=0 && num.at(0) == '0'){
                num = num.substr(1);
            }
            int length = num.size();
            if (length == 0){
                num = "0";
            }
            bool flag=  false;
            for (int i=0;i<length-1;i++){
               
                if ((num.at(i) ) > (num.at(i+1) )){
                    flag=  true;
                    if ( i == 0){
                        num = num.substr(1);
                       
                    }else{
                       
                        string tempStr = num.substr(0,i) ;
                        if ((i+1) < num.size()){
                           tempStr = tempStr + num.substr((i+1));
                        }
                        num = tempStr;
                    }
                    break;
                }
            }
            if (flag == false){
                num = num.substr(0,num.size()-1);
            }
           
            k--;
        }

        if (num.size() == 0)
            num = "0";
        if (num.size() > 1){
            num = truncZero(num);
        }
        return num;
    }
};

Leetcode 368. Largest Divisible Subset solution

Problem statement could be found @https://leetcode.com/problems/largest-divisible-subset/

Approach -

For every element n, check previous (n-1) elements and see if there modulo is zero. Whenever modulo is zero, store the chain length and index for the max value



Solution

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
       
        if (nums.size() <=1){
            return nums;
        }
       
        sort(nums.begin(), nums.begin() + nums.size());
        int *indexArr = new int[nums.size()];
        int *sizeArr = new int[nums.size()];
       
        for(int i=0;i<nums.size();i++){
            indexArr[i] = i;
            sizeArr[i] = 0;
        }
        int maxSize = 0;
        int maxIndex = 0;
        for(int i=0;i<nums.size();i++){
            for (int j=i-1;j>=0;j--){
                if ((nums[i]%nums[j]) == 0){
                    if (sizeArr[i] < (sizeArr[j] +1)){
                        sizeArr[i] = sizeArr[j] + 1;
                        indexArr[i] = j;
                        if (maxSize < sizeArr[i]){
                            maxSize = sizeArr[i];
                            maxIndex = i;
                        }
                    }
                   
                }
            }
        }
        vector<int> retVal;
        while (indexArr[maxIndex] != maxIndex){
            retVal.push_back(nums[maxIndex]);
            maxIndex = indexArr[maxIndex] ;
        }
        retVal.push_back(nums[maxIndex]);
        vector<int> opRetVal;
       
       for (int i=retVal.size()-1;i>=0;i--){
            opRetVal.push_back(retVal[i]);
        }
        return opRetVal;
    }
};

Leetcode 396. Rotate Function solution

Problem statement could be found @https://leetcode.com/problems/rotate-function/

Solution Approach-
Lets consider the numbers given in example [4,3,2,6] so we have following combinations
4 * 0 + 3* 1 + 2 *2 + 6 * 3
3 * 0 + 2 * 1 + 6 * 2 + 4 * 3
2 * 0 + 6 * 1 + 4 * 2 + 3 * 3
6 * 0 +  4 * 1 + 3 * 3 + 2 * 3

If one looks it closely it would seems like a sliding window for following array
4, 3,2,6,4,3,2

Above step means append  (n-1) elements to original vector.

Another optimization is  between first and second step, the difference is

In first step
Step 1. totalSum = 25
Step2. pSum = 3 +  2 + 6
Step 3. now in step2, total value has to be decreased by pSum as we shift left and now 4 * 3 has to be added, where 4 is the new element value & 3 (vector size -1).

At every slide of window these steps are applied



Following is the code

class Solution {
public:
   
    int maxRotateFunction(vector<int>& A) {
        if (A.size() == 0)
            return 0;
           
       
         if (A.size() == 1)
            return A[0]*0;
           
       int maxSum  = 0;
       int pSum = 0;
       int size = A.size();
     
       for (int i=0;i<size;i++) {
           maxSum = maxSum + (A[i] * i);
           if (i != 0 )
            pSum = pSum + A[i];
       }
       for (int i=0;i<size-1;i++){
           A.push_back(A[i]);
       }
      int gMax = maxSum;
    //  size = A.size();
      for (int i=1;i<size ;i++){
          //maxSum - pSum;
          maxSum  = maxSum - pSum + A[size+i-1] * (size - 1);
          pSum = pSum - A[i]  + A[i+size-1];
          if (maxSum > gMax)
            gMax = maxSum;
      }
      return gMax;
    }
};

Leetcode 365. Water and Jug Problem solution

Problem statement could be found @https://leetcode.com/problems/water-and-jug-problem/

Solution code

class Solution {
public:
    int getHCF(int x, int y){
         if ( y == 1)
            return 1;
        if (x%y == 0)
            return y;
        return getHCF(y, x%y);
    }
    bool canMeasureWater(int x, int y, int z) {
        if ( (x+y) < z){
            return false;
        }
        int hcf = 0;
        if (x > y)
            hcf = getHCF(x,y);
        else
            hcf = getHCF(y,x);
   
        if (z%hcf == 0)  
            return true;
        else
            return false;
    }
};

Leetcode 398. Random Pick Index solution

Problem statement could be found @https://leetcode.com/problems/random-pick-index/

Initial approach - Initially I started by creating a map of elements and their index list but this got TLE as the memory is given as constraint. The reason for this thought was index once and query multiple times.

Second approach - Compare the values on fly and save matching indexes. Then generate random value and mod by nos of instances of matching indexes, using the value received after mod to do find the index. This was accepted

Following is the code with second approach

class Solution {
 
    vector<int> elementVector;
    size_t vectorSize ;
public:
    Solution(vector<int> nums) {
      elementVector = nums;
      vectorSize = nums.size();
     
     
     
    }
   
    int pick(int target) {
        vector<int> indexVect;
        for (int i=0;i<vectorSize; i++){
            if (elementVector[i] == target)
                indexVect.push_back(i);
        }
        int indexSize = indexVect.size();
        int randVal = (rand()%indexSize);
        return indexVect[randVal];
    }
};

Leetcode 399 Evaluate Division Solution

Problem description could be found @https://leetcode.com/problems/evaluate-division/

Approach - The solution is a DFS to be done on Graph, where graph nodes are the divisor and dividends. Value obtained from result is the edge weight between divisor and dividend node

 The first idea in  my mind was to create adjacency matrix with assumption that there are only 1 length string but it failed as sample testcases had  strings like ab, cd. So had to go with Adjacency list solution. Following is the accepted code which ran in 3 msec

struct node{
  double weight;
  string adjacentNode;
 
  node (double wt, string dest){
      this->weight = wt;
      this->adjacentNode = dest;
  }
};

class Graph{
    private:
        map<string, list<node *> *> nodeMap;
    public:
        Graph(){
           
        }
        void addNode(string src, string des, double wt){
            node *tempNode = new node(wt, des);
           
            list<node *> *nodeList;
            if (nodeMap.count(src) == 0){
                nodeList = new list<node *>();
                nodeMap[src] = nodeList;
            }else{
               nodeList =  nodeMap.at(src);
            }
            nodeList->push_back(tempNode);
           
            // add in reverse way
            node *tempOppNode = new node(1.0/wt, src);
           
            list<node *> *revList;
            if (nodeMap.count(des) == 0){
                revList = new list<node *>();
                nodeMap[des] = revList;
               
            }else{
               revList =  nodeMap.at(des);
            }
            revList->push_back(tempOppNode);
        }
       
        bool contains(string key){
            if (nodeMap.count(key) != 0)
                return true;
            return false;
        }
       
        double dfs(string src, string dest, set<string> traversed){
            list<node *> *myList = nodeMap[src];
            if (traversed.find(src) != traversed.end())
                return -1.0;
               
            if (myList == NULL){
                return -1.0;
            }
            traversed.insert(src);
           for (list<node *>::iterator it=myList->begin();
                    it != myList->end() ; it++){
               node *listNode = *it;
               if (listNode->adjacentNode == dest){
                   traversed.erase(src);
                   return listNode->weight;
               }else{
                   double d = dfs(listNode->adjacentNode, dest, traversed);
                   if (d != -1.0){
                       traversed.erase(src);
                       return d * listNode->weight;
                   }
               }
           }
           traversed.erase(src);
           return -1;
        }
};


class Solution {
public:
 
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        Graph g ;
        for (int i=0;i<equations.size();i++)   {
            pair<string, string> val = equations[i];
            double value = values[i];
            g.addNode(val.first, val.second, value);
         
         
        }
       
        vector<double> retVal;
        for (size_t i=0;i<queries.size();i++){
            string src = queries[i].first;
            string dest = queries[i].second;
            if (src == dest){
                if (g.contains(src))
                    retVal.push_back(1.0);
                else
                    retVal.push_back(-1.0);
            }else{
                set<string> traversed;
                double d = g.dfs(src, dest, traversed);
                retVal.push_back(d);
            }
        }
        return retVal;
    }
}; 

Leetcode 395 Longest Substring with At Least K Repeating Character Solution

Problem Statement could be found @https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

Solution:-
Idea is to first count all character occurrence in a string. If a character is repeated less than k times, then is shouldn't be considered and can act string splitter.
class Solution {
    int repeatCount;
    int maxSubSize;
public:
    int helper(string s){
        int tempMaxSize = 0;
        if (s.size() < repeatCount){
            return 0;
        }
        //int tempMaxSize
        int arr[26] = {0};
        for (int i=0;i<s.size();i++){
            arr[s.at(i) -'a'] ++;
        }
       
        int startLength = 0;
        int flag = false;
        int charCount = 0;
        for (int i=startLength;i<s.size();i++){
            // this could act as breaker
            int charVal = (s.at(i) -'a');
         
            if (arr[charVal] < repeatCount){
                if (charCount == 0)
                    charCount = 1;
                string temp = s.substr(startLength,charCount);
                int tempL = helper(temp);
                if (tempL > tempMaxSize)
                    tempMaxSize = tempL;
                startLength = i+1;
                flag = true;
                charCount = 0;
            }else{
                charCount ++;
            }
        }
        if (flag == false && s.size() >= repeatCount  ){
            //maxSubSize = s.size();
            tempMaxSize = s.size();
            return tempMaxSize ;
        }else{
            string temp = s.substr(startLength);
            int tempL = helper(temp);
            if (tempL > tempMaxSize){
                tempMaxSize = tempL;
            }
        }
           
        return tempMaxSize;
    }
    int longestSubstring(string s, int k) {
        repeatCount  = k ;
        maxSubSize = 0;
        int tempMaxSize = helper(s);
        if (tempMaxSize > maxSubSize)
            return tempMaxSize;
        else
            return maxSubSize;
    }
};

Leet code 397. Integer Replacement

Problem Statement could be found @ https://leetcode.com/contest/4/problems/integer-replacement/

Solution:

There are two important points in this problem:
1. A value might be touched upon multiple times hence it is important to memoize the values
2. If the value is the max value of int (2,147,483,647) , then using just int in algo would give wrong value as for odd case 2,147,483,647 would go out integer range. Hence one should use unsigned int

Following is the code

class Solution {
    int max;
    map<unsigned int, int> valMap;
public:
    int algo(unsigned int n){
         if (n == 1)
            return 0;
        if (valMap.count(n) != 0){
            return valMap[n];
        }
        if (n%2 == 0){
            valMap[n] = integerReplacement(n/2) + 1;
            return (valMap[n]);
        }else{
            int plusOne = integerReplacement(n + 1) +1;
            int minusOne = integerReplacement(n-1) + 1;
            if (plusOne < minusOne){
                valMap.insert(pair<unsigned int,int>( n,  (plusOne )));
                return (plusOne );
            }
            else{
                valMap.insert(pair<unsigned int,int> (n, (minusOne )));
                return (minusOne );
            }
               
        }
    }
    int integerReplacement(int n) {
      unsigned int l = n;
      return algo(n);
    }
};

Solution to 376. Wiggle Subsequence

Problem Statement could be found @ https://leetcode.com/problems/wiggle-subsequence/

Solution code


class Solution {
    vector<int> smaller;
    vector<int> larger;
public:
    int wiggleMaxLength(vector<int>& nums) {
        bool addToSmall ;
        int size = nums.size();
        for (int i=size-2; i>=0;i--){
            if (nums[i] == nums[i+1]){
                nums.erase(nums.begin() + (i+1));
            }
        }
       
        if (nums.size() <= 2)
            return nums.size();
           
       int index = 0;
       int count = 0;
       while (index < (nums.size()-1)){
           if (nums[index] < nums[index+1]){
               count ++;
               index = index+1;
               while ( (nums[index] < nums[index+1]) && (index < (nums.size()-1))){
                   index++;
               }
             
           }else{
                if (nums[index] > nums[index+1]){
                   count ++;
                    while ( (nums[index] > nums[index+1]) && (index < (nums.size()-1))){
                       index++;
                   }
                }
           }
       }
       return (count+1);
    }
};

Microsoft interview experience

Telephonic Round

1. 

Given n light bulbs, write two methods. 

isOn(i) to determine if a light bulb is on
toggle(start, end) to toggle all the light bulbs in the range 

The question is present at career cup https://www.careercup.com/question?id=5668664122540032

2. Given a number n, tell the count of distinct binary search trees that could be formed from it

Face to Face

Round 1:

1. Implement Singleton design pattern

2. Find majority element in an array

Round 2:

1. Given a string, return longest palindromic sub string

Leetcode 393 UTF-8 Validation Solution

Problem Statement could be found at following link

https://leetcode.com/problems/utf-8-validation/

Solution:


class Solution {
    private:
    const static int singleByteMask = 0x00000080;
    const static int multiByteFollower = 0x000000C0;
 
    const static int byte2Mask = 0x000000E0;
    const static int byte3Mask = 0x000000F0;
    const static int byte4Mask = 0x000000F8;
public:
    bool isSingleByte(int val){
           val = val & singleByteMask;
           return (val == 0);
    }
 
    bool isMultiByteFollower(int val){
        val = val & multiByteFollower;
           return (val == 128);
    }
    bool validUtf8(vector<int>& data) {
        int multiCharCount = 0;
        for (int index=data.size()-1;index>=0;index--){
            int num = data[index];
            if ( isSingleByte(num) == true){
                if (multiCharCount != 0)
                    return false;
            }else{
                if (isMultiByteFollower(num)){
                    multiCharCount++;
                    if (multiCharCount > 3)
                        return false;
                }else{
                    if (multiCharCount ==0)
                        return false;
                    else{
                        if (multiCharCount == 1){
                            num = byte2Mask & num;
                            if (num != 192){
                             
                                return false;
                            }else{
                                multiCharCount = 0;
                            }
                        }else if (multiCharCount == 2){
                             num = byte3Mask & num;
                             if (num != 224){
                               
                                return false;
                             }else{
                                multiCharCount = 0;
                             }
                        }else if (multiCharCount == 3){
                            num = byte4Mask & num;
                             if (num != 240){
                               
                                return false;
                             }else{
                                multiCharCount = 0;
                             }
                        }
                    }
                }
             
            }
        }
        return (multiCharCount ==0) ;
    }
};

Leetcode 394 Solution to Decode String

Problem Statement is present at
https://leetcode.com/problems/decode-string/


Idea:
Lets say string is 2[a]3[bc]
Take two stacks - First stack contains the number encountered and other the characters encountered.
When you hit closing bracket, then unwind char stack to create the string to be repeated and read from number stack the frequency of repetition,



Solution:

class Solution {
    stack<int> numStack;
    stack<int> charStack;
    string retString;
private:
    bool isInt(char x){
        if  ( ((x-'0')>=0) && ((x-'9') <=9)){
            return true;
        }
        return false;
    }
public:
    string decodeString(string s) {
       for (int i=0;i<s.size();i++){
           char x = s.at(i);
         
           if (isInt(x)){
               int v = 0;
               int tempL = 0;
               while (isInt(s.at(i+tempL))){
                   v = (v *10) + (s.at(i+tempL) - '0');
                   tempL++;
               }
               //tempL--;
             
             
               tempL--;
               i = i+tempL;
               numStack.push(v);
           }else{
                if (numStack.empty()){
                       retString = retString + x;
                       continue;
                }
             
               if (x != ']'){
                   charStack.push(x);
               }else{
                   int repeatCount = numStack.top();
                   numStack.pop();
                   char stringChar = charStack.top();
                   string iString ;
                   while (stringChar != '['){
                       iString = stringChar + iString;
                       charStack.pop();
                       stringChar = charStack.top();
                   }
                   charStack.pop();
                     
                    string tempString;
                   for (int count=0;count<repeatCount;count++)
                        tempString =  tempString + iString;
               
                   if (numStack.empty()){
                       retString = retString + tempString;
                   }else{
                       for (int index=0;index<tempString.size();index++ )
                            charStack.push(tempString.at(index));
                   }
                 
               }
           }
       }
       return retString;
    }
};

Leetcode 392 : Is Subsequence

Problem Statement could be found at
https://leetcode.com/problems/is-subsequence/


Solution:- Since the original string is very big so DP is not suggested here. So the idea is to pick every character of pattern one by one and find in original string and keep a track of matching characters, if the match count equals final length then it is sub sequence otherwise not

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int index = 0;
        int i=0;
       
        int stringLength = t.size();
        int patternSize = s.size();
        int matchCount = 0;
        for (;(i<patternSize) && (index < stringLength );i++){
            char patternChar = s.at(i);
            while (index < stringLength){
               if (patternChar == t.at(index)){
                index++;  
                matchCount++;
                break;
               }
               index++;
            }
        }
        if ( matchCount == patternSize)
            return true;
        else
            return false;
    }
};

Solution to Leetcode 387. : First Unique Character in a String

Following is the link for problem statement
https://leetcode.com/problems/first-unique-character-in-a-string/

Solution:

class Solution {
public:
    int firstUniqChar(string s) {
        int valArray[26] = {0};
       
       
        for(int i=0;i<s.size();i++){
            valArray[s.at(i) - 'a'] ++;
        }
        int i=0;
        for(;i<s.size();i++){
            if (valArray[s.at(i) - 'a']  == 1){
               return i;
            }
        }
        return -1;
    }
};

Status : Accepted

Leetcode 389 Solution : Find the difference

Problem description is given in following link

https://leetcode.com/problems/find-the-difference/

Solution:

class Solution {
public:
    char findTheDifference(string s, string t) {
        int val = 0;
        for (int i=0;i<t.size();i++){
            val = val + t.at(i);
        }
       
        for (int i=0;i<s.size();i++){
            val = val - s.at(i);
        }
        return val;
    }
};

Status : Accepted

Solution Leetcode 386. Lexicographical Numbers

Following is the link to description of the problem

https://leetcode.com/problems/lexicographical-numbers/


Solution code

class Solution {
    vector<int> v;
    int limit;
private:
    void generateNos(int nos){
        if (nos > limit){
            return;
        }
       
        v.push_back(nos);
       
        for (int i=0;i<10;i++){
       
            int temp = (nos * 10) + i;
            generateNos(temp);
           
        }
        return ;
    }
public:

    vector<int> lexicalOrder(int n) {
        limit = n;
        for (int i=1;i<10;i++){
            generateNos(i);
        }
        return v;
    }
};

Time taken : 1259 msec
Status: Accepted

Interview experience at Amazon

Round 1

1. Given an array tell the minimum range to sort such that complete array is sorted


Round 2:

1. Given an array like following
    a1a2a3a4 .... anb1b2b3b4b5b6.... bn

Ouput
  a1b1a2b2a3b3... anbn


3. Given a an array of form like
 89 88 12 32 98 97

tell the largest   number which can be formed from it
That is output would be 989789883212

However, this question wasn't explicitly/directly like to this. The question was given following array
4 5 6 9 8 7
convert it to
9 8 7 6 5 4



Round 3:

1. Design a token management system