LinkedIn Phone Screen Interview
Summary
I had a phone screen interview at LinkedIn where I was asked to implement a data structure for managing tickets with weighted random selection, requiring O(1) average time for all operations.
Full Experience
Hi, got an interesting question in Phone screen interview. Hopefully it will help someone. Trying to share the idea of the question. the actual language might be different in the question.
Linked has organised a fair. Based on some good action a linkedin member will be given 1 ticket. Based on some other bad action, a ticket will be taken from the member. Implement three methods addTicket(memberId) , removeTicket(memberId) and getRandom(). getRandom() should pick a member with weighted probability based on number of tickets a memeber has. Example if a member has 5 tickets and another one has 1 ticket, then the probability of the member with 5 tickets is higher than the one with 1 ticket. All 3 functions should be O(1) average case.
Its a variation of Insert Delete getRandom question
Hope it helps.
Interview Questions (1)
Weighted Random Selection with O(1) Operations
LinkedIn has organized a fair. Based on some good action, a LinkedIn member will be given 1 ticket. Based on some other bad action, a ticket will be taken from the member. Implement three methods: addTicket(memberId), removeTicket(memberId), and getRandom(). getRandom() should pick a member with weighted probability based on the number of tickets a member has. For example, if a member has 5 tickets and another one has 1 ticket, then the probability of the member with 5 tickets is higher than the one with 1 ticket. All 3 functions should be O(1) average case. This is a variation of the Insert Delete GetRandom O(1) question.