Daily Archives: October 20, 2021
C# || How To Implement RandomizedSet – Insert Delete GetRandom O(1) Using C#
The following is a module with functions which demonstrates how to implement RandomizedSet – Insert Delete GetRandom O(1) using C#.
1. RandomizedSet – Problem Statement
Implement the RandomizedSet class:
- RandomizedSet() Initializes the RandomizedSet object.
- bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
- bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
- int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in average O(1) time complexity.
Example 1:
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
2. RandomizedSet – Solution
The following is a solution which demonstrates how to implement RandomizedSet – Insert Delete GetRandom O(1).
The main idea of this solution is to use a list to store the values added, and use a map to determine if an item has been added already.
The map is also used to store the list index of the added item. This makes it so we know which index to work with when we want to remove an item from the list.
To ensure proper removal, we ‘swap’ places of the value to remove with the last item in the list. This makes it so only the last item in the list is always the index to have items removed from.
|
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 |
// ============================================================================ // Author: Kenneth Perkins // Date: Oct 20, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to implement RandomizedSet // ============================================================================ public class RandomizedSet { // For randomizing the list private Random r; // To determine if an item has been added, and store its list index private Dictionary<int, int> map; // To store the items added private List<int> values; public RandomizedSet() { r = new Random(); map = new Dictionary<int, int>(); values = new List<int>(); } // Inserts a value to the set. Returns true if the set did not already contain the specified element public bool Insert(int val) { // Determine if item exists in map if (map.ContainsKey(val)) { return false; } // Add value to the list values.Add(val); // Save the value with its list index to the map map[val] = values.Count - 1; return true; } // Removes a value from the set. Returns true if the set contained the specified element public bool Remove(int val) { // Determine if item exists in map if (!map.ContainsKey(val)) { return false; } // Get the current index for the item to remove var currentIndex = map[val]; // Get the last index for the item at the end var lastIndex = values.Count - 1; // 'Swap' places of the last item in the list with the item to be removed values[currentIndex] = values[lastIndex]; // Update the map for the item that we 'swapped' with its new list index map[values[currentIndex]] = currentIndex; // Remove the swapped item from the list (this is the item to be removed) values.RemoveAt(lastIndex); // Remove the item to be removed from the map map.Remove(val); return true; } // Get a random element from the set public int GetRandom() { var randomIndex = r.Next(0, values.Count); return values[randomIndex]; } }// 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:
[null,true,false,true,1,true,false,2]
C# || How To Determine Whether A Binary Tree Is A Symmetric Tree Using C#
The following is a module with functions which demonstrates how to determine whether a binary tree is a symmetric tree using C#.
1. Is Symmetric – Problem Statement
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: false
2. Is Symmetric – Solution
The following is a solution which demonstrates how to determine whether a binary tree is a symmetric tree.
For two trees to be mirror images, the following three conditions must be true:
• 1 - Their root node's key must be same
• 2 - The left subtree of left tree and right subtree of right tree have to be mirror images
• 3 - The right subtree of left tree and left subtree of right tree have to be mirror images
|
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: Oct 20, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Determines whether a binary tree is a symmetric tree // ============================================================================ /** * 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 bool IsSymmetric(TreeNode root) { return IsMirror(root, root); } private bool IsMirror(TreeNode a, TreeNode b) { if (a == null && b == null) { return true; } if (a == null || b == null) { return false; } // 1. The two root nodes have the same value // 2. The left subtree of one root node is a mirror // reflection of the right subtree of the other root node // 3. The right subtree of one root node is a mirror // reflection of the left subtree of the other root node return a.val == b.val && IsMirror(a.left, b.right) && IsMirror(a.right, b.left); } }// 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
false
C# || How To Traverse Bottom Up Binary Tree Level Order Using C#
The following is a module with functions which demonstrates how to traverse bottom up binary tree level order using C#.
1. Level Order Bottom – Problem Statement
Given the root of a binary tree, return the bottom-up level order traversal of its nodes’ values. (i.e., from left to right, level by level from leaf to root).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
2. Level Order Bottom – Solution
The following is a solution which demonstrates how to traverse bottom up binary tree level order.
The idea of this solution is to have a result list which keeps track of the items found on each level. A variable is also used to keep track of the maximum depth levels in the tree. The max depth level is used to insert node values into their appropriate result list slot.
|
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: Oct 20, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Determines how to traverse a tree bottom up level order // ============================================================================ /** * 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 { private List<IList<int>> result = new List<IList<int>>(); private int maxDepth = 0; public IList<IList<int>> LevelOrderBottom(TreeNode root) { Traverse(root, 0); return result; } private void Traverse(TreeNode node, int depth) { if (node == null) { return; } // Keep track of max depth level if (depth > maxDepth) { maxDepth = depth; } // Determine if new depth level should be added to the result list // Add the new level to the start of the result list if (result.Count == depth) { result.Insert(0, new List<int>()); } // Add the current node value to the corresponding result level index result[maxDepth - depth].Add(node.val); // Keep exploring left and right nodes Traverse(node.left, depth + 1); Traverse(node.right, depth + 1); } }// 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:
[[15,7],[9,20],[3]]
[[1]]
[]
C# || How To Get The Sum Of Binary Tree Nodes With Even Valued Grandparents Using C#
The following is a module with functions which demonstrates how to get the sum of binary tree nodes with even valued grandparents using C#.
1. Sum Even Grandparent – Problem Statement
Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.
A grandparent of a node is the parent of its parent if it exists.
Example 1:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.
Example 2:
Input: root = [1]
Output: 0
2. Sum Even Grandparent – Solution
The following is a solution which demonstrates how to get the sum of binary tree nodes with even valued grandparents.
The idea of this solution is to simply traverse the tree, and for each recursive call, we keep track of the parent node and the grandparent node of each node.
If a node has a grandparent, we check to see if it is an even number. If it is, the result is incremented.
|
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 |
// ============================================================================ // Author: Kenneth Perkins // Date: Oct 20, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Determines how to get the sum of even valued tree grandparents // ============================================================================ /** * 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 { private int result = 0; public int SumEvenGrandparent(TreeNode root) { Traverse(root, null, null); return result; } private void Traverse(TreeNode node, TreeNode parent, TreeNode grandParent) { if (node == null) { return; } // If a grandparent exists and its an even number, // add the current node value to the result if (grandParent != null && grandParent.val % 2 == 0) { result += node.val; } // Keep exploring left & right nodes // setting the current node as the parent // and the current parent node as the grandparent Traverse(node.left, node, parent); Traverse(node.right, node, parent); } }// 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:
18
0
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
