Tagged: Problem Solving Toggle Comment Threads | Keyboard Shortcuts

  • loctv 8:32 pm on December 16, 2019 Permalink | Reply
    Tags: Problem Solving,   

    Topological Sort and Tasks Scheduling (Kahn’s algorithm) 

    Topological Sort of a directed graph (a graph with unidirectional edges) is a linear ordering of its vertices such that for every directed edge (U, V) from vertex U to vertex VU comes before V in the ordering.

    Given a directed graph, find the topological ordering of its vertices.

    Example 1:

    Input: Vertices=4, Edges=[3, 2], [3, 0], [2, 0], [2, 1]
    Output: Following are the two valid topological sorts for the given graph:
    1) 3, 2, 0, 1
    2) 3, 2, 1, 0

    Capture

    Example 2:

    Input: Vertices=5, Edges=[4, 2], [4, 3], [2, 0], [2, 1], [3, 1]
    Output: Following are all valid topological sorts for the given graph:
    1) 4, 2, 3, 0, 1
    2) 4, 3, 2, 0, 1
    3) 4, 3, 2, 1, 0
    4) 4, 2, 3, 1, 0
    5) 4, 2, 0, 3, 1

    Capture

    Here are a few fundamental concepts related to topological sort:

    1. Source: Any node that has no incoming edge and has only outgoing edges is called a source.
    2. Sink: Any node that has only incoming edges and no outgoing edge is called a sink.
    3. So, we can say that a topological ordering starts with one of the sources and ends at one of the sinks.
    4. A topological ordering is possible only when the graph has no directed cycles, i.e. if the graph is a Directed Acyclic Graph (DAG). If the graph has a cycle, some vertices will have cyclic dependencies which makes it impossible to find a linear ordering among vertices.

    To find the topological sort of a graph we can traverse the graph in either a Breadth First Search (BFS) way using Kahn’s algorithm or Depth First Search (DFS). We will start with all the sources, and in a stepwise fashion, save all sources to a sorted list. We will then remove all sources and their edges from the graph. After the removal of the edges, we will have new sources, so we will repeat the above process until all vertices are visited.

    [preserved_text 1fbfd1112ea81554cf8bd39aca16ff45 /]

    Time Complexity

    In step ‘d’, each vertex will become a source only once and each edge will be accessed and removed once. Therefore, the time complexity of the above algorithm will be O(V+E), where ‘V’ is the total number of vertices and ‘E’ is the total number of edges in the graph.

    Space Complexity

    The space complexity will be O(V+E), since we are storing all of the edges for each vertex in an adjacency list.

    Tasks Scheduling

    There are ‘N’ tasks, labeled from ‘0’ to ‘N-1’. Each task can have some prerequisite tasks which need to be completed before it can be scheduled. Given the number of tasks and a list of prerequisite pairs, find out if it is possible to schedule all the tasks.

    Example 1:

    Input: Tasks=3, Prerequisites=[0, 1], [1, 2]
    Output: true
    Explanation: To execute task '1', task '0' needs to finish first. Similarly, task '1' needs to finish 
    before '2' can be scheduled. A possible scheduling of tasks is: [0, 1, 2] 
    

    Example 2:

    Input: Tasks=3, Prerequisites=[0, 1], [1, 2], [2, 0]
    Output: false
    Explanation: The tasks have cyclic dependency, therefore they cannot be scheduled.

    As you can see, we can represent the task and its dependency as an edge in a directed graph. There’s a little change in the above code that need to be changed to solve this problem so I let this as an exercise for you. Instead of returning a list, you just need to return a boolean.

    Another application of Topological Sort is to check if a directed graph contains a cycle.

     

     

     

     
  • loctv 5:34 pm on December 15, 2019 Permalink | Reply
    Tags: Problem Solving   

    Understanding how to generate permutation in Java 

    Given a set of distinct numbers, find all of its permutations.

    Permutation is defined as the re-arranging of the elements of the set. For example, {1, 2, 3} has the following six permutations:

    1. {1, 2, 3}
    2. {1, 3, 2}
    3. {2, 1, 3}
    4. {2, 3, 1}
    5. {3, 1, 2}
    6. {3, 2, 1}

    If a set has ‘n’ distinct elements it will have n! permutations.

    Example 1:

    Input: [1,3,5]
    Output: [1,3,5], [1,5,3], [3,1,5], [3,5,1], [5,1,3], [5,3,1]

    Let’s take the example-1 mentioned above to generate all the permutations. Following a BFS approach, we will consider one number at a time:

    1. If the given set is empty then we have only an empty permutation set: []
    2. Let’s add the first element (1), the permutations will be: [1]
    3. Let’s add the second element (3), the permutations will be: [3,1], [1,3]
    4. Let’s add the third element (5), the permutations will be: [5,3,1], [3,5,1], [3,1,5], [5,1,3], [1,5,3], [1,3,5]

    Let’s analyze the permutations in the 3rd and 4th step. How can we generate permutations in the 4th step from the permutations of the 3rd step?

    If we look closely, we will realize that when we add a new number (5), we take each permutation of the previous step and insert the new number in every position to generate the new permutations. For example, inserting ‘5’ in different positions of [3,1] will give us the following permutations:

    1. Inserting ‘5’ before ‘3’: [5,3,1]
    2. Inserting ‘5’ between ‘3’ and ‘1’: [3,5,1]
    3. Inserting ‘5’ after ‘1’: [3,1,5]

    Here is the visual representation of this algorithm:

    Capture

    Here’s the non-recursive version:

      public static List<List> findPermutations(int[] nums) {
        List<List> result = new ArrayList();
        Queue<List> permutations = new LinkedList();
        permutations.add(new ArrayList());
        for (int currentNumber : nums) {
          // we will take all existing permutations and add the current number to create new permutations
          int n = permutations.size();
          for (int i = 0; i < n; i++) {
            List oldPermutation = permutations.poll();
            // create a new permutation by adding the current number at every position
            for (int j = 0; j <= oldPermutation.size(); j++) {
              List newPermutation = new ArrayList(oldPermutation);
              newPermutation.add(j, currentNumber);
              if (newPermutation.size() == nums.length)
                result.add(newPermutation);
              else
                permutations.add(newPermutation);
            }
          }
        }
        return result;
      }
    

    and its recursive version:

      public static List<List> generatePermutations(int[] nums) {
        List<List> result = new ArrayList();
        generatePermutationsRecursive(nums, 0, new ArrayList(), result);
        return result;
      }
    
      private static void generatePermutationsRecursive(int[] nums, int index, List currentPermutation,
          List<List> result) {
        if (index == nums.length) {
          result.add(currentPermutation);
        } else {
          // create a new permutation by adding the current number at every position
          for (int i = 0; i <= currentPermutation.size(); i++) {
            List newPermutation = new ArrayList(currentPermutation);
            newPermutation.add(i, nums[index]);
            generatePermutationsRecursive(nums, index + 1, newPermutation, result);
          }
        }
      }
    
     
  • loctv 1:29 pm on December 14, 2019 Permalink | Reply
    Tags: Problem Solving   

    Knapsack: Top-down, Memoization & Bottom-up 

    Introduction

    Given the weights and profits of ‘N’ items, we are asked to put these items in a knapsack which has a capacity ‘C’. The goal is to get the maximum profit out of the items in the knapsack. Each item can only be selected once, as we don’t have multiple quantities of any item.

    Let’s take the example of Merry, who wants to carry some fruits in the knapsack to get maximum profit. Here are the weights and profits of the fruits:

    Items: { Apple, Orange, Banana, Melon }
    Weights: { 2, 3, 1, 4 }
    Profits: { 4, 5, 3, 7 }
    Knapsack capacity: 5

    Let’s try to put various combinations of fruits in the knapsack, such that their total weight is not more than 5:

    Apple + Orange (total weight 5) => 9 profit
    Apple + Banana (total weight 3) => 7 profit
    Orange + Banana (total weight 4) => 8 profit
    Banana + Melon (total weight 5) => 10 profit

    This shows that Banana + Melon is the best combination as it gives us the maximum profit and the total weight does not exceed the capacity.

    Problem Statement

    Given two integer arrays to represent weights and profits of ‘N’ items, we need to find a subset of these items which will give us maximum profit such that their cumulative weight is not more than a given number ‘C’. Each item can only be selected once, which means either we put an item in the knapsack or we skip it.

    Basic Solution

    A basic brute-force solution could be to try all combinations of the given items (as we did above), allowing us to choose the one with maximum profit and a weight that doesn’t exceed ‘C’. To try all the combinations, our algorithm will look like:

      public int solveKnapsack(int[] profits, int[] weights, int capacity) {
        return knapsackRecursive(profits, weights, capacity, 0);
      }
    
      private int knapsackRecursive(int[] profits, int[] weights, int capacity, int currentIndex) {
        // base checks
        if (capacity <= 0 || currentIndex >= profits.length)
          return 0;
    
        // recursive call after choosing the element at the currentIndex
        // if the weight of the element at currentIndex exceeds the capacity, we shouldn't process this
        int profit1 = 0;
        if( weights[currentIndex] <= capacity )
            profit1 = profits[currentIndex] + knapsackRecursive(profits, weights,
                    capacity - weights[currentIndex], currentIndex + 1);
    
        // recursive call after excluding the element at the currentIndex
        int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);
    
        return Math.max(profit1, profit2);
      }
    

    Complexity:

    For recursive function with two separate calls of itself, the time complexity is O(2​^n). Since recursive calls work the same way as DF search, space complexity is O(n).

    Top-down Dynamic Programming with Memoization

    Memoization is when we store the results of all the previously solved sub-problems and return the results from memory if we encounter a problem that has already been solved.

    Since we have two changing values (capacity and currentIndex) in our recursive function knapsackRecursive(), we can use a two-dimensional array to store the results of all the solved sub-problems. As mentioned above, we need to store results for every sub-array (i.e. for every possible index ‘i’) and for every possible capacity ‘c’.

      public int solveKnapsack(int[] profits, int[] weights, int capacity) {
        Integer[][] dp = new Integer[profits.length][capacity + 1];
        return knapsackRecursive(dp, profits, weights, capacity, 0);
      }
    
      private int knapsackRecursive(Integer[][] dp, int[] profits, int[] weights, int capacity,
          int currentIndex) {
    
        // base checks
        if (capacity <= 0 || currentIndex >= profits.length)
          return 0;
    
        // if we have already solved a similar problem, return the result from memory
        if(dp[currentIndex][capacity] != null)
          return dp[currentIndex][capacity];
    
        // recursive call after choosing the element at the currentIndex
        // if the weight of the element at currentIndex exceeds the capacity, we shouldn't process this
        int profit1 = 0;
        if( weights[currentIndex] <= capacity )
            profit1 = profits[currentIndex] + knapsackRecursive(dp, profits, weights,
                    capacity - weights[currentIndex], currentIndex + 1);
    
        // recursive call after excluding the element at the currentIndex
        int profit2 = knapsackRecursive(dp, profits, weights, capacity, currentIndex + 1);
    
        dp[currentIndex][capacity] = Math.max(profit1, profit2);
        return dp[currentIndex][capacity];
      }
    

    Time and Space complexity

    Since our memoization array dp[profits.length][capacity+1] stores the results for all subproblems, we can conclude that we will not have more than  N*C subproblems (where ‘N’ is the number of items and ‘C’ is the knapsack capacity). This means that our time complexity will be O(N*C).

    The above algorithm will use O(N*C) space for the memoization array. Other than that we will use O(N) space for the recursion call-stack. So the total space complexity will be O(N*C + N), which is asymptotically equivalent to O(N*C)

    Bottom-up Dynamic Programming

    Let’s try to populate our dp[][] array from the above solution by working in a bottom-up fashion. Essentially, we want to find the maximum profit for every sub-array and for every possible capacity. This means that dp[i][c] will represent the maximum knapsack profit for capacity ‘c’ calculated for the first ‘i’ items.

    So, for each item at index ‘i’ (0 <= i < items.length) and capacity ‘c’ (0 <= c <= capacity), we have two options:

    1. Exclude the item at index ‘i’. In this case, we will take whatever profit we get from the sub-array excluding this item => dp[i-1][c]
    2. Include the item at index ‘i’ if its weight is not more than the capacity. In this case, we include its profit plus whatever profit we get from the remaining capacity and from previous items => profit[i] + dp[i-1][c-weight[i]]

    Finally, our optimal solution will be maximum of the above two values:

        dp[i][c] = max (dp[i-1][c], profit[i] + dp[i-1][c-weight[i]]) 
      public int solveKnapsack(int[] profits, int[] weights, int capacity) {
        // basic checks
        if (capacity &lt;= 0 || profits.length == 0 || weights.length != profits.length)
          return 0;
    
        int n = profits.length;
        int[][] dp = new int[n][capacity + 1];
    
        // populate the capacity=0 columns, with '0' capacity we have '0' profit
        for(int i=0; i &lt; n; i++)
          dp[i][0] = 0;
    
        // if we have only one weight, we will take it if it is not more than the capacity
        for(int c=0; c &lt;= capacity; c++) {
          if(weights[0] &lt;= c)
            dp[0][c] = profits[0];
        }
    
        // process all sub-arrays for all the capacities
        for(int i=1; i &lt; n; i++) {
          for(int c=1; c &lt;= capacity; c++) {
            int profit1= 0, profit2 = 0;
            // include the item, if it is not more than the capacity
            if(weights[i] &lt;= c)
              profit1 = profits[i] + dp[i-1][c-weights[i]];
            // exclude the item
            profit2 = dp[i-1][c];
            // take maximum
            dp[i][c] = Math.max(profit1, profit2);
          }
        }
    
        // maximum profit will be at the bottom-right corner.
        return dp[n-1][capacity];
      }
    

     

    Time and Space complexity

    The above solution has the time and space complexity of O(N*C), where ‘N’ represents total items and ‘C’ is the maximum capacity.

     
  • loctv 2:02 pm on March 3, 2019 Permalink | Reply
    Tags: Problem Solving   

    Hackerrank: Waiter 

    You are a waiter at a party. There are  stacked plates on pile A0. Each plate has a number written on it. Then there will be Q iterations. In i-th iteration, you start picking up the plates in  Ai-1 from the top one by one and check whether the number written on the plate is divisible by the i-th prime. If the number is divisible, you stack that plate on pile Bi . Otherwise, you stack that plate on pile Ai. After Q iterations, plates can only be on pile B1,B2,..,Bq,Aq. Output numbers on these plates from top to bottom of each piles in order of B1,B2,…,Bq,Aq.

    Input Format

    The first line contains two space separated integers, N and Q.
    The next line contains N space separated integers representing the initial pile of plates, i.e., A0. The leftmost value represents the bottom plate of the pile.

    Constraints

    • 1 <= N <=5 * 10^4
    • 2 <= number_ith <= 10^4
    • 1 <= Q <= 1200

    Output Format

    Output N lines. Each line contains a number written on the plate. Printing should be done in the order defined above.

    Sample Input 0

    5 1
    3 4 7 6 5
    

    Sample Output 0

    4
    6
    3
    7
    5
    

    Explanation 0

    Initially:

     A0 = [3, 4, 7, 6, 5]<-TOP

    After 1 iteration:

     A0 = []<-TOP

     B1 = [6, 4]<-TOP

     A1 = [5, 7, 3]<-TOP

    We should output numbers in B1  first from top to bottom, and then output numbers in A1 from top to bottom.

    Sample Input 1

    5 2
    3 3 4 4 9
    

    Sample Output 1

    4
    4
    9
    3
    3
    

    Explanation 1

    Initially:

    A0 = [3, 3, 4, 4, 9]<-TOP

    After  iteration:

    A0 = []<-TOP

    B1 = [4, 4]<-TOP

    B2 = [9, 3, 3]<-TOP

    After  iteration:

    A1 = []<-TOP

    B1 = [4, 4]<- TOP

    B2 = [3, 3, 9]<-TOP

    We should output numbers in B1  first from top to bottom, and then output numbers in B2 from top to bottom.


    You can tell that the Explanation 1 is wrong but it doesn’t matter. The problem description is quite confusing, but it’s really simple.

    You’re given a set and you have to split that set into two separate parts, one that is divisible by some prime numbers, and the other isn’t. The visible part are constructed by multiple stacks. Each iteration i-th, you go through the stack A, if any element in stack A is divisible by i-th prime, put it into a stack B i-th, otherwise put it back in a new stack of A, which will reverse the original stack.

    Later on, either when new stack A is empty or we run out of the iteration loop, we go through the stacks B, pop out each element in each stack and print it out. Then go through the final stack A, which might or might not be empty.


    This my the solution in Java.

    https://github.com/MrNocTV/Algorithms/blob/master/SolvedProblems/HackerRank/src/Waiter.java

     
  • loctv 5:22 pm on February 27, 2019 Permalink | Reply
    Tags: Problem Solving   

    Hackerrank : Maximum Element 

    You have an empty sequence, and you will be given N queries. Each query is one of these three types:

    1 x  -Push the element x into the stack.
    2    -Delete the element present at the top of the stack.
    3    -Print the maximum element in the stack.
    

    Input Format

    The first line of input contains an integer, N. The next N lines each contain an above mentioned query. (It is guaranteed that each query is valid.)

    Constraints
    1 <= N <= 10^5
    1 <= x <= 10^9
    1 <= type <= 3

    Output Format

    For each type  query, print the maximum element in the stack on a new line.

    Sample Input

    10
    1 97
    2
    1 20
    2
    1 26
    1 20
    2
    3
    1 91
    3
    

    Sample Output

    26
    91

    First thing you should notice is the constraint:
    1 <= N <= 10^5
    Most of the time, if you see the constraint is 10^5 (ten to the power of 5), it means your solution must be at most O(n log n) or better.

    Okey, since it’s marked as “Easy” so there will be no hidden things that you need to figure out. Basically you need to build a stack and get the biggest elements in the stack and quick / fast as possible, so this is all about data structure.

    Obviously we need a stack, to push and pop items as required. But how can we tell which item in the stack is biggest.

    The easiest solution is go through the stack and get the max item. It works but it’s too slow. The time complexity will be O(n^2), roughly.

    Method1: 
    We can use an additional collection, like a Heap, more specifically, a MaxHeap to store the elements in order. To insert an item to a Heap, it is O(n log n), to remove an item in a heap, it’s aso O(n log n). Finally, this is what we want, to get the biggest element as fast as possible. Specifically for MaxHeap, the top will be the biggest element. Overall this will work and the time complexity will be roughly O(n log n). The hardest thing is to implement the MaxHeap yourself.

    Method2:
    This is more “language-oriented”. It removes the “re-invent the wheel” part, no need to implement MaxHeap yourself.
    In Java we have a SortedSet, it’s really fast for adding item as well as lookup smallest/largest item. The only problem though, is duplicated items. We need to watch out for duplicated items. Obviously, because set only stores non duplicated items. We can use a Map to store the item and its frequency. When the frequency goes down to 1, we know that we can remove the item from the set, as well as the frequency map. This is relatively fast, but it consumes a lot of spaces. It’s O(n) in space complexity.

    Method3:
    This is when “algorithm” comes to handy. Let’s say we need to insert an item, and also we need to know what is the maximum value after we insert the new item. If this still isn’t enough for you then please continue reading. So instead of just saving an item, you can also save the max value so far given the new item, also we need a global max variable to know the max value so far. The item on the top of the stack is guaranteed to be paired with the biggest element. When the stack is empty we need to reset the maximum value and when popping item out of stack, we need to update the global max value (if needed).

    There may be more solutions for this problem but these are what I’ve come up with.

    Here’s the sample code if you get trouble implementing the mentioned solutions.


    Method2:
    https://github.com/MrNocTV/Algorithms/blob/master/SolvedProblems/HackerRank/src/MaximumElement1.java

    Method3:
    https://github.com/MrNocTV/Algorithms/blob/master/SolvedProblems/HackerRank/src/MaximumElement2.java

     
  • loctv 1:53 pm on July 13, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Segment Tree: min/max range queries problem. 

    Given an array arr[0…n-1] and multiple queries. With each query, we need to find the minimum (or maximum) value from index qs (query start) to qe (query end) where 0 <= qs <= qe < n.

    Examples:

    Input : arr[] = {1, 8, 5, 9, 6, 14, 2, 4, 3, 7}
    queries = 5
        qs = 0 qe = 4
        qs = 3 qe = 7
        qs = 1 qe = 6
        qs = 2 qe = 5
        qs = 0 qe = 8
    Output: Minimum = 1 and Maximum = 9
        Minimum = 2 and Maximum = 14
        Minimum = 2 and Maximum = 14
        Minimum = 5 and Maximum = 14
        Minimum = 1 and Maximum = 14
    

    There are multiple ways for solving this problem.

    1. Simple solution:
    Each query, we run through arr[qs…qe], find and print out the min/maximum value. This approach is useful on a small scale problem, but when array involves thousands of elements and we have thousands of queries, it is impractical, since its time complexity is O(q * n), with q is number of queries and n is number of elements in array.

    2. Segment Tree
    Utilize the properties of segment tree can help us solve this problem efficiently.
    A segment tree is a binary tree, the way it is built can be compared to merge sort algorithm. The root node contains the min value in range [0…n-1], left and right child of root node contains range of half left and half right: [0…mid] and [mid+1…0], respectively. This can be applied on left and right child of any node.
    Except leaf nodes, leaf nodes contain elements in the original array.

    RangeMinimumQuery.png

    Segment tree of array: [2, 5, 1, 4, 9, 3]

    Number of elements in segment tree is 2*n – 1, with n is the number of elements in the array. But since we gonna use array for the implementation, we need 2*next_power_of_two(n) – 1, next_power_of_two is a function return the smallest possible power of two that is bigger than n. Example next_power_of_two(5) will yield 8.

    Time complexity will be O(q * logn) with q is the number of queries and n is number of elements in array, which is significantly faster than the simple approach.

    class SegmentTree:
    
        ########################### Private Interface ############################
    
        def __init__(self, arr):
            self._seg_tree = [float('Inf')]*(2*self._next_power_of_two(len(arr))-1)
            # input array
            self._arr = arr
            self._construct_tree(self._arr, self._seg_tree, 0, len(self._arr)-1, 0)
    
        def _construct_tree(self, arr, seg_tree, low, high, pos):
            if low >= high:
                # build two child first
                # (value, (range)) -> help query easier
                seg_tree[pos] = (arr[low], (low, low))
                return
            mid = (low+high) // 2
    
            # build left subtree
            self._construct_tree(arr, seg_tree, low, mid, 2*pos+1)
            # build right subtree
            self._construct_tree(arr, seg_tree, mid+1, high, 2*pos+2)
    
            # build the parent of two children above
            # get min of two children, and range is [low, high]
            seg_tree[pos] = (min(seg_tree[self._left(pos)][0], seg_tree[self._right(pos)][0]), (low, high))
    
        def _is_power_of_two(self, n):
            return n > 0 and (n & (n-1)) == 0
    
        def _next_power_of_two(self, n):
            # if n is already a power of two, return it
            if self._is_power_of_two(n):
                return n
            count = 0
            while n > 0:
                count += 1
                # right shift bit = divide by 2
                n = n >> 1
            # 1 << count = 2**count
            return 1 << count
    
        def _left(self, p):
            # return left child of p
            return p*2 + 1
    
        def _right(self, p):
            # return right child of p
            return p*2 + 2
    
        def _has_child(self, p):
            # check if p has children
            return self._left(p) < len(self._seg_tree) and self._right(p) < len(self._seg_tree)               ########################### Public Interface ############################          def query_min(self, qs, qe, pos):         # since there are some INF element         # we need to check instance type         if isinstance(self._seg_tree[pos], float):             return float('Inf')         # get range of the current 'pos'         # and min of current range         start, end = self._seg_tree[pos][1]         min_val = self._seg_tree[pos][0]                  # case 1: range of node is within qs and qe          #       => return min of range
            if qs <= start and qe >= end:
                return min_val
    
            # case 2: range of node is outside qs and qe
            #       => return INF (indicate redundant value)
            if end < qs or start > qe:
                return float('Inf')
    
            # case 3: range of node is partition overlapped with qs and qe
            #       return min([left_child, qs, qe], [right_child, qs, qe])
            # first we need to check if it has child
            # if no, return its value, otherwise call query_min for left and right child
            if self._has_child(pos):
                return min(self.query_min(qs, qe, self._left(pos)), self.query_min(qs, qe, self._right(pos)))
            else:
                return self._seg_tree[pos][0]
    

    As you can see in the query_min() method, there are three cases can happen.
    1. The range of current node is completely inside the range of query.
    2. The range of current node is completely outside the range of query.
    3. The range of current node is partition overlapped with the range of query.

    More understanding can be gained after watching this video. In my opinion, it is by far the most understandable video describing how a min/max query works on segment tree.
    Segment Tree Query Demo

    Some problem for practising:
    https://www.hackerrank.com/challenges/service-lane/problem
    http://www.spoj.com/problems/RMQSQ/

     
  • loctv 6:41 pm on March 19, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: Manasa and Stones 

    Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that two consecutive stones have a difference of either a or b. Legend has it that there is a treasure trove at the end of the trail and if Manasa can guess the value of the last stone, the treasure would be hers. Given that the number on the first stone was 0, find all the possible values for the number on the last stone.

    Note: The numbers on the stones are in increasing order.

    Input Format

    The first line contains an integer T, i.e. the number of test cases. T test cases follow; each has 3 lines. The first line contains n (the number of stones). The second line contains a, and the third line contains b.

    Constraints

    1 <= T <= 10
    1 <= n, a, b <= 10^3

    Output Format

    Space-separated list of numbers which are the possible values of the last stone in increasing order.

    Sample Input

    2
    3 
    1
    2
    4
    10
    100
    

    Sample Output

    2 3 4 
    30 120 210 300 
    

    Explanation

    All possible series for the first test case are given below:

    1. 0,1,2
    2. 0,1,3
    3. 0,2,3
    4. 0,2,4

    Hence the answer 2 3 4.

    Series with different number of final steps for second test case are the following:

    1. 0, 10, 20, 30
    2. 0, 10, 20, 120
    3. 0, 10, 110, 120
    4. 0, 10, 110, 210
    5. 0, 100, 110, 120
    6. 0, 100, 110, 210
    7. 0, 100, 200, 210
    8. 0, 100, 200, 300

    Hence the answer 30 120 210 300.

    Approach:

    1. Using backtracking. Generate all possible sequences, get all last values, and put them into a set. This is acceptable with n small (less than 15), since the complexity is O(2^n). Here is the code for backtracking
    2. Analyze. Let’s take 2 examples above and find out the pattern. In the first example, n = 3 and there are 3 different ending values, max value is 4 and the difference from the largest to the smallest is 1 (4 -> 3 -> 2) . In the second example, n = 4 and there are 4 different ending values, max value is 300 and difference between pairs is 90. Have you seen the pattern yet? With n, there are n different values, the largest value is max(a,b)*(n-1), the difference is max(a,b) – min(a,b), or a – b, if a is bigger, otherwise b-a. How can we know that this pattern is the one that we’re looking for. First, since there are only two values a,b, assume a is bigger than b (it works the same way if b is bigger than a). Then the biggest possible value you can get is b*(n-1). since the first one is 0. The second biggest is b*(n-1) – (a-b), since this is the second biggest, the last value is b, instead of a. We c0ntinue this as long as the value return after calculate the difference is positive. And this is actually n-1 times, since we already manually calculate the largest.

    Source code. The chain function is how you print out all possible stones chain, with complexity O(2^n). Inside main is the code to solve this problem.

    def chain(n, arr, options):
        for i in options:
            arr[n] = arr[n-1] + i
            if n == len(arr) - 1:
                print(arr)
            else:
                chain(n+1, arr, options)
    
    def test():
        chain(1, [0]*4, (10, 100))
    
    if __name__ == '__main__':
        t = int(input().strip())
        for _ in range(t):
            n = int(input().strip())
            a = int(input().strip())
            b = int(input().strip())
            if b > a:
                a, b = b, a
            pos_values = [0]*n
            pos_values[0] = a*(n-1)
            for i in range(1, len(pos_values)):
                pos_values[i] = pos_values[i-1] - (a-b)
            pos_values = list(set(pos_values))
            print(*sorted(pos_values))
    
     
  • loctv 10:50 pm on March 7, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: Check Mirror in N-ary tree 

    *Difficulty: Medium

    Given two n-ary tree’s the task is to check if they are mirror of each other or not.

    Example

    1                      1
    /    \                 /   \
    2      3             3     2

    Output: 1

    1                        1
    /  \                    /  \
    2    3                2     3

    Output: 0

    Note: you may assume that root of both the given tree as 1.

    Input:
    The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains two space separated values n and e denoting the no of nodes and edges respectively. Then in the next line two lines are 2*e space separated values u,v denoting an edge from u to v for the both trees .

    Output:
    For each test case in a new line print 1 if both the trees are mirrors of each other else print 0.

    Constraints:
    1<=T<=20
    1<=n<=15
    1<=e<=20

    Example:
    Input:

    2
    3 2
    1 2 1 3
    1 3 1 2
    3 2
    1 2 1 3
    1 2 1 3
    Output:
    1
    0

    Approach: Since this is a N-arr tree, that means one node can have multiple child. So the easiest way is to consider it as a graph. Each graph has a list of adjacent nodes. The way to to check  if two threes (or graphs if you will) are mirror of each other or not is:

    1. They have the same number of nodes
    2. All node have the same number of adjacent nodes
    3. The child list of each node in the first tree when reversed will be exactly like the one in the node of second tree and vice versa.

    Implementation: Python 3

    def is_mirror(tree_1, tree_2):
        if len(tree_1) != len(tree_2):
            return False
        for node in tree_1:
            if len(tree_1[node]) != len(tree_2[node]):
                return False 
            if tree_1[node] != list(reversed(tree_2[node])):
                return False 
        return True 
    
    def create_tree():
        tree = {}
        arr = list(map(int, input().strip().split()))
        for i in range(0,len(arr),2):
            if arr[i] in tree:
                tree[arr[i]].append(arr[i+1])
            else:
                tree[arr[i]] = [arr[i+1]]
        return tree
    
    if __name__ == '__main__':
        t = int(input().strip())
        for _ in range(t):
            n, e = list(map(int, input().strip().split()))
            tree_1 = create_tree()
            tree_2 = create_tree()
            # print(tree_1)
            # print(tree_2)
            print(1 if is_mirror(tree_1, tree_2) else 0)
    
     
  • loctv 12:49 pm on February 22, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: 

    *Difficulty: Easy

    Problem:

    ctci-find-the-running-median-english

    Approach:
    Since the constraints is so high, we need a way to insert and sort the array (or list) that has the complexity equal or lower than O(logn). With n loop and each loop costs O(logn) we have the complexity O(nlogn), which is acceptable. Using linked list and binary search is one of the possible ways. But If you know Python, this problem can be solved in 10 lines of code, using insort method from bisect module.

    Implementation: Python 3

    import bisect
    
    n = int(input())
    l = []
    for _ in range(n):
        ai = int(input())
        bisect.insort(l, ai)
        if len(l) % 2 == 0:
            print('%.1f' % ((l[len(l)//2-1]+l[len(l)//2])/2))
        else:
            print('%.1f' % (l[len(l)//2]))
    
     
  • loctv 11:46 pm on February 21, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: Separate the Numbers 

    *Difficulty: Easy

    Problem:
    separate-the-numbers-english

    Approach:
    Here’s how I did it, and I think example is the best way to explain it:
    Example:
    s = 1011121314
    Start with first number = 1, next is 0, False
    Start with first number = 10, next is 11, next is 12, …..
    Eventually, return True
    The maximum length of first number will be equal len(s) // 2 (if length s is even), or len(s) // 2 + 1 (length s is odd)
    Let’s take another example:
    10000001000001
    First number: 1, next 0 => False
    First number: 10, next 00=> False
    First number: 100, next 000=>False
    First number: 1000. next 000=>False
    ….
    First number:1000000 next 1000001 => True
    Hope you get the idea :>

    Implementation: Python 3

    def is_beautiful(number):
        if number == '' or number[0] == '0' or len(number) <= 2:
            return [False] 
        bound = len(number) // 2
        start_length = 1
        while start_length <= bound:
            first_str = number[:start_length]
            first_int = int(first_str)
            i = start_length
            try:
                while i < len(number):
                    next = next_str(i, first_str, first_int, number)
                    if next is None:
                        break
                    else:
                        changed = False
                        next_1, next_2 = next
                        if int(next_1) == first_int+1:
                            first_str = next_1
                            first_int = int(next_1)
                            i += len(next_1)
                            changed = True 
                        else:
                            if next_2:
                                if int(next_2) == first_int+1:
                                    first_str = next_2
                                    first_int = int(next_2)
                                    i += len(next_2)
                                    changed = True 
                        # cant found next number 
                        if not changed:
                            break
                        # check out of bound 
                        if i > len(number):
                            break
                        # all numbers statisfy the condition
                        if i == len(number):
                            return True, number[:start_length]
            except Exception:
                pass
            start_length += 1
        return [False]
    
    def next_str(i, first_str, first_int , number):
        # get the next number 
        # check if it has equal or longer length 
        # return two next, but only one of them is usable 
        next_1 = ""
        next_2 = ""
        if i < len(number):
            if number[i] == '0':
                return None 
            else:
                if i + len(first_str) <= len(number):
                    next_1 = number[i:i+len(first_str)]
                if i + len(first_str) + 1 <= len(number):
                    next_2 = number[i:i+len(first_str)+1]
                return next_1, next_2
        return None
    
    def main():
        t = int(input())
        for _ in range(t):
            number = str(input().strip())
            result = is_beautiful(number)
            if result[0]:
                print('YES', result[1])
            else:
                print('NO')
    
    if __name__ == '__main__':
        main()
    
     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel