

Interview preparation kit, Searching

Ice Cream Parlor

• Thought: This problem is similar to this video, which serves as an example of google's interview. the only difference is we print the position of matched pairs, like pos_i and pos_j with criteria cost[pos_i] + cost[pos_j] equals to K There is no need for brute force in O(N^2), or binary search in O(NlogN), only need a map to store the occurances of each price.
• Analysis:
  • Time complexity: O(N), iterating the whole string and implement the statistical data
  • Space complexity: O(N), by using a map data to store the statistical data.

void whatFlavors(vector<int> cost, int money) 
{
    // init
    unordered_map<int, cost_data> mymap; // for statistical purpose of cost and its occurance
    int n = cost.size();
    for(int i = 0; i < n ; i++)
    {
        mymap[cost[i]].pos = i + 1;
        mymap[cost[i]].cnt++;
    }

    // iterate map process
    int cost_1 = 0, cost_2 = 0;
    for(int i = 0; i < n ; i++)
    {
        cost_1 = cost[i];
        cost_2 = money - cost_1;
        if(cost_2 == cost_1) // should be exisiting exactly 2, ex : 2 + 2 = 4 for unique solution
        {
            if(mymap[cost_1].cnt == 2) 
            {
                printf("%d %d\n", i + 1, mymap[cost_1].pos); // 1-base
                return;
            }
        }
        else
        {
            if(mymap[cost_2].cnt == 1) //exists for the other cost
            {
                printf("%d %d\n", i + 1, mymap[cost_2].pos);  // 1-base
                return;
            }
        }
    }
}

Pairs

• Thought: Similar to the first problem in this page, use map to check the occurance will be fine, solve in linear time and there is no need for brute force solution
• Analysis:
  • Time complexity: O(N), iterating the whole string and implement the statistical data
  • Space complexity: O(N), by using a map data to store the statistical data.

int pairs(int k, vector<int> arr) 
{
    int res = 0, n = arr.size();
    unordered_map<int, int> mymap;
    for(int i = 0; i < n; i++)
    {
        mymap[arr[i]]++;
    }

    for(int i = 0 ; i < n; i++)
    {
        if(mymap[arr[i] - k] == 1) // all the elements are unique, directly check if occurance exists 1
        {
            res++;
        }
    }
    return res;
}