[Uber][LeetCode] Employee Importance

Problem: You have a data structure of employee information, including the employee's unique ID, importance value, and direct subordinates' IDs.

You are given an array of employees employees where:

• employees[i].id is the ID of the ith employee.
• employees[i].importance is the importance value of the ith employee.
• employees[i].subordinates is a list of the IDs of the direct subordinates of the ith employee.

Given an integer id that represents an employee's ID, return the total importance value of this employee and all their direct and indirect subordinates.

Example:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

Input: employees = [[1,2,[5]],[5,-3,[]]], id = 5
Output: -3
Explanation: Employee 5 has an importance value of -3 and has no direct subordinates.
Thus, the total importance value of employee 5 is -3.

Constraints:

• 1 <= employees.length <= 2000
• 1 <= employees[i].id <= 2000
• All employees[i].id are unique.
• -100 <= employees[i].importance <= 100
• One employee has at most one direct leader and may have several subordinates.
• The IDs in employees[i].subordinates are valid IDs.

Approach: If we look closely it is kind of a tree problem. We are given the node of the tree and we need to get the sum of all the values of the nodes of the subtree whose root is given input node. 

We can build a tree using the given info and then we can simply apply DFS / preorder traversal to get the sum of the importance of all the nodes of the subtree.

Implementation in C#:

/*

// Definition for Employee.

class Employee {

    public int id;

    public int importance;

    public IList<int> subordinates;

}

*/

public class EmployeeValue

{

    public int Importance { get; set; }

    public IList<int> Children { get; set; }

    

    public EmployeeValue(int importance, IList<int> children)

    {

        this.Importance = importance;

        this.Children = children;

    }

}

class Solution 

{

    public int GetImportance(IList<Employee> employees, int id) 

    {

        var employeeTree = this.BuildEmployeeTree(employees);

        return this.GetImportanceHelper(employeeTree, id);

    }

    

    private int GetImportanceHelper(Dictionary<int, EmployeeValue> employeeTree, int currId)

    {

        int totalImportance = employeeTree[currId].Importance;

        foreach (int id in employeeTree[currId].Children)

        {

            totalImportance += this.GetImportanceHelper(employeeTree, id);

        }

        return totalImportance;

    }

    

    private Dictionary<int, EmployeeValue> BuildEmployeeTree(IList<Employee> employees)

    {

        var tree = new Dictionary<int, EmployeeValue>();

        foreach(var employee in employees)

        {

            tree[employee.id] = new EmployeeValue(employee.importance, employee.subordinates);

        }

        return tree;

    }

}

Complexity: O(n) where n is the length of the employees list.

[Flipkart][LeetCode] Cheapest Flights Within K Stops

Problem: There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

Approach: We can use BFS here with little modifications:

1. Number of levels will be limited by k.
2. Can visit the same node multiple times.

We can then put an optimization here which is we will revisit the same node again only if the price of current visit is less than of the price of previous visit. 

Implementation in C#:

public class GraphLink

{

    public int Node { get; set; }

    public int Price { get; set; }

    public GraphLink(int node, int price)

    {

        this.Node = node;

        this.Price = price;

    }

}

public class QueueElement

{

    public int Node {get; set;}

    public int Price {get; set;}

    public QueueElement(int node, int price)

    {

        this.Node = node;

        this.Price = price;

    }

}

public class Solution {

    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) 

    {

        int length = flights?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }        

        var graph = this.BuildGraph(n, flights);

        int stops = 0;

        Queue<QueueElement> queue = new Queue<QueueElement>();

        queue.Enqueue(new QueueElement(src, 0));

        int[] prices = new int[n];

        Array.Fill(prices, int.MaxValue);

        while (stops <= k && queue.Count > 0)

        {

            int size = queue.Count;

            for (int i = 0; i < size; ++i)

            {

                QueueElement elem = queue.Dequeue();

                if (graph[elem.Node] == null)

                {

                    continue;

                }

                int currPrice = elem.Price;

                foreach (var link in graph[elem.Node])

                {

                    int nextPrice = currPrice + link.Price;

                    if (nextPrice >= prices[link.Node])

                    {

                        continue;

                    }

                    prices[link.Node] = nextPrice;

                    queue.Enqueue(new QueueElement(link.Node, nextPrice));

                }

            }

            ++stops;

        }

        return prices[dst] == int.MaxValue ? -1 : prices[dst];

    }

    

    private List<GraphLink>[] BuildGraph(int n, int[][] flights)

    {

        List<GraphLink>[] graph = new List<GraphLink>[n];

        foreach (var flight in flights)

        {

            if (graph[flight[0]] == null)

            {

                graph[flight[0]] = new List<GraphLink>();

            }

            graph[flight[0]].Add(new GraphLink(flight[1], flight[2]));

        }

        return graph;

    }

}

