Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution:

class Solution {
public:
    void process_vector(vector<int>& tmp, vector<pair<int, int> >& nums) {
        for (int i = 0; i < tmp.size(); i++) {
            nums.push_back(make_pair(tmp[i], i));
        }
    }
   
    static bool comp(pair<int, int> first, pair<int, int> second) {
        return first.first < second.first;
    }
   
    vector<int> twoSum(vector<int>& tmp, int target) {
        vector<int> sol;
        vector<pair<int, int> > nums;
        process_vector(tmp, nums);
        sort(nums.begin(), nums.end(), comp);
        if (nums.size() == 0) {
            return sol;
        }
       
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int temp_sum = nums[left].first + nums[right].first;
            if (temp_sum == target) {
                sol.push_back(nums[left].second);
                sol.push_back(nums[right].second);
                return sol;
            } else if (temp_sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return sol;
    }
};

Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree 

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int dia = 0, height = 0;
        height = helper(root, dia);
        // Get edges from number of nodes.
        return dia > 1 ? dia  - 1: 0;
    }
   
    int helper(TreeNode *root, int& dia) {
        if (root == NULL) {
            return 0;
        }
        int left_height = 0, right_height = 0, left_dia = 0, right_dia = 0;
       
        left_height = helper(root -> left, left_dia);
        right_height = helper(root -> right, right_dia);
       
        dia = max(left_height + right_height + 1, max(left_dia, right_dia));
        return max(left_height, right_height) + 1;
    }
};

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int size = nums.size();
        int sum = 0, maxSum = nums[0];
        for (int i = 0; i < size; i++) {
            if (sum < 0) {
                sum = nums[i];
            } else {
                sum += nums[i];
            }
            maxSum = max(maxSum, sum);
        }
        return maxSum;
    }
};

Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Note: You can assume that

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• the answer is guaranteed to fit into signed 32-bit integer

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

Subscribe to see which companies asked this question.

class Solution {
public:
    int change(int amount, vector<int> coins) {
        /* // Recursive.
        if (amount == 0) {
            return 1;
        }
        if (amount < 0 || coins.size() == 0) {
            return 0;
        }
        int denom = coins[0];
        int factor = 0, sol = 0;
        coins.erase(coins.begin());
        
        while (denom * factor <= amount) {
            sol += change(amount - denom * factor, coins);
            factor++;
        }
        return sol;
        */
        // Dynamic.
        int ch[amount + 1][coins.size() + 1];
        
        for (int i = 0; i < coins.size() + 1; i++) {
            ch[0][i] = 1;
        }
        for (int i = 1; i < amount + 1; i++) {
            ch[i][0] = 0;
        }
        
        for (int i = 1; i < amount + 1; i++) {
            for (int j = 1; j < coins.size() + 1; j++) {
                int sol = 0;
                int factor = 0;
                while (factor * coins[j - 1] <= i) {
                    sol += ch[i - factor * coins[j - 1]][j - 1];
                    factor++;
                }
                ch[i][j] = sol;
            }
        }
        return ch[amount][coins.size()];
    }
};

=====================

/******************************************************************************

                              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 <vector>

#include <map>

using namespace std;

int helper(vector<int>& input, int idx, int target,

            map<string, int>& mp) {

    string key = to_string(idx) + ":" + to_string(target);

    if (mp.count(key) != 0) {

        return mp[key];

    }

    if (idx >= input.size()) {

        mp[key] = 0;

        return 0;

    }

    if (target < 0) {

        mp[key] = 0;

        return 0;

    } else if (target == 0) {

        mp[key] = 1;

        return 1;

    }

    

    int a = helper(input, idx, target - input[idx], mp);

    int b = helper(input, idx + 1, target, mp);

    mp[key] = a + b;

    return a + b;

}

int minWays(vector<int>& input, int target) {

    /*

    - recursive & memoization

    map<string, int> mp;

    int ans = helper(input, 0, target, mp);

    return mp["0:" + to_string(target)];

    */

    

    //- dynamic programming

    if (input.size() == 0) {

        return 0;

    }

    vector<int> dp(target + 1, 0);

    dp[0] = 1;

    

    

    /*

    // This will give total permutations.

    for (int i = 1; i <= target; i++) {

        for (auto value : input) {

            if (i - value >= 0) {

                dp[i] += dp[i - value];

            }

        }

    }

    */

    

    // But what we need is just the combination. So,

    for (auto value: input) {

        for (int i = value; i <= target; i++) {

            dp[i] += dp[i - value];

        }

    }

    return dp[target];

}

int main()

{

    cout<<"Hello World" << endl;

    

    vector<int> input;

    int target;

    // Test case 1:

    input = {1, 2, 5};

    target = 0;

    cout << minWays(input, target) << endl;

    

    // Test case 2:

    input.clear();

    input = {};

    target = 5;

    cout << minWays(input, target) << endl;

    

    // Test case 3:

    input.clear();

    input = {1, 2, 5};

    target = 5;

    cout << minWays(input, target) << endl;

    

    // Test case 4:

    input.clear();

    input = {1, 5, 15};

    target = 125;

    cout << minWays(input, target) << endl;

    

    return 0;

}

Poor Pigs.

There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.

Answer this question, and write an algorithm for the follow-up general case.

Follow-up:

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the "poison" bucket within p minutes? There is exact one bucket with poison.

Solution:

class Solution {

public:

    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {

        // one pig can identify 5 buckets.

        // 2 pig can identify 5 X 5 buckets.

        // 3 pig can identify 5 X 5 X 5 buckets.

        // and so on..

        int pig = 0;

        int linear_bucket_count = minutesToTest/minutesToDie + 1;

        while (pow(linear_bucket_count, pig) < buckets) {

            pig++;

        }

        

        return pig;

    }

};

Beautiful Arrangement

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:

1. The number at the ith position is divisible by i.
2. i is divisible by the number at the ith position.

Now given N, how many beautiful arrangements can you construct?

Example 1:

Input: 2
Output: 2
Explanation: 

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

Note:

1. N is a positive integer and will not exceed 15.

static int countArrangements(int n,int[] data){
    if(n<=0){
      return 1;
    }
    int count = 0;
    for(int i=0;i<n;++i){

      // Just check if any number can be placed at n index.
      if(data[i]%n == 0 || n%data[i] ==0){
        swap(data,i,n-1);
        count += countArrangements(n-1,data);
        swap(data,i,n-1);
      }
    }
    return count;
  }

  static void swap(int[] data,int i,int j){
    int temp = data[i];
    data[i] = data[j];
    data[j] = temp;
  }

  static int arrangements(int n) {
    int[] data = new int[n];
    for(int i=0;i<n;++i){
      data[i] = i+1;
    }
    return countArrangements(n,data);
  }

Recover Binary Search Tree

Problem:

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Solution:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *cur_min = new TreeNode(INT_MIN), *one = NULL, *sec = NULL;
        check(root, cur_min, one, sec);
        if (one && sec) {
            int tmp = one -> val;
            one -> val = sec -> val;
            sec -> val = tmp;
        }
        return;
    }
    void check(TreeNode *root, TreeNode *&cur_min, TreeNode *&one, TreeNode *&sec) {
        if (!root) {
            return;
        }
        check(root -> left, cur_min, one, sec);
        if (cur_min -> val >= root -> val) {
            if (one == NULL) {
                one = cur_min;
            }
            sec = root;
        }
        cur_min = root;
        check(root -> right, cur_min, one, sec);
        return;
    }
};