[Daily Coding Problem] Problem #1 : Google Interview 문제

daily coding #1

This problem was recently asked by Google.

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

 

Bonus: Can you do this in one pass?

 

1. If the number of elements in the given list is small, I can use Brute Force Algorithm. Time complexity would be O(N^2)
리스트에 들어있는 원소의 사이즈가 작다면 Brute Force를 사용할 수 있을 것이다. O(N^2)

 

ls=[10,15,3,7]
k=17
f=False
for i in range(len(ls)):
    for j in range(len(ls)):
        if ls[i]+ls[j]==k:
            f=True
            break
    if f==True:
        print(True) 
        break

 

2.
If the number of elements in the given list is large, I can use HashSet. The average time complexity would be O(N), but the Worst time complexity would be O(N^2) as same as the Brute force algorithm.
사이즈가 크다면 HashSet을 이용할 수 있을 것이다. 평균 시간 복잡도는 O(N)이지만 최악은 O(N^2).

 

ls=[10,15,3,7]
k=17
Hashset=set(ls)#convert list to set / The data structure used in this is Hashing.
for i in ls:
    if k-i in Hashset:#Average time complexity of 'in' operator in set is O(1), Worst time complexity O(N)
        print(True)
        break

 

여러분도 Daily Coding Problem 문제를 풀어보고 싶다면 아래에 들어가서 신청하면 된다.

https://www.dailycodingproblem.com/ 

Daily Coding Problem