BS - Find the First and Last of A Given Number in A Sorted Array (Amazon Interview Question)

1. Problem Description

This is an Amazon interview question for software develop engineer from careercup. Here is the original thread,

"

Find the first and last occurrence of a number in a sorted array of integers 

For Example: int[] a = {1,2,3,4,5,5,7,8}

- testsync012345 5 days ago in United States for Kindle | Report Duplicate | Flag ".

2. Implementation

Sorted array - a significant reminder to use binary search. This is O(logN) solution and use recursive implementation. Does this question remind you of something? Think about equal_range in STL.

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

// Implementation

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

#include <vector>

template <typename T>

void FindTheFirstOfGivenNumberInSortedArray(const std::vector<T>& sortedArray,

                                            const T& val,

                                            const long start,

                                            const long end,

                                            size_t& first)

{

    if (start > end) {

        return;

    }

    const size_t mid = (start + end) >> 1;

    auto iter = sortedArray.begin();

    if (*(iter + mid) == val) {

        // special case: hit the beginning of the array

        // normal case: the left hand side has a smaller value

        // otherwise continue binary search

        if (mid == 0 || *(iter + mid - 1) < val) {

            first = mid;

        }

        else {

            FindTheFirstOfGivenNumberInSortedArray(sortedArray, 

                                                   val,

                                                   start,

                                                   mid - 1,

                                                   first);

        }

    }

    else {

        FindTheFirstOfGivenNumberInSortedArray(sortedArray,

                                               val,

                                               mid + 1,

                                               end,

                                               first);

    }

}

template <typename T>

void FindTheLastOfGivenNumberInSortedArray(const std::vector<T>& sortedArray,

                                           const T& val,

                                           const size_t arr_len,

                                           const long start,

                                           const long end,

                                           size_t& last)

{

    if (start > end) {

        return;

    }

    const size_t mid = (start + end) >> 1;

    auto iter = sortedArray.begin();

    if (*(iter + mid) == val) {

        // special case: hit the end of array

        // normal case: the right hand side has a larger value

        // otherwise continue with binary search

        if (mid == (arr_len - 1) || *(iter + mid + 1) > val) {

            last = mid;

        }

        else {

            FindTheLastOfGivenNumberInSortedArray(sortedArray,

                                                  val,

                                                  arr_len,

                                                  mid + 1,

                                                  end,

                                                  last);

        }

    }

    else {

        FindTheLastOfGivenNumberInSortedArray(sortedArray,

                                              val,

                                              arr_len,

                                              start,

                                              mid - 1,

                                              last);

    }

}

template <typename T>

bool FindTheFirstAndLastOfGivenNumberInSortedArray(const std::vector<T>& sortedArray,

                                                   const T& val,

                                                   const size_t arr_len,

                                                   const long start,

                                                   const long end,

                                                   size_t& first,

                                                   size_t& last)

{

    if (start > end) {

        // does not find the given value

        return false;

    }

    const size_t mid = (start + end) >> 1;

    auto iter = sortedArray.begin();

    if (*(iter + mid) == val)

    {

        // find the given value

        if (mid == 0 || *(iter + mid - 1) < val) {

            // hit the first occurrence

            first = mid;

        }

        else {

            // find the first occurrence in the left part of array

            FindTheFirstOfGivenNumberInSortedArray(sortedArray,

                                                   val,

                                                   start,

                                                   mid - 1,

                                                   first);

        }

        if (mid == (arr_len - 1) || *(iter + mid + 1) > val) {

            // hit the last occurrence

            last = mid;

        }

        else {

            // find the last occurrence in the right part of array

            FindTheLastOfGivenNumberInSortedArray(sortedArray,

                                                  val,

                                                  arr_len,

                                                  mid + 1,

                                                  end,

                                                  last);

        }

        return true;

    }

    else if (*(iter + mid) > val) {

        return FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,

                                                             val,

                                                             arr_len,

                                                             start,

                                                             mid - 1,

                                                             first,

                                                             last);

    }

    else

    {

        return FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,

                                                             val,

                                                             arr_len,

                                                             mid + 1,

                                                             end,

                                                             first,

                                                             last);

    }

}

template <typename T>

