After the First Phone in discussion, I was asked to select few dates for the technical interview, I chosed 3. After cancelling and postponing the first one, finally i got the call from the technical interviewer.
The question was considerably easy. The first question is
You have a Election data stored in the array of objects and you need to find the leading candidates at a given timestamp.
The data is as follows:
votes = [{'candidate':'a', 'timestamp':2},{'candidate':'c', 'timestamp': 5},{'candidate':'c', 'timestamp': 12}]
timestamp = 5
Each of the above Array Elements contains the vote from a individual, the candidate is the person they voted for and the timestamp is the time at which it took place.
The Question is I need to write a method which will accept a timestamp and takes a array of votes, I need to return the leading candidate within that timestamp duration. I came up with the linear time solution, and its as follows.
def leading_candidate(votes, timestamp):
leading_candidate = ""
max_votes = 0
candidates = {}
for vote in votes:
if vote['timestamp'] <= timestamp:
if vote['candidate'] not in candidates:
candidates[vote['candidate']] = 1
else:
candidates[vote['candidate']] += 1
for candidate in candidates:
if candidates[candidate] > max_votes:
max_votes = candidates[candidate]
leading_candidate = candidate
return leading_candidate
The second question is to modify the same method to accept another field k , and it should return the first k leading candidates of the votecast at that particular timestamp, I came up with following solution,
def leading_candidates(votes, timestamp,k):
candidates = {}
leading_candidates = []
for vote in votes:
if vote['timestamp'] <= timestamp:
if vote['candidate'] not in candidates:
candidates[vote['candidate']] = 1
else:
candidates[vote['candidate']] += 1
sorted_votes = sorted(candidates.values())[:k]
for candidate in candidates:
if candidates[candidate] in sorted_votes:
leading_candidates.append(candidate)
return leading_candidates
print(leading_candidates(votes, timestamp, 2))As you can see the second solution has a time complexity of O(kn) where k is the time it takes to find the index in the leading candidates sorted array, In the worst case, it can be O(n^2) and because of sorting it may be at least O(nlogn).
Is there any way we can make it work with O(n)?