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


1 answer


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

+3


source







All Articles