bool FindTheFirstAndLastOfGivenNumberInSortedArray(const std::vector<T>& sortedArray,

                                                   const T& val,

                                                   size_t& first,

                                                   size_t& last)

{

    if (sortedArray.empty()) {

        return false;

    }

    const size_t len = sortedArray.size();

    return FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,

                                                         val,

                                                         len,

                                                         0,

                                                         len - 1,

                                                         first,

                                                         last);

}

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

// Test

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

#include <cassert>

void TestFindTheFistAndLastOfGivenNumberInSortedArray()

{

    std::vector<int> sortedArray;

    size_t first, last;

    {

        assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,

                                                             1,

                                                             first,

                                                             last) == false);

    }

    {

        sortedArray = { 5 };

        assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,

            1,

            first,

            last) == false);

        assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,

            5,

            first,

            last) == true);

        assert(first == 0 && last == 0);

    }

    {

        sortedArray = { 5, 6 };

        assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,

                                                             5,

                                                             first,

                                                             last) == true);

        assert(first == 0 && last == 0);

        assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,

                                                             6,

                                                             first,

                                                             last) == true);

        assert(first == 1 && last == 1);

    }

    {

        sortedArray = { 5, 5, 5, 5, 5 };

        assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,

            5,

            first,

            last) == true);

        assert(first == 0 && last == 4);

        assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,

            6,

            first,

            last) == false);

    }

    {

        sortedArray = { 1, 2, 3, 5, 5, 5, 5, 5, 6, 7, 8 };

        assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,

            5,

            first,

            last) == true);

        assert(first == 3 && last == 7);

    }

}

Sort An Array with Three Distinct Numbers (Microsoft Interview Question)

1. Problem Description

This is a Microsoft interview question for software develop engineer from careercup. Here is the orignal thread,

"

Sort an array of 0s, 1s and 2s 

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

The problem is similar to http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

But they have added 1 trick into the question, You cannot use high = n;

It means don't calculate the length of array.

Can anyone help me in writing the code for this problem ?

- NoMind 10 days ago in India | Report Duplicate | Flag ".

2. Pseudo-code

The first idea popping into my head is to use the idea of quick sort. Use the mid value as the pivotal value to partition the array. But this will requires two traverse of the array. For instance,

    - pivotal value = 1, {2, 2, 2, 0, 0, 0, 1, 1, 1}

    - The first iteration: {1, 1, 1, 0, 0, 0, 2, 2, 2}

    - Then pick pivotal value = 0, on the left part {1, 1, 1, 0, 0, 0}

This process quires two traverses of the array. But the interviewers require only traversing the array only once.

My idea is to use the mid value as the pivotal value and start two partitions process as Example 1,

    - Partition 1: move the high value to the right

    - Partition 2: move the low value to the left

    - Start these two partitions process in the same traversing. 

Example 1

3. Implementation

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

// Implementation

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

#include <vector>

void SortArrayWith3DistinctNumbers(std::vector<int>& arr,

                                   const int low,

                                   const int mid,

                                   const int high)

{

    if (arr.empty()) {

        return;

    }

    const size_t len = arr.size();

    long posToHoldHigh = len - 1;

    while (posToHoldHigh >= 0 && arr[posToHoldHigh] == high) {

        --posToHoldHigh;

    }

    long posOfFirstOne = -1;

    for (long idx = 0; idx <= posToHoldHigh; ++idx) {

        if (arr[idx] == high) {

            // partition 1: move high (2) to the right

            arr[idx] = arr[posToHoldHigh];

            arr[posToHoldHigh] = high;

            while (posToHoldHigh >= 0 && arr[posToHoldHigh] == high) {

                --posToHoldHigh;

            }

        }

        if (arr[idx] == mid && posOfFirstOne < 0) {

            posOfFirstOne = idx;

        }

        if (arr[idx] == low && posOfFirstOne >= 0) {

            // partition 2: move low (0) to the left

            arr[idx] = mid;

            arr[posOfFirstOne] = low;

            ++posOfFirstOne;

        }

    }

}

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

// Test

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

#include <cassert>

void TestSortArrayWithThreeDistinctNumbers()

