October 30, 2021 – My Programming Notes

Daily Archives: October 30, 2021

C# || How To Flatten A Multilevel Doubly Linked List Using C#

October 30, 2021 admin No comments

The following is a module with functions which demonstrates how to flatten a doubly linked list using C#.

1. Flatten – Problem Statement

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] Output: [1,2,3,7,8,11,12,9,10,4,5,6] Explanation:
The multilevel linked list in the input is as follows:

After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3] Output: [1,3,2] Explanation:
The input multilevel linked list is as follows:
1---2---NULL | 3---NULL

Example 3:

Input: head = [] Output: []

2. Flatten – Solution

The following are two solutions which demonstrates how to flatten a doubly linked list.

Iterative





		
		
			2. Flatten Iterative - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to flatten a doubly linked list
// ============================================================================
/*
// Definition for a Node.
public class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}
*/
public class Solution {
    public Node Flatten(Node head) {
        var current = head;
        var stack = new Stack<Node>();

        // Loop through nodes
        while (current != null) {

            // Check to see if node has child
            if (current.child != null) {
                // If current node has a next node, save to stack
                // so we can reconnect it to the tail
                // of the child node later
                if (current.next != null) {
                    stack.Push(current.next);
                }

                // Set the next node as the child,
                // we will now iterate down this path
                current.next = current.child;

                // Set the previous node as the current
                current.next.prev = current;

                // Set child to null
                current.child = null;

            } else if (current.next == null) {
                // Reconnect node at the top of the
                // stack to the tail child node
                if (stack.Count > 0) {
                    // Set the next node as the reconnected node,
                    // we will now iterate down this path
                    current.next = stack.Pop();
                    current.next.prev = current;
                }
            }
            current = current.next;
        }

        return head;
    }
}// http://programmingnotes.org/
			
				
					
				
					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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to flatten a doubly linked list
// ============================================================================
/*
// Definition for a Node.
public class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}
*/
public class Solution {
    public Node Flatten(Node head) {
        var current = head;
        var stack = new Stack<Node>();
 
        // Loop through nodes
        while (current != null) {
 
            // Check to see if node has child
            if (current.child != null) {
                // If current node has a next node, save to stack
                // so we can reconnect it to the tail
                // of the child node later
                if (current.next != null) {
                    stack.Push(current.next);
                }
 
                // Set the next node as the child,
                // we will now iterate down this path
                current.next = current.child;
 
                // Set the previous node as the current
                current.next.prev = current;
 
                // Set child to null
                current.child = null;
 
            } else if (current.next == null) {
                // Reconnect node at the top of the
                // stack to the tail child node
                if (stack.Count > 0) {
                    // Set the next node as the reconnected node,
                    // we will now iterate down this path
                    current.next = stack.Pop();
                    current.next.prev = current;
                }
            }
            current = current.next;
        }
 
        return head;
    }
}// http://programmingnotes.org/

Recursive





		
		
			2. Flatten Recursive - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to flatten a doubly linked list
// ============================================================================
/*
// Definition for a Node.
public class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}
*/
public class Solution {
    public Node Flatten(Node head) {
        Flatten(head, null);
        return head;
    }

    private Node Flatten(Node current, Node previous) {
        if (current == null) {
            return previous;
        }

        // If previous node exists, set the next and previous values
        if (previous != null) {
            previous.next = current;
            current.prev = previous;
        }

        // Save the next node so we can reconnect it to the tail
        // of the child node later
        var next = current.next;

        // Traverse down child path.
        // If children exist, this returns the last child for the current node
        var tail = Flatten(current.child, current);

        // Child path has been explored, set to null
        current.child = null;

        // Reconnect the next node to the tail child node
        return Flatten(next, tail);
    }
}// http://programmingnotes.org/
			
				
					
				
					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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to flatten a doubly linked list
