Created
January 7, 2020 19:46
-
-
Save jianminchen/126f36592034fded6933958b5949e20f to your computer and use it in GitHub Desktop.
I worked on the algorithm second time on Jan. 6, 2020 8:00 PM mock interview. I solved the problem first, and then think about how to optimize the solution.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // the problem statement: minimized square sum - https://gist.github.com/jianminchen/d5c7a2f18cc5066edacd7b5a2392e881 | |
| using System; | |
| using System.Collections.Generic; | |
| // To execute C#, please define "static void Main" on a class | |
| // named Solution. | |
| class Solution | |
| { | |
| static void Main(string[] args) | |
| { | |
| // ["Bob", "Alice", "Bob"] | |
| // map - Alice 1 | |
| // bob - 1 | |
| // charlie - 1 | |
| // 2^2 - Alice | |
| // Bob 1^2 + 1 ^2 | |
| // C 2^2 | |
| // Input: ["Bob", "Alice", "Bob"] | |
| // line 18 | |
| // Bob - one interval | |
| // alice - two interval 1, 1 | |
| // Bob - one interval - skip this one | |
| // 1^2+1^2 +1^2 = 3 | |
| // Bob - 1^2 | |
| // Alice 1^2 + 1^2 = 2 | |
| // linear | |
| // brute force - for each name -> go through once | |
| // | |
| var names = new string[]{"Bob", "Alice", "Bob"}; | |
| var number = CalculateCumulativeSquareNew(new List<string>(names)); | |
| Console.WriteLine(number); | |
| //var names2 = new string[]{"alice"}; | |
| //Console.WriteLine(CalculateCumulativeSquare(new List<string>(new List<string>(names2)))); | |
| } | |
| // o(n * n) -> O(n) - math formula | |
| // bob, charlie, apple | |
| public static int CalculateCumulativeSquareNew(List<string> names ) | |
| { | |
| if(names == null || names.Count == 0) // alice, bob, bob | |
| return 0; | |
| var length = names.Count; | |
| var hashSet = new HashSet<string>(names); // O(n) | |
| int sum = 0; | |
| foreach(var uniqueName in hashSet) | |
| { | |
| // alice, bob, bob | |
| int count = 0; | |
| for(int i = 0; i < length; i++) // O(n) | |
| { | |
| var name = names[i]; // i == 1, | |
| var isCurrent = name.CompareTo(uniqueName) == 0; | |
| if(!isCurrent) | |
| count++; // 1, 1 | |
| var isLastOne = !isCurrent && (i == (length - 1) || names[i + 1].CompareTo(uniqueName) == 0); | |
| if(isLastOne) | |
| { | |
| sum += count * count; // 1 | |
| count = 0; | |
| } | |
| } | |
| } | |
| return sum; // 5 | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment