Updates from July, 2016 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 9:32 am on July 16, 2016 Permalink | Reply
    Tags:   

    Problem: The Maximum Subarray 

    *Difficulty: Easy

    Problem:

    Given an array A = [a0,a1,…a(n-1)]  of n elements, find the maximum possible sum of a

    1. Contiguous subarray
    2. Non-contiguous (not necessarily contiguous) subarray.

    Empty subarrays/subsequences should not be considered.

    Input Format

    First line of the input has an integer T . T  cases follow.
    Each test case begins with an integer N . In the next line, N integers follow representing the elements of array A.

    Constraints:

    1 <= T <= 10
    1 <= N <= 10^5
    -10^4 <= ai <= 10^4

    The subarray and subsequences you consider should have at least one element.

    Output Format

    Two, space separated, integers denoting the maximum contiguous and non-contiguous subarray. At least one integer should be selected and put into the subarrays (this may be required in cases where all elements are negative).

    Sample Input

    2 
    4 
    1 2 3 4
    6
    2 -1 2 3 4 -5
    

    Sample Output

    10 10
    10 11
    

    Explanation

    In the first case:
    The max sum for both contiguous and non-contiguous elements is the sum of ALL the elements (as they are all positive).

    In the second case:
    [2 -1 2 3 4] –> This forms the contiguous sub-array with the maximum sum.
    For the max sum of a not-necessarily-contiguous group of elements, simply add all the positive elements.

    How to solve: 

    From Wiki : Kadane’s algorithm:
    Screen Shot 2016-07-16 at 4.29.44 PM

    Time complexity of this algorithm is O(n)
    Full implementation:
    Screen Shot 2016-07-16 at 4.31.48 PM

    Advertisements
     
  • loctv 6:40 am on July 16, 2016 Permalink | Reply
    Tags:   

    Problem: Minimum Distances 

    *Difficulty: Easy

    Problem:

    Consider an array of n integers, A = [a0,a1,…,a(n-1)] . The distance between two indices,i  and j, is denoted by di,j = |i-j|.

    Given A, find the minimum di,j such that ai = aj  and i != j . In other words, find the minimum distance between any pair of equal elements in the array. If no such value exists, print -1.

    Note: |a| denotes the absolute value of a.

    Input Format

    The first line contains an integer, n , denoting the size of array A.
    The second line contains n  space-separated integers describing the respective elements in array A.

    Constraints

    1 <= n <= 10^3
    1 <= ai <= 10^5

    Output Format

    Print a single integer denoting the minimum di,j in A; if no such value exists, print -1 .

    Sample Input

    6
    7 1 3 4 1 7
    

    Sample Output

    3
    

    Explanation
    Here, we have two options:

    •  a1 and a4 are both 1, so d1,4  = |1-4| = 3 .
    •  a0 and a5 are both 7, so d0,5   = |0-5| = 5.

    The answer is min(3,5) = 3.

    How to solve: 

    First create a dictionary store the input order of ai, if the next input a(i+k) = ai, then the distance will be k, and the new position of ai will be i + k.
    Here is the step by step running:

    pos = [-1,-1,-1,-1,-1,-1,-1,-1] (size of this array equal max(A)+1), or 10^5 + 1, because maximum of ai is 10^5
    A = [7,1,3,4,1,7]
    min_dis = len(pos) , or 10^3 if you want, because the maximum size of A will be 10^3

    a0 = 7
    pos = [-1,-1,-1,-1,-1,-1,-1,0] (input order of 7 is 0)

    a1 = 1
    pos = [-1,1,-1,-1,-1,-1,-1,0]

    a2 = 3
    pos = [-1,1,-1,2,-1,-1,-1,0]

    a3 = 4
    pos = [-1,1,-1,2,3,-1,-1,0]

    a4 = 1, pos[1] = 1 => distance = 4-1 = 3 , update: pos[1] = 4

    a5 = 7, pos[7] = 0 => distance = 5-0 = 5, update: pos[7] = 5

    Implementation in Python2:

    Screen Shot 2016-07-16 at 1.20.00 PM

     
  • loctv 5:11 am on July 16, 2016 Permalink | Reply
    Tags:   

    Problem: Greedy Florist 

    *Difficulty: Easy

    Problem:

    You and K – 1 friends want to buy N flowers. Each fi flower has some cost ci . The florist is greedy and wants to maximize his number of new customers, so he increases the sale price of flowers for repeat customers; more precisely, if a customer has already purchased x flowers, price P for fi  is  Pfi  = (x+1) x ci .

    Find and print the minimum cost for your group to purchase N flowers.

    Note: You can purchase the flowers in any order.

    Input Format

    The first line contains two integers, N (number of flowers to purchase) and K  (the size of your group of friends, including you).
    The second line contains N  space-separated positive integers describing the cost (c0,c1,..c(N-1)) for each flower .

    Constraints

     

    1 <= N,K <= 100
    1 <= ci <= 10^6
    answer < 2^31
    0 <= i  <= N-1

    Output Format

    Print the minimum cost for buying flowers.

    Sample Input 0

    3 3
    2 5 6
    

    Sample Output 0

    13
    

    Sample Input 1

    3 2
    2 5 6
    

    Sample Output 1

    15
    

    Explanation

    Sample Case 0:
    There are flowers and people in your group. Each person buys one flower and the sum of prices paid is dollars, so we print .

    Sample Case 1:
    There are flowers and people in your group. The first person purchases flowers, and , in order of decreasing price; this means they buy the more expensive flower first at price Pf1 = (0+1) x 5 = 5 dollars  and the less expensive flower second at price Pf0 = (1+1) x 2 = 4 dollars. The second person buys the most expensive flower at price Pf2 = (0+1)x6 dollars  . We print the sum of these purchases (5+4+6), which is 15.

    How to solve:

    This problem can be solved by using ordinal principle in heuristic.
    Given a set of input and k groups, your task is finding a proper order of the input such that after distributing all elements in the input set into k groups, you achieve something as smallest or least as possible.
    For example you’re given a set of n works, each work can be done in wi hours, and k machines. Your work is assign works to machines so that the time to complete those works is smallest ( or shortest).
    The order could be ascending or descending, depend on the problem.
    Let say k flowers is in the list flowers, and you and k-1 friends is in the list group – each intialized with zero .
    Here to solve this problem, you sort the flowers list in descending order base on their cost in dollar. Go through flowers list, assign each value to an element in group list, and the element in the group list must have the lowest value at that moment.
    Here’s an example:
    5 2
    1 2 7 9 100

    We got 2 flowers and 2 people.
    First we sort it in descending order :
    100 9 7 2 1
    p1 : paid =  0, purchased = 0
    p2 : paid = 0, purchased  = 0
    For 100 we can assign it to any person
    p1 : paid = 100, purchased = 1
    p2 : paid = 0, purchased = 0
    For 9, at the moment, p1 has the lowest paid value, so we assign 9 to p1
    p1 : paid = 100, purchased = 1
    p2 : paid = 9, purchased = 1
    For 7, p1 still has the lowest paid value, so we assign (1+1)*7 to p1
    p1 : paid = 100, purchased = 1
    p2 : paid = 9 + (1+1)*7 = 23, purchased = 2
    For 2, p1 still has the lowest paid value, so we assign (2+1)*2 to p1
    p1 : paid = 100, purchased = 1
    p2 : paid = 23 + (2+1)*2 = 29 , purchased = 3
    For 1, likewise, we assign (3+1)*1 to p1
    p1 : paid = 100, purchased = 1
    p2 : paid = 29 + (3+1)*1 = 33, purchased = 4

    The total money that you and your friends have to pay to buy those 5 flowers is 100 + 33 = 133. Easy, isn’t it? But here is the problem, the answer for this example is 130. Here is what we need to change : Checking for the smallest paid is not enough, you have to check if that person buys that flower, then how many money cost in total, if that money is the smallest ?
    So here is the implementation in Python2:
    Screen Shot 2016-07-16 at 12.02.24 PM
    l is the list of people, each people is a dict {‘purchased’:0, ‘paid’:0}, cost is the money cost for the current flower, total is the current cost of all flowers that’ve been purchased.
    min_value here is the min of money cost in total after someone purchase new flower with the cost in the arguments.

    Go through each person :
    —-check if that person buy that flower will end up with the smallest total money cost:
    ——–then mark it as the smallest total money cost
    ——–and mark which person
    then return the person ( the person that buy that flower lead to the smallest money cost in total)

    Here’s the main method:
    Screen Shot 2016-07-16 at 12.07.23 PM
    If the number of flowers smaller or equal with the number of people, then we just return the sum of all those flowers.

    Bonus: Big test case
    Input

    60 18
    120854 100862 523789 849072 23733 355147 660925 59103 801528 607947 51312
     754005 823629 876280 23088 668838 214629 641310 66064 541147 97284 579336 
    319949 193067 35064 227785 376976 146458 258150 551784 961936 189099 552128
     318057 39381 41667 316754 680180 681303 7132 472252 791845 540485 464674
     336442 572655 724577 627822 553055 986861 944776 588636 966817 892103 
    737744 478475 668429 809085 362250 597680

    Output:

    46361218
     
  • loctv 2:52 am on July 16, 2016 Permalink | Reply
    Tags: Computer Tricks   

    How to change Mac’s terminal background color 

    You need to select which profile you want to be your default in the preferences for the Terminal application. Here is a way you do that:

    1. Open the Terminal.app
    2. Select “Terminal” Menu then “Preferences…”
    3. Select the “Profiles” Tab
    4. Click and highlight a theme listed under Profiles.
    5. Press the “Default” button near the bottom of the window.
    6. Open a new Terminal window, it should now have the theme that you selected as the new default.

    Screen Shot 2016-07-16 at 9.48.52 AM

    Close terminal, and then re open it, woala !!

    Screen Shot 2016-07-16 at 9.50.08 AM

     
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