Instantly share code, notes, and snippets.

Embed
What would you like to do?
using System;
using System.Collections.Generic;
using System.Linq;
using Xunit;
namespace Demo.LearnByDoing.Tests.RandomStuff.Glassdoor.Asana
{
/// <summary>
/// Reference: https://www.youtube.com/watch?v=eaYX0Ee0Kcg
/// MinHeap: https://www.youtube.com/watch?v=t0Cq6tVNRBA
/// </summary>
public class KClosePointsToOriginTest
{
[Fact]
public void TestHappyPath()
{
var points = new[]
{
(X: -2, Y: 4),
(X: 0, Y: -2),
(X: -1, Y: 0),
(X: 3, Y: 5),
(X: -2, Y: -3),
(X: 3, Y: 2),
};
var expected = new[]
{
(X: -2, Y: -3),
(X: -1, Y: 0),
(X: 0, Y: -2),
};
const int k = 3;
var actual = GetKClosestPointsToOrigin(k, points).ToList();
Assert.True(expected.SequenceEqual(actual));
}
private IEnumerable<(int, int)> GetKClosestPointsToOrigin(int k, (int X, int Y)[] points)
{
var pointToDistanceMap = BuildPointToDistanceMap(points);
var maxHeap = BuildMaxHeapMap(k, points);
for (int i = k; i < points.Length; i++)
{
// Replace the biggest with the current smallest
if (pointToDistanceMap[points[i]] < maxHeap.Peek().Distance)
{
maxHeap.Poll();
maxHeap.Add((points[i].X, points[i].Y, pointToDistanceMap[points[i]]));
}
}
while (maxHeap.HasItem())
{
var (x, y, _) = maxHeap.Poll();
yield return (x, y);
}
}
private Dictionary<(int, int), double> BuildPointToDistanceMap((int x, int y)[] points)
{
return points.ToDictionary(point => point, CalculateDistance);
}
private double CalculateDistance((int X, int Y) point) => Math.Sqrt(point.X * point.X + point.Y * point.Y);
private GenericMaxHeap<(int X, int Y, double Distance)> BuildMaxHeapMap(int k, (int X, int Y)[] points)
{
return points
.Take(k)
.Aggregate(new GenericMaxHeap<(int X, int Y, double Distance)>(new GenericMaxHeapComparer()),
(heap, point) =>
{
heap.Add((point.X, point.Y, CalculateDistance(point)));
return heap;
});
}
}
class GenericMaxHeapComparer: IComparer<(int X, int Y, double Distance)>
{
public int Compare((int X, int Y, double Distance) x, (int X, int Y, double Distance) y)
{
return (int) (x.Distance - y.Distance);
}
}
class GenericMaxHeap<T>
{
private T[] _items;
private int _capacity = 10;
private int _size;
private readonly IComparer<T> _comparer;
public GenericMaxHeap(IComparer<T> comparer)
{
_comparer = comparer;
_items = new T[_capacity];
}
public T Peek()
{
if (_size == 0) throw new ArgumentOutOfRangeException();
return _items[0];
}
public T Poll()
{
if (_size == 0) throw new ArgumentOutOfRangeException();
// move last item to the front and heapify down
var item = _items[0];
_items[0] = _items[_size - 1];
_size--;
HeapifyDown();
return item;
}
public bool HasItem() => _size > 0;
public void Add(T item)
{
EnsuareCapacity();
// Add it to the end and heapify up!
_items[_size] = item;
_size++;
HeapifyUp();
}
private void EnsuareCapacity()
{
if (_size < _capacity) return;
_capacity *= 2;
var items = new T[_capacity];
Array.Copy(_items, items, items.Length);
_items = items;
}
/// <summary>
/// Move the last item to as high as it can move up
/// </summary>
/// <remarks>
/// While there is a parent, which is less than the current item,
/// replace the parent with the current item by moving it up.
/// set the current index to that of the parent.
/// </remarks>
private void HeapifyUp()
{
var index = _size - 1;
while (HasParent(index) && _comparer.Compare(GetParentValue(index), _items[index]) < 0)
{
Swap(index, GetParentIndex(index));
index = GetParentIndex(index);
}
}
/// <summary>
/// Move the first item to as low as it can in the tree
/// </summary>
/// <remarks>
/// while the child exists (check left child only)
/// Get the larger child's index between Left & Right child
/// if the current item is bigger than the larger child's value, then break out of the loop
/// else swap the larger child with the current item
/// </remarks>
private void HeapifyDown()
{
var index = 0;
// Heap always starts from "left" child so no need to check for right child.
while (HasLeftChild(index))
{
int largestChildIndex = GetLeftChildIndex(index);
if (HasRightChild(index) && _comparer.Compare(GetRightChildValue(index), GetLeftChildValue(index)) < 0)
largestChildIndex = GetRightChildIndex(index);
if (_comparer.Compare(_items[index], _items[largestChildIndex]) < 0) break;
Swap(index, largestChildIndex);
index = largestChildIndex;
}
}
private bool HasParent(int childIndex) => GetParentIndex(childIndex) >= 0;
private bool HasLeftChild(int index) => GetLeftChildIndex(index) < _size;
private bool HasRightChild(int index) => GetRightChildIndex(index) < _size;
private int GetParentIndex(int childIndex) => (childIndex - 1) / 2;
private int GetLeftChildIndex(int index) => index * 2 + 1;
private int GetRightChildIndex(int index) => index * 2 + 2;
private T GetParentValue(int childIndex) => _items[GetParentIndex(childIndex)];
private T GetLeftChildValue(int index) => _items[GetLeftChildIndex(index)];
private T GetRightChildValue(int index) => _items[GetRightChildIndex(index)];
private void Swap(int index1, int index2) =>
(_items[index1], _items[index2]) = (_items[index2], _items[index1]);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment