News & Events
코딩 인터뷰 준비하기: 10가지 알고리즘
이 포스팅에서는 FAANG 인터뷰에 공통으로 출제되는 여러 기본 알고리즘에 대한 솔루션을 제시하고 공유한다.
왜 알고리즘인가?
만약 여러분이 파이썬에 비교적 익숙하지 않고 (FAANG이 포함된) 상위 기업들을 대상으로 인터뷰를 준비할 계획이라면, 명심하라: 당신은 지금 당장 알고리즘을 연습할 필요가 있다.
처음 문제를 풀기 시작했을 때처럼 순진하게 굴지 말자. 몇 가지 알고리즘을 푸는 것이 재미 있다고 생각 했음에도 불구하고, 필자는 연습하는 데 많은 시간을 쓰지 않았으며 더 빠르고 효율적인 솔루션을 구현하는 데는 더 적은 시간을 보냈다. 필자는 하루 종일 알고리즘을 푸는 것은 너무 지루하고 실제 업무 환경에서 실용적이지 않았으며 장기적으로 도움이 되지 않을 것이라 생각했었다.
“알고리즘을 해결하는 방법을 알면 구직 과정에서 경쟁력을 확보할 수 있다.”
필자는 틀렸었다. 여전히 다른 기술에 집중하지 않고 알고리즘에 너무 많은 시간을 쏟는 것만으로는 꿈의 직업을 가질 수 없다고 생각한다. 하지만 프로그래머로서 매일매일 복잡한 문제들이 나타나기 때문에, 대기업들은 후보자의 문제 해결력과 관심에 대한 통찰력을 모으기 위해 표준화된 과정을 찾아야 한다는 것을 안다. 세밀한 기술을 익혀야 해 유명하지 않은 기업도 비슷한 평가 방식을 채택하는 경향이 있기 때문에 알고리즘 해결 방법을 알면 구직 과정에서 경쟁 우위를 점할 수 있다는 의미다.
세상의 모든것이 있다
알고리즘을 좀 더 일관되게 풀기 시작한 지 얼마 지나지 않아 필자는 알고리즘을 연습하고, 이를 해결하기 위한 가장 효율적인 전략을 배우고, 면접을 준비할 수 있는 자원이 많다는 것을 알게 되었다(HackerRank, LeetCode, CodingBat, GeeksForGeeks 는 몇 가지 예시에 불과하다).
인터뷰 질문을 연습하면서, 이러한 웹사이트들은 종종 기업별로 알고리즘을 그룹화하고, 사람들의 인터뷰 경험에 대한 상세한 요약을 공유하는 블로그를 포함하며, 프리미엄 플랜의 일부로 모의 인터뷰 질문을 제공하기도 한다.
예를 들어 LeetCode를 사용하면 특정 회사 및 빈도별로 면접 질문을 필터링할 수 있다. 또한 난이도(쉬움, 중간 및 하드)를 선택할 수도 있다.
일반적인 패턴을 인식하고 10분 이내에 효율적인 솔루션을 코딩하려면 많은 시간과 노력이 필요하다.
“처음에는 힘들더라도 실망하지 말자. 완전히 정상적인 것이다.”
만약 당신이 처음에 문제를 풀기 위해 정말 고군분투한다면, 이것은 완전히 정상적이다. 경험이 더 많은 파이썬 프로그래머라면 적절한 교육 없이 단기간에 많은 알고리즘을 해결하기 어렵다는 것을 알게 될 것이다.
또한 면접이 예상대로 풀리지 않고 알고리즘을 이제 막 풀기 시작했더라도 실망하지 말자. 매일 몇 개씩 문제를 풀며 몇 달씩 준비하고 정기적으로 리허설을 한 뒤 면접에 참여하는 사람들이 있다.
아래에는 전화 코딩 면접에서 반복적으로 출제되는 10개의 알고리즘(주로 문자열 조작 및 배열)을 선택했다. 문제 수준은 평이하므로 초심자에게 적합할 것이다.
아래 솔루션은 구현 가능한 수많은 잠재적 솔루션 중 하나일 뿐이며 BF(“Brute Force”) 솔루션이기도 하다. 런타임과 사용된 메모리 사이의 올바른 균형을 찾기 위해 당신만의 버전을 자유롭게 코딩해보자.
문자열 조작
1. Reverse Integer
# Given an integer, return the integer with reversed digits.
# Note: The integer could be either positive or negative.
def solution(x):
string = str(x)
if string[0] == ‘-‘:
return int(‘-‘+string[:0:-1])
else:
return int(string[::-1])
print(solution(-231))
print(solution(345))
Output:
-132
543
슬라이싱 기술을 연습하는데 도움이 되는 워밍업 알고리즘이다. 하나 까다로운 부분은 정수가 음수인 경우를 고려하는 것이다. 이 문제를 여러 방면으로 보아왔지만, 이는 보통 더 복잡한 요구의 출발점이다.
2. 평균 단어 길이
# For a given sentence, return the average word length.
# Note: Remember to remove punctuation first.
sentence1 = “Hi all, my name is Tom…I am originally from Australia.”
sentence2 = “I need to work very hard to learn more about algorithms in Python!”
def solution(sentence):
for p in “!?’,;.”:
sentence = sentence.replace(p, ”)
words = sentence.split()
return round(sum(len(word) for word in words)/len(words),2)
print(solution(sentence1))
print(solution(sentence2))
Output:
4.2
4.08
Algorithms that require you to apply some simple calculations using strings are very common, therefore it is important to get familiar with methods like .replace() and .split()that in this case helped me removing the unwanted characters and create a list of words, the length of which can be easily measured and summed.
문자열을 사용하여 간단한 계산을 적용해야 하는 알고리즘은 매우 일반적이므로 .replace() 및 .split()와 같은 메소드에 익숙해지는 것이 중요하다. 이 경우 원하지 않는 문자를 제거하고 단어 리스트를 만들고 길이를 쉽게 측정하고 합할 수 있다.
3. Add Strings
# Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
# You must not use any built-in BigInteger library or convert the inputs to integer directly.
#Notes:
#Both num1 and num2 contains only digits 0-9.
#Both num1 and num2 does not contain any leading zero.
num1 = ‘364’
num2 = ‘1836’
# Approach 1:
def solution(num1,num2):
eval(num1) + eval(num2)
return str(eval(num1) + eval(num2))
print(solution(num1,num2))
#Approach2
#Given a string of length one, the ord() function returns an integer representing the Unicode code point of the character
#when the argument is a unicode object, or the value of the byte when the argument is an 8-bit string.
def solution(num1, num2):
n1, n2 = 0, 0
m1, m2 = 10**(len(num1)-1), 10**(len(num2)-1)
for i in num1:
n1 += (ord(i) – ord(“0”)) * m1
m1 = m1//10
for i in num2:
n2 += (ord(i) – ord(“0”)) * m2
m2 = m2//10
return str(n1 + n2)
print(solution(num1, num2))
Output:
2200
2200
첫 번째 접근법은 간결성과 문자열 기반 입력을 동적으로 평가하는 방법론을 사용하는 직관력, 두 번째 접근법은 문자의 유니코드 코드 포인트를 통해 두 문자열을 실제 숫자로 재구성하는 ord( ) 함수의 현명한 사용을 위한 방법이다. 굳이 둘 중 하나를 선택해야 한다면 첫 번째 접근법이 더 복잡해 보여서 두 번째 접근법을 택하겠지만, 좀 더 발전된 문자열 조작과 계산이 필요한 ‘중간’과 ‘하드’ 알고리즘을 풀 때 편리하다.
4. First Unique Character
# Given a string, find the first non-repeating character in it and return its index.
# If it doesn’t exist, return -1. # Note: all the input strings are already lowercase.
#Approach 1
def solution(s):
frequency = {}
for i in s:
if i not in frequency:
frequency[i] = 1
else:
frequency[i] +=1
for i in range(len(s)):
if frequency[s[i]] == 1:
return i
return -1
print(solution(‘alphabet’))
print(solution(‘barbados’))
print(solution(‘crunchy’))
print(‘###’)
#Approach 2
import collections
def solution(s):
# build hash map : character and how often it appears
count = collections.Counter(s) # <– gives back a dictionary with words occurrence count
#Counter({‘l’: 1, ‘e’: 3, ‘t’: 1, ‘c’: 1, ‘o’: 1, ‘d’: 1})
# find the index
for idx, ch in enumerate(s):
if count[ch] == 1:
return idx
return -1
print(solution(‘alphabet’))
print(solution(‘barbados’))
print(solution(‘crunchy’))
Output:
1
2
1
###
1
2
1
이 경우에는 두 가지 솔루션이 제공되어 있는데, 알고리즘을 처음 접하는 경우 첫 번째 접근 방식이 빈 딕셔너리에서 시작하여 간단한 카운터로 구축되기 때문에 조금 더 익숙해 보인다.
그러나 두 번째 접근 방식을 이해하는 것은 장기적으로 훨씬 더 도움이 될 것이다. 해당 알고리즘에서 필자가 직접 chars counter를 만드는 대신 단순히 collection.Counter(s)를 사용하고 range(len(s))을 보다 명쾌하게 지수를 식별할 수 있는 함수인 enumerate(s)로 대체했기 때문이다.
5. Valid Palindrome
# Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
# The string will only contain lowercase characters a-z.
s = ‘radkar’
def solution(s):
for i in range(len(s)):
t = s[:i] + s[i+1:]
if t == t[::-1]: return True
return s == s[::-1]
solution(s)
Output:
True
“Valid Palindrome” 문제는 고전적인 문제이고 아마도 여러 가지 방법으로 접하게 될 것이다. 이 경우, 최대 한 개의 문자를 제거하여 날씨를 확인하는 것이 과제이며, 문자열은 역방향 문자열과 일치한다. s = ‘radkar’ 함수가 ‘k’를 제외함으로써 True를 반환할 때, 우리는 팰린드롬인 단어 ‘radar’ 얻는다.
배열
6. Monotonic Array
# Given an array of integers, determine whether the array is monotonic or not.
A = [6, 5, 4, 4]
B = [1,1,1,3,3,4,3,2,4,2]
C = [1,1,2,3,7]
def solution(nums):
return (all(nums[i] <= nums[i + 1] for i in range(len(nums) – 1)) or
all(nums[i] >= nums[i + 1] for i in range(len(nums) – 1)))
print(solution(A))
print(solution(B))
print(solution(C))
Output:
True
False
True
자주 출제되는 또 다른 문제이며 제공된 솔루션은 원라이너로 작성할 수 있을 정도로 매우 명확하다. 배열이 단조 증가 또는 단조 감소인 경우에만 단조로운 배열이고 이를 평가하기 위해 위의 알고리즘은 반복 가능한 모든 항목이 참이면 True를 반환하는 all() 함수를 사용하고 그렇지 않으면 False를 반환한다. 반복 가능한 개체가 비어 있으면 all() 함수도 True를 반환한다.
7. Move Zeroes
#Given an array nums, write a function to move all zeroes to the end of it while maintaining the relative order of
#the non-zero elements.
array1 = [0,1,0,3,12]
array2 = [1,7,0,0,8,0,10,12,0,4]
def solution(nums):
for i in nums:
if 0 in nums:
nums.remove(0)
nums.append(0)
return nums
solution(array1)
solution(array2)
Output:
[1, 3, 12, 0, 0]
[1, 7, 8, 10, 12, 4, 0, 0, 0, 0]
배열을 사용할 경우 .remove() 및 .append() 메서드를 사용한다. 이 문제에서는 먼저 원래 배열에 속하는 각 0을 제거한 다음 끝에 동일한 배열에 추가하기 위해 사용했다.
8. Fill The Blanks
# Given an array containing None values fill in the None values with most recent
# non None value in the array
array1 = [1,None,2,3,None,None,5,None]
def solution(array):
valid = 0
res = []
for i in nums:
if i is not None:
res.append(i)
valid = i
else:
res.append(valid)
return res
solution(array1)
Output:
[1, 1, 2, 3, 3, 3, 5, 5]
필자 역시 실제 인터뷰에서 몇 번 이 문제를 접했다. 두 번 모두 솔루션에 엣지 케이스를 포함해야 했다(간단함을 위해 생략). 문서상으로는 이 알고리즘은 구축하기 쉽지만 for 루프와 if 문장으로 무엇을 달성하고자 하는지 명확히 해야 하며 None 값으로 작업하는 데 익숙해야 한다.
9. Matched & Mismatched Words
#Given two sentences, return an array that has the words that appear in one sentence and not
#the other and an array with the words in common.
sentence1 = ‘We are really pleased to meet you in our city’
sentence2 = ‘The city was hit by a really heavy storm’
def solution(sentence1, sentence2):
set1 = set(sentence1.split())
set2 = set(sentence2.split())
return sorted(list(set1^set2)), sorted(list(set1&set2)) # ^ A.symmetric_difference(B), & A.intersection(B)
print(solution(sentence1, sentence2))
Output:
([‘The’,’We’,’a’,’are’,’by’,’heavy’,’hit’,’in’,’meet’,’our’,
‘pleased’,’storm’,’to’,’was’,’you’],
[‘city’, ‘really’])
이 문제는 상당히 직관적이지만 이 알고리즘은 set() , intersection() or 과 symmetric_difference()or ^와 같은 매우 일반적인 집합 연산을 활용하므로 솔루션을 더욱 정교하게 만드는 데 매우 유용하다. 이러한 문제를 처음 접하는 경우 다음 문서를 확인하자.
10. Prime Numbers Array
# Given k numbers which are less than n, return the set of prime number among them
# Note: The task is to write a program to print all Prime numbers in an Interval.
# Definition: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
n = 35
def solution(n):
prime_nums = []
for num in range(n):
if num > 1: # all prime numbers are greater than 1
for i in range(2, num):
if (num % i) == 0: # if the modulus == 0 is means that the number can be divided by a number preceding it
break
else:
prime_nums.append(num)
return prime_nums
solution(n)
Output:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
필자는 또 다른 클래식한 문제로 이 섹션을 마무리하고 싶었다. 소수 정의와 계수 연산을 모두 잘 알고 있다면 range(n)를 루핑하는 솔루션을 쉽게 찾을 수 있다.
결론
해당 포스팅에서는 코딩 면접에서 자주 묻는 10가지 파이썬 알고리즘의 솔루션을 공유했다. 잘 알려진 기술 회사와의 인터뷰를 준비하는 경우 이 포스팅은 일반적인 알고리즘 패턴을 숙지한 다음 더 복잡한 질문으로 넘어갈 수 있는 좋은 출발점이 될 것이다. 또한 이 포스팅에 제시된 연습은 Leetcode와 GeekForGeeks에서 사용 가능한 문제에 대한 약간의 재해석이라는 점에 유의하자. 필자는 그 분야의 전문가와는 거리가 멀기 때문에 제시한 해결책은 그저 지시적인 해결책일 뿐이다.
번역 – 핀인사이트 인턴연구원 강지윤(shety0427@gmail.com)
원문 보러가기>