// ============================================================================
/*
// Definition for a Node.
public class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}
*/
public class Solution {
    public Node Flatten(Node head) {
        Flatten(head, null);
        return head;
    }
 
    private Node Flatten(Node current, Node previous) {
        if (current == null) {
            return previous;
        }
 
        // If previous node exists, set the next and previous values
        if (previous != null) {
            previous.next = current;
            current.prev = previous;
        }
 
        // Save the next node so we can reconnect it to the tail
        // of the child node later
        var next = current.next;
 
        // Traverse down child path.
        // If children exist, this returns the last child for the current node
        var tail = Flatten(current.child, current);
 
        // Child path has been explored, set to null
        current.child = null;
 
        // Reconnect the next node to the tail child node
        return Flatten(next, tail);
    }
}// 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,7,8,11,12,9,10,4,5,6] [1,3,2] []

C# || How To Traverse Binary Tree Zigzag Level Order Using C#

October 30, 2021 admin No comments

The following is a module with functions which demonstrates how to traverse binary tree zigzag level order using C#.

1. Zigzag Level Order – Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1] Output: [[1]]

Example 3:

Input: root = [] Output: []

2. Zigzag Level Order – Solution

The following is a solution which demonstrates how to traverse binary tree zigzag level order.

This solution uses Breadth First Search to explore items at each level.





		
		
			2. Zigzag Level Order - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 29, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to traverse a tree zigzag 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 {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        var stack = new Stack<TreeNode>();

        // Add root to stack
        if (root != null) {
            stack.Push(root);
        }

        var leftToRight = true;
        while (stack.Count > 0) {
            var queue = new Queue<TreeNode>();
            var level = new List<int>();

            // Add items at the top of the stack to the current level
            for (var itemCount = stack.Count; itemCount > 0; --itemCount) {
                var current = stack.Peek();
                stack.Pop();

                level.Add(current.val);
                queue.Enqueue(current);
            }

            // Add level to result
            result.Add(level);

            // Go through items in the queue and add them to the stack in the proper order
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Peek();
                queue.Dequeue();

                // Add children to the stack
                // Left to right or Right to left order
                if (leftToRight) {
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                } else {
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                }
            }
            // Alternate order for the next level
            leftToRight = !leftToRight;
        }
        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 29, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to traverse a tree zigzag 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 {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        var stack = new Stack<TreeNode>();
 
        // Add root to stack
        if (root != null) {
            stack.Push(root);
        }
 
        var leftToRight = true;
        while (stack.Count > 0) {
            var queue = new Queue<TreeNode>();
            var level = new List<int>();
 
            // Add items at the top of the stack to the current level
            for (var itemCount = stack.Count; itemCount > 0; --itemCount) {
                var current = stack.Peek();
                stack.Pop();
 
                level.Add(current.val);
                queue.Enqueue(current);
            }
 
            // Add level to result
            result.Add(level);
 
            // Go through items in the queue and add them to the stack in the proper order
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Peek();
                queue.Dequeue();
 
                // Add children to the stack
                // Left to right or Right to left order
                if (leftToRight) {
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                } else {
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                }
            }
            // Alternate order for the next level
            leftToRight = !leftToRight;
        }
        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:

[[3],[20,9],[15,7]] [[1]] []

C# || How To Find Longest Duplicate Substring Using C#

October 30, 2021 admin No comments

The following is a module with functions which demonstrates how to find the longest duplicate substring using C#.

1. Longest Dup Substring – Problem Statement

Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is “”.

Example 1:

Input: s = "banana" Output: "ana"

Example 2:

Input: s = "abcd" Output: ""

2. Longest Dup Substring – Solution

The following is a solution which demonstrates how find the longest duplicate substring.

This solution uses Binary Search and Rolling Hash.





		
		
			2. Longest Dup Substring - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the longest duplicate substring
