C# mock interview practice on July 2 2020
July 2, 2020
911. Online Election
It is challenge to come out the idea how to solve the problem. I think that I should have worked on a simple test case first, so that I can come out the idea how to solve the problem quickly.
Case study
votes with person id = new int[]{1, 2}
vote with time = new int[]{0, 5}
votes with person id = new int[]{1, 2}
vote with time = new int[]{0, 5}
Explain the above example, at time 0, vote person with id = 1, at time 5 vote person with id = 2.
So at time 0, the votes are saved in personMap, key value pair is {0, 1};
timeMap has pairs of {{0, 1}}
at time 5, the votes are saved in personMap, key values pairs are {{0, 1}, {2, 1}}
timeMap has pair of {{0, 1}, {5, 2}}
timeMap has pairs of {{0, 1}}
at time 5, the votes are saved in personMap, key values pairs are {{0, 1}, {2, 1}}
timeMap has pair of {{0, 1}, {5, 2}}
Query time 3, so go through times table [0, 5], find the index position 1 since 5 > 3, we need to calculate the time 0 - how many votes for each person.
The idea is to go over each time, and then increment the current voted person with a new vote, and also update max voted person up to this time.
Use a variable to track maximum vote count and person Id.
Here are my highlights:
- Design two hashmaps personMap and timeMap
- One hashmap is to save intermediate data for each person, the value is count of votes; Let us call personMap.
- Second hashmap is to save current time and most voted latest person id;
- Also copy times array to help binary search time;
- Apply binary search using given time, the challenge part is to deal with negative index of the array return; bit flip operation using C# ~
Performance talk
I took extra time, and I did not learn that it can be simplified using two hashmap with Dictionary<int, int>, and I started to write structure like Dictionary<int, Tuple<int, int, int>>; After 20 minutes or so, I noticed that there is no need to keep lastIndex for each person's vote, also for each time every person vote count need to be saved.
I took extra time, and I did not learn that it can be simplified using two hashmap with Dictionary<int, int>, and I started to write structure like Dictionary<int, Tuple<int, int, int>>; After 20 minutes or so, I noticed that there is no need to keep lastIndex for each person's vote, also for each time every person vote count need to be saved.
Binary search algorithm is applied using C# interface Array.BinarySearch. I had to look up Google about negative index return and how to flip bits.
I spent over 60 minutes to solve the problem. Need to expedite problem solving. Need to solve more algorithms.
Leetcode mock interview has two algorithms. This one is the first one. It is medium level.
public class TopVotedCandidate {
private Dictionary<int, int> personMap;
private Dictionary<int, int> timeMap;
private int[] timesCopy;
public TopVotedCandidate(int[] persons, int[] times) {
if (persons == null || times == null || persons.Length == 0 ||
times.Length == 0)
return;
personMap = new Dictionary<int, int>();
timeMap = new Dictionary<int, int>();
// Each time,
var length = times.Length;
timesCopy = new int[length];
for (int i = 0; i < length; i++)
{
timesCopy[i] = times[i];
}
var maxPersonId = 0;
var maxCount = 0;
for (int i = 0; i < length; i++)
{
var personId = persons[i];
if (!personMap.ContainsKey(personId))
{
personMap.Add(personId, 0);
}
personMap[personId]++;
var currentCount = personMap[personId];
if (currentCount >= maxCount)
{
maxPersonId = personId;
maxCount = currentCount;
}
// Find person with more vote, last vote as well
timeMap.Add(times[i], maxPersonId);
}
}
// apply binary search
// challenge part is negative return - next large index's bit complement number
// Look up Google and find C# ~ flip bits operator
public int Q(int t) {
var index = Array.BinarySearch(timesCopy, t);
if (index >= 0)
{
var time = timesCopy[index];
if (timeMap.ContainsKey(time))
{
return timeMap[time];
}
}
else
{
var smaller = ~index - 1; // bit complement
var time2 = timesCopy[smaller];
return timeMap[time2];
}
return -1;
}
}
/**
- Your TopVotedCandidate object will be instantiated and called as such:
- TopVotedCandidate obj = new TopVotedCandidate(persons, times);
- int param_1 = obj.Q(t);
*/
