Tag Archives: c-sharp
C# || Backspace String Compare – How To Backspace Compare Two Strings Using C#
The following is a module with functions which demonstrates how to backspace compare two strings using C#.
1. Backspace Compare – Problem Statement
Given two strings s and t, return true if they are equal when both are typed into empty text editors. ‘#’ means a backspace character.
Note that after backspacing an empty text, the text will continue empty.
Example 1:
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".
Example 2:
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".
Example 3:
Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".
2. Backspace Compare – Solution
The following is a solution which demonstrates how to backspace compare two strings.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// ============================================================================ // Author: Kenneth Perkins // Date: May 23, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to backspace compare two strings // ============================================================================ public class Solution { public bool BackspaceCompare(string s, string t) { return Clean(s) == Clean(t); } public string Clean(string source) { // Create result buffer var buffer = new StringBuilder(); foreach (var ch in source) { if (ch == '#') { // Backspace by removing the last character in the buffer if (buffer.Length > 0) { buffer.Length -= 1; } } else { // Add the character to the buffer buffer.Append(ch); } } return buffer.ToString(); } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
true
true
false
C# || How To Design Underground System To Keep Track Of Customer Travel Times Between Stations Using C#
The following is a module with functions which demonstrates how to design an underground system to keep track of customer travel times between different stations using C#.
1. Underground System – Problem Statement
An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.
Implement the UndergroundSystem class:
- void checkIn(int id, string stationName, int t)
- A customer with a card ID equal to id, checks in at the station stationName at time t.
- A customer can only be checked into one place at a time.
- void checkOut(int id, string stationName, int t)
- A customer with a card ID equal to id, checks out from the station stationName at time t.
- double getAverageTime(string startStation, string endStation)
- Returns the average time it takes to travel from startStation to endStation.
- The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.
- The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation.
- There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.
You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time t1 then checks out at time t2, then t1 < t2. All events happen in chronological order.
Example 1:
Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15); // Customer 45 "Leyton" -> "Waterloo" in 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20); // Customer 27 "Leyton" -> "Waterloo" in 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // Customer 32 "Paradise" -> "Cambridge" in 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. One trip "Paradise" -> "Cambridge", (14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.00000. Two trips "Leyton" -> "Waterloo", (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38); // Customer 10 "Leyton" -> "Waterloo" in 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 12.00000. Three trips "Leyton" -> "Waterloo", (10 + 12 + 14) / 3 = 12
Example 2:
Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667
2. Underground System – Solution
The following is a solution which demonstrates how to design an underground system to keep track of customer travel times between different stations.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// ============================================================================ // Author: Kenneth Perkins // Date: May 1, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to design underground system // ============================================================================ public class UndergroundSystem { Dictionary<string, KeyValuePair<int, int>> checkoutMap; Dictionary<int, KeyValuePair<string, int>> checkInMap; public UndergroundSystem() { checkoutMap = new Dictionary<string, KeyValuePair<int, int>>(); // Route - {TotalTime, Count} checkInMap = new Dictionary<int, KeyValuePair<string, int>>(); // Uid - {StationName, Time} } public void CheckIn(int id, string stationName, int t) { checkInMap[id] = new KeyValuePair<string, int>(stationName, t); } public void CheckOut(int id, string stationName, int t) { var checkIn = checkInMap[id]; var route = checkIn.Key + "_" + stationName; var totalTime = t - checkIn.Value; var checkout = checkoutMap.ContainsKey(route) ? checkoutMap[route] : new KeyValuePair<int, int>(0, 0); checkoutMap[route] = new KeyValuePair<int, int>(checkout.Key + totalTime, checkout.Value + 1); } public double GetAverageTime(string startStation, string endStation) { var route = startStation + "_" + endStation; var checkout = checkoutMap[route]; return (double) checkout.Key / checkout.Value; } }// http://programmingnotes.org/ /** * Your UndergroundSystem object will be instantiated and called as such: * UndergroundSystem obj = new UndergroundSystem(); * obj.CheckIn(id,stationName,t); * obj.CheckOut(id,stationName,t); * double param_3 = obj.GetAverageTime(startStation,endStation); */ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]
C# || How To Add Simple Object Change Tracking To Track Changes Using C#
The following is a module with functions which demonstrates how to add simple object change tracking to track changes made to an object using C#.
Contents
1. Overview
2. Basic Usage
3. Accept Changes
4. Reject Changes
5. Ignore Tracking For Property
6. Notify Property Changed
7. Utils Namespace
8. More Examples
1. Overview
The following is a simple abstract change tracker class which implements INotifyPropertyChanged and IRevertibleChangeTracking which provides functionality to track object changes, and to ‘accept’ or ‘revert’ changes.
To use this class, simply inherit the abstract class, and your all set!
Note: Don’t forget to include the ‘Utils Namespace‘ before running the examples!
2. Basic Usage
The example below demonstrates the use of ChangeTracker.BeginChanges to start tracking object changes, as well as ChangeTracker.GetChanges to get the changes made to an object.
The following example demonstrates the basic usage of adding change tracking to an object, and making and getting changes.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
// Basic Usage using Utils; // Declare class and inherit ChangeTracker public class Person : ChangeTracker { public string FirstName { get; set; } public string LastName { get; set; } public int? Age { get; set; } } // Declare data var person = new Person { FirstName = "Kenneth", LastName = "Perkins", Age = 31 }; // Required: Changes made to this object will start being // tracked the moment this function is called person.BeginChanges(); // Make changes to the object person.FirstName = "Jennifer"; person.LastName = "Nguyen"; person.Age = 28; // Get changes made to the object var changes = person.GetChanges(); // Display the changes Console.WriteLine($"Changes: {changes.Count}"); foreach (var change in changes) { Console.WriteLine($" PropertyName: {change.PropertyName}, OriginalValue: {change.OriginalValue}, CurrentValue: {change.CurrentValue}"); } // expected output: /* Changes: 3 PropertyName: FirstName, OriginalValue: Kenneth, CurrentValue: Jennifer PropertyName: LastName, OriginalValue: Perkins, CurrentValue: Nguyen PropertyName: Age, OriginalValue: 31, CurrentValue: 28 */ |
3. Accept Changes
The example below demonstrates the use of ChangeTracker.AcceptChanges to accept modification changes made to an object.
This function commits all the changes made to the object since either ChangeTracker.BeginChanges was called, or since ChangeTracker.AcceptChanges was last called.
When the accept function is called, all the changes made to the object up to that point will be marked as the current ‘source of truth’ for change tracking.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
// Accept Changes using Utils; // Declare class and inherit ChangeTracker public class Person : ChangeTracker { public string FirstName { get; set; } public string LastName { get; set; } public int? Age { get; set; } } // Declare data var person = new Person { FirstName = "Kenneth", LastName = "Perkins", Age = 31 }; // Required: Changes made to this object will start being // tracked the moment this function is called person.BeginChanges(); // Make changes to the object person.FirstName = "Lynn"; person.LastName = "P"; person.Age = 10; // Accept all the changes made to the object up to // this point as the source of truth for change tracking person.AcceptChanges(); // Get changes made to the object var changes = person.GetChanges(); // Display the changes // Note: No changes will display because the most recent modifications has been accepted Console.WriteLine($"Changes: {changes.Count}"); foreach (var change in changes) { Console.WriteLine($" PropertyName: {change.PropertyName}, OriginalValue: {change.OriginalValue}, CurrentValue: {change.CurrentValue}"); } // expected output: /* Changes: 0 */ |
4. Reject Changes
The example below demonstrates the use of ChangeTracker.RejectChanges to reject modification changes made to an object.
This function rejects all the changes made to the object since either ChangeTracker.BeginChanges was called, or since ChangeTracker.AcceptChanges was last called.
When the reject function is called, all the changes made to the object up to that point reverts back to the objects state before modifications initially began or modifications was last accepted.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
// Reject Changes using Utils; // Declare class and inherit ChangeTracker public class Person : ChangeTracker { public string FirstName { get; set; } public string LastName { get; set; } public int? Age { get; set; } } // Declare data var person = new Person { FirstName = "Kenneth", LastName = "Perkins", Age = 31 }; // Required: Changes made to this object will start being // tracked the moment this function is called person.BeginChanges(); // Make changes to the object person.FirstName = "Sole"; person.LastName = "P"; person.Age = 19; // Rejects all the changes made to the object up to // this point and reverts back to the objects state // before modifications were made person.RejectChanges(); // Get changes made to the object var changes = person.GetChanges(); // Display the changes // Note: No changes will display because the most recent modifications has been rejected Console.WriteLine($"Changes: {changes.Count}"); foreach (var change in changes) { Console.WriteLine($" PropertyName: {change.PropertyName}, OriginalValue: {change.OriginalValue}, CurrentValue: {change.CurrentValue}"); } // expected output: /* Changes: 0 */ |
5. Ignore Tracking For Property
The example below demonstrates the use of ChangeTracker.ChangeTrackerIgnore attribute to mark a specific property to be ignored from change tracking.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
// Ignore Tracking For Property using Utils; // Declare class and inherit ChangeTracker public class Person : ChangeTracker { public string FirstName { get; set; } public string LastName { get; set; } [ChangeTrackerIgnore] public int? Age { get; set; } } // Declare data var person = new Person { FirstName = "Kenneth", LastName = "Perkins", Age = 31 }; // Required: Changes made to this object will start being // tracked the moment this function is called person.BeginChanges(); // Make changes to the object person.FirstName = "Jennifer"; person.LastName = "Nguyen"; person.Age = 28; // Get changes made to the object var changes = person.GetChanges(); // Display the changes Console.WriteLine($"Changes: {changes.Count}"); foreach (var change in changes) { Console.WriteLine($" PropertyName: {change.PropertyName}, OriginalValue: {change.OriginalValue}, CurrentValue: {change.CurrentValue}"); } // expected output: /* Changes: 2 PropertyName: FirstName, OriginalValue: Kenneth, CurrentValue: Jennifer PropertyName: LastName, OriginalValue: Perkins, CurrentValue: Nguyen */ |
6. Notify Property Changed
The example below demonstrates the use of ChangeTracker.NotifyPropertyChanged to fire the PropertyChanged event notifying that the specified property value has changed.
In the class declaration, simply add ChangeTracker.NotifyPropertyChanged to the properties you wish to notify changes, and add a PropertyChanged event handler function to receive the notifications.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
// Notify Property Changed using Utils; // Declare class and inherit ChangeTracker // Modify the properties you wish to notify changes public class Person : ChangeTracker { string _firstName; public string FirstName { get { return _firstName; } set { _firstName = value; NotifyPropertyChanged(value); } } string _lastName; public string LastName { get { return _lastName; } set { _lastName = value; NotifyPropertyChanged(value); } } int? _age; public int? Age { get { return _age; } set { _age = value; NotifyPropertyChanged(value); } } } // Declare data var person = new Person { FirstName = "Kenneth", LastName = "Perkins", Age = 31 }; // Set custom event handler function for property changed event person.PropertyChanged += Person_PropertyChanged; // Required: Changes made to this object will start being // tracked the moment this function is called person.BeginChanges(); // Make changes to the object person.FirstName = "Jennifer"; person.LastName = "Nguyen"; person.Age = 28; // Declare Custom event handler function for the PropertyChanged event public static void Person_PropertyChanged(object sender, System.ComponentModel.PropertyChangedEventArgs e) { var eventArgs = (ChangeTracker.PropertyChangedTrackedEventArgs)e; Console.WriteLine($"Event Handler Changes:"); Console.WriteLine($" PropertyName: {eventArgs.PropertyName}, OriginalValue: {eventArgs.OriginalValue}, CurrentValue: {eventArgs.CurrentValue}"); } // expected output: /* Event Handler Changes: PropertyName: FirstName, OriginalValue: Kenneth, CurrentValue: Jennifer Event Handler Changes: PropertyName: LastName, OriginalValue: Perkins, CurrentValue: Nguyen Event Handler Changes: PropertyName: Age, OriginalValue: 31, CurrentValue: 28 */ |
7. Utils Namespace
The following is the Utils Namespace. Include this in your project to start using!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 |
// ============================================================================ // Author: Kenneth Perkins // Date: Apr 10, 2022 // Taken From: http://programmingnotes.org/ // File: Utils.cs // Description: Handles general utility functions // ============================================================================ using System; using System.Linq; using System.Reflection; using System.Collections.Generic; using System.Runtime.CompilerServices; namespace Utils { public abstract class ChangeTracker : System.ComponentModel.INotifyPropertyChanged, System.ComponentModel.IRevertibleChangeTracking { protected Dictionary<string, ITrackedChange> Tracked { get; set; } public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged; public bool IsTracking { get { return Tracked.Count > 0; } } /// <summary> /// Gets the objects changed status /// </summary> /// <returns><see langword="true"/> if the objects content has changed since either <see cref="BeginChanges"/> /// was called, or since <see cref="AcceptChanges"/> was last called; <see langword="false"/> otherwise</returns> public bool IsChanged { get { if (!_isChanged && IsTracking) { var trackedChanges = GetTrackedChanges(); if (trackedChanges.Any(x => x.DetectChange(GetValue(x.Property)))) { _isChanged = true; } } return _isChanged; } protected set { _isChanged = value; } } private bool _isChanged = false; protected ChangeTracker() { Tracked = new Dictionary<string, ITrackedChange>(); } /// <summary> /// Fires the PropertyChanged event notifying that the specified property value changed /// </summary> /// <param name="currentValue">The current value</param> /// <param name="originalValue">The original value</param> /// <param name="propertyName">The corresponding property name</param> protected void NotifyPropertyChanged(object currentValue, object originalValue, [CallerMemberName] string propertyName = "") { this.PropertyChanged?.Invoke(this, new PropertyChangedTrackedEventArgs(propertyName, originalValue, currentValue)); } /// <summary> /// Fires the PropertyChanged event notifying that the specified property value changed /// </summary> /// <param name="currentValue">The current value</param> /// <param name="propertyName">The corresponding property name</param> protected virtual void NotifyPropertyChanged(object currentValue, [CallerMemberName] string propertyName = "") { NotifyPropertyChanged(currentValue, GetTrackedChange(propertyName)?.OriginalValue, propertyName); } /// <summary> /// Starts the tracking operation on the object. Changes made to the /// object will start being tracked the moment this function is called /// </summary> /// <exception cref="InvalidOperationException">Changes have already begun</exception> public virtual void BeginChanges() { ThrowIfTrackingStarted(); Track(GetTrackableProperties()); IsChanged = false; } /// <summary> /// Ends the tracking operation on the object. Any pending tracked changes made to the /// object since either <see cref="BeginChanges"/> was called, or since <see cref="AcceptChanges"/> /// was last called will be lost the moment this function is called /// </summary> /// <exception cref="InvalidOperationException">Change tracking has not started</exception> public virtual void EndChanges() { ThrowIfTrackingNotStarted(); Tracked.Clear(); IsChanged = false; } /// <summary> /// Sets the current object state as its default state by accepting the modifications. /// Commits all the changes made to this object since either <see cref="BeginChanges"/> /// was called, or since <see cref="AcceptChanges"/> was last called /// </summary> /// <exception cref="InvalidOperationException">Change tracking has not started</exception> public virtual void AcceptChanges() { ThrowIfTrackingNotStarted(); var trackedChanges = UpdateTracked(); foreach (var change in trackedChanges) { change.AcceptChange(); } IsChanged = false; } /// <summary> /// Resets the current objects state by rejecting the modifications. Rejects /// all changes made to the object since either <see cref="BeginChanges"/> /// was called, or since <see cref="AcceptChanges"/> was last called /// </summary> /// <exception cref="InvalidOperationException">Change tracking has not started</exception> public virtual void RejectChanges() { ThrowIfTrackingNotStarted(); var trackedChanges = GetTrackedChanges(); foreach (var change in trackedChanges) { SetValue(change.Property, change.OriginalValue); change.RejectChange(); } IsChanged = false; } /// <summary> /// Returns a list containing information of all the properties with changes /// applied to it since either <see cref="BeginChanges"/> was called, or /// since <see cref="AcceptChanges"/> was last called /// </summary> /// <returns>A list containing the changes made to the object</returns> /// <exception cref="InvalidOperationException">Change tracking has not started</exception> public virtual List<ITrackedChange> GetChanges() { ThrowIfTrackingNotStarted(); var result = new List<ITrackedChange>(); var trackedChanges = UpdateTracked(); foreach (var change in trackedChanges) { if (change.HasChanges) { result.Add(change); } } return result; } /// <summary> /// Returns a list containing information of all the properties being tracked /// </summary> /// <returns>A list containing property tracking information</returns> /// <exception cref="InvalidOperationException">Change tracking has not started</exception> public List<ITrackedChange> GetTracked() { ThrowIfTrackingNotStarted(); return Tracked.Values.ToList(); } /// <summary> /// Updates the tracking status of all the properties being tracked /// </summary> /// <returns>A list containing properties being tracked</returns> protected IEnumerable<TrackedChange> UpdateTracked() { var trackedChanges = GetTrackedChanges(); Track(trackedChanges.Select(x => x.Property)); return trackedChanges; } /// <summary> /// Keeps track of the original and current values of the provided properties /// </summary> /// <param name="properties">The properties to track</param> protected void Track(IEnumerable<PropertyInfo> properties) { if (properties != null) { foreach (var prop in properties) { Track(prop, GetValue(prop)); } } } /// <summary> /// Keeps track of the original and current value of the provided property /// </summary> /// <param name="property">The property to track</param> /// <param name="currentValue">The current value of the property</param> protected void Track(PropertyInfo property, object currentValue) { TrackedChange currentChange = null; if (!IsTrackedChange(property.Name)) { Func<object, object, bool> hasChangedFunc = (original, current) => { return HasValuesChanged(original, current); }; currentChange = new TrackedChange { Property = property, OriginalValue = currentValue, HasChangedFunc = hasChangedFunc }; Tracked.Add(property.Name, currentChange); } else { currentChange = GetTrackedChange(property.Name); currentChange.CurrentValue = currentValue; currentChange.Status = TrackedChange.TrackingStatus.Checked; currentChange.LastChecked = DateTime.Now; } if (currentChange.HasChanges) { IsChanged = true; } } /// <summary> /// Class which contains property tracking information /// </summary> protected class TrackedChange : ITrackedChange { public enum TrackingStatus { Unchecked, Checked } public PropertyInfo Property { get; set; } public string PropertyName { get { return Property?.Name; } } public object OriginalValue { get; set; } public object CurrentValue { get; set; } public TrackingStatus Status { get; set; } = TrackingStatus.Unchecked; public bool HasChanges { get { return Status == TrackingStatus.Checked && DetectChange(CurrentValue); } } public DateTime? LastChecked { get; set; } = null; public Func<object, object, bool> HasChangedFunc { get; set; } public bool DetectChange(object currentValue) { return HasChangedFunc(OriginalValue, currentValue); } public void AcceptChange() { OriginalValue = CurrentValue; RejectChange(); } public void RejectChange() { CurrentValue = null; Status = TrackingStatus.Unchecked; LastChecked = null; } } /// <summary> /// Provides support for object change tracking /// </summary> public interface ITrackedChange { string PropertyName { get; } object OriginalValue { get; } object CurrentValue { get; } } /// <summary> /// Provides data for the <see cref=" System.ComponentModel.PropertyChangedEventArgs"/> event /// </summary> public class PropertyChangedTrackedEventArgs : System.ComponentModel.PropertyChangedEventArgs { public object OriginalValue{ get; private set; } public object CurrentValue { get; private set; } public PropertyChangedTrackedEventArgs(string propertyName, object originalValue, object currentValue) : base(propertyName) { OriginalValue = originalValue; CurrentValue = currentValue; } } /// <summary> /// Attribute which allows a property to be ignored from being tracked /// </summary> public class ChangeTrackerIgnoreAttribute : System.Attribute {} #region "Helpers" protected bool IsTrackedChange(string propertyName) { return Tracked.ContainsKey(propertyName); } protected TrackedChange GetTrackedChange(string propertyName) { return IsTrackedChange(propertyName) ? (TrackedChange)Tracked[propertyName] : null; } protected IEnumerable<TrackedChange> GetTrackedChanges() { return Tracked.Select(pair => (TrackedChange)pair.Value); } protected virtual IEnumerable<PropertyInfo> GetTrackableProperties() { return this.GetType().GetProperties() .Where(p => !p.DeclaringType.Equals(typeof(ChangeTracker)) && p.CanRead && p.CanWrite && !p.GetCustomAttributes<ChangeTrackerIgnoreAttribute>(false).Any() ); } protected virtual object GetValue(PropertyInfo property) { return property?.GetValue(this, property.GetIndexParameters() .Count() == 1 ? new object[] { null } : null); } protected virtual void SetValue(PropertyInfo property, object value) { if (property != null && property.CanWrite) { property.SetValue(this, value); } } protected virtual bool HasValuesChanged<T>(T originalValue, T currentValue) { return !EqualityComparer<T>.Default.Equals(originalValue, currentValue); } protected void ThrowIfTrackingNotStarted() { if (!IsTracking) { throw new InvalidOperationException("Change tracking has not started. Call 'BeginChanges' to start change tracking"); } } protected void ThrowIfTrackingStarted() { if (IsTracking) { throw new InvalidOperationException("Change tracking has already started"); } } #endregion } }// http://programmingnotes.org/ |
8. More Examples
Below are more examples demonstrating the use of the ‘Utils‘ Namespace. Don’t forget to include the module when running the examples!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
// ============================================================================ // Author: Kenneth Perkins // Date: Apr 10, 2022 // Taken From: http://programmingnotes.org/ // File: Program.cs // Description: The following demonstrates the use of the Utils Namespace // ============================================================================ using System; using System.Diagnostics; using System.Collections.Generic; using System.Threading.Tasks; using Utils; public class Program { // Declare class and inherit ChangeTracker // Modify the properties you wish to notify changes public class Person : ChangeTracker { string _firstName; public string FirstName { get { return _firstName; } set { _firstName = value; NotifyPropertyChanged(value); } } string _lastName; public string LastName { get { return _lastName; } set { _lastName = value; NotifyPropertyChanged(value); } } int? _age; //[ChangeTrackerIgnore] public int? Age { get { return _age; } set { _age = value; NotifyPropertyChanged(value); } } } static void Main(string[] args) { try { // Declare data var person = new Person { FirstName = "Kenneth", LastName = "Perkins", Age = 31 }; // Set custom event handler function for property changed event person.PropertyChanged += Person_PropertyChanged; // Required: Changes made to this object will start being // tracked the moment this function is called person.BeginChanges(); var changes1 = person.GetChanges(); // Make changes to the object person.FirstName = "Jennifer"; person.LastName = "Nguyen"; person.Age = 28; // Get changes made to the object var changes2 = person.GetChanges(); // Display the changes DisplayChanges(changes2); // --- Accept changes --- // Make changes to the object person.FirstName = "Lynn"; person.LastName = "P"; person.Age = 10; var changes3 = person.GetChanges(); // Accept all the changes made to the object up to // this point as the source of truth for change tracking person.AcceptChanges(); // Get changes made to the object var changes4 = person.GetChanges(); // Display the changes // Note: No changes will display because the most recent modifications has been accepted DisplayChanges(changes4); // --- Reject changes --- // Make changes to the object person.FirstName = "Sole"; person.LastName = "P"; person.Age = 19; // Rejects all the changes made to the object up to // this point and reverts back to the objects state // before modifications were made person.RejectChanges(); // Get changes made to the object var changes5 = person.GetChanges(); // Display the changes // Note: No changes will display because the most recent modifications has been rejected DisplayChanges(changes5); } catch (Exception ex) { Display(ex.ToString()); } finally { Console.ReadLine(); } } // Declare Custom event handler function for the PropertyChanged event public static void Person_PropertyChanged(object sender, System.ComponentModel.PropertyChangedEventArgs e) { var eventArgs = (ChangeTracker.PropertyChangedTrackedEventArgs)e; Display($"Event Handler Changes:"); Display($" PropertyName: {eventArgs.PropertyName}, OriginalValue: {eventArgs.OriginalValue}, CurrentValue: {eventArgs.CurrentValue}"); } public static void DisplayChanges(List<ChangeTracker.ITrackedChange> changes) { Display($"Changes: {changes.Count}"); foreach (var change in changes) { Display($" PropertyName: {change.PropertyName}, OriginalValue: {change.OriginalValue}, CurrentValue: {change.CurrentValue}"); } Display("============"); } static void Display(string message) { Console.WriteLine(message); Debug.Print(message); } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
C# || Remove Linked List Elements – How To Remove All Target Linked List Elements Using C#
The following is a module with functions which demonstrates how to remove all target linked list elements using C#.
1. Remove Elements – Problem Statement
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
Example 1:
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Example 2:
Input: head = [], val = 1
Output: []
Example 3:
Input: head = [7,7,7,7], val = 7
Output: []
2. Remove Elements – Solution
The following is a solution which demonstrates how to remove all target linked list elements.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
// ============================================================================ // Author: Kenneth Perkins // Date: Apr 2, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to remove all target linked list elements // ============================================================================ /** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode RemoveElements(ListNode head, int val) { var ptr = head; // Loop through data checking to see if the next node equals the target value while (ptr != null && ptr.next != null) { // If the next node value is the target value, set the next node // to point to the one after it if (ptr.next.val == val) { ptr.next = ptr.next.next; } else { // Advance to the next node ptr = ptr.next; } } // If the head equals the target value, advance to the next if (head != null && head.val == val) { head = head.next; } return head; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
[1,2,3,4,5]
[]
[]
C# || How To Compare Version Numbers Using C#
The following is a module with functions which demonstrates how to compare version numbers using C#.
1. Compare Version – Problem Statement
Given two version numbers, version1 and version2, compare them.
Version numbers consist of one or more revisions joined by a dot ‘.’. Each revision consists of digits and may contain leading zeros. Every revision contains at least one character. Revisions are 0-indexed from left to right, with the leftmost revision being revision 0, the next revision being revision 1, and so on. For example 2.5.33 and 0.1 are valid version numbers.
To compare version numbers, compare their revisions in left-to-right order. Revisions are compared using their integer value ignoring any leading zeros. This means that revisions 1 and 001 are considered equal. If a version number does not specify a revision at an index, then treat the revision as 0. For example, version 1.0 is less than version 1.1 because their revision 0s are the same, but their revision 1s are 0 and 1 respectively, and 0 < 1.
Return the following:
- If version1 < version2, return -1.
- If version1 > version2, return 1.
- Otherwise, return 0.
Example 1:
Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both "01" and "001" represent the same integer "1".
Example 2:
Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: version1 does not specify revision 2, which means it is treated as "0".
Example 3:
Input: version1 = "0.1", version2 = "1.1"
Output: -1
Explanation: version1's revision 0 is "0", while version2's revision 0 is "1". 0 < 1, so version1 < version2.
2. Compare Version – Solution
The following is a solution which demonstrates how to compare version numbers.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// ============================================================================ // Author: Kenneth Perkins // Date: Mar 1, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to compare version numbers // ============================================================================ public class Solution { public int CompareVersion(string version1, string version2) { var revisions1 = version1.Split("."); var revisions2 = version2.Split("."); var length = Math.Max(revisions1.Length, revisions2.Length); for (int index = 0; index < length; ++index) { var v1 = index < revisions1.Length ? int.Parse(revisions1[index]) : 0; var v2 = index < revisions2.Length ? int.Parse(revisions2[index]) : 0; if (v1 < v2) { return -1; } else if (v1 > v2) { return 1; } } return 0; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
0
0
-1
C# || How To Find The Difference Between Two Strings Using C#
The following is a module with functions which demonstrates how to find the difference between two strings using C#.
1. Find The Difference – Problem Statement
You are given two strings s and t.
String t is generated by random shuffling string s and then add one more letter at a random position.
Return the letter that was added to t.
Example 1:
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.
Example 2:
Input: s = "", t = "y"
Output: "y"
2. Find The Difference – Solution
The following is a solution which demonstrates how to find the difference between two strings.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// ============================================================================ // Author: Kenneth Perkins // Date: Feb 6, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find the difference between two strings // ============================================================================ public class Solution { public char FindTheDifference(string s, string t) { var result = ' '; // Create a map with the frequency each character has been seen from the first string var seen = new Dictionary<char, int>(); foreach (var letter in s) { seen[letter] = (seen.ContainsKey(letter) ? seen[letter] : 0) + 1; } // Decrease the frequency of the characters we've seen from the second string foreach (var letter in t) { // Either we havent seen this character, or its frequency has reached 0 if (!seen.ContainsKey(letter) || seen[letter] == 0) { result = letter; break; } // Decrease the frequency --seen[letter]; } return result; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
"e"
"y"
C# || How To Get Total Sum Root To Leaf Binary Numbers In Binary Tree Using C#
The following is a module with functions which demonstrates how to get the total sum root to leaf binary numbers in a binary tree using C#.
1. Sum Root To Leaf – Problem Statement
You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit.
- For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.
For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.
The test cases are generated so that the answer fits in a 32-bits integer.
A leaf node is a node with no children.
Example 1:
Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
Example 2:
Input: root = [0]
Output: 0
2. Sum Root To Leaf – Solution
The following is a solution which demonstrates how to get the total sum root to leaf binary numbers in a binary tree.
This solution uses Depth First Search to explore items at each level.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
// ============================================================================ // Author: Kenneth Perkins // Date: Jan 10, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to get sum root to leaf binary numbers // ============================================================================ /** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public int SumRootToLeaf(TreeNode root) { return Traverse(root, 0); } private int Traverse(TreeNode node, int currentSum) { if (node == null) { return 0; } // Calculate current sum currentSum = (currentSum * 2) + node.val; // We have reached a leaf node if (node.left == null && node.right == null) { return currentSum; } // Keep traversing left and right calculating the sum return Traverse(node.left, currentSum) + Traverse(node.right, currentSum); } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
22
0
C# || Jump Game III – How To Check If You Can Reach Target Value In Array Using C#
The following is a module with functions which demonstrates how to check if you can reach a target value in an array using C#.
1. Can Reach – Problem Statement
Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i – arr[i], check if you can reach to any index with value 0.
Notice that you can not jump outside of the array at any time.
Example 1:
Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:
All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3
Example 2:
Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation:
One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3
Example 3:
Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.
2. Can Reach – Solution
The following are two solutions which demonstrates how to check if you can reach a target value in an array.
The following solution uses Depth First Search when looking for the target value.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// ============================================================================ // Author: Kenneth Perkins // Date: Dec 8, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Determines if a target value can be reached in an array // ============================================================================ public class Solution { public bool CanReach(int[] arr, int start) { var visited = new bool[arr.Length]; return DFS(arr, start, visited); } public bool DFS(int[] arr, int currentIndex, bool[] visited) { // Make sure parameters are in bounds if (currentIndex < 0 || currentIndex >= arr.Length) { return false; } // Check to see if the index has been visited if (visited[currentIndex]) { return false; } // Check to see if we found the target value if (arr[currentIndex] == 0) { return true; } // Mark current index as visited visited[currentIndex] = true; // Keep searching forwards and backwards var forwards = currentIndex + arr[currentIndex]; var backwards = currentIndex - arr[currentIndex]; return DFS(arr, backwards, visited) || DFS(arr, forwards, visited); } }// http://programmingnotes.org/ |
The following solution uses Breadth First Search when looking for the target value.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// ============================================================================ // Author: Kenneth Perkins // Date: Dec 8, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Determines if a target value can be reached in an array // ============================================================================ public class Solution { public bool CanReach(int[] arr, int start) { var visited = new bool[arr.Length]; var queue = new Queue<int>(); queue.Enqueue(start); while (queue.Count > 0) { var currentIndex = queue.Dequeue(); // Check to see if we found the target value if (arr[currentIndex] == 0) { return true; } // Mark current index as visited visited[currentIndex] = true; // Keep searching forwards and backwards var forwards = currentIndex + arr[currentIndex]; var backwards = currentIndex - arr[currentIndex]; var directions = new List<int>{forwards, backwards}; foreach (var direction in directions) { if (direction >= 0 && direction < arr.Length && !visited[direction]) { queue.Enqueue(direction); } } } return false; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
true
true
false
C# || Maximum Product Subarray – How To Find Largest Product In Contiguous Subarray Using C#
The following is a module with functions which demonstrates how to find the largest product in a contiguous subarray using C#.
1. Max Product – Problem Statement
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
It is guaranteed that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
2. Max Product – Solution
The following is a solution which demonstrates how to find the largest product in a contiguous subarray.
This solution is inspired by Kadane’s algorithm to find the result.
The idea here is similar to the ‘Maximum Subarray‘ problem.
In this solution, we have two values:
- The current cumulative maximum product up to current element
- The current cumulative minimum product up to current element
Each loop iteration, these values are updated by either multiplying the new element at the current index with the existing product, or starting fresh from current index.
When a negative number is encountered, the current max and current min values are swapped, because multiplying a negative number makes a big number smaller, and multiplying a negative number makes small number bigger. So their intent is redefined by swapping.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
// ============================================================================ // Author: Kenneth Perkins // Date: Dec 2, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find maximum product contiguous subarray // ============================================================================ public class Solution { public int MaxProduct(int[] nums) { // Store the result var result = nums[0]; // The current maximum and minimum product of the subarray var currentMin = nums[0]; var currentMax = nums[0]; for (int index = 1; index < nums.Length; ++index) { // Swap current max/min because multiplying // a negative number makes a big number smaller, // and multiplying a negative number makes small number bigger. // So their intent is redefined by swapping if (nums[index] < 0) { var temp = currentMax; currentMax = currentMin; currentMin = temp; } // Determine the max/min product for the current number. // It is either the current number itself // or the max/min by the previous values times the current one currentMax = Math.Max(nums[index], currentMax * nums[index]); currentMin = Math.Min(nums[index], currentMin * nums[index]); // Keep track of the current max result result = Math.Max(result, currentMax); } return result; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
6
0
C# || Maximum Subarray – How To Find Largest Sum In Contiguous Subarray Using C#
The following is a module with functions which demonstrates how to find the largest sum in a contiguous subarray using C#.
1. Max Sub Array – Problem Statement
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
2. Max Sub Array – Solution
The following is a solution which demonstrates how to find the largest sum in a contiguous subarray.
This solution uses Kadane’s algorithm to find the result.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// ============================================================================ // Author: Kenneth Perkins // Date: Dec 2, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find maximum sum in contiguous subarray // ============================================================================ public class Solution { public int MaxSubArray(int[] nums) { var result = nums[0]; var current = result; for (int index = 1; index < nums.Length; ++index) { current = Math.Max(nums[index], nums[index] + current); result = Math.Max(result, current); } return result; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
6
1
23
C# || String To Integer (atoi) – How To Convert String To Signed Integer Using C#
The following is a module with functions which demonstrates how to convert a string to 32-bit signed integer using C#.
1. My Atoi – Problem Statement
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).
The algorithm for myAtoi(string s) is as follows:
- Read in and ignore any leading whitespace.
- Check if the next character (if not already at the end of the string) is ‘-‘ or ‘+’. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
- Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
- Convert these digits into an integer (i.e. “123” -> 123, “0032” -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
- If the integer is out of the 32-bit signed integer range [-231, 231 – 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 – 1 should be clamped to 231 – 1.
- Return the integer as the final result.
Note:
- Only the space character ‘ ‘ is considered a whitespace character.
- Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.
Example 1:
Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.
Example 2:
Input: s = " -42"
Output: -42
Explanation:
Step 1: " -42" (leading whitespace is read and ignored)
^
Step 2: " -42" ('-' is read, so the result should be negative)
^
Step 3: " -42" ("42" is read in)
^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.
Example 3:
Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.
Example 4:
Input: s = "words and 987"
Output: 0
Explanation:
Step 1: "words and 987" (no characters read because there is no leading whitespace)
^
Step 2: "words and 987" (no characters read because there is neither a '-' nor '+')
^
Step 3: "words and 987" (reading stops immediately because there is a non-digit 'w')
^
The parsed integer is 0 because no digits were read.
Since 0 is in the range [-231, 231 - 1], the final result is 0.
Example 5:
Input: s = "-91283472332"
Output: -2147483648
Explanation:
Step 1: "-91283472332" (no characters read because there is no leading whitespace)
^
Step 2: "-91283472332" ('-' is read, so the result should be negative)
^
Step 3: "-91283472332" ("91283472332" is read in)
^
The parsed integer is -91283472332.
Since -91283472332 is less than the lower bound of the range [-231, 231 - 1], the final result is clamped to -231 = -2147483648.
2. My Atoi – Solution
The following is a solution which demonstrates how to convert a string to 32-bit signed integer.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// ============================================================================ // Author: Kenneth Perkins // Date: Nov 30, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to convert string to integer // ============================================================================ public class Solution { public int MyAtoi(string s) { // 1. Advance leading whitespace var index = 0; while (index < s.Length && char.IsWhiteSpace(s[index])) { ++index; } // 2. Determine if number is positive or negative var sign = 1; if (index < s.Length && (s[index] == '-' || s[index] == '+')) { if (s[index] == '-') { sign = -1; } ++index; } // 3. Convert char digits to numeric value var result = 0; while (index < s.Length && char.IsDigit(s[index])) { var digit = CharToInt(s[index]); // Check for overflow if (result > (int.MaxValue - digit) / 10) { return sign == -1 ? int.MinValue : int.MaxValue; } result = (result * 10) + digit; ++index; } return result * sign; } private static int CharToInt(char ch) { return ch - '0'; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
42
-42
4193
0
-2147483648
C# || Maximal Rectangle – How To Find Largest Rectangle Area Using C#
The following is a module with functions which demonstrates how to find the largest rectangle area containing only 1’s using C#.
1. Maximal Rectangle – Problem Statement
Given a rows x cols binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.
Example 1:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.
Example 2:
Input: matrix = []
Output: 0
Example 3:
Input: matrix = [["0"]]
Output: 0
Example 4:
Input: matrix = [["1"]]
Output: 1
Example 5:
Input: matrix = [["0","0"]]
Output: 0
2. Maximal Rectangle – Solution
The following is a solution which demonstrates how to find the largest rectangle area containing only 1’s.
This solution uses the monotonic stack approach.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// ============================================================================ // Author: Kenneth Perkins // Date: Nov 30, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find the largest rectangle area // ============================================================================ public class Solution { public int MaximalRectangle(char[][] matrix) { if (matrix.Length == 0) { return 0; } var result = 0; var histogram = new int[matrix[0].Length + 1]; for (int row = 0; row < matrix.Length; ++row) { var stack = new Stack<int>(); for (int col = 0; col <= matrix[row].Length; ++col) { // Set value if (col < matrix[row].Length) { if (matrix[row][col] == '1') { histogram[col] += 1; } else { histogram[col] = 0; } } // Compute area while (stack.Count > 0 && histogram[stack.Peek()] >= histogram[col]) { var area = histogram[stack.Pop()] * (stack.Count == 0 ? col : (col - stack.Peek() - 1)); result = Math.Max(result, area); } stack.Push(col); } } return result; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
6
0
0
1
0
C# || How To Find The Largest Component Size By Common Factor Using C#
The following is a module with functions which demonstrates how to find the largest component size by common factor using C#.
1. Largest Component Size – Problem Statement
You are given an integer array of unique positive integers nums. Consider the following graph:
- There are nums.length nodes, labeled nums[0] to nums[nums.length – 1],
- There is an undirected edge between nums[i] and nums[j] if nums[i] and nums[j] share a common factor greater than 1.
Return the size of the largest connected component in the graph.
Example 1:
Input: nums = [4,6,15,35]
Output: 4
Example 2:
Input: nums = [20,50,9,63]
Output: 2
Example 3:
Input: nums = [2,3,6,7,4,12,21,39]
Output: 8
2. Largest Component Size – Solution
The following is a solution which demonstrates how to find the largest component size by common factor.
The following solution uses a union find set to group connections together.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
// ============================================================================ // Author: Kenneth Perkins // Date: Nov 28, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find largest common factor // ============================================================================ public class Solution { public int LargestComponentSize(int[] nums) { var set = new UnionFindSet(nums.Max() + 1); // Calculate primes set for all elements foreach (var num in nums) { for (var k = 2; k * k <= num; ++k) { if (num % k == 0) { set.Union(num, k); set.Union(num, num / k); } } } // Count the apperance of parents, return the maxium one. // All connected nodes will point to same parent var map = new Dictionary<int, int>(); var result = 1; foreach (var num in nums) { var count = set.Find(num); map[count] = (map.ContainsKey(count) ? map[count] : 0) + 1; result = Math.Max(result, map[count]); } return result; } public class UnionFindSet { private int[] parent; public UnionFindSet(int size) { parent = new int[size]; for (int i = 0; i < parent.Length; ++i) { parent[i] = i; } } public void Union(int x, int y) { parent[Find(x)] = parent[Find(y)]; } public int Find(int x) { if (parent[x] != x) { parent[x] = Find(parent[x]); } return parent[x]; } } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
4
2
8
C# || Accounts Merge – How To Merge A List Of Emails Using C#
The following is a module with functions which demonstrates how to merge a list of emails using C#.
1. Accounts Merge – Problem Statement
Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.
Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.
After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.
Example 1:
Input: accounts = [["John","[email protected]","[email protected]"],["John","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]
Output: [["John","[email protected]","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]
Explanation:
The first and second John's are the same person as they have the common email "[email protected]".
The third John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', '[email protected]'], ['John', '[email protected]'],
['John', '[email protected]', '[email protected]', '[email protected]']] would still be accepted.
Example 2:
Input: accounts = [["Gabe","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Ethan","Ethan5[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]
Output: [["Ethan","[email protected]","[email protected]","[email protected]"],["Gabe","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]
2. Accounts Merge – Solution
The following is a solution which demonstrates how to merge a list of emails.
The following solution uses a union find set to group accounts with matching emails together.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
// ============================================================================ // Author: Kenneth Perkins // Date: Nov 28, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to merge a list of emails // ============================================================================ public class Solution { public IList<IList<string>> AccountsMerge(IList<IList<string>> accounts) { var set = new UnionFindSet(accounts.Count); // Map email to their component index var emailComponents = new Dictionary<string, int>(); for (int i = 0; i < accounts.Count; ++i) { var account = accounts[i]; for (int j = 1; j < account.Count; ++j) { var email = account[j]; // Assign component group as the account index var group = i; if (!emailComponents.ContainsKey(email)) { emailComponents[email] = group; } else { // Union this group with the previous group of the email set.Union(group, emailComponents[email]); } } } // Store emails corresponding to the components parent var emailGroups = new Dictionary<int, List<string>>(); foreach (var email in emailComponents.Keys) { var group = emailComponents[email]; var groupParent = set.Find(group); if (!emailGroups.ContainsKey(groupParent)) { emailGroups[groupParent] = new List<string>(); } emailGroups[groupParent].Add(email); } // Sort the emails and add the account name var result = new List<IList<string>>(); foreach (var group in emailGroups.Keys) { var emails = emailGroups[group]; emails.Sort(StringComparer.Ordinal); emails.Insert(0, accounts[group][0]); result.Add(emails); } return result; } public class UnionFindSet { int[] parent; int[] size; public UnionFindSet(int count) { parent = new int[count]; size = new int[count]; for (int index = 0; index < count; ++index) { parent[index] = index; size[index] = 1; } } public int Find(int x) { if (parent[x] != x) { parent[x] = Find(parent[x]); } return parent[x]; } public void Union(int x, int y) { var parentX = Find(x); var parentY = Find(y); if (parentX == parentY) { return; } if (size[parentX] >= size[parentY]) { size[parentX] += size[parentY]; parent[parentY] = parentX; } else { size[parentY] += size[parentX]; parent[parentX] = parentY; } } } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
[["John","[email protected]","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]
[["Gabe","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Ethan","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]