// ============================================================================
public class Solution {
    public string LongestDupSubstring(string s) {
        // Convert string to array of ascii integers
        // to implement constant time slice
        var nums = new int[s.Length];
        for (int index = 0; index < s.Length; ++index) {
            nums[index] = (int)s[index] - (int)'a';
        }

        // Keeps track of substring start index and length
        var startIndex = -1;
        var substrLength = -1;

        // Use binary search to find the largest possible length of a duplicate substring
        var left = 1;
        var right = s.Length;
        while (left < right) {
            var mid = left + (right - left) / 2;

            // Rolling hash (Rabin-Karp)
            var index = RollingSearch(nums, mid);

            // Substring found
            if (index != -1) {
                if (mid > substrLength) {
                    startIndex = index;
                    substrLength = mid;
                }
                left = mid + 1;

            // Substring not found
            } else {
               right = mid;
            }
        }
        return substrLength != -1 ? s.Substring(startIndex, substrLength): "";
    }

    private int RollingSearch(int[] nums, int mid) {
        var seen = new HashSet<long>();

        // Base value for the rolling hash function
        var a = 31;

        // Current hash
        var hash = Hash(nums, mid, a);

        seen.Add(hash);

        long pow = 1;
        for (var index = 1; index < mid; ++index) {
            pow *= a;
        }

        var result = -1;
        for (var index = 1; index < nums.Length - mid + 1; ++index) {
            // Compute rolling hash
            hash = RollingHash(pow, hash, nums[index - 1], nums[index + mid - 1], a);

            // Hash found
            if (seen.Contains(hash)) {
                result = index;
                break;
            }
            // Hash not found
            seen.Add(hash);
        }
        return result;
    }

    private long Hash(int[] nums, int mid, int a) {
        long h = 0;
        long aL = 1;
        for (var index = mid; index >= 1; --index) {
            h += (nums[index - 1] + 1) * aL;
            aL *= a;
        }
        return h;
    }

    private long RollingHash(long pow, long hash, int left, int right, int a) {
        return (hash - (left + 1) * pow) * a + (right + 1);
    }
}// http://programmingnotes.org/
			
				
					
				
					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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the longest duplicate substring
// ============================================================================
public class Solution {
    public string LongestDupSubstring(string s) {
        // Convert string to array of ascii integers
        // to implement constant time slice
        var nums = new int[s.Length];
        for (int index = 0; index < s.Length; ++index) {
            nums[index] = (int)s[index] - (int)'a';
        }
 
        // Keeps track of substring start index and length
        var startIndex = -1;
        var substrLength = -1;
 
        // Use binary search to find the largest possible length of a duplicate substring
        var left = 1;
        var right = s.Length;
        while (left < right) {
            var mid = left + (right - left) / 2;
 
            // Rolling hash (Rabin-Karp)
            var index = RollingSearch(nums, mid);
 
            // Substring found
            if (index != -1) {
                if (mid > substrLength) {
                    startIndex = index;
                    substrLength = mid;
                }
                left = mid + 1;
 
            // Substring not found
            } else {
               right = mid;
            }
        }
        return substrLength != -1 ? s.Substring(startIndex, substrLength): "";
    }
 
    private int RollingSearch(int[] nums, int mid) {
        var seen = new HashSet<long>();
 
        // Base value for the rolling hash function
        var a = 31;
 
        // Current hash
        var hash = Hash(nums, mid, a);
 
        seen.Add(hash);
 
        long pow = 1;
        for (var index = 1; index < mid; ++index) {
            pow *= a;
        }
 
        var result = -1;
        for (var index = 1; index < nums.Length - mid + 1; ++index) {
            // Compute rolling hash
            hash = RollingHash(pow, hash, nums[index - 1], nums[index + mid - 1], a);
 
            // Hash found
            if (seen.Contains(hash)) {
                result = index;
                break;
            }
            // Hash not found
            seen.Add(hash);
        }
        return result;
    }
 
