August 2016 ~ Coding Interview Questions With Solutions

Sunday 28 August 2016

Single Number

Krishna Chaurasia array, bitwise, geeksforgeeks, interview, interviewbit, xor 19 comments

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.

Example:
I/P = [1, 2, 3, 2, 3, 1, 3]
O/P = 3

Approach: Take xor of all the elements. The number of terms occurring even number of times get cancelled due to property of xor that a ^ a = 0

#include<iostream>
using namespace std;

int main(){
    int arr[] = {2, 3, 3, 3, 3, 4, 2, 4, 4, 2, 4}; //{1, 2, 4, 4, 10, -8};

    int n = sizeof(arr)/sizeof(arr[0]);
    int result = 0;
    for(int i = 0 ; i < n ; i++ ){
        result = result ^ arr[i];
    }
    cout << result << " is the odd time occurring element!" << endl;
    return 0;
}

Range Sum Query - Immutable

Krishna Chaurasia array, interview, leetcode, vector 2 comments

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

You may assume that the array does not change.
There are many calls to sumRange function.

Approach: Compute the sum till all the ith index in the array for all 0 <= i < n. Use this precomputed values to return the sum.

class NumArray {
public:
    vector<int> array;
    vector<int> sum;
    NumArray(vector<int> &nums) {
        for(int i = 0 ; i < nums.size(); i++){
            array.push_back(nums[i]);
        }
        //preProcess after the vector is initialized
        preProcess();
    }
    
    //preProcess to store the sum till all i in a vector since the function is called many times
    void preProcess(){
        sum.push_back(0);
        for(int i = 1; i <= array.size(); i++){
            sum.push_back(sum[i - 1] + array[i - 1]);
        }
    }

    int sumRange(int i, int j) {
        //return sum directly from the calculated sums
        int res = sum[j + 1] - sum[i];
        return res;
    }
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);

Largest Number

Krishna Chaurasia array, geeksforgeeks, interviewbit, sorting No comments

Given a list of non-negative integers, return the largest number that can be formed by their arrangement.

Eg. For the list [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Approach: We need sorting but in the modified way since if we have the number 9, 80 in the list then the largest number can be 980 but sorting will give 809. So, we modify sorting such that the for the pair(X, Y) in the list X comes first after sorting if XY > YX where XY represents concatenation of X and Y. Thus, for 9, 80, we will have the sorting result as 980 since 980 > 809.

int myCompare(int a, int b){
    string X = to_string(a);
    string Y = to_string(b);
    string XY = X.append(Y);
    string YX = Y.append(X);
    return XY.compare(YX) > 0 ? 1 : 0;
}

string Solution::largestNumber(const vector<int> &A) {
    vector<int> temp(A);
    string result =  "";
    int count = 0;
    for(int i = 0 ; i < A.size(); i++){
        if(A[i] == 0){
            count++;
        }
    }
    //handling all 0 vector
    if(count == A.size()){
        result = "0";
        return result;
    }
    //sort as per modified compare function
    sort(temp.begin(), temp.end(), myCompare);
    
    string out = "";
    //make a string for the result
    for(int i = 0; i < A.size(); ++i){
        result.append(to_string(temp[i]));
    }
    return result;
}

Week 4 Assignment Solution

Krishna Chaurasia MOOC, software testing

This post provides solution to the fourth assignment of the online course Software Testing offered by MHRD. The answers to each questions are marked in red. Explanation for numerical problems are given below each problem.

You can download the pdf version of the solution here.

Which statement below BEST describes non-functional testing?

The process of testing an integrated system to verify that it meets specified requirements.
The process of testing to determine the compliance of a system to coding standards.
Testing without reference to the internal structure of a system.
Testing system attributes, such as usability, reliability or maintainability.

Which of the following statements are TRUE?

Regression testing and acceptance testing are the same.
Regression tests show if all defects in the modified part of the code have been resolved.
Regression tests are performed to detect if code changes have introduced defects.
Regression tests should be performed during integration testing.

Which of the following types of testing is not performed during system testing?

Stress testing
Functionality testing
Recovery testing
White box testing

Alpha and Beta testing are considered to be which one of the following types of testing?

Regression testing
Unit testing
Integration testing
System testing

For large programs, which one of the following integration testing strategy is rarely used?

Big-bang
Top-down
Bottom-up
Mixed

Which one of the following is true of a pure top-down integration testing process?

Requires only stubs for testing
Requires only drivers for testing
Requires both stubs and drivers for testing
Requires neither stubs nor drivers for testing

After a program has been modified, which one of the following options characterizes the regression test cases:

All test cases
Test cases that execute the modified statements
Test cases that execute the affected or modified statements
Test cases that execute the unaffected statements

Which one of the following types of program models is normally used to design the integration test plan?

CFG
DFD
Structure chart
State chart

Suppose in order to estimate the number of latent errors in a program, you seed it with 100 errors of different kinds. After testing the software using its full test suite, you discover only 80 of the introduced errors. You discover 16 other errors also. Estimate the number of latent errors in the software.

Explanation: Using the formula n * [(S - s) / s] for latent errors where n = 16, S = 100 and s = 80, we get the answer as 4.

Beta testing is usually performed by which one of the following?

Test team
Development team
Friendly customers
Customers

Note: Post any queries related to the solution in the course forum only.

Majority Element in a Sorted Array

Krishna Chaurasia array, binary search, geeksforgeeks, majority element, sorted array 2 comments

Write an algorithm to find if a given integer x appears more than n/2 times in a sorted array of n integers. See this for a similar problem on Majority Element.

Approach: Use binary search to find the first occurrence of x in the array.
TC = O(log(n))

#include <iostream>
#include <cmath>
using namespace std;

int binsrch(int *arr, int x, int low, int high){
    if(low <= high){
        int mid = (low + high) / 2;
        // returns the first occurrence of x
        if(arr[mid] == x && (arr[mid] > arr[mid - 1] || mid == 0)){
           return mid;
        }
        if(x > arr[mid]){
            return binsrch(arr, x, mid + 1, high);
        } else{
            return binsrch(arr, x, low, mid - 1);
        }
    }
    return -1;
}

int isMajority(int *arr, int x, int n){
    int first = binsrch(arr, x, 0, n - 1);
    if(first == -1){
        return 0;
    }
    if((first + n/2) <= (n - 1) && arr[first + n/2] == x){
        return 1;
    }
    return 0;
}

using namespace std;

int main(){
    int arr[] ={1, 2, 3, 4, 4, 4, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 4;
    if(isMajority(arr, x, n)){
        cout << x << " is the majority element." << endl;
    } else{
        cout << x << " is not the majority element." << endl;
    }

    return 0;
}

Majority Element

Krishna Chaurasia array, frequency, geeksforgeeks, majority element, Moore's Voting No comments

Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Idea : To find the majority element using Moore's Voting Algorithm

Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

#include<iostream>
using namespace std;

int main(){
    int arr[] = {2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 2, 4, 4}; //{1, 2, 4, 4, 10, -8};

    int n = sizeof(arr)/sizeof(arr[0]);
    int count,  majorityElt;
    majorityElt = arr[0];
    count = 1;
    for(int i = 1 ; i < n ; i++ ){
        if(arr[i] == majorityElt){
            count++;
        } else {
            count--;
        }
        if(count == 0){
            count = 1;
            majorityElt = arr[i];
        }
    }
    count = 0;
    for(int i = 0 ; i < n ; i++){
        if(arr[i] == majorityElt){
            count++;
        }
    }
    if(count > n/2){
        cout << majorityElt << " is the majority element " << endl;
    } else{
        cout << "No such element exists" << endl;
    }
    return 0;
}

Two Sum Zero

Krishna Chaurasia array, geeksforgeeks, programming 4 comments

An array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero.

Approach : Using the approach given in the 2 Sum post.

#include <iostream>
#include <cmath>
using namespace std;

void mergeSort(int *, int, int);
void merger(int *, int, int, int);
void sumToZero(int *, int);

void sumToZero(int *arr, int n){
    int i = 0, j = n - 1, sum, minSum, minLeft, minRight;
    minSum = 999999;
    minLeft = i;
    minRight = j;
    while(i < j){
        sum = arr[i] + arr[j];
        if(abs(sum) > abs(minSum)){
            minSum = sum;
            minLeft = i;
            minRight = j;
        }
        if(sum < 0){
            i++;
        } else{
            j--;
        }
    }
    cout << "Elements whose sum is close to 0 : " << arr[minLeft] << " " << arr[minRight];
    cout << endl;
}

void mergeSort(int *arr, int low, int high){
    int mid;
    if(low < high){
        mid = (low + high)/2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merger(arr, low, mid, high);
    }
}

void merger(int *arr, int low, int mid, int high){
    int n1 = mid - low + 1;
    int n2 = high - mid;
    int left[n1], right[n2];
    int i, j, k;
    i = 0;
    while(i < n1){
        left[i] = arr[i + low];
        i++;
    }
    i = 0;
    while(i < n2){
        right[i] = arr[i + mid + 1];
        i++;
    }
    i = 0;
    j = 0;
    k = low;
    while(i < n1 && j < n2){
        if(left[i] <= right[j]){
            arr[k++] = left[i++];
        } else{
            arr[k++] = right[j++];
        }
    }
    while(i < n1){
        arr[k++] = left[i++];
    }
    while(j < n2){
        arr[k++] = right[j++];
    }
}

int main(){

    int arr[] = {1, 60, -10, 70, -80, 85};
    int n = sizeof(arr)/sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    sumToZero(arr, n);
    return 0;
}

3Sum Closest

Krishna Chaurasia array, interviewbit, leetcode, sorting, triplet No comments

Given an array A of n integers, find three integers in A such that the sum is closest to a given value. Return the sum of the three integers. You may assume that each input would have exactly one solution.
It is a modified version of the problem 3 Sum

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        //sort the vector
        sort(nums.begin(), nums.end());
        int temp = 0, j, k, diff = INT_MAX, out = 0;
        for(int i = 0; i < nums.size(); i++){
            j = i + 1;
            k = nums.size() - 1;
            while(j < k){
                temp = nums[i] + nums[j] + nums[k];
                //update the minimum diff till now and store the output 
                if(abs(temp - target) < diff){
                    diff = abs(temp - target);
                    out = temp;
                }
                //if diff is 0, return the output else increment or decrement based on the current (temp - target) value
                if(diff == 0){
                    return out;
                }else if(temp - target < 0){
                    j++;
                }else{
                    k--;
                }
            }
        }
        return out;
    }
};

