Posts

Mapping a Tree to a HashTable data structure

-
Image
I think a HashTable (of a HashSet) is a very convenient way to represent a tree. It gives you instant access to any element of the tree if there is a unique id representing each node. The problem (and code) below exemplifies this point. Once the representation is there, performing a Depth-First Search becomes very trivial. Code is down below, cheers, ACC. Kill Process - LeetCode You have  n  processes forming a rooted tree structure. You are given two integer arrays  pid  and  ppid , where  pid[i]  is the ID of the  i th  process and  ppid[i]  is the ID of the  i th  process's parent process. Each process has only  one parent process  but may have multiple children processes. Only one process has  ppid[i] = 0 , which means this process has  no parent process  (the root of the tree). When a process is  killed , all of its children processes will also be killed. Given an integer  kill ...
Post a Comment
Read more

Binary Search to Find Next Greater Element V

-
You can use the .BinarySearch method of List<T>. It works well, there is a bit of a trick that you need to do when the return index is negative (just assign it to its complement, ~index). No need to perform the Binary Search "by hand" anymore. Achieves a good NLogN, fast solution. LC suggests a Tree to be used but this approach (two lists, one for even, one for odd) works well. Code is down below, cheers, ACC. Count Smaller Elements With Opposite Parity - LeetCode You are given an integer array  nums  of length  n . The  score  of an index  i  is defined as the number of indices  j  such that: i < j < n nums[j] < nums[i] nums[i]  and  nums[j]  have different parity (one is even and the other is odd). Return an integer array  answer  of length  n , where  answer[i]  is the score of index  i .   Example 1: Input:   nums = [5,2,4,1,3] Output:   [2,1,2,0,0] Explanation: Fo...
Post a Comment
Read more