llamatatsu
BAN USERThis is an ideal case for an AVL tree implementation. Print the boundary values before rotation. Worst case complexity for insertion is O(logn).
(Surprised they asked this in an interview)
C#:
public class Node
{
public int val;
public List<Node> adjacent;
public Node(int val)
{
this.val = val;
this.adjacent = new List<Node>();
}
}
public void IsBipartite()
{
List<int> set1 = new List<int>();
List<int> set2 = new List<int>();
Node source = graph.First().Value;
if (IsBipartite(source, set1, set2, true))
{
Console.WriteLine("Graph is Bipartite");
}
else
{
Console.WriteLine("Graph is not Bipartite");
}
}
// Is Graph Bipartite
// For a graph to be bipartite; itshould have two sets of distinct vertices whose;
// Intersection is an empty set
// Union consists of all vertices in the Graph
// Create 2 Lists to represent this set
// Set sourceIsSet2 to true for the first/root node of the graph
public bool IsBipartite(Node current, List<int> set1, List<int> set2, bool sourceIsSet2)
{
// If the current node is already in set2 and source node was also in set2;
// return false else true
if (set2.Contains(current.val))
return sourceIsSet2 ? false : true;
// If the current node is already in set1 and source node was also in set2;
// return false else true
else if (set1.Contains(current.val))
return sourceIsSet2 ? true : false;
// If sourceIsSet2; add the current node to set1, else add it to set2
if (sourceIsSet2)
set1.Add(current.val);
else
set2.Add(current.val);
// Parse through all adjacent Nodes
foreach (Node adj in current.adjacent)
{
// If self directed, it's not a bipartite graph
if (current.val == adj.val)
{
return false;
}
// Quit execution only if a false condition is encountered, else propogate
if (!IsBipartite(adj, set1, set2, !sourceIsSet2))
return false;
}
return true;
}
Input:
n - number of lifespans
2D array [n, 2] with births and deaths
Algorithm:
1. Create hashtable<year, frequency> to hold population frequencies
2. Parse through lifespans - O(n)
2a. Insert frequencies in the Hashtable; +1 for births, -1 for deaths - O(1)
3. Sort Hashtable by year to compute running frequency - O(nlogn)
4. Parse through the Hashtable and find year with Max population - O(n)
Time complexity: O(nlogn)
Improvement:
Clearly sorting takes most amount of time here. Looking for a way to do this without sorting.
C# Code:
#region Find year with max population given Births and Deaths
public void MaxPopulationYear()
{
// Given a list of people with birth and death years
int[,] lifeSpan = { { 2000, 2010 },
{ 1975, 2005 },
{ 1975, 2003 },
{ 1803, 1809 },
{ 1750, 1869 },
{ 1840, 1935 },
{ 1803, 1921 },
{ 1894, 1921 }};
int[,] lifSpan = { { 1900, 1910 },
{ 1910, 1975 },
{ 1910, 1980 },
{ 1905, 1945 },
{ 1950, 1960 },
{ 1970, 1995 },
{ 1950, 1980 },
{ 1990, 1995 }};
MaxPopulationYear(lifeSpan);
MaxPopulationYear(lifSpan);
}
public void MaxPopulationYear(int[,] lifeSpan)
{
// Hashtable to hold value of Population by frequency
Dictionary<int, int> popFreqByYear = new Dictionary<int, int>();
// Loop through the lifespan to create the hashtable - O(p); p - people
for (int i = 0; i < lifeSpan.GetLength(0); i++)
{
UpdateFreq(popFreqByYear, lifeSpan[i, 0], 1);
UpdateFreq(popFreqByYear, lifeSpan[i, 1], -1);
}
int maxPopYear = GetMaxPopYear(popFreqByYear);
Console.WriteLine(maxPopYear);
}
private int GetMaxPopYear(Dictionary<int, int> popFreqByYear)
{
int maxPop = 0;
int maxPopYear = 0;
int currentPop = 0;
// Orderby is an implementation of stable quick sort = O(nlogn); O(pLogp)
// Foreach gros through the hash table p times; O(p)
foreach (var pop in popFreqByYear.OrderBy(o => o.Key))
{
currentPop += pop.Value;
if (maxPop < currentPop)
{
maxPop = currentPop;
maxPopYear = pop.Key;
}
}
return maxPopYear;
}
// Looks if value is present in Hashtable - O(1)
// Returns updates if present or updates it
private void UpdateFreq(Dictionary<int, int> popFreqByYear, int year, int update)
{
int value;
if (popFreqByYear.TryGetValue(year, out value))
{
popFreqByYear[year] = value + update;
return;
}
popFreqByYear[year] = update;
}
#endregion
I'm maintaining a Queue of all the elements in the window. I dequeue an old element and enqueue a new element to calculate the window sum.
There are 2 integers first and last that are used to identify the position of the subarray
private int MaxSubArray(int[] nums, int k)
{
int windowSum = 0, maxSum = 0; // For comparison of Maxsum
int first = 0, last = k-1; // Indexes of the max sum sub-array
Queue<int> numQueue = new Queue<int>(); // Elements in the window
// Generate sum of the first window
for (int i = 0; i < k; i++)
{
windowSum += nums[i];
numQueue.Enqueue(nums[i]);
}
maxSum = windowSum;
// Iterate through the rest of the array to find higher sum
for (int i = 1; i < nums.Length - k + 1; i++)
{
int deq = numQueue.Dequeue();
windowSum += nums[i + k - 1] - deq; // Sum of this window
numQueue.Enqueue(nums[i + k - 1]);
// If sum of this window is more than current maxSum
// then we have found a new max sum
if (windowSum > maxSum)
{
first = i;
last = i + k;
maxSum = windowSum;
}
}
return maxSum;
}
C#
- llamatatsu July 18, 2019