Updates from January, 2017 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 11:09 pm on January 4, 2017 Permalink | Reply
    Tags: ,   

    Problem: LCS with permutations 

    *Difficulty: Easy

    Given two strings in lowercase, find the longest string whose permutations are subsequence of given two strings. The output longest string must be sorted.

    Examples:

    Input  :  str1 = "pink", str2 = "kite"
    Output : "ik" 
    The string "ik" is the longest sorted string 
    whose one permutation "ik" is subsequence of
    "pink" and another permutation "ki" is 
    subsequence of "kite". 
    
    Input  : str1 = "working", str2 = "women"
    Output : "now"
    
    Input  : str1 = "geeks" , str2 = "cake"
    Output : "ek"
    
    Input  : str1 = "aaaa" , str2 = "baba"
    Output : "aa"
    

    Input:
    First line of the input contains no of test cases  T, then T test cases follow. Each test case consist of 2 space separated integers n and m denoting the size of string str1 and str2 respectively. The next two lines contains the 2 string str1 and str2 .
    Output:
    For each test case print the output string in sorted order.
    Constraints:
    1 <= T <= 30
    1 <= size(str1),size(str2)<= 100
    Example:
    Input:
    2
    6 6
    abcdef
    edgfhr
    3 2
    abc
    ca

    Output:
    def
    ac

    Implementation: Python2.7

    """
        @author: loctv
        @time: 11:04PM January 4, 2017
    """
    
    #code
    def frequency_of_chars_in(string):
        """
            Calculate frequency of each characters in string
        """
        d = {}
        for c in string:
            d[c] = d.setdefault(c, 0) + 1
        return d
    
    def lcs_with_permutations(string1, string2):
        """
            Get LCS of string1 and string2 with permutations
            Same as get all common characters of string1 and string2
        """
        d_string1 = frequency_of_chars_in(string1)
        d_string2 = frequency_of_chars_in(string2)
        res = bytearray('')
        for c in d_string1:
            if c in d_string2 and d_string2[c]:
                res.extend(c*min(d_string1[c], d_string2[c]))
                d_string1[c] = 0 #mark as readed
                d_string2[c] = 0 #mark as readed
        for c in d_string2:
            if c in d_string1 and d_string1[c]:
                res.extend(c*min(d_string1[c], d_string2[c]))
                d_string1[c] = 0 #mark as readed
                d_string2[c] = 0 #mark as readed
        #print the result in sorted order
        print ''.join(sorted(list(str(res))))
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            size1, size2 = map(int, raw_input().strip().split())
            string1 = raw_input().strip()
            string2 = raw_input().strip()
            lcs_with_permutations(string1, string2)
    
    
    Advertisements
     
  • loctv 10:23 pm on January 4, 2017 Permalink | Reply
    Tags: ,   

    Problem: Max and Min Products 

    *Difficulty: Easy

    Given a set, we need to find maximum and minimum possible product among all subsets of the set.
    Examples:

    Input : arr[] = {4, -2, 5};
    Output: Maximum product = 20 
            Minimum product = -40
    Maximum product is obtained by multiplying
    4 5
    Minimum product is obtained by multiplying 
    4, -2, 5
    
    Input : arr[] = {-4, -2, 3, 7, 5, 0, 1};
    Output: Maximum product = 840 
            Minimum product = -420
    Maximum product is obtained by multiplying
    -4, -2, 3, 7, 5
    Minimum product is obtained by multiplying 
    -4, 3, 7,

     

    Input:
    The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated denoting the elements of the array.

    Output:
    Print the maximum product followed by a space followed by minimum subset product.

    Constraints:
    1 ≤ T ≤ 40
    1 ≤ N ≤ 20
    -100 ≤ A[i] <= 100

    Example:
    Input
    2
    3
    1 2 3
    4
    -1 -2 -3 -4

    Output

    6 1
    24 -24

    """
        @autho: loctv
        @time: 09:52PM January 4, 2017
    """
    import itertools
    import operator
    
    def all_sub_sets(l):
        """
            generate all sub sets (with length 1,2,3,....n)
            l: list of numbers
        """
        bound = len(l)
        for i in range(1, bound+1):
            yield itertools.combinations(l, i)
    
    def max_min_products(l):
        """
            find max and min product from all sub sets
            l: list of numbers
        """
        max_product, min_product = -100**20, 100**20
        for sub_sets in all_sub_sets(l):
            for sub_set in sub_sets:
                product = reduce(operator.mul, sub_set)
                if product > max_product:
                    max_product = product
                if product < min_product:
                    min_product = product
        print max_product, min_product
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            n = input()
            l = map(int, raw_input().strip().split())
            max_min_products(l)
    
    
     
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