Complexity: (n + m + m * k) where m is the length of flights which is basically number of edges in the graph.

[Flipkart][LeetCode] Number of Visible People in a Queue

Problem: There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the ith person.

A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]).

Return an array answer of length n where answer[i] is the number of people the ith person can see to their right in the queue.

Example:

Input: heights = [10,6,8,5,11,9]
Output: [3,1,2,1,1,0]
Explanation:
Person 0 can see person 1, 2, and 4.
Person 1 can see person 2.
Person 2 can see person 3 and 4.
Person 3 can see person 4.
Person 4 can see person 5.
Person 5 can see no one since nobody is to the right of them.

Input: heights = [5,1,2,3,10]
Output: [4,1,1,1,0]

Approach: We maintain a stack in descending order. We iterate through every element of the input array and check with the top of the stack say 'a', if we found current element is greater than 'a' then we can safely say that 'a' can see current element so we increase the number of element 'a' can see but as we can see that current element greater than 'a', 'a' can't see beyond current element so we can safely pop the top of the stack.

Implementation in C#:

    public int[] CanSeePersonsCount(int[] heights) 

    {

        int length = heights.Length;

        int[] result = new int[length];

        Stack<int> stack = new Stack<int>();

        for (int i = 0; i < length; ++i)

        {

            while (stack.Count > 0 && heights[i] > heights[stack.Peek()])

            {

                ++result[stack.Pop()];

            }

            if (stack.Count > 0)

            {

                ++result[stack.Peek()];

            }

            stack.Push(i);

        }

        return result;

    }

Complexity: O(n)

[Uber][LeetCode] Reverse Pairs

Problem: Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where:

• 0 <= i < j < nums.length and
• nums[i] > 2 * nums[j].

Example:

Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1

Approach: We can use Merge sort approach here. The only change which we need to make is while merging the two (left and right) sorted array we can check how many reverse pair are there.

 

Implementation in C#:

    public int ReversePairs(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        return this.CountReversePairs(nums, 0, length - 1);

    }

    private int CountReversePairs(int[] nums, int left, int right)

    {

        if (left >= right)

        {

            return 0;

        }

        int mid = left + (right - left) / 2;

        int leftRevCount = this.CountReversePairs(nums, left, mid);

        int rightRevCount = this.CountReversePairs(nums, mid + 1, right);

        int mergeRevCount = this.Merge(nums, left, mid, right);

        return leftRevCount + rightRevCount + mergeRevCount;

    }

    private int Merge(int[] nums, int left, int mid, int right)

    {

        int i = left;

        int j = mid + 1;

        var temp = new List<int>();

        int revPairsCount = this.GetReversPairs(nums, left, mid, right);

        while (i <= mid && j <= right)

        {

            if (nums[i] > nums[j])

            {

                temp.Add(nums[j++]);

            }

            else

            {

                temp.Add(nums[i++]);

            }

        }

        while (i <= mid)

        {

            temp.Add(nums[i++]);

        }

        while (j <= right)

        {

            temp.Add(nums[j++]);

        }

        i = left;

        for (j = 0; j < temp.Count; ++j)

        {

            nums[i++] = temp[j];

        }

        return revPairsCount;

    }

    private int GetReversPairs(int[] nums, int left, int mid, int right)

    {

        int j = mid + 1;

        int revPairsCount = 0;

        for (int i = left; i <= mid; ++i)

        {

            while (j <= right && nums[i] > (long)(2 * (long)nums[j]))

            {

                ++j;

            }

            revPairsCount += (j - (mid + 1));

        }

        return revPairsCount;

    }

Complexity: O(nlogn)

[Uber][LeetCode] Flatten Nested List Iterator

Problem: You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList

res = []

while iterator.hasNext()

    append iterator.next() to the end of res

return res

If res matches the expected flattened list, then your code will be judged as correct.

Example:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Approach: We will flatten the list using DFS in an additional DS like Queue and then just return it from that Queue when HasNext or Next is called.

Implementation in C#:

/**

 * // This is the interface that allows for creating nested lists.

 * // You should not implement it, or speculate about its implementation

 * interface NestedInteger {

 *

 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.

 *     bool IsInteger();

 *

 *     // @return the single integer that this NestedInteger holds, if it holds a single integer

 *     // Return null if this NestedInteger holds a nested list

 *     int GetInteger();

 *

 *     // @return the nested list that this NestedInteger holds, if it holds a nested list

 *     // Return null if this NestedInteger holds a single integer

 *     IList<NestedInteger> GetList();

 * }

 */

