Microsoft SDE 1 | Oncampus | Codility | 6 Nov 2021
Anonymous User
465

This same question repeated
Q1)
https://leetcode.com/discuss/interview-question/645247/return-the-biggest-integer-of-values-in-a-path-of-length-four-in-a-matrix

 #include <bits/stdc++.h>
using namespace std;
int dfs(vector<vector<int>> &board, int i, int j, vector<vector<int>> &visited, int length){
    
    int n = board.size();
    int m = board[0].size();
    
    if(i<0 || i>=n || j<0 || j>=m || length==0 || visited[i][j] == 1)
        return 0;
    
    int ans = board[i][j]*pow(10, length-1);
    visited[i][j] = 1;
    int ret = ans;
    ret = max(ret, ans + dfs(board, i+1, j, visited, length-1));
    ret = max(ret, ans + dfs(board, i-1, j, visited, length-1));
    ret = max(ret, ans + dfs(board, i, j+1, visited, length-1));
    ret = max(ret, ans + dfs(board, i, j-1, visited, length-1));
    visited[i][j] = 0;
    return ret;
}
int solution(vector<vector<int>> &board){
    int n = board.size();
    int m = board[0].size();
    
     if(n==1){
	     int ans = 0;
	     for(int i=0; i+3<m; i++)
	        ans = max(ans, board[0][i]*1000 + board[0][i+1]*100 + board[0][i+2]*10 + board[0][i+3]);
	     for(int i=m-1; i>=3; i--)
	        ans = max(ans, board[0][i]*1000 + board[0][i-1]*100 + board[0][i-2]*10 + board[0][i-3]);
	    return ans;
	 }
	 if(m==1){
	     int ans = 0;
	     for(int i=0; i+3<n; i++)
	        ans = max(ans, board[i][0]*1000 + board[i+1][0]*100 + board[i+2][0]*10 + board[i+3][0]);
	     for(int i=n-1; i>=3; i--)
	        ans = max(ans, board[i][0]*1000 + board[i-1][0]*100 + board[i-2][0]*10 + board[i-3][0]);
	     return ans;
	 }
    
    int max_ele = 0;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            max_ele = max(max_ele, board[i][j]);
    
    int ans = 0;
    int length = 4;
    vector<vector<int>> visited(n, vector<int>(m, 0));
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++){
            if(board[i][j] == max_ele){
                int smallans = dfs(board, i, j, visited, length);
                ans = max(ans, smallans);
            }
        }
    return ans;
}
int main() {
	int n, m;
	cin>>n>>m;
	vector<vector<int>> board(n, vector<int>(m, 0));
	for(int i=0; i<n; i++)
	    for(int j=0; j<m; j++)
	        cin>>board[i][j];
	 
	 cout<<solution(board);
	return 0;
}

Q2) https://medium.com/beyond-programming/maximum-number-of-points-that-can-lie-inside-the-circle-algorithm-problem-of-the-week-ii-e75457414d32

Maximum number of points that can lie inside the circle

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

class Point{
    public:
        int x;
        int y;
        char s;
    Point(int _x,int _y,char _s){
        x=_x;
        y=_y;
        s=_s;
    }
    double distance(){
        return sqrt(x*x+y*y);
    }
    char getTag(){
        return s;
    }
};
  int solution(string S, vector<int> X, vector<int> Y) {
        vector<Point*> list;
        for (int i = 0; i < X.size(); i++) {
            Point *p= new Point(X[i], Y[i], S[i]);
            list.push_back(p);
        }

        sort(list.begin(),list.end(),[&](Point* &a,Point* &b){
            return a->distance()<b->distance();
        });
        map<char,Point*> m;
    
        for (int i = 0; i < list.size(); i++) {
            Point *point = list[i];
            if (m.find(point->getTag())!=m.end()) {
                Point *firstPoint = m[point->getTag()];
                return firstPoint->distance()== point->distance()? m.size() - 1 : m.size();
            } else 
                m[point->getTag()]=point;
        }

        return m.size();
    }

int main()
{
    string S="ABDCA";
    vector<int> X{2,-1,-4,-3,3},Y{2,-2,4,1,-3};
    cout<<solution(S,X,Y);
    return 0;
}
Comments (0)