Trifacta – Alteryx : coding Interview Question

Got call from instahyre. Process took 1 week to schedule and conduct the interview
Round 1 :

1.) Given the array of length N with numbers from 1 to N , with possible missing number in between. Return the next missing number
eg : arr = [1,2,3,5,6,7,8,9,10] , output = 4
arr = [1 , 2 ,3 4, ,5,6,7,8,9,10] , output = 11
constant space

2.) N number of times Rotated sorted array. Return the number if present else -1

#include <iostream>
#include<vector>
using namespace std;

// 1 2 3 5 6 : 4
// 76 4 2 1  : 3

// 1 2 3 4  : 3
// 1 2 4 4  : 3
//3
// size of array  : 4 ,
// aray[4] :   
//
// 1 <= n;
//   


/*

  1 2 3 4 5 6 7

  3 4 5 6 7 1 2
   



*/

class Solution{
public :

    int binarySearch(vector<int> inputArr , int s , int e ,  int &searchNumber){
          int m;
          while(s < e){
            // 0 ,1 ,2 ,3 ,4
             //3 ,4 ,5 ,6 ,7 ,1, 2
                  m = s + (e-s)/2;
                  if(inputArr[m] == searchNumber){
                  return m;
                  }
                  if(inputArr[m] < searchNumber){
                    s = m+1;
                  }else{
                    e = m-1;
                  }

          }
    return s; 
    }


//3 ,4 ,5 ,6 ,7 ,1, 2


    int getPivot(vector<int> inputArr){
          int s = 0 , e = inputArr.size()-1 , m;
          while(s < e){
               m = s + (e-s)/2;
               if( m == s || m ==e || ( inputArr[m-1] > inputArr[m] && inputArr[m+1] > inputArr[m] ) ){
                 return m;
               }
               if(inputArr[m] > inputArr[e]){
                 s = m;
               }else{
                 e = m;
               }

          }
          return -1;
    }

    int searchNumber(vector<int> inputArr , int searchNumber){
      int s = 0 , e = inputArr.size()-1;
      
      if(){
      }
      
      int pivot = getPivot(inputArr);
//3 ,4 ,5 ,6 ,7 ,1, 2

//cout<<"pivot="<<pivot<<endl;

      if(inputArr[e] >= searchNumber){
        s = pivot;
      }else{
         e = pivot-1;
      }
      cout<<"..."<<s<<"...."<<e<<endl;
      int index =binarySearch(inputArr , s , e , searchNumber); 
      return inputArr[index] == searchNumber ? index : -1;

    }


    int getMissingNumber(vector<int> inputArr){
          
          int ans = inputArr.size()+1;



          for(int i = 0 ; i < inputArr.size() ; i++ ){

             if( abs(inputArr[i]) <= inputArr.size() ){
             
                  inputArr[abs(inputArr[i])-1] = -1 * abs(inputArr[inputArr[i]-1]);
             }
          }
//cout<<"done";
          

          for(int i = 0 ; i < inputArr.size() ; i++ ){

             if( inputArr[i] > 0){
                  ans = i+1;
                  break;
             }
          }

          return ans;
    
    }


} ;




// To execute C++, please define "int main()"
int main() {
   
   vector<int> inputArr{ 3 ,4 ,5 ,6 ,7 ,1, 2};
   Solution s;
   //cout<<s.getMissingNumber(inputArr);
  cout<<s.searchNumber(inputArr , 2);
  return 0;
}

Round 2. (System Design)

Design Package Manager like npm:
Functionality :
Package Uploader:
a.) One can uploade the package
b.) manage the versioning

Package Downloader
a.) any user can donwload the package
b.) search the package

given : 10 thounsands wirte on every 10 million downloads
storage & replication is managed by cloud team
How / what meta information to be stored ?
How / where (client side / server side) dependency packages will be resolved.
eg : deplendent page , aerospiike version > 3.0.0.0 ,
or aerospiike version > 3.0.0.0 & aerospiike <= 6.0
something like above cases

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
error

Enjoy this blog? Please spread the word :)

0
Would love your thoughts, please comment.x
()
x