public class NestedIterator 

{

    public NestedIterator(IList<NestedInteger> nestedList) {

        this.queue = new Queue<int>();

        foreach (NestedInteger integer in nestedList)

        {

            this.FillQueue(integer);

        }

    }

    public bool HasNext() 

    {

        return queue.Count > 0;

    }

    public int Next() 

    {

        return this.HasNext() ? queue.Dequeue() : -1;

    }

    

    private void FillQueue(NestedInteger nestedInteger)

    {

        if (nestedInteger.IsInteger())

        {

            this.queue.Enqueue(nestedInteger.GetInteger());

        }

        else

        {

            IList<NestedInteger> list = nestedInteger.GetList();

            foreach (NestedInteger integer in list)

            {

                this.FillQueue(integer);

            }

        }

    }

    

    private Queue<int> queue; 

}

Complexity: O(n)

[LeetCode] Longest Happy String

Problem: A string s is called happy if it satisfies the following conditions:

• s only contains the letters 'a', 'b', and 'c'.
• s does not contain any of "aaa", "bbb", or "ccc" as a substring.
• s contains at most a occurrences of the letter 'a'.
• s contains at most b occurrences of the letter 'b'.
• s contains at most c occurrences of the letter 'c'.

Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "".

A substring is a contiguous sequence of characters within a string.

Example:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It is the only correct answer in this case.

Constraints:

• 0 <= a, b, c <= 100
• a + b + c > 0

Approach: I am using a simple greedy approach. The intuition is simple; let's say we want to put 'a' in the result "s". We can only do that in case of the number of a's remaining are more than number of 'b' and 'c' and we haven't put 'a' 2 times continuously already in the "s". The other condition could be if 'b' or 'c' are already put continuously 2 times.

The same condition can be applied for when we try to put 'b' or 'c'. That's all about the approach. Look at the implementation for more understanding.

Implementation in C#:

    public string LongestDiverseString(int a, int b, int c) 

    {

        StringBuilder sb = new StringBuilder();

        int total = a + b + c;

        int currACount = 0, currBCount = 0, currCCount = 0;

        while(total > 0)

        {

            if ((a >= b && a >= c && currACount < 2) || 

                (a > 0 && (currBCount == 2 || currCCount == 2)))

            {

                sb.Append('a');

                --a;

                currBCount = 0;

                currCCount = 0;

                ++currACount;

            }

            

            else if ((b >= a && b >= c && currBCount < 2) || 

                     (b > 0 && (currACount == 2 || currCCount == 2)))

            {

                sb.Append('b');

                --b;

                currACount = 0;

                currCCount = 0;

                ++currBCount;

            }

            else if ((c >= a && c >= b && currCCount < 2) || 

                     (c > 0 && (currACount == 2 || currBCount == 2)))

            {

                sb.Append('c');

                --c;

                currACount = 0;

                currBCount = 0;

                ++currCCount;

            }

            --total;

        }

        return sb.ToString();

    }

Complexity: O(n) where n = a + b + c

[Uber][LeetCode] Find First and Last Position of Element in Sorted Array

Problem: Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Approach: We can use binary search to find the first position and last position of the target given the array is sorted.

Implementation in C#:

    public int[] SearchRange(int[] nums, int target) 

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return new int[] {-1, -1 };

        }

        if (length == 1)

        {

            return nums[0] == target ? new int[] {0, 0} : new int[] {-1, -1};

        }

        int first = this.FindFirstOccurence(nums, target, 0, length - 1);

        if (first == -1)

        {

            return new int[] {-1, -1 };

        }

        return new int[] {first, this.FindLastOccurence(nums, target, 0, length - 1) };

    }

    

    private int FindFirstOccurence(int[] nums, int target, int low, int high)

    {

        if (low > high)

        {

            return -1;

        }

        int mid = low + (high - low) / 2;

        if (nums[mid] == target && (mid == 0 || nums[mid] > nums[mid - 1]))

        {

            return mid;

        }

        if (target <= nums[mid])

        {

            return this.FindFirstOccurence(nums, target, low, mid - 1);

        }

        return this.FindFirstOccurence(nums, target, mid + 1, high);

    }

    

    private int FindLastOccurence(int[] nums, int target, int low, int high)

    {

        if (low > high)

        {

            return -1;

        }

        int mid = low + (high - low) / 2;

        if (nums[mid] == target && (mid == nums.Length - 1 || nums[mid] < nums[mid + 1]))

        {

            return mid;

        }     

        if (target < nums[mid])

        {

            return this.FindLastOccurence(nums, target, low, mid - 1);

        }        

        return this.FindLastOccurence(nums, target, mid + 1, high);

    }

Complexity: O(log n)