Software Engineer Interview Questions Part-1

/*
1. Given an array which is in ascending order till some point and then descending order till end. find peak element

*/
Solution 1 :
#include <bits/stdc++.h>
using namespace std;

int peak_value(vector<int>a, int start, int end){
    if (start==end)  return a[start];
    if(start>end) return 0;
    int mid=(start+end)/2;
    if(a[mid]<a[mid+1]){
       return peak_value(a,mid+1, end);
    }else if(a[mid]>a[mid+1]){
        if((mid-1)>=0){
            if(a[mid-1]>a[mid]){
                return peak_value(a, start, mid-1);
            }else{
                return a[mid];
            }
        }else{
            return a[mid];
        }
    }
}

int find_the_peak_value(vector<int> a){
    if(a.size()==0){
        return 0;
    }else{
        cout<<"calling first peak_value function"<<endl;
        return (peak_value(a, 0, a.size()-1) );
    }
}

int main(){
    static const int arr[] = {1,2,3,4,5,3,1};
    vector<int> vec (arr, arr + sizeof(arr) / sizeof(arr[0]) );
    cout<<find_the_peak_value(vec);
    return 0;
}

/*
Problem 2 
Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature.
[73, 74, 75, 71, 70, 76, 72] -> [1, 1, 3, 2, 1, nothing, nothing]
November 22, 2017  
*/
Solution 2::

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> T={73, 74, 75, 71, 70, 76, 72};
    vector<int> wait_time(T.size());

    wait_time[wait_time.size()-1]=0;
    for(int i=wait_time.size()-2; i>=0; i--){
        if(T[i]<T[i+1]){
            wait_time[i]=1;
        }else{
            if(wait_time[i+1]==0){
                wait_time[i]=0;
            }else{
                wait_time[i]=wait_time[i+1]+1;
            }
        }
    }
    for(auto it=wait_time.begin();it!=wait_time.end();it++){
        cout<<*it<<" ";
    }
    return 0;
}

/*
Problem 3 :
You have given height array of array. Generate the original array.

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

A[i] value in input array is the number of greater element on right side.
November 20, 2017
*/

Solution 3:

Here is the logic behind the question:

The given input has size 7 so you have to fill each position by picking one element from array [1,2,3,4,5,6,7]. Now the given height array of array is [6,3,0,2,2,0,0]. Here first height is 6 it means that 6 elements must be greater than the picking element. So we every time pick the (A[i]+1)th greatest element from the remaining array of [1,2,3,4,5,6,7].

For 1st position A[i] is 6. So pick 7th greatest element that is 1. Remaining array [2,3,4,5,6,7].
For 2nd position A[i] is 3. So pick 4th greatest element that is 4. remaining array [2,3,5,6,7].
For 3rd position A[i] is 0 so pick 1st greatest element that is 7. remaining array [2,3,5,6].
Similar process will run until we fill the all position.

If you use an array, it's O(n^2) time due to the remove operation that copies n/2 elements worst case average.
If you use a tree, (sorted map, red black tree etc) you can get away with O(n*lg(n)) time.

#include <bits/stdc++.h>
using namespace std;
vector<int> generate(const vector<int> &in) {

int s = in.size();
vector<int> out(s+1);
vector<int> inserted;

for(int i = 1; i <= s; i++)
inserted.push_back(i);

    int curRemain = s-1;
for(int i = 1; i <= s; i++)
{
    int small = curRemain - in[i-1];
    out[i]=inserted[small];
    inserted.erase(inserted.begin()+small);
    curRemain--;
}
out.erase(out.begin());
return out;
}
int main(){
    vector <int> cool={6,3,0,2,2,0,0};
    vector<int> str_vec = generate(cool);
     for(auto it = str_vec.begin(); it != str_vec.end(); it++) {
         cout << *it << " ";
     }
    return 0;
}

 Keep following the Blog for more posts like these to improve Algorithms , Competitive Programming and for Interview Preparations . Happy Coding !!
You can see my potfolio here