    private long Hash(int[] nums, int mid, int a) {
        long h = 0;
        long aL = 1;
        for (var index = mid; index >= 1; --index) {
            h += (nums[index - 1] + 1) * aL;
            aL *= a;
        }
        return h;
    }
 
    private long RollingHash(long pow, long hash, int left, int right, int a) {
        return (hash - (left + 1) * pow) * a + (right + 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:

"ana" ""

C# || Group Anagrams – How To Group Array Of Anagrams Using C#

October 30, 2021 admin No comments

The following is a module with functions which demonstrates how to group an array of anagrams using C#.

1. Group Anagrams – Problem Statement

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""] Output: [[""]]

Example 3:

Input: strs = ["a"] Output: [["a"]]

2. Group Anagrams – Solution

The following is a solution which demonstrates how to group an array of anagrams.

The idea of this solution is to generate a simple hash key for each anagram.

The hash key is made up consisting of a digit, and a letter. These two values represents the character count, and the letter found in the given string.

For example, given the input ["eat","tea","tan","ate","nat","bat"] we create a hash for each anagram as follows:

anagram: eat, hash: 1a1e1t anagram: tea, hash: 1a1e1t anagram: tan, hash: 1a1n1t anagram: ate, hash: 1a1e1t anagram: nat, hash: 1a1n1t anagram: bat, hash: 1a1b1t

The hash key is generated similar to the counting sort technique. We use this hash to group the anagrams together.





		
		
			2. Group Anagrams - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to group anagrams
// ============================================================================
public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var result = new List<IList<string>>();
        var seen = new Dictionary<string, List<string>>();

        // Go through the anagrams
        foreach (var anagram in strs) {
            // Create a hash for this anagram
            var hash = Hash(anagram);

            // Check if this hash key exists
            if (!seen.ContainsKey(hash)) {
                seen[hash] = new List<string>();
            }

            // Add anagram to matching bucket
            seen[hash].Add(anagram);
        }

        // Build result
        foreach (var pair in seen) {
            result.Add(pair.Value);
        }

        return result;
    }

    private string Hash(string input) {
        var alphabet = new int[26];
        foreach (var ch in input) {
            ++alphabet[ch - 'a'];
        }
        var sb = new StringBuilder();
        for (int position = 0; position < alphabet.Length; ++position) {
            if (alphabet[position] > 0) {
                sb.Append(alphabet[position]);
                sb.Append((char)('a' + position));
            }
        }
        return sb.ToString();
    }
}// http://programmingnotes.org/
			
				
					
				
					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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to group anagrams
// ============================================================================
public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var result = new List<IList<string>>();
        var seen = new Dictionary<string, List<string>>();
 
        // Go through the anagrams
        foreach (var anagram in strs) {
            // Create a hash for this anagram
            var hash = Hash(anagram);
 
            // Check if this hash key exists
            if (!seen.ContainsKey(hash)) {
                seen[hash] = new List<string>();
            }
 
            // Add anagram to matching bucket
            seen[hash].Add(anagram);
        }
 
        // Build result
        foreach (var pair in seen) {
            result.Add(pair.Value);
        }
 
        return result;
    }
 
    private string Hash(string input) {
        var alphabet = new int[26];
        foreach (var ch in input) {
            ++alphabet[ch - 'a'];
        }
        var sb = new StringBuilder();
        for (int position = 0; position < alphabet.Length; ++position) {
            if (alphabet[position] > 0) {
                sb.Append(alphabet[position]);
                sb.Append((char)('a' + position));
            }
        }
        return sb.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:

[["eat","tea","ate"],["tan","nat"],["bat"]] [[""]] [["a"]]

Daily Archives: October 30, 2021

C# || How To Flatten A Multilevel Doubly Linked List Using C#

C# || How To Traverse Binary Tree Zigzag Level Order Using C#

C# || How To Find Longest Duplicate Substring Using C#

C# || Group Anagrams – How To Group Array Of Anagrams Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories