Updates from July, 2016 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 12:58 pm on July 17, 2016 Permalink | Reply
    Tags:   

    Problem: Cut the sticks 

    *Difficulty: Easy

    Problem:

    You are given N sticks, where the length of each stick is a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the smallest stick.

    Suppose we have six sticks of the following lengths:

    5 4 4 2 2 8
    

    Then, in one cut operation we make a cut of length 2 from each of the six sticks. For the next cut operation four sticks are left (of non-zero length), whose lengths are the following:

    3 2 2 6
    

    The above step is repeated until no sticks are left.

    Given the length of N sticks, print the number of sticks that are left before each subsequent cut operations.

    Note: For each cut operation, you have to recalcuate the length of smallest sticks (excluding zero-length sticks).

    Input Format
    The first line contains a single integer N.
    The next line contains integers: a0, a1,…aN-1 separated by space, where represents the length ith of the stick.

    Output Format
    For each operation, print the number of sticks that are cut, on separate lines.

    Constraints

    1 <= N <= 1000
    1 <= ai <= 1000

    Sample Input 0

    6
    5 4 4 2 2 8
    

    Sample Output 0

    6
    4
    2
    1
    

    Sample Input 1

    8
    1 2 3 4 3 3 2 1
    

    Sample Output 1

    8
    6
    4
    1
    

    Explanation

    Sample Case 0 :

    sticks-length        length-of-cut   sticks-cut
    5 4 4 2 2 8             2               6
    3 2 2 _ _ 6             2               4
    1 _ _ _ _ 4             1               2
    _ _ _ _ _ 3             3               1
    _ _ _ _ _ _           DONE            DONE
    

    Sample Case 1

    sticks-length         length-of-cut   sticks-cut
    1 2 3 4 3 3 2 1         1               8
    _ 1 2 3 2 2 1 _         1               6
    _ _ 1 2 1 1 _ _         1               4
    _ _ _ 1 _ _ _ _         1               1
    _ _ _ _ _ _ _ _       DONE            DONE
    
    Advertisements
     
  • loctv 12:31 pm on July 17, 2016 Permalink | Reply
    Tags:   

    Problem: Equal Stacks 

    *Difficulty: Easy

    Problem:

    You have three stacks of cylinders where each cylinder has the same diameter, but they may vary in height. You can change the height of a stack by removing and discarding its topmost cylinder any number of times.

    Find the maximum possible height of the stacks such that all of the stacks are exactly the same height. This means you must remove zero or more cylinders from the top of zero or more of the three stacks until they’re all the same height, then print the height. The removals must be performed in such a way as to maximize the height.

    Note: An empty stack is still a stack.

    Input Format

    The first line contains three space-separated integers, n1, n2, and n3, describing the respective number of cylinders in stacks 1, 2, and 3. The subsequent lines describe the respective heights of each cylinder in a stack from top to bottom:

    • The second line contains n1  space-separated integers describing the cylinder heights in stack 1.
    • The third line contains n2 space-separated integers describing the cylinder heights in stack 2.
    • The fourth line contains n3 space-separated integers describing the cylinder heights in stack 3.

    Constraints

    0<= n1,n2,n3 <= 10^5
    0 < height of any cylinder <=100

    Output Format

    Print a single integer denoting the maximum height at which all stacks will be of equal height.

    Sample Input

    5 3 4
    3 2 1 1 1
    4 3 2
    1 1 4 1
    

    Sample Output

    5
    

    Explanation

    Initially, the stacks look like this:

    initial stacks

    Observe that the three stacks are not all the same height. To make all stacks of equal height, we remove the first cylinder from stacks 1  and 2 , and then remove the top two cylinders from stack 3 (shown below).

    modified stacks

    As a result, the stacks undergo the following change in height:

    1. 8-3 = 5
    2. 9 – 4 = 5
    3. 7-1-1 =5

    All three stacks now have height = 5 . Thus, we print 5  as our answer.

    How to solve:

    Well, you just need to pop the highest stack until all stacks have equal heights.

    Implementation: Python 2

    Screen Shot 2016-07-17 at 7.29.57 PM

    *Problem from Hackerrank

     
  • 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

     
  • 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

     
  • loctv 5:50 am on July 15, 2016 Permalink | Reply
    Tags:   

    Problem: Maximum Draws 

    *Difficulty: Baby step

    Problem:

    Jim is off to a party and is searching for a matching pair of socks. His drawer is filled with socks, each pair of a different color. In its worst case scenario, how many socks (x) should Jim remove from his drawer until he finds a matching pair?

    Input Format
    The first line contains the number of test cases T.
    Next T lines contains an integer N which indicates the total pairs of socks present in the drawer.

    Output Format
    Print the number of Draws (x) Jim makes in the worst case scenario.

    Constraints

    1 <= T <= 1000
    0 < N < 10^6 

    Sample Input

    2
    1
    2
    

    Sample Output

    2
    3
    

    Explanation
    Case 1 : A pair of socks are present, hence exactly 2 draws for the socks to match.
    Case 2 : 2 pair of socks are present in the drawer. The first and the second draw might result in 2 socks of different color. The 3rd sock picked will definitely match one of previously picked socks. Hence, 3.

    How to solve:
    If you got 3 pairs of socks, then you got total three colors. After first 3 draws, the worst scenario is color 1, color 2, color 3. Then the fourth draw must be one of the colors that we got.
    If you got 4 pairs of socks, then you got total four colors. After first 4 draws, the worst scenario is color 1, color 2, color 3, color 4. Then the fifth draw must be one of the colors that we got.
    So on …
    Let n is the number of pair of socks, then just print out n + 1.

     
  • loctv 5:36 am on July 15, 2016 Permalink | Reply
    Tags:   

    Problem: Find Point 

    *Difficulty: Baby step

    Problem:

    Given two points P and Q, output the symmetric point of point P about Q.

    Input Format
    The first line contains an integer representing the number of testcases
    Each test case is a line containing four space separated integers Px Py Qx Qy  representing the (x,y) coordinates of P and Q.

    Constraints

    1 <= T <= 15
    -100 <= x,y <= 100

    Output Format
    For each test case output x and y coordinates of the symmetric point (each point in a new line).

    Sample Input

    2
    0 0 1 1
    1 1 2 2
    

    Sample Output

    2 2
    3 3

    How to solve:
    Suppose we got two point A(x,y) and B(x,y) the formula to calculate the coordinates of the middle point is:

    midx = (xA + xB )/ 2
    midy = (yA + yB)/ 2

    We already have the middle point and A, we just need to find xB

    xB = 2*midX – xA
    yB = 2*midY – yA

    Supper easy
    Screen Shot 2016-07-15 at 12.30.26 PM

     
  • loctv 4:49 am on July 15, 2016 Permalink | Reply  

    Problem: String Similarity (Z Function) 

    *Difficulty: Hard

    Problem:

    For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings “abc” and “abd” is 2, while the similarity of strings “aaa” and “aaab” is 3.

    Calculate the sum of similarities of a string S with each of it’s suffixes.

    Input:
    The first line contains the number of test cases T. Each of the next T lines contains a string each.

    Output:
    Output T lines containing the answer for the corresponding test case.

    Constraints:
    1 <= T <= 10
    The length of each string is at most 100000 and contains only lower case characters.

    Sample Input:

    2
    ababaa  
    aa
    

    Sample Output:

    11  
    3
    

    Explanation:
    For the first case, the suffixes of the string are “ababaa”, “babaa”, “abaa”, “baa”, “aa” and “a”. The similarities of these strings with the string “ababaa” are 6,0,3,0,1, & 1 respectively. Thus, the answer is 6 + 0 + 3 + 0 + 1 + 1 = 11.

    For the second case, the answer is 2 + 1 = 3.
    Note: I copy entire problem from hackkerrank just for education purpose, please don’t give me a lawsuit for the license or copyright 🙂

    How to solve:
    Well, to be honest,  I can only think of two way to solve. Unfortunately, they’re both O(n^2) complexity. Here is the easiest one, which I can instantly think of
    Screen Shot 2016-07-15 at 11.10.22 AM
    It works, but it’s too slow for all kind of input (I will explain later, because my second method work well on some kind of input, but not all) . The idea is dividing the string from input into substrings, check for the prefix similarity between the substring and the original string.

    My second method:

    Screen Shot 2016-07-15 at 11.17.07 AM

    This work well on some input like this:

    ababaa

    Start, we got i = 1, l = 0, r = 0, n = 0 (n means next, store the position of the next point, the next point is the first character (count from 1) of the substring that is the same with the character at 0)
    – The substring starts from i = 1 is ‘babaa’, prefix similarity = 0 , just because the first letter of the substring is different than the letter at position 0
    – The substring starts from i = 2 is ‘abaa’, prefix similarity = 3 (‘aba’), l = 2, r = 4, n = 4. Here we can choose either to step forward from r or n, because they’re both equal 4. So i = 4
    – The substring starts from i = 4 is ‘aa’, prefix similarity = 1 (‘a’), l = 4,r=4,n=0. Here because l == r, i will be equal with r + 1. Then reset l,r to zero
    – The substring starts from i = 5 is ‘a’, prefix similarity = 1 (‘a’), l = 4, r = 4, n = 0. Here is reach the end of the string, we check l,r. If l is not zero, if l equals r, then plus 1, otherwise, plus ((r-l)+1)
    Result = length(s) + 0 + 3 + 1 + 1 = 11
    But this method will run with O(n^2) complexity on some input like this:

    aaaaaaa

    abababababa

     

    And here is the ultimate method, aka Z FUNCTION .

    I don’t know you can understand it or not, but I don’t have time to understand it, so I skip to the most important part, the implementation of z function .
    Screen Shot 2016-07-15 at 11.33.20 AM

    And here is the implementation in Python 2 : (stringSimilarity)
    Screen Shot 2016-07-15 at 11.34.59 AM

    Note the last line of code , we must add length of the input string into the result, because the string itself is also its prefix similarity string, and the z function run from 1.

    Unfortunately, I cant update .txt file, which is big testcase file. So you have to spend your hackos to download it.
    After all, this is nothing than just implementation of an algorithm. If you can think of the z function without reading the article or searching for google, then you’re genius. :>

     

     

     
  • loctv 11:23 am on July 14, 2016 Permalink | Reply
    Tags:   

    Problem 102: Triangle containment 

    *Difficulty: Easy

    Problem:

    Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed.

    Consider the following two triangles:

    A(-340,495), B(-153,-910), C(835,-947)

    X(-175,41), Y(-421,-714), Z(574,-645)

    It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.

    Using triangles.txt (right click and ‘Save Link/Target As…’), a 27K text file containing the co-ordinates of one thousand “random” triangles, find the number of triangles for which the interior contains the origin.

    NOTE: The first two examples in the file represent the triangles in the example given above.

    How to solve: Python 2

    Well, you can use one of two ways below:
    1.

    In general, the simplest (and quite optimal) algorithm is checking on which side of the half-plane created by the edges the point is.
    Here is the triangle formed by three points, p1,p2,p3 and the point p inside
    Screen Shot 2016-07-14 at 5.54.58 PM

    If p inside the triangle, p has to be on the side of the half-plane created by edges: p1p2, p2p3, p1p3 .
    Here’s how you calculate the sign value of a point and an edge of triangle

    Screen Shot 2016-07-14 at 5.57.53 PM

    p inside the triangle created by three point p1,p2,p3 only if all signs value of p and p1p2, p2p3, p1p3 must be negative. Here is the checking function:
    Screen Shot 2016-07-14 at 6.02.29 PM
    p,p1,p2,p3 are Point  constructed by the class below:
    Screen Shot 2016-07-14 at 6.04.21 PM 1
    Open the file, read line by line and perform checking, if p inside the triangle, increase the count variable. Finally, print out the count variable
    Screen Shot 2016-07-14 at 6.06.19 PM
    Solution took 11.66 ms

    2.
    Using Barycentric coordinate system
    From stackoverflow:
    Screen Shot 2016-07-14 at 6.20.13 PM
    Screen Shot 2016-07-14 at 6.20.51 PM
    I leave you the implementation of this method.

     
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