### 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

*/

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**
## Comments

## Post a Comment