Anti Diagonals

Krishna Chaurasia anti diagonals, geeksforgeeks, interviewbit, matrix 3 comments

Give a N*N square matrix, return an array of its anti-diagonals.

Input:  
1 2 3
4 5 6
7 8 9
Output :
[ 
  [1],
  [2, 4],
  [3, 5, 7],
  [6, 8],
  [9]
]

Approach : The point to observe here is that the sum of i (row number) and j (column number) is constant for each anti-diagonal.
For example:
Diagonal 1 has i + j = 0
Diagonal 2 has i + j = 1
and so on.
So define s = i + j
Loop with s from 0 to 2*(N-1) (maximum sum possible)
Now if s = i+j then j = s-i
So we have reduced the problem to two variables: s and i (O(n^2)).

vector<vector<int> > Solution::diagonal(vector<vector<int> > &A) {

    vector<vector<int>> result;
    vector<int> diagonal;
    
    int n = A.size();
    if(n == 0)
        return result;
    for(int d = 0; d <= 2*(n-1); d++) {
       for(int i = 0; i <= d; i++) {
           int j = d - i;
           //continue if i or j exceeds their bounds
           if(i >= n || j >= n)
                continue;
           diagonal.push_back(A[i][j]);
       }
       result.push_back(diagonal);
       diagonal.clear();
   }
   return result;
}

Sunday 28 August 2016

Single Number

Range Sum Query - Immutable

Friday 26 August 2016

Largest Number

Week 4 Assignment Solution

Thursday 25 August 2016

Majority Element in a Sorted Array

Wednesday 24 August 2016

Majority Element

Two Sum Zero

Monday 22 August 2016

3Sum Closest

Sunday 21 August 2016

Anti Diagonals

Contact Me

Popular Posts

Categories

Blog Archive

| Privacy Policy | Disclaimer | Resume |

| Terms of Use | Contact Us | Site Map |