[면접] Algorithm Mock Interview(라이브코딩) 멘토링 후기

[22.07.24]

- Review

이주람 멘토님의 개발자 성장 및 Mock Algorithm Interview에 대한 멘토링을 수강하였다.

처음에는 개발자 동기 부여 및 좋은 엔지니어가 되는 방법을 알려주셨고, 이후 두 차례에 걸쳐 문제를 풀이하며 조언을 해주셨다.

그 중 Mock Interview에 관한 부분만 후기를 작성하고자 한다.

 

Mock Interview란 훈련 목적으로 사용되는 면접의 에뮬레이션이다. 개발자를 뽑는 기업들 중에 해외 기업에서는 아주 많은 라이브코딩을 실행하고 있고, 국내에서도 유니콘 기업들과 유명한 IT 기업들은 라이브코딩에 인터뷰 일부를 할애한다.

실제로 코딩을 잘하는 것도 중요하지만, 이런 자리에서 원래 알던 것을 제대로 표현할 수 있어야 하기에 멘토링을 수강하였다.

 

문제 풀이는 algoexpert.io에서 진행하였고, 그 중 쉬운 문제 하나, 어려운 문제 하나로 진행하였다.

 

라이브 코딩의 평가 항목

- 알고리즘 수행 능력(시간,공간 복잡도, trade off, 자료구조)

- 코딩 능력(알고리즘 구현능력, 클린코드, 문제 푸는 중 보인다, follow-up)

- 문제 해결 능력(문제를 해결하기 위한 질문을 하는 것, 상태 질문, 엣지 케이스 질문, 작은 케이스부터 시작)

- 커뮤니케이션 능력(인터뷰어에게 자신이 무엇을 하는지 전달, 모든 코드에 이유가 있는지 설명)

 

라이브코딩 풀이

라이브코딩은 문제당 20~40분 정도 진행되었고, 최종 제출 시에 완성되지 않은 코드일 수도 있으나, 수정하지 않고 작성하겠습니다

(틀린 코드일 가능성 있습니다.)

 

1번째 질문(20분 소요)

https://www.algoexpert.io/questions/river-sizes

AlgoExpert | Ace the Coding Interviews

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define W 1005
#define H 1005

bool visited[W][H];

int dy[4] = {-1,0,1,0};
int dx[4] = {0,-1,0,1};

bool Safe(int y, int x){
  if(y > -1 && x > -1 && y < W && x < H){
    return true;
  }
  return false;
}

int find_flood_fill(const vector<vector<int>> & matrix, int y, int x){
	int ret = 1;
	visited[y][x] = true;
	
	for(int d = 0; d < 4; d++){
		int dY = y + dy[d];
		int dX = x + dx[d];

		if(Safe(dY,dX) && matrix[dY][dX] == 1 && !visited[dY][dX]){
			ret += find_flood_fill(matrix, dY,dX);
		}
	}

	return ret;
}

vector<int> riverSizes(vector<vector<int>> matrix) {
	vector<int> result;
	for(int i = 0; i < matrix.size(); i++){
		for(int j = 0; j < matrix[i].size(); j++){
			if(matrix[i][j] == 1 && !visited[i][j]){
				result.push_back(find_flood_fill(matrix,i,j));
			}
	}	 
}

  sort(result.begin(), result.end());
  return result;
}

간단한 플러드 필 문제입니다. bfs/dfs 두 가지 방식으로 풀 수 있는데 저는 dfs로 풀었는데, 지금 생각을 해보니 vector를 계속 호출할 수 있고 스택 문제도 발생할 수 있으니 현실적으로 bfs가 더 적합하다고 판단됩니다. 문제의 최대 사이즈가 주어지지 않으니 크기를 #define으로 설정해 변경할 수 있도록 하였고, Safe와 dy, dx를 사용해 안전검사와 방향을 지정해주었습니다. 어디서 나는지 모를 Segmentation 오류가 발생하여 제출은 하지 못하였지만 로직은 비슷한 것 같아 인터뷰에는 응할 수 있어 보입니다. 실제 인터뷰에서는 문제를 solve하지 못해도 로직을 적어낸다면 인터뷰에 응할 수 있다고 하니 알고리즘을 모르겠더라도 브루트포스로라도 해결해보려고 시도하는 편이 좋다고 합니다.

 

2번째 질문(40분 소요)

https://www.algoexpert.io/questions/max-profit-with-k-transactions

AlgoExpert | Ace the Coding Interviews

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

#define MAX_TRANSACTION 1000
#define MAX_DAY 100

int dp[MAX_TRANSACTION][MAX_DAY];

int maxProfitWithKTransactions(vector<int> prices, int k) {
  for(int i = 1; i <= k; i++){
      for(int j = 0; j < prices.size(); j++){
          dp[i][j] = (j == 0) ? dp[i-1][j] : max(dp[i][j-1], dp[i-1][j]);
          
          for(int k = j - 1; k >= 0; k--){
              if(prices[j] > prices[k]){
                  int compare = (k == 0) ? 0 : dp[i-1][k-1];
                  dp[i][j] = max(dp[i][j], compare + (prices[j] - prices[k]));
              }
              else
                  break;
          }
      }
  }
  
  return dp[k][prices.size() - 1];
}

짧은 시간내에 풀어내기에는 조금 어려운 dp문제입니다. 40분 정도가 소요되었고, 10분마다 힌트를 하나씩 주셨는데 실제 인터뷰에서도 진전이 없으면 힌트를 주신다고 합니다. (인터뷰 진행을 위해서) 멘토님께 최대 날짜의 범위와 차액의 데이터 범위를 여쭤보고 시작했고, 상수 지정 등은 크게 상관없다고 하셔서 38분정도 지났을 때 solve했습니다. 만약 손코딩으로 진행하거나 컴파일러에 제출할 수 없었다면 solve하기 어려워보입니다. 멘토님도 이정도면 라이브코딩 문제에서는 상위권 문제라고 하셔서 이정도까지 완벽히 풀어내진 못해도 큰 지장은 없어 보입니다.

 

풀이과정도 본다고 합니다. 테스트 케이스 만들어보는게 중요!

2번 문제는 통과되었습니다

 

평가표

https://www.algoexpert.io/mock-interviews/feedback?id=fake_feedback_form

AlgoExpert | Ace the Coding Interviews

평가표입니다. 스스로를 판단해보는 시간을 가졌습니다.

 

추가적인 TIPS

- 진짜 확신이 없을 때 다 해결한 것 같다고 면접관에게 말하지 않기 (오류가 날 경우 감점사유)

- 문제에 대한 질문을 많이해야 한다.

- edge 케이스를 찾아내는 걸 좋아한다.(예외처리)

- 한 번에 끝까지 푸는 것이 아닌 천천히 올라가야한다.

- Step을 분류해서 인터뷰를 내므로 신중하게 파악해야한다 

1. 시작점에서 끝점까지 도달가능한가?
2. 그 경로를 나타낼 수 있는가?
3. weight가 있다면 최단경로는?

- 테스트 케이스는 실제로 코드로 짜는 것이 아닌 손과 텍스트를 이용해서 입증하는 것을 좋게 본다

- 작성하려고 하는 solution을 대략적으로 설명 가능해야한다.