19 months ago

Gigaliths 570

IIT Ropar

Job Link

Hacker rank Assessment with duration of 2 days

Question 1

Implementation based question involving finding suitable house rental prices based on some given square feet area. The algorithm was clearly described, and you just have to optimally implement the same using some relevant data structure.

Question 2

2. Maximum Path
Your goal is to find the maximum path value of viable paths in a pyramid. A viable path is one where you take at most one step to the left or right as you progress down the nodes of the pyramid. You must pass through every level. The total path value is the sum of the values in the nodes traversed by your path. The diagram below represents a simple 3-layer pyramid with 4 possible path :

In the above example, the correct answer is 7, which is achieved by the blue path. The black (1), red paths (5) and green (5) lines are represent viable paths, but do not achieve the highest value. Data will be presented to you as a 1D array of integers, so in the case of the above example, your function will receive an array [1, 3, -1, 3, 1, 5] as input and will be expected to produce the integer 7 asoutput

Question 3

You will be given a time series data of mercury levels in a river. There will be 20 missing points in the time series, and you have to effectively predict them with any suitable approach. The points were assigned based on the accuracy of the output of predicted mercury levels on the missing points.

7 months ago

Viraj Dhirajbhai Pansuriya • 10

Ahmedabad

Question 2: Maximum Path..

Intuition: 

you hvae to keep track of 2 variables : depth and side where from depth you can find starting node index at depth level and side will give us how much amount should we move at right side, 

Based on that you can find out index of node and use DP table to memoize. 

#include <bits/stdc++.h>
  using namespace std;
  #define ll long long
  
   unordered_map < long long , long long  > dp;  
  
  ll check(int depth  , int side , vector < int > & arr){
    
    int index = (depth)*(depth+1)/2; 
    index += side; 
    
    if(index >= arr.size()) {
      return 0; 
    }
    
    if(dp.find(index) != dp.end()) return dp[index]; 
    ll a = check(depth+1 , side , arr); 
    ll b = check(depth + 1 , side +1 ,  arr); 
    return  dp[index] =  max(a , b) + arr[index]; 
    
  }
  
  void solve(){
  
    ll n ; cin>>n ; 
    vector < int > arr(n); 
    for(int i = 0 ; i < n ; i++) cin>>arr[i]; 
    ll ans = check(0 , 0, arr) ; 
    cout<<ans<<endl; 
    
  }
  
  

  int main() {
    solve(); 
    return 0;
  }