{

    std::vector<int> arr;

    SortArrayWith3DistinctNumbers(arr, 0, 1, 2);

    assert(arr.empty() == true);

    arr = { 2, 2, 2, 0, 0, 0, 1, 1, 1 };

    SortArrayWith3DistinctNumbers(arr, 0 , 1, 2);

    assert(arr == std::vector<int>({ 0, 0, 0, 1, 1, 1, 2, 2, 2 }));

    arr = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };

    SortArrayWith3DistinctNumbers(arr, 0, 1, 2);

    assert(arr == std::vector<int>({ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2 }));

}

BTS - Detect If Two Trees Have the Same Elements (Amazon Interview Question)

1. Problem Description
This originally an Amazon interview question for software development engineer from careercup. Here is the thread,
"

Given two Binary Trees (not BST). Each node of both trees has an integer value. Validate whether both trees have the same integers, there could be repetitive integers.
ex-
Tree1:
5
1 6
5 4 3 6

Tree2:
1
3 4
6 5
have identical integers.

- teli.vaibhav 21 days ago in United States | Report Duplicate | Flag "

2. Implementation
The idea is quite simple that it is to use hash table to take all the elements from the first tree and then check if the second tree has exactly same elements as in the hash table. There is no special about the algorithm but I am going to demonstrate how to use recursive (in some sort of function programming sense) functions to implement the solution. Because tree structure is a very good source to understand functional programming particularly in the sense of sub-problem.

// ********************************************************************************
// Implementation
// ********************************************************************************
#include <memory>
#include <queue>
#include <stack>
#include <vector>
#include <unordered_map>

template<typename T>
struct TreeNode
{
    TreeNode(const T& d)
    : data(new T(d)), left(nullptr), right(nullptr)
    {}
    ~TreeNode()
    {
        std::shared_ptr<T>().swap(data);
    }

    std::shared_ptr<T> data;
    TreeNode* left;
    TreeNode* right;
};

template<typename T>
void ConstructTreeRecursive(const std::vector<T>& input,
                                         int startIndex,
                                         int endIndex,
                                         TreeNode<T>** node)
{
    if (startIndex > endIndex) {
        *node = nullptr;
        return;
    }

    const int curIndex = (startIndex + endIndex) >> 1;
    *node = new TreeNode<T>(input[curIndex]);
    ConstructTreeRecursive(input,
                           startIndex,
                           curIndex - 1,
                           &(*node)->left);
    ConstructTreeRecursive(input,
                           curIndex + 1,
                           endIndex,
                           &(*node)->right);
}

template<typename T>
TreeNode<T>* ConstructTreeRecursive(const std::vector<T>& input)
{
    if (input.empty()) {
        return nullptr;
    }

    TreeNode<T>* root = nullptr;
    ConstructTreeRecursive(input, 0, input.size() - 1, &root);
    return root;
}

template<typename T>
void GetUniqueElementsOfTree(const TreeNode<T>* tree,
                             std::unordered_map<T, bool>& values)
{
    if (tree == nullptr) {
        return;
    }

    if (values.find(*tree->data) == values.end()) {
        values[*tree->data] = false;
    }

    GetUniqueElementsOfTree(tree->left, values);
    GetUniqueElementsOfTree(tree->right, values);
}

template<typename T>
bool CheckTreeAgainstValues(const TreeNode<T>* tree,
                            std::unordered_map<T, bool>& values)
{
    if (tree == nullptr) {
        // hit here, not exactly sure if two trees match
        // because the 2nd tree could have less elements
        // then have to go through the entire hash table
        // to check if any element missing in the 2nd tree
        return true;
    }

    if (values.find(*tree->data) == values.end()) {
       // if an element does not appear in the first tree,
       // then the answer is false.
        return false;
    }
    else {
       // An element appears in both trees.
        values[*tree->data] = true;
    }

    bool result = CheckTreeAgainstValues(tree->left, values);
    if (result) {
        // carry on to exhaust the rest of the 2nd tree
        result = CheckTreeAgainstValues(tree->right, values);
    }

    return result;
}

