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