Add One To Number

Problem:

Given a non-negative number represented as an array of digits,
add 1 to the number ( increment the number represented by the digits ).
The digits are stored such that the most significant digit is at the head of the list.


NOTE: Certain things are intentionally left unclear in this question which you should practice asking the interviewer.
For example, for this problem, following are some good questions to ask :

• Q : Can the input have 0’s before the most significant digit. Or in other words, is 0 1 2 3 a valid input?
• A : For the purpose of this question, YES
  
• Q : Can the output have 0’s before the most significant digit? Or in other words, is 0 1 2 4 a valid output?
• A : For the purpose of this question, NO. Even if the input has zeros before the most significant digit.

Example:
If the vector has [1, 2, 3]
the returned vector should be [1, 2, 4]
as 123 + 1 = 124.

Solution:

The algorithm is simple where we add 1 to the least significant digit and propagate the  carry to most significant digit.

The problem here is to handle the boundary cases where in the initial array we have zeros in the most significant digit , but the output array cannot have trailing zeros. A very simple approach is to create a new array for the number obtained after adding 1 and removing initial zeros.

C++ code:

vector<int> plusOne(vector<int> &A) {
    int s, carry=1;
    s = A.size();
    vector <int> result;
    for(int i=s-1;i>=0;i--)
    {
        int sum;
        sum = A[i] + carry;
        carry = sum/10;
        result.push_back(sum%10);
    }
    result.push_back(carry);
    s = result.size();
    int i = s-1;
    vector<int> ans;
    while(i>=0 && result[i]==0)
    {
        i--;
    }
    while(i>=0)
    {
        ans.push_back(result[i]);
        i--;
    }
    return ans;
}

Max Sum Contiguous Subarray

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

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.

Solution:

Since the problem demands that the subarray should contain at least one element, in the base case where  size of given array is one, then return this value.

The idea that if we have to find the max sum of contiguous subarray till index i, we calculate the max sum till index i-1 and add the array value at index i in this. If the new max value is greater than the array value at index i we continue same process with i+1 index else we replace the max value till index i with A[i].
Our final answer is the maximum of all the intermediate max sum values obtained. 



C++ Code:

int maxSubArray(const vector &A) {
    int s = A.size();
    int ans = A[0], m = 0;
    if(s==1)
        return A[0];
    for(int i = 0; i < s; i++)
    {

        m = m + A[i];
        if(m < A[i])
            m = A[i];
        if(ans < m)
            ans = m;
    }
    return ans;
}

Min Steps in Infinite Grid

Problem: You are in an infinite 2D grid where you can move in any of the 8 directions:

(x,y) to  (x+1, y), (x - 1, y), (x, y+1), (x, y-1),

 (x-1, y-1), (x+1,y+1), (x-1,y+1), (x+1,y-1)

You are given a sequence of points and the order in 

which you need to cover the points. Give the minimum number

 of steps in which you can achieve it. You start from the first point.

Input : [(0, 0), (1, 1), (1, 2)]
Output : 2

It takes 1 step to move from (0, 0) to (1, 1). It takes one more step to move from (1, 1) to (1, 2).


Solution:

As we have to cover all the given points in the specified order, if we can find the minimum number of steps required to reach from a starting point to next point, the sum of all such minimum steps for covering all the points would be our answer.

One way to reach form a point (x1,y1) to (x2, y2) is to move abs(x2-x1) steps in horizontal direction and abs(y2-y1) steps in vertical direction, but this is not the shortest path to reach (x2,y2). The best way would be to cover the maximum possible distance in diagonal direction and remaining in horizontal or vertical direction. If we look closely this just reduces to maximum of abs(x2-x1) and abs(y2-y1).

Example
x1 = 5, y1= 20
x2 = 15, y2 = 15

we first move diagonally to reach (10,15) this takes 5 steps and then we move 5 units in x direction, which again takes 5 steps. In total this is 10 steps which is equal to MAX(abs(15-5), abs(15-20))

C++ code:

int coverPoints(vector<int> &X, vector<int> &Y) {

    int s1=X.size(), s2=Y.size(),ans=0;

    for(int i=1;i<s1;i++)

    {

        ans = ans + (abs(X[i]-X[i-1])<abs(Y[i]-Y[i-1])?abs(Y[i]-Y[i-1]):abs(X[i]-X[i-1]));

    }

    return ans;

}