template<typename T>
bool CheckTwoTreesWithSameValues(const TreeNode<T>* left, const TreeNode<T>* right)
{
    using HashMap = std::unordered_map<T, bool>;
    HashMap leftValues;
    GetUniqueElementsOfTree(left, leftValues);

    if (CheckTreeAgainstValues(right, leftValues)) {
        // check if all the elements appear in the 2nd tree or not.
        auto iterEnd = leftValues.end();
        for (auto iter = leftValues.begin(); iter != iterEnd; ++iter)
        {
            if (!iter->second) {
                // an element missing in the 2nd tree
                return false;
            }
        }
        // two trees match
        return true;
    }
 
    // an element missing in the 1st tree
    return false;
}

// ********************************************************************************
// Test
// ********************************************************************************
void TestCasesOfCheckTwoTreesWithSameElements()
{
    const std::vector<int> testInput1 = { 1, 3, 5, 7, 2, 4, 6, 8 };
    auto tree1 = ConstructTreeRecursive(testInput1);
    assert(tree1 != nullptr);

    {
        TreeNode<int>* invalid1 = nullptr;
        TreeNode<int>* invalid2 = nullptr;

        assert(CheckTwoTreesWithSameValues(invalid1, invalid2) == true);
        assert(CheckTwoTreesWithSameValues(tree1, invalid2) == false);
        assert(CheckTwoTreesWithSameValues(invalid1, tree1) == false);
    }

    {
        const std::vector<int> testInput2 = { 1, 3, 5, 7, 2, 4, 6, 1, 5, 2, 4 };
        auto tree2 = ConstructTreeRecursive(testInput2);
        assert(tree2 != nullptr);
        assert(CheckTwoTreesWithSameValues(tree1, tree2) == false);
        DeleteTree(&tree2);
    }

    {
        const std::vector<int> testInput2 = { 1, 3, 5, 7, 2, 4, 6, 8, 1, 3, 5, 7, 2, 4, 6, 8 };
        auto tree2 = ConstructTreeRecursive(testInput2);
        assert(tree2 != nullptr);
        assert(CheckTwoTreesWithSameValues(tree1, tree2) == true);
        DeleteTree(&tree2);
    }

    {
        const std::vector<int> testInput2 = { 1, 3, 5, 7, 2, 4, 6, 8, 1, 3, 5, 7, 2, 4, 6, 8, 9 };
        auto tree2 = ConstructTreeRecursive(testInput2);
        assert(tree2 != nullptr);
        assert(CheckTwoTreesWithSameValues(tree1, tree2) == false);
        DeleteTree(&tree2);
    }

    DeleteTree(&tree1);
}

Data Structure and Algorithm - Find the Largest Number by Replacing One Array to Another (Microsoft Interview Question)

1. Problem Description
This is a Microsoft interview question for software develop engineer from careercup. Here is the original thread,
"

Given two arrays were digits of one array represent a number,maxmise the number by replacing it with elements of second array. 

eg:
arr={3,1,4,5,6}
rep={1,9,5,2,3}

after replacement
arr={9,5,4,5,6}
one digit of rep can be used to replace only once.

- ritwik_pandey 14 days ago in United States | Report Duplicate | Flag ".

2. Analysis
The idea is quite simple that replace top digit in arr with the largest number in rep if it's less, and then replace the second top digit in arr with the largest number in the remaining of rep, and then so on so forth. If the current digit in arr is larger than all the remaining of rep, then go to next digit.

This problem can be solved by borrow the idea of the merging step in the merge sort. Not the exactly same but the similar pointer operations in two arrays. Sort rep array in the descending order. Have two pointers pointing to the beginning of two arrays, arrPtr and repPtr. If the digit arrPtr points to is less than repPtr, then replace it and both pointer move forward by 1. If not, then arrPtr moves forward by 1 and repPtr stays.

Pseudo code:
1. Sort rep in the descending order as sortedRep
2. Two pointers points to arr and sortedRep as arrPtr and repPtr
3. Compare the value arrPtr points to with the value repPtr points to
    * If less, replace the value arrPtr points to with the value repPtr points to
       And move arrPtr and repPtr forward by 1
    * If not less, move attPtr forward by 1
4. Repeat Step 3 until either pointer reaches the end

Complexity:
O(n) + O(mlogm),
where n = sizeof(arr) and m = sizeof(rep)

3. Example

Example 1