Задача: Max Points on a Line
Гарачае сонца асвяціла спальню. Яркія прамяні прабеглі па твары старэйшага распрацоўніка Васіля. “Яшчэ пяць хвіліначак”, – хітрая надзея праслізнула ў галаве Васі, і ён расцягнуўся ў задаволенай усмешцы, пакуль нечакана не зразумеў, што праспаў. Які ўжо дзень запар ён прачынаўся з мабільным тэлефонам у руцэ і прапушчаным будзільнікам. Усё гэта дзіка раздражняла, але хітры арганізм не ўспрымаў праблемы Васіля ўсур’ёз і асабіста прымаў рашэнне аб адключэнні будзільніка раней, чым Вася паспяваў зразумець, што адбываецца. Разбірацца з гэтым часу не было, вось-вось ужо павінен быў пачацца чарговы важны мітынг. Ужо цэлы тыдзень каманда не можа зрабіць выбар, дзе лепш размяшчаць вельмі важную кнопку. Неабходнасць асабістай прысутнасці на мітынгу Васілю была не да канца зразумела, як і сама прычына такога пакутлівага выбару. Але, як бэкенд распрацоўшчык, ён увесь час павінен быў пацвярджаць: “Калі кнопка будзе размяшчацца на дзесяць пікселяў правей, то гэта не паламае бэкенд”.
Васіль усё больш разумеў, што часу на саму распрацоўку ў яго не хапае, таму ўсё часцей гартаў LinkedIn, наведваў розныя мітапы і гуляў у настольныя гульні з незнаёмымі людзьмі ў пошуках новых распрацоўнікаў у сваю каманду. Нашай рэдакцыі ўдалося атрымаць адну з задач, якую Вася прапануе ў якасці тэставай. Таму прапануем разам разабрацца з рашэннем, раптам Васіль напіша і табе!
Пастаноўка задачы. Хай ёсць мноства кропак на плоскасці. Неабходна знайсці прамую, якая праходзіць праз найбольшую колькасць кропак.
Поўную рэалізацыю на C#, як і заўсёды, можна паглядзець на GitHub праекта coding-interview.
Паколькі прамых на плоскасці бясконцае мноства, то і пошук адказу можа заняць вечнасць, а твой інтэрв’юер вельмі заняты чалавек, яму яшчэ ўдзельнічаць у камандным мітынгу аб выбары імя і колеру кнопкі. Таму паспрабуем паскорыцца і аптымізаваць падыход.
Абмяжуем мноства прамых, якія патэнцыйна могуць з’яўляцца адказам. Калі мноства кропак пустое, то любая прамая будзе з’яўляцца адказам. Напрыклад, можна вяртаць прамую, якая праходзіць праз цэнтр каардынатаў.
Прамая адназначна задаецца двума рознымі кропкамі, таму будзем перабіраць усе магчымыя пары розных кропак, будаваць па іх прамую, і правяраць прыналежнасць кропак гэтай прамой.
Мы працуем з рэчаіснымі каардынатамі, таму параўнанне кропак будзе ажыццяўляцца з нейкай дакладнасцю, адсюль і назва метадаў: AllPointsAreAlmostEqual, IsAlmostEqual и гэтак далей. Апусцім пакуль што рэалізацыю геаметрычных метадаў і спынімся на пабудове цела алгарытму:
public (Line<double> Line, int PointsCount) FindLine(List<Point<double>> points)
{
if (AllPointsAreAlmostEqual(points))
{
var point = points.FirstOrDefault() ?? new Point<double>(0, 0);
var line = LinesFactory.BuildAnyLine(point);
return (Line: line, PointsCount: points.Count);
}
var maxPointsOnLineCount = 0;
Line<double> bestLine = new Line<double>(1, 0, 0);
foreach (var firstPoint in points)
{
foreach (var secondPoint in points)
{
if (secondPoint.IsAlmostEqual(firstPoint))
{
continue;
}
var line = LinesFactory.BuildLine(firstPoint, secondPoint);
var pointsOnLineCount = points.Count((p) => line.AlmostContains(p));
if (pointsOnLineCount > maxPointsOnLineCount)
{
maxPointsOnLineCount = pointsOnLineCount;
bestLine = line;
}
}
}
return (Line: bestLine, PointsCount: maxPointsOnLineCount);
}
private bool AllPointsAreAlmostEqual(List<Point<double>> points)
{
var p1 = points.FirstOrDefault();
return points.All((p) => p.IsAlmostEqual(p1));
}Дадзены алгарытм мае кубічную складанасць O(n^3): нам неабходна перабраць усе магчымыя пары кропак O(n^2), пабудаваць па іх прамую O(1) і праверыць прыналежнасць кропак гэтай прамой O(n).
Разгледзім выпадак, калі тры кропкі ляжаць на адной прамой:
Зафіксуем кропку A ў якасці першай кропкі прамой. Наш рэалізаваны алгарытм спачатку пабудуе прамую па пары кропак (A, B) і праверыць прыналежнасць кропак дадзенай прамой, а потым для пары кропак (A, C). Але гэта адна і тая ж прамая! Больш за тое, калі пара кропак (A, B) і пара кропак (A, C) фармуюць адну і тую ж прамую, то гэта значыць, што ўсе тры кропкі ляжаць на гэтай прамой.
Паколькі мы зафіксавалі першую кропку прамой A, то мы можам сцвярджаць, што ўсе прамыя праходзяць праз гэтую кропку, а гэта значыць іх можна адназначна задаць вектарам напрамкі прамой. Больш за тое, калініярныя вектары будуць адпавядаць адной і той жа прамой:
Такім чынам, для кожнай зафіксаванай кропкі неабходна знайсці напрамак (нейкі нармалізаваны вектар), якому калініярна найбольшая колькасць вектараў, што фарміруюцца парай розных кропак.
Часова ўвядзем абмежаванне на каардынаты кропак. Няхай усе нашы кропкі маюць толькі цэлалікавыя каардынаты. Тады каардынаты ўсіх накіравальных вектараў таксама будуць цэлалікавымі. Тады для нармалізацыі каардынатаў падзелім абедзве каардынаты на іх найбольшы агульны дзельнік. Гэты вектар не з’яўляецца нармалізаваным у матэматычным сэнсе, але дазваляе выкарыстоўваць яго як эталон для ўсіх калініярных дадзенаму вектару вектараў. Напрыклад, вектары (4, 2) і (-2, -1) пераўтворацца да вектару (2, 1).
На аснове сказанага вышэй пабудуем палепшанае рашэнне для цэлалікавых каардынатаў. Зададзім цела асноўнага метаду. Для кожнай зафіксаванай кропкі будзем знаходзіць напрамак з найбольшай колькасцю калініярных вектараў:
public (Line<long> line, int PointsCount) FindLineFast(List<Point<long>> points)
{
(var origin, var direction, var pointsCount) = FindVectorFast(points);
var line = LinesFactory.BuildLine(origin, direction);
return (line, pointsCount);
}
private (Point<long> Origin, Vector<long> Direction, int PointsCount) FindVectorFast(
List<Point<long>> points)
{
if (AllPointsAreEqual(points))
{
var origin = points.FirstOrDefault() ?? new Point<long>(0, 0);
var direction = new Vector<long>(1, 1);
return (Origin: origin, Direction: direction, PointsCount: points.Count);
}
Point<long> bestOrigin = new Point<long>(0, 0);
Vector<long> bestDirection = new Vector<long>(1, 1);
var maxPointsCount = 0;
foreach (var origin in points)
{
(var direction, var pointsCount) = FindDirectionWithMaxPointsCount(origin, points);
if (pointsCount > maxPointsCount)
{
bestOrigin = origin;
bestDirection = direction;
maxPointsCount = pointsCount;
}
}
return (Origin: bestOrigin, Direction: bestDirection, PointsCount: maxPointsCount);
}
private bool AllPointsAreEqual(List<Point<long>> points)
{
var p1 = points.FirstOrDefault();
return points.All((p) => p.IsEqual(p1));
}Рэалізуем алгарытм знаходжання найлепшага вектара напрамку для зафіксаванай кропкі:
private (Vector<long> Direction, int PointsCount) FindDirectionWithMaxPointsCount(
Point<long> origin,
List<Point<long>> points)
{
int originDuplicates = 0;
var pointsCountPerDirection = new Dictionary<long, Dictionary<long, int>>();
int maxPointsCount = 0;
Vector<long> bestDirection = new Vector<long>(1, 1);
foreach (var linePoint in points)
{
if (linePoint.IsEqual(origin))
{
++originDuplicates;
continue;
}
var direction = NormalizeDirection(
VectorsFactory.BuildVector(origin, linePoint)
);
var pointsCount = AddDirectionAndGetPointsCount(
pointsCountPerDirection,
direction
);
if (pointsCount > maxPointsCount)
{
maxPointsCount = pointsCount;
bestDirection = direction;
}
}
return (Direction: bestDirection, PointsCount: maxPointsCount + originDuplicates);
}Рэалізуем пабудову нармалізаванага вектару і падлік колькасці калініярных яму вектараў. Для гэтага створым асацыятыўны двухмерны масіў, дзе ў якасці ключэй будуць выступаць каардынаты (X, Y) нармалізаванага вектару, а ў якасці значэнняў – колькасць вектараў, калінеярных дадзеныму вектару:
private Vector<long> NormalizeDirection(Vector<long> direction)
{
long gcdValue = Arithmetic.GCD(direction.X, direction.Y);
return new Vector<long>(direction.X / gcdValue, direction.Y / gcdValue);
}
private int AddDirectionAndGetPointsCount(
Dictionary<long, Dictionary<long, int>> directionsCountPerOrigin,
Vector<long> direction)
{
if (!directionsCountPerOrigin.TryGetValue(direction.X, out var fixedXCounts))
{
fixedXCounts = new Dictionary<long, int>();
directionsCountPerOrigin[direction.X] = fixedXCounts;
}
if (!fixedXCounts.TryGetValue(direction.Y, out var count))
{
count = 0;
}
fixedXCounts[direction.Y] = count + 1;
return count + 1;
}Такім чынам мы атрымалі алгарытм са складанасцюO(n^2), дзе для кожнай зафіксаванай кропкі O(n) знаходзіцца найлепшы вектар напрамку O(n).
Важнай заўвагай да алгарытму вышэй з’яўляецца рэалізацыя падліку найбольшага агульнага дзельніка(GCD). Выніковы дзельнік таксама выканае паварот вектару ў патрэбную чвэрць.
public static long GCD(long x, long y)
{
long cx = Math.Abs(x);
long cy = Math.Abs(y);
while (cx != 0)
{
(cx, cy) = (cy % cx, cx);
}
return (x, y) switch
{
(long xv, _) when xv < 0 => -cy,
(0, long yv) when yv < 0 => -cy,
_ => cy
};
}Алгарытм вышэй прызначаны для працы з цэлалікавымі каардынатамі. Дапусцім, што ўсе нашы каардынаты зададзены з нейкай дакладнасцю digitsPrecision (колькасць значных лічбаў пасля коскі). Тады мы можам выканаць падлік, памножыўшы ўсе каардынаты на multiplier = 10 ^ digitsPrecision, і звесці рашэнне задачы да выпадку, апісанаму вышэй. А выніковы адказ атрымаем зваротным пераўтварэннем (дзяленнем на multiplier):
public (Line<double> line, int PointsCount) FindLineFast(
List<Point<double>> points,
int digitsPrecision = DefaultDigitsPrecision)
{
double multiplier = Math.Pow(10, digitsPrecision);
var longPoints = points.Select((p) => new Point<long>(
Convert.ToInt64(Math.Round(p.X * multiplier)),
Convert.ToInt64(Math.Round(p.Y * multiplier))
)).ToList();
(var longOrigin, var longDirection, var pointsCount) = FindVectorFast(longPoints);
var origin = new Point<double>(
longOrigin.X / multiplier,
longOrigin.Y / multiplier
);
var direction = new Vector<double>(
longDirection.X / multiplier,
longDirection.Y / multiplier
);
return (LinesFactory.BuildLine(origin, direction), pointsCount);
}На гэтым мне трэба развітвацца, а табе, дарагі чытач, прапаную азнаёміцца з іншымі разборамі задач, якія могуць трапляцца на тэхнічных сумоўях. Да хуткіх сустрэч!
