Thank you very much for posting this video! It is such great insight for those of us with zero experience to try and understand what will be expected at entry level. Special thanks to Eric for representing as well.

Well, now I feel a lot better after seeing this mock int. Thanks a lot!

As he was hinting at with the circle. The most efficient way is to shuffle the list and then have everyone give to their right. So after shuffling, create a hat dict and and do an enumerate loop through the shuffled players to assign key values. We then need to loop through hat and assign keys and values to an output dict in a circular manner (ie wrapping around when the end of the player list is reached). For anyone interested, see below. import random def go(players): random.shuffle(players) hat = {} for key, player in enumerate(players, start=1): hat[key] = player secret_santa = {} for player_key in hat: secret_santa[hat[player_key]] = hat[(player_key % len(players)) + 1] return secret_santa print(go(players))

Appreciate your interview series, they are so informative! I was just coding along with the interview and created a O(N) stack based solution. I'll paste it here in case anyone is curious about one approach to the initial problem. import random ''' Solution Steps: 1. Create a stack for players 2. Iterate through players and randomly select pairs 3. Pop each respective player off the players stack after appending to temp list 3. Append temp pair list to result matches list 4. Once stack is empty then return result matches list Note: players list provided is should probably be even if everyone has a pair ''' def go(players): result_matches = [] while(len(players) >= 2): # Get first player temp_match = [] player_one_index = random.randint(0, len(players) - 1) temp_match.append(players[player_one_index]) players.pop(player_one_index) # Get second player player_two_index = random.randint(0, len(players) - 1) temp_match.append(players[player_two_index]) players.pop(player_two_index) # Append first and second player to temp list result_matches.append(temp_match) return result_matches players = ["Fred", "Wilma", "Barney", "Pebbles", "Bam Bam", "Kevin"] santas = go(players) print(santas)

@ACROSSOVER123

2 жыл бұрын

I like this one alot. It seems simple but does it still work if the amount of players are an odd number. I dont want to seem like im critiquing because I have no real world coding experience but I was just curious

@EvgeniyaJZ

Жыл бұрын

I think it doesn't work because the result is [['Barney', 'Kevin'], ['Wilma', 'Bam Bam'], ['Pebbles', 'Fred']]. Means Barney gives to Kevin, Wilma to Bam Bam and Pebbles to Fred. But then, who do Kevin, Bam Bam and Fred give to? Since it should be random, Kevin can't give to Barney, Bam Bam to Wilma and Fred to Pebbles I would assume.

@lawia8369

Жыл бұрын

wrong solution

@jonformantes4910

Жыл бұрын

The issue is that you're popping two players. This is initially what I wrote and was like wow so easy. Then realized in actual secret santa, you can't remove both people. If you remove player_one_index, they are no longer able to receive either. You would need to have a copy of the player list. So you can remove people from a givers/receivers. You would also need to check to make sure that the first index doesnt produce the same person from the second list. I haven't finished it. But your soln would leave an individual alone. That doesn't make sense for actual secret santa

Thank You so much for posting the video. It has been very helpful to me.

I stopped the video and answered the question for myself, I saw the "bam bam issue" crop up and solved it, then hearing Scott say that most people got tripped up on that at 56:40 made me super excited that I solved the problem well.

from random import shuffle def do(players): ''' By shuffling the players, the list is now in random order. Therefore, the player following any position is also in random order ''' shuffle(players) # randomize the players return [ [g,r] for g,r in zip(players, players[1:]+players[0:1])] players = ["Fred", "Wilma", "Barney", "Pebbles", "Bam Bam"] santas = do(players) print(santas)

This was cool to see. Props to him

Thanks man i was looking for back end interview

@DonTheDeveloper

2 жыл бұрын

I got you

These are great! Props to Eric for having the guts to put himself out there

@jokubasto

11 ай бұрын

Ti😮l😅😅8m🎉g.i Mmlm5kj😮😂

@jokubasto

11 ай бұрын

7

@jokubasto

11 ай бұрын

Lqp9i6😅7i

I paused the video to try it out and this was my approach import random def go(players): results = {} givers = random.sample(players, k=3) receivers = [p for p in players if p not in givers] for idx, giver in enumerate(givers): results[giver] = receivers[idx] return results players = [ 'Fred', 'Wilma', 'Barney', 'Pebbles', 'Betty', 'Bam bam' ] santas = go(players) print(santas)

Great video! Props to Eric for doing it live and recorded!

Guys, always talk through solution and discuss time/space tradeoffs BEFORE implementing code

Always hard to be on the spot :). From a 20+ year career C# guy I did this exercise in C# with a recursive method, always elegant.

Here's my solution with big O time complexity of O(n): import random def random_pairer(peeps): random.shuffle(peeps) pairs=[] for i in range(len(peeps)): if i==len(peeps)-1: pairs.append([peeps[i],peeps[0]]) else: pairs.append([peeps[i],peeps[i+1]]) return pairs

That's a very patient interviewer. Is this interview for an backend python developer internship or a job interview? I have never had the experience of having such a patient interviewer... I mean, there is usually a time component attached to solving each problem.

Everyone receives the gift once and everyone gives out the gift once -> The graph only has 1 indegree and 1 out degree -> Must be a cycle of length(list). So just pick random permutation and print all the pairs. [A, ,B, C, D] -> randomize to [B, D, A, C] -> print out [[B,D], [D, A], [A,C], [C, B]]

@KabeloMoiloa

Жыл бұрын

basically this is what i came up with first. if this is how easy coding interviews are then maybe i should consider it.

@WhiteSharkconcac

Жыл бұрын

@@KabeloMoiloa Well it's easy to you then maybe you are good at this stuff. Try picking up programming and apply for SWE jobs. As you can see from the video, only 2 people out of hundred applicants got this question right. That means it's not intuitive to most people.

@enriqueferreira4882

Жыл бұрын

yes, the first think I visualize is the graph being a full cycle, the rest is pretty straightforward

@antoinenijhuis450

3 ай бұрын

Why does it have to be a cycle? Can't we have A->B, B->A, C->D, D->C for instance?

Here you go: from random import shuffle players = ["Fred", "Barney", "Wilma", "Pebles", "Bam Bam"] n = len(players) shuffle(players) for i, j in zip(range(0, n), range(-1, n - 1)): print(players[i], "gifts", players[j]) ------- I guess the takeaway is to always try and fix the problem as far up in the code as possible. If you start by randomizing where each player sits in the circle, everybody can just give a present to the one sitting to their left. This aproach also avoid invalid configurations where the last person can only give to himself: 1 -> 2 2 -> 1 3 -> Oh no To avoid this problem you need a special rule running in the second to last iteration that gifts to the last person if possible although that skews the randomness a bit. If that's nok OK you could do a random swap of pairs. Oh and _do_ take a piece of paper and play around with dot's and arrows on it. It really helps with understanding the root causes of the problem.

@runekg

2 жыл бұрын

That solution is a bit more tricky. A takeaway is that a lot of the gnarly index lookups, while True loops and of-by-on errors can be avoided by using set operations. It goes like this: from random import choice players = ["Fred", "Barney", "Wilma", "Pebles", "Bam Bam"] gifted = {} received = {} left = set(players) for giver in players: candidates = left - {giver} if not candidates: # We are on Bam Bam and he has no one to give his gift to. Swap random pairs. p1 = choice(players[:-1]) # Random player that isn't Bam Bam gifted[giver] = p1 # Make Bam Bam give to that player gifted[received[p1]] = giver # Make the giver to random player give to Bam Bam instead break # We are done. receiver = choice(list(candidates)) gifted[giver] = receiver received[receiver] = giver left.remove(receiver) for giver, receiver in gifted.items(): print(giver, "->", receiver)

@ChrisGraceComedy

Жыл бұрын

ahhhhh that circle idea is so good. I was trying to implement the "what if the second to last person..." factor. Here's your circle idea in ruby: def santa(players) shuffled_circle = players.shuffle gift_list = Hash.new shuffled_circle.each_with_index do |x,idx| gift_list[x] = shuffled_circle[idx-1] end gift_list end muuuuuch simpler. thanks for this idea!

@axeberge

Жыл бұрын

I also solved this as a digraph, however, i've realized it's not actually giving all the possible solutions, which i think we want. In particular we are leaving out all solutions with symmetric gift givings. E.g. Fred --> Barney, Barney --> Fred, Wilma --> Pebles, Pebles --> Bam Bam, Bam Bam --> Wilma.

import random def go(players): output = [] random.shuffle(players) for i, player in enumerate(players): snd = (i + 1) % len(players) output.append([player, players[snd]]) return output

I feel like this was way over thought. Shuffle the list, enumerate it assigning n to n+1, wrap the last person to the first person. from random import shuffle people=['fred','wilma','barney','bam bam','betty'] shuffle(people) s=[people[-1],people[0]] for i,v in enumerate(people[:-1]): s.append([people[i],people[i+1]]) print(s)

This is a graph problem, example solution: def go(players: list[str]): res = [] prv_idx = random.randint(0, len(players)-1) prv_name = players.pop(prv_idx) first = prv_name while len(players) > 0: nxt_idx = random.randint(0, len(players)-1) nxt_name = players.pop(nxt_idx) res.append([prv_name, nxt_name]) prv_name = nxt_name last = nxt_name res.append([last, first]) return res ps. I'm looking for job :)

import random class Solution(object): def SpinBox(self, arr, index): # swap pairs in array till index n = len(arr) i = 0 while i arr[i], arr[n-1-i] = arr[n-1-i], arr[i] i += 1 return arr def method(self, magicBox): santa = [] count = len(magicBox) index = random.randint(0, count-1) randomBox = self.SpinBox(magicBox, index) for i in range(0, count, 2): santa.append([randomBox[i], randomBox[i+1]]) return santa

should you ask the interviewer if you want the brute force solution or an optimized one? also I know you should think about how youre going to solve the problem but would it be a red flag if you go on a solution that would not work because of a restriction and then realize later on, forcing you to rethink your solution? or should you have a clear cut solution and then figure how to implement on the way? which of the two are interviewers referring to when they say they want to see how candidates problem solve?

@prestonrasmussen1758

Жыл бұрын

Sometimes it can help to briefly describe the brute force solution as a junking off point to help understand where you can optimize. However, it is probably not worth it to code the brute force solution, unless the brute force solution is pretty close to optimal (which it can be in more complicated problems or recursion problems where the brute force solution itself is nontrivial). You should always describe your solution to your interviewer before programming. Think about this part as almost like a project planning session where the interviewer is a senior engineer collaborating with you. If your solution has pitfalls in the approach or is not optimal enough, the interviewer should push back and ask questions about certain edge cases that would break the solution (or ask you the Ru time of the solution and point out that it should be faster). You basically should never start programming until the interviewer approves your approach. I used to do interviews when I worked for a FAANG-like company, and in those interviews we had certain cutoffs for optimizations that if a solution didn’t meet that threshold it was as good as not having solved the problem at all. However, interviewers will make sure you describe a correct solution before asking you to code it. Interviewers will also help with hints if you get stuck and asking them clarifying questions is always a positive

have you done a front end version of this? if you haven’t can you?

@DonTheDeveloper

2 жыл бұрын

kzread.info/dash/bejne/qKOh16WGndK0qag.html

Is a degree required for backend engineering, or Is it possible to be self taught as a backend?

Nice video, but the biggest question I have is.... is the blonde guitar on the right an Epiphone? My Dad ha one just like it, many many years ago, but the resolution isn't good enough for me to read the name. :)

@anotheraleks

Жыл бұрын

looks like a Gibson

@anotheraleks

Жыл бұрын

my bad, was looking at the Les Paul

It s golang in his shirt, for that i ll watch the vid xd

I did it in 10 minutes Am I missing something?? def santa(list_of_people): output_list =[] temp_list = list_of_people random.shuffle(temp_list) while len(temp_list) > 0: for i in range(0, int(len(temp_list)/2)): temp_holder = temp_list[-2:] temp_list = temp_list[:-2] output_list.append(temp_holder) return output_list

I do not get Bam bam trick but here my code: why not just shuffle :D from random import shuffle def go(players): result = [] receivers = createShuffle(players[:]) givers = createShuffle(players[:]) print(receivers, givers) while not checkNotSame(receivers, givers): print("Not same") givers = createShuffle(players) result = [[i,j] for i, j in zip(receivers,givers)] return result def checkNotSame(list1, list2): for i,j in zip(list1,list2): if i==j: return False return True def createShuffle(playerslist): shuffle(playerslist) return playerslist players = ["Barney", "Fred", "Betty", "Wilma", "Bam bam"] print(go(players))

import random names: list[str] = [ "Fred", "Wilma", "Barney", "Boo Boo", "Pebbles" ] def get_pairings(names: list[str]): valid = False while not valid: shuffled = list(names) random.shuffle(shuffled) valid = not any(name == shuffled_name for name, shuffled_name in zip(names, shuffled)) return [[name, shuffled_name] for name, shuffled_name in zip(names, shuffled)] print(get_pairings(names))

For some reason your video isn't loading for me 😢

@DonTheDeveloper

Жыл бұрын

Weird! Unfortunately, I can't diagnose that from my end. Try viewing it on another browser or device.

function secrectSanta(players) { let receivers = players.slice(); let result = [] for (let i = 0; i let giver = players[i]; let isNotOK = true; let receiver = ''; while (isNotOK) { index = Math.floor(Math.random() * (receivers.length)); receiver = receivers[index]; if (giver !== receiver) isNotOK = false; } result.push([giver, receiver]); receivers.splice(receivers.indexOf(receiver), 1); } return result; } **Answered in JS

import random; def secret_santa(): seen = set() players = ['Fred', 'Wilma', 'Barney', 'Betty', 'Pebbles', 'Bam Bam'] result = [] for i, player in enumerate(players): j = pick_random(i, seen, len(players)) result.append([player, players[j]]) return result def pick_random(curr: int, set: set, length: int): rand = random.randrange(0, length) if rand != curr and rand not in set: set.add(rand) return rand else: return pick_random(curr, set, length)

How is this relevant to the actual real work? (It's not) And if this is relevant it means you only need to know basic programming.

I will post the code: players = { "luiz", "paulo", "maria" } def go(players): return ["xiaomi","iphone","sansung"] def friends(players): contx = 0 conty = 0 for x in players: contx = contx + 1 for y in go(players): conty = conty + 1 if(contx == conty): print(x+" presente: ", y) conty = 0 friends(players) print luiz presente: xiaomi paulo presente: iphone maria presente: sansung

My proposed code for the technical interview question: import random def go(lst): newlst1 = [] newlst2 = [] newlst3 = [] for a in lst: print(a) if len(newlst1) != 2: newlst1.append(a) elif len(newlst1) == 2 and len(newlst2) != 2: newlst2.append(a) else: newlst3.append(a) if len(newlst3) != 2: newlst3member = random.choice([newlst1[0],newlst2[0]]) print(newlst3member) newlst3.append(newlst3member) return [newlst1,newlst2,newlst3] player = ["Fred","Wilma","Berney","Pebbles","Bam Bam"] random.shuffle(player) print(go(player))

I tried it, came up with "not so optimized solution", using javascript: const players = ["Fred", "Wilma", "Barney", "Pebbles", "Bam Bam", "joy"]; const executePairing = (players) => { if (players.length % 2 !== 0) { console.log("Please input an even number of players"); return; } const array = players; const shuffledArray = array.sort((a, b) => 0.5 - Math.random()); let newPlayers = shuffledArray; let counter = newPlayers.length; let output = []; for (let i = 0; i ranNo = Math.random() * newPlayers.length; ranNo = Math.floor(ranNo); while (ranNo === 0) { ranNo = Math.random() * newPlayers.length; ranNo = Math.floor(ranNo); } output.push([newPlayers[0], newPlayers[ranNo]]); newPlayers.splice(ranNo, 1); newPlayers.splice(newPlayers[0], 1); } console.log(output); }; executePairing(players);

Here is my solution using a dict and sets, from my analysis the time complexity is O(n), can anyone tell me if that's correct? def go(players_list): import random if len(players_list) raise Exception('There has to be at least two people playing.') santas = {} for player in players_list: players_set = set(players_list) players_set.discard(player) #remove yourself from the set of people to receive gifts free_to_receive = list(players_set.difference(santas.values())) #leave only the ones that haven't received a gift yet #at this point it could be that everyone has given or received except you, and you can't #send a gift to urself if not len(free_to_receive): return [[giver, santas[giver]] for giver in santas] idx = random.randint(0, len(free_to_receive)) - 1 #random selection receiver = free_to_receive[idx] santas.update({player: receiver}) #add the gifter to the dict return [[giver, santas[giver]] for giver in santas]