The function of getting the winner at a given time
I want to discuss with smarter programmers this question, which was asked in a recent interview, walks you through my approaches and asks how you would effectively tackle this problem. Truly appreciate your ideas :)
Suppose you are given an array:
arr = [[sam,123],[ram,124],[kris,125],[hen,127],[kris,135], [sam,140],...]
where each cell represents the candidate's name and a timestamp (which increments and new entries are added continuously). This array can have millions of entries.
Write a function findWinner (arr, timestamp) that returns the name of the winner before this timestamp, the given timestamp may or may not be in the given array. For a tie "tie"
My approaches:
Approach 1:
a. Create a function voteCount(mydict, a) which takes an entry a and stores the count of each candidate in a dictionary and returns a dictionary say mydict
b. Create a function getMax(mydict) which takes the dictionary mydict created and sorts the dictionary with respect to values(count here), checks if there is a repeat (names) with respect to max as one edge case and print out "tie" or prints out the name of the max candidate
c. Create a function findWinner(arr, timestamp) which takes the input array arr, and a given timestamp and iterate through each entry in the array untill the given timestamp and take the name arr[i][0] and call voteCount(mydict, arr[i][0]) on it.
d. After the loop finishes run getMax on mydict and print out the results
I was thinking of memoization in this scenario because there was no space constraints
Approach 2:
a. Create a datastructure Node with a name and count like the one below:
class Node
attr_accessor :name, :count
def initialize(name,count)
@name = name
@count = count
end
end
b. In the getMax(mydict), take each key value pair as a node in a heap and run a max-heapify function with node.count and print out the root name(For edge case of tie, we can check with root left child and right child)
source to share
Create SortedMap<Integer, Set<String>>
(for example a red-black tree) where keys are timestamps and values ββare the names of the winners at that timestamp. Also create Map<String, Integer>
where keys are names and values ββare evaluations (initialized to zero). Then iterate over the array:
SortedMap<Integer, Set<String>> timestampMap = new RedBlackTree()
Map<String, Integer> scoreMap = new HashMap()
Set<String> currentWinners
foreach [name, timestamp] in array {
int currentNameScore = scoreMap.get(name) + 1
scoreMap.put(name, currentNameScore)
int currentWinnerScore = scoreMap.get(currentWinners.first())
if(currentWinners.contains(name) || currentNameScore > currentWinnerScore) {
currentWinners = new Set(name)
} else if(currentWinnerScore == currentNameScore) {
currentWinners = currentWinners.copy().add(name)
}
timestampMap.put(timestamp, currentWinners)
}
You use a Map
name to track each current score, then you determine if the score matches or exceeds the winner's current score. A query SortedMap
for a given timestamp (or immediately preceding timestamp if the given key is missing) is an O (log (n)) operation. (See example SortedMap for an example of typical operations on SortedMap
). Initialization SortedMap
is O (n * log (n)), so it makes sense to use this approach if you are doing multiple queries on the data (otherwise your linear search will be faster).
source to share