# 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)
```

```
+3

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) {
}
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).

+3

source

All Articles