Python interview with a LinkedIn engineer: Matching pairs
ฝัง
- เผยแพร่เมื่อ 27 ส.ค. 2019
- Book a mock interview or coaching session with a LinkedIn engineer as early as tomorrow on interviewing.io! Sign up here: interviewing.io/signup
Check out the feedback by the LinkedIn interviewer and the full transcript on interviewing.io/recordings/Py...
Or view other Python interviews: interviewing.io/mocks
Disclaimer: All interviews are shared with explicit permission from the interviewer and the interviewee, and all interviews are anonymous. interviewing.io has the sole right to distribute this content. - วิทยาศาสตร์และเทคโนโลยี
![เกิดใหม่ทั้งทีก็เป็นสไลม์ไปซะแล้ว ซีซั่น 3 - ตอนที่ 65 [ซับไทย]](http://i.ytimg.com/vi/4EsinscQCfs/mqdefault.jpg)
Want to give it a shot?? Sign up with us to make sure your upcoming interviews are the best they can be by practicing with our experienced engineers. interviewing.io/signup?.com&
The interviewer said he was glad he tested for duplicates because it would of been poor performance if he didnt test for that, but @1:33, he saids you can assume their would be no duplicates in the list.
Yeah, the interviewer sucks here. Dinged interviewee for not thinking of duplicates before coding, though he explicitly asked about this. Also, duplicates were reintroduced by the interviewer leading interviewee astray. Interviewee was worried about double-counting a single entry in the list: {[1, 2, 4], 4} -> "2 and 2" and used {[2], 4} as an example. Interviewer latched onto this and suggested he could check for an input list with only one item in it. An absolutely stupid suggestion, which interviewee rightly ignored. But it moved the interviewee to implement the double-counting check as a duplicates check.
Here is my solution for this problem; No need for second loop:
def find_pair(values, target):
value_dict = {}
for value in values:
if (target - value) in value_dict:
return "{} and {}".format(target - value, value)
value_dict[value] = value
return "No Valid Pair"
If only real job interviews were this easy. It's always "code a solution to the cure for cancer with O(log n)
A slow, but space efficient solution
Def find_pair_sum(values, sum)
For i in range(len(values)):
For j in range(i, len(values)):
If (values[i] + values[j] == sum):
Return values[i], values[j]
Return None
Speed is of triangle numbers of N - 1, which is similar to (N(N-3))/2 at the longest, but only uses a few bytes of ram, for i and j. Not really proportional to N.
Boggless that’s how I’d solve it as well. I wonder what the interviewer would think
best solution :
1. use set (because the question didnt ask for the index, else you need to use a hashmap)
2. complete it in one iteration - O(n) by checking whether the complement exists in the set then and there.
java solution:
static int[] getMatchingPairs(int[] nums, int target){
HashSet set = new HashSet();
for(int num : nums){
int complement = target - num;
if(set.contains(complement)) return new int[] {complement, num};
set.add(num);
}
return new int[] {-1, -1};
}
waiting for the day when interviewers asks me such questions lol
Still conducting it in Python 2 I see! Can't say how pleased I am that we decided to move to 3.x sooner rather than later. So many interesting quirks with 2 but don't think it would be right for us to make any tutorials other than for 3 anymore!
Seeing xrange() always reminds me of Raymond Hettinger's account of how he improved Python by putting generators anywhere he could. Great guy and would definitely recommend any of his keynotes for inspiration for those preparing for any Python-heavy roles.
The interview was 3 years old. Look at the date at top middle. But yeah weird that they were still using python 2
Hettinger's talks are great! They made me always strive to make my code more succinct and clear. Now, I cringe when I see someone iterating over a list with 'for i in range(len(a))'
I am so happy this exists
t=[14,13,6,7,8,10,1,2]
target=3
cnt=0
for i in t:
if (i < target and cnt==0):
#find the pair that equals target
for pair in t:
tot=i + pair
if tot == target:
Print i, pair
cnt +=1
else:
break
Note that this is O(nsquared) complexity, while their answer is O(2n).
def find_pairs(values,target):
for num,x in enumerate(values):
if x > target:
pass
else:
solution = target - x
if solution in values[num+1:]:
return str(solution) + '&' + str(x)
return ('No pairs')
@@drocpdp
How about this:
def find(nums, target):
comp = { }
for num in nums:
try:
if comp[num] == num:
return [num, target - num]
except:
comp[target - num] = target - num
return []
time complexity O(log N)
worst case O(N) when no matching pairs
@13.55 that excitement when 'interviewer' finally 'understands' that -2 and says "its because 0 - 2 = -2 , True is 0" :( , man please in what language True is 0 man its 1 - 3
exactly
@@gsb22 I noticed that too. But in Bash 0 = Success
def pairs(nums, target):
for num in range(len(nums)):
if (target-nums[num]) in nums[num+1:]:
return(str(nums[num])+ " and " + str((target-nums[num])))
return("can't be done")
Hey, just started learning coding by myself, can you please walk me through your solution? It works very well and I would like to fully understand it.
This may throw index out of range
Just one for loop needed and I guess it'd be more efficient to exclude values > target.
def find_pair(values, target):
val_dict = {}
for val in values:
if val < target:
if val_dict.get(val) in values:
print(f"pairs found {val} {val_dict[val]}")
return 0
val_dict[val] = target - val
print("None found")
return 1
I had to sit and read this one but it is very clever!
The code could be really neat and short for this approach 😊
Tried this out
def check_sum(list_values,target_sum):
rem=list(map(lambda x:target_sum-x,list_values))
for i,x in enumerate(rem):
if x in list_values:
print("This two values are complimentary {} and {}".format(x,list_values[i]))
def getpairs(values, target):
for i in values:
target_diff = target - i
for j in values:
if target_diff == j:
return str(i) + " and " + str(j)
return "No valid pairs."
this won't be the best wrt to complexity isn't it
This is wrong, as it doesn't solve the duplicates issue. You are also using i and j to represent values in a list, when usually these refer to indicies. This also has slower time complexity than the solution shown in this video.
“Python is generally easy for interviews” you got that right. Lmao
This interviewer needs to stop eating...
Code for this question:
x=[12,14,8,6,1,2]
y=x
for i in x:
for j in y:
if i+j==3:
result=f"{i},{j}"
break
print(result)
You know you’re in the right career field when your interviewer’s name is admiral velociraptor😂
Unless those are generated names… hope they’re not
They're sorta generated. Part of our onboarding flow. But users get to cycle through them til they find one they like.
What a nice interviewer though, i've yet to actually get feedback from anyone when I ask.
I haven't gone through the whole video but thought of this solution.
def find_pairs(values, target):
pairs = {}
for index, x in enumerate(values):
if x not in pairs:
pairs[target-x] = x
else:
return [pairs[x], x]
return 'No Valid Pairs'
- Pairs will store (target-number) as the key and number of number as the value
Rest is easy to figure out.
After reading some comments I think we can improve your solution by using a set Instead :
def find_pairs(values, target):
complements = Set()
for x in values :
if x not in complements:
complements.add(target-x)
else:
return [x, target- x]
return 'No Valid Pairs'
Most optimal solution:
A single pass through the dataset, using a hash map. For each value, you check the compliment of the value against the target. If it exists in the hash map (O(1) lookup), you have you two values, if it doesn't exist in the hash map, add it to the hash map and move on to the next value.
def findMatch(self, dataset, target):
map = {}
for i, n in enumerate(dataset):
m = target - n
if m in map:
return [map[m], i]
else:
map[n] = i
you return the positions of the numbers in the dataset, not the numbers.
@@nmertsch8725 Good eye. Yea I chose to return back the index since I could then alter the dataset from there. However to your point, it should return what was asked. Simple change and the essence of the solution is the same.
map is a keyword in python, it should not be used as a variable name.
Also you don't need the self parameter since it is a function rather than a method.
def find_pair(number_array, targeted_sum):
for i in range(len(number_array) - 1):
for j in range(i + 1, len(number_array)):
if number_array[i] >= targeted_sum or number_array[j] >= targeted_sum:
continue
if (number_array[i] + number_array[j]) == targeted_sum:
return '%d and %d' % (number_array[i], number_array[j])
return 'No possible'
Literally just needed a extra check before the inner return to see if it's the same number
Is any way to improve this?
from itertools import combinations
def find_pairs (values , target):
if target > 1 and len(values) > 1:
comb = combinations(values, 2)
try:
print('{} and {}'.format(*next(filter(lambda x : sum(x) == target, comb)))))
except StopIteration:
print('None Found')
[1] and target = 2, will give "1 and 1" as a solution, which would be incorrect.
He fixed that. The {[2], 4} test case verifies this.
def find_pairs(a,target):
dic = {i: target-i for i in a if target-i>=0}
for i in dic.keys():
if dic[i] in dic:
return i,dic[i]
return 'no pairs'
How about this:
def find(nums, target):
comp = { }
for num in nums:
try:
if comp[num] == num:
return [num, target - num]
except:
comp[target - num] = target - num
return []
time complexity O(log N)
worst case O(N) when no matching pairs
how about this (nice, simple and short):
# Program to give valid pairs which add up to target
def get_pairs(nums, target):
sublist = list(filter(lambda x: x
The sub list is a nice optimization for a list containing a lot of large and therefore useless integers.
There is no need to incur a nlogn penalty for sorting your list, because you do not use the list being sorted to your advantage. You iterate through every possible pair. That approach will work regardless if the list is sorted.
If you're going to pay for the sort, you can utilize the sorted feature of the list to walk the sorted list using two pointers.
Additionally, your inner for loop will allow your algorithm to return an incorrect solution. For example, consider input [1,2,3,4] your algorithm will send [2,2] as the answer, which is incorrect. You can fix this problem by considering the information that iterate thru in your second loop.
Currently, your algorithm's time complexity is O(n + mlogm + m^2) where n is the length of the input list and m is the length of integers smaller than the target. The optimal time complexity in python is a pure O(n) solution where n is the length of the input list.
All that said, thank you for sharing :)
Why wouldn't you just use a set instead of a hash table? Better space complexity and constant lookup time
But Python sets and dictionaries are the same thing, hashtables.
The 2sum solution was truly horrendous. From the misspelled "complement" to using a dictionary as a set, to concatenating integers with strings, to using two loops when one would do, to returning a string that describes an exceptional situation. Sorry for the negative comment.
agreed
We really need the Simon Cowell of interviewers, just tell it like it is.
It’s helpful for the beginners amongst us
“Hello”
def find_pairs(values, target):
num_list = []
for value in values:
if value < target:
num_list.append(value)
for num in num_list:
for x in num_list:
if target == num + x:
return str(num) + " and " + str(x)
I guess I should have finished the video before finishing the code but hey, I am not interviewing.
Please change title to - Python interview with a LinkedIn engineer: Two Sum
Here's a javascript solution given there's no duplicates. Best O(log n) Worst O(n)
const findPairs = (values, target) => {
let possibleValue = {};
let matchedTuple = false;
for(let i = 0; i < values.length; i++ ){
const current = values[i];
if(current < target){
possibleValue = {
[current - 1]: current,
};
const match = possibleValue[current];
if(match) {
matchedTuple = [current, match];
break;
}
}
i++;
}
return matchedTuple || 'no matched pairs';
}
I am confused
How this is faster than a "nested for loop"?
""for tagert_compliment in val_dict"" --- The in operator also uses a for loop btw.
He wrote "if tagert_compliment in val_dict" which is O(1) due to hashing. In dicts, it is O(1), but lists are O(n). Dicts can be O(n), but that is for uncommon cases.
kinda surprised interviewer gave the 'hire' decision. The two sum problem is something that should take 5 min to code up per each of the two solutions (2 pointers / set or hash table if you need to return indexes) instead of 30 min for one
I was thinking to apply for jobs at LinkedIn. super easy interview 🤣
The interview is not about how to solve this problem. They want to know how he generally deals with problems, how he thinks about new tasks and how he acts if something does not work as intended. Also I doubt the hiring process only consisted of this one interview. He handed in a resume, possibly some code projects he worked at and other stuff.
Learning interview questions by heart is one thing, but the job does not consist of solving small problems, it is just a way to get to know him.
2 pointers doesn't work if the list isn't sorted. There wasn't any info to suggest the list would be sorted. best sorting algorithm is O(nlogn), making that approach bad.
My solution looks a bit abstract but still doing the task
def find_pairs(values, target):
pairs = []
if len(values) > 1:
[[pair.sort(), pairs.append(pair), print("{0} and {1}".format(pair[0], pair[1]))] for pair in [[(target-x), x] for x in values if (target-x) in values] if pair not in pairs]
else:
print("No valid pairs")
return pairs
my solution:
target_num = 9 # change target_num to whatever you want
list = [1, 10, 4, 5] # change numbers in list to whatever you want
def find_pair(temp, ind1):
ind2 = 0
for num in list:
if ind2 != ind1:
if num + temp == target_num:
print(f"#'s that add up to {target_num}: ( {temp}, {num} ) ")
return True
ind2 += 1
ind = 0
for num_ in list:
if find_pair(num_, ind) == True:
break
elif ind == len(list)-1:
print(f"No pairs add up to {target_num}");
ind += 1
#No need of dictionary. We can sort the list and iterate
#may be add one more step is to remove numbers that are already >=target from the list
def findPair(l,target):
l.sort()
for i,item in enumerate(l):
for j in range(i,len(l)):
if item + l[j] == target:
print (item,l[j])
l=[6,8,12,9,17,10,45]
target=21
findPair(l,target)
def find_pairs(elements, total):
seen = set()
for element in elements:
complement = total - element
if complement in seen:
# Assume stable ordering
return f"{complement} and {element}"
# adding while iterating reduces actual space,
# although does not affect time complexity
# adding after checking prevents elements being their own complement unless
# duplicate exists
# e.g. find_pairs([3], 6) should be "No valid pairs"
# find_pairs([3, 3], 6) should be "3 and 3"
seen.add(element)
return "No valid pairs"
absolutely. not sure why a second iteration was needed
dan the solution could have done much more easily, like looping through the array 2 levels and compare each some 2 values with the target, the store them in a array
If you loop twice over array, your time complexity will be n^2 and time complexity of one loop is O(n) and dictionary check is O(1)
I dont quite get why he chose python and then wrote code like that.
Hi,all.
Whar about
a = [14,13,6,7,8,10,1,2]
def foo(a,v):
dct = {}
[dct.update({x:v-x}) for x in a if x
arr = [14, 13, 6, 7, 8, 10, 1, 2 ]
target = 3
for i in arr:
for j in arr:
if j + i == target:
print(f'{i} and {j}')
break
This works right?
It works yeah, but it is not performance in time complexity because it is On^2. For small array would be okay. But not for millions data array
@@ricardoolartepuell2011 that's something I want to learn, data structures and algorithms, right? Do you know some good sources?
I am currently trying to learn too, with Colt Steve course at Udemy
Nice job!
The code was a bit more complicated than it should have been though. I'm not even sure I get their code, can someone explain?
Here's how I would do it.
def find_pairs(values, target):
if target > 1:
valuedict = set() #assume no duplicates (update: it still works with dups)
for value in values:
if target - value in valuedict:
return (value, target - value)
valuedict.add(value)
print('none found')
Exactly what I wrote. It's a lot simpler and also happens to be faster because the worst case time is n i think. He was layering a bunch of if statements after he committed to a sub optimal solution. I've also donr that many times lol.
Could somebody explain what they talk about at 4:22? Why and how is he optimizing for time? Thank you!
Using a HashSet makes looking up old values really fast, but creating the data structure takes up more space in memory. The opposite of this would be a brute force search of the array (ie use a nested for-loop to test every possible pair of ints in the array). This brute force method is much less efficient in terms of time, but more memory efficient because you don't have to create a HashSet to hold extra copies of the values.
In this case, because we're working with small sets of numbers and only doing one search, it sees silly to care about how much memory we're using. Making one HashSet to hold a set of 10 or less ints isn't strenuous for your machine. However, prospective employees are expected to handle enormous sets of data...if this array was millions of entries long and we had to handle thousands of similar arrays simultaneously, space complexity may matter more. The interviewer is just trying to see if the interviewee understand the tradeoffs between space and time efficiency.
@@davidadams255 I see, thanks for the in depth explanation!
@@ianchui Instead of doing what David said, if we were optimizing for space, you don't need to brute force it. You can sort the array which is a nlogn operation, and then from there use a two pointer approach to find your target. This would be O(1) space, and O(n) + O(nlogn) -> O(n log n) time
Good follow-up: if our element size is bounded we can use buckets to store freq and use that, linear time queries constant space proportional to element size window
this audio was pretty bad
def find_pairs(values, target):
for value in values:
pair = target - value
values.remove(value)
if pair in values:
return value,pair
values.append(value)
return "No Valid Pairs"
values.remove is an O(N) operation
def findpairs(n,m):
m=int(m)
start=0
end=0
n.sort()
matchfound=False
if len(n)
Found a simpler way to do it.
def find_pairs(values,target):
for x in values:
for e in values[1:-1]:
if x + e == target:
print(x,"and",e)
print(True)
else:
print("not valid")
x = find_pairs([14,13,6,7,8,10,1,2],3)
The criticism in the comments are ridiculous. The whole purpose of this is to practice, learn, get better, and gather feedback. This is why young software developers have a hard time because of the rude personalities that's in the area. Golden rule is to treat others the way you want to be treated. Let's not act like day one geniuses and have never improved in this line of work. smh
I'm new to software job interview + mock test, but is it true that the interviewer (person who hiring from the job/company), they positioned themself like as if they were a teammate/work colleague, so between a person who hire and candidate it's like they communicating to helping each other, and something like that?
so the person who hire is already have the answer/solutions of the problem given right ?
def find_pairs(arr, target):
d = {arr[i] : False for i in range(len(arr))}
ans = []
for num in arr:
reminder = target - num
if d[num] == False and reminder in d and num and num != reminder:
ans.append(f"{num} and {reminder}")
d[num] = True
d[target - num] = True
return ans if ans else "no valid pairs."
def matching_pairs(arr,target):
dict = {}
f = True
count = 0
for i in arr:
value = target - i
if value == target//2:
count += 1
if count > 1:
dict[value] = True
else:
dict[value] = True
for j in arr:
if j in dict:
f = False
return j,target-j
if f:
return "no valid pair exist !"
['{0} and {1}'.format(n, target - n) for n in values if target - n in values][0]
'Howboudat!'
Slow
It's good if values is a set at this point. Crashes with no answer, though.
"compliment" LOL
def find_pairs(values, target):
""" If any pair of values sums to target, return them """
for value in values:
if target-value in values and not (value*2)==target:
return (value, target-value)
Doesn't play nice with duplicates in the values tho.
its also extremely slow
the solution he found is extremely complicated and unecessary, this can be easily done with a double for interation, and then testing the sum of the numbers: for i in values:
for j in values:
if i+j==target:
list1.append(i)
list1.append(j)
a=sorted(set(list1))
list2.append(a)
list1.clear()
then wth a litlle tupple and sets adjustment, you can easily extract the numbers, without duplicates, i don;t understand why the long complicated coding, programers need to be simple and efficient.
@@nurgeldiguyzmuhammedov7829 it's most "efiicient" solution ( whatever that means), you don't have to use it, you can use your own expert solution
your solution is not efficient at all mate.
@@Corpsecreate yes it is
lol @ actually getting two sum in an interview
def solution(l,n):
for i in l :
if n-i in l:
return str(i) + " and " + str(n-i)
else :
return "none!"
I don’t understand why he is using dict[value] - target, (@ ; @) dict[value] = True which also = 1 and 1-3= -2 that’s why it’s constant -2 in print. It’s so easy and how could this question get fucked up....
This is why the industry gets a bad rep because of statements like this. Everyone learns and people make mistakes. Grow up
Typical hash map question. It can be solved with O(N) complexity.
can not believe he accepted using hash table, he just cut the corner, the actual answer is using sort then step through elements from start and end end to find the pair.
Leetcode easy problems for noobs 101.
Please don't watch it's not worth of watching because he spends 30 minutes on the most easiest coding problem that can be solved in 5 minutes and it will have much better space and time complexity and cleaner code.
Maybe what's important is the back in forth conversation not the code itself.
I found it interesting. my school never taught the application of hash tables. only the concept of them.
how could get better than O(n) for this? lol
@@shungu you can't. However he is right that this solution was absolute trash
@@pendragon7600 agreed! Was surprised the interviewer didn't ask him if he could get it down to O(n) instead of O(n + n) not that I wouldn't hire him for that. Although you can get this down to O(log n) best and O(n) worst
really ez with 2 pointers using 2sum method
2 pointer solution is not optimal for two sum with an unsorted list. Best solution is using a hashmap one pass.
@@aviralsaxena5153 sort then use 2sum
@@amirnuriev9092 Sorting is the reason why it is not optimal. Sorting itself is NlogN. The optimal solution in terms of run time is a one pass O(n).
@@aviralsaxena5153 well see i said ez which means simple and really easy to implement and it's efficient enough in almost every case
@@amirnuriev9092 Sure it may be easy, but the point is, for interviews, which is the only place this is used, no interviewer is going to accept a nlogn solution for two sum.
Rather confusing interview. We write python to literally provide micro services in numerous docker containers reading/writing to Qs/Topics/S3 buckets/Lambdas/FTP servers/RSDBs/plotting graphs and you spend this entire interview on find the sum of two numbers in a list?? This is a bash interview! If this was my interview I would fail it. If you asked me to write 1000 lines to contact a server reliably and download a terabyte of data, I am good.
Here's the dynamic solution. Took about 10 min.
target = 3
values = [14, 13, 6, 7, 8 , 10, 1, 2]
for x in range(0, len(values)):
testValue = values[x]
for y in range(0, len(values)):
valueToAdd = values[y]
if testValue + valueToAdd == target:
print("index" + str(x) + " and index " + str(y) + " add up to " + str(target))
else:
print("invalid match")
# you gief cookie now?
Yea, really easy question though
@@Alessandro-nq3tm I still finished mine faster than the interviewee! :P
Isnt that O(n^2) instead of O(n)?
This is a terrible solution lol it's literally brute force.
@@aviralsaxena5153 yes
shall not pass!
Content aside, I found the interviewee's talking style just a touch annoying, a bit overconfident. He never directly admitted to any mistake, always like, "yeah, yeah, I knew that". Personality is also (very) important to be accepted as part of a team.
This is literally Two Sums 😱 you need to study more my friend
First question on Leetcode :)
First question on Leetcode :)
lul here's my cheeky hacker way I solved it in about 30 sec. Dude never said anything about the data set being unpredictable...
target = 3
values = [14, 13, 6, 7, 8 , 10, 1, 2]
for x in range(0, len(values)):
test = values[x] + values[x+1]
if test == target:
print("sick, you found that index " + str(x) + " and " + str(x+1) + " add up to " + str(target))
break
else:
print("nah son...")
@@alizafar7080 thanks bro!
No, sorry.. Your code works for this one example, but not other examples because you're only comparing neighboring values, and "1" and "2" happen to be neighboring. Look at your loop. You check 14 + 13, then 13+6, then 6+7, then 7+8, etc. Therefore, your code breaks if you have a target of 3 and your input is simply [1, 99, 2]
@@stardreamse it also doesn't locate the nearest bagel house to me, but that wasn't asked for either.
@@chimerablack4913 Hey, it's been 4 months, hopefully, you've learned how to take constructive criticism maturely.
@@pescuaz who da fuck is that guy