code_m's Profile User Rating: -----

Reputation: 24 Tradesman
Group:
Contributors
Active Posts:
197 (0.1 per day)
Joined:
21-April 09
Profile Views:
4,538
Last Active:
User is offline Yesterday, 08:53 AM
Currently:
Offline

Previous Fields

Country:
US
OS Preference:
Linux
Favorite Browser:
Who Cares
Favorite Processor:
Intel
Favorite Gaming Platform:
Playstation
Your Car:
Hyundai
Dream Kudos:
25

Latest Visitors

Icon   code_m is looking for a job (willing to relocate). Please see my linkedin profile for more information.

Posts I've Made

  1. In Topic: Codility Challenge: Detected Time Complexity

    Posted 21 Jul 2014

    View Postsepp2k, on 20 July 2014 - 11:24 PM, said:

    sum(A[start:end]) takes O(end - start) time, which is O(end) in the worst case (that is the case where start stays at zero until the end). It will be executed with end taking the values 1 through n. So in total the time complexity will be O(sum end = 1 .. n: n) = O(n^2).


    So I still wanted to prove this, so I refactored the code to use only one loop, but still operate using sum and a slice. This did improve the overall performance, but was still rated at O(n**2):
    def solution(K, A):
        start = 0
        count = 0
        for end in xrange(1, len(A) + 1):
            if sum(A[start:end]) >= K:
                start = end
                count += 1
        return count
    


    So it seems this is definitely the case. Manually calculating the sum does provide a O(n) solution, though I don't really care for it.
  2. In Topic: Codility Challenge: Detected Time Complexity

    Posted 20 Jul 2014

    View Postsepp2k, on 20 July 2014 - 11:24 PM, said:

    sum(A[start:end]) takes O(end - start) time, which is O(end) in the worst case (that is the case where start stays at zero until the end). It will be executed with end taking the values 1 through n. So in total the time complexity will be O(sum end = 1 .. n: n) = O(n^2).

    Thanks. Didn't think that the sum's complexity would change the algorithm complexity.

    View Postmacosxnerd101, on 20 July 2014 - 11:33 PM, said:

    Rather than using the built-in sum() function, use a sum variable. Add the first n elements from start until end. If that is less than K, look at the end + 1 element and add it to the running total. Then look at the end + 2 element and add it to the running total if necessary. This is a linear time complexity solution.

    I figured that out. I was bothered by the reported complexity, not the actual solution. That's why it's in the Computer Science forum, not the "programming help" forum for python.
  3. In Topic: Have I created a memory leak (c-style strings)?

    Posted 12 Dec 2013

    I was aware there are bugs in the code, such as the edge case Salem_c mentioned. I appreciate the input, but I was only concerned about the memory usage of the code.

    So to be clear, I should be calling delete[] working; before my function returns? Should be truncating the array of result to the length of the string? If so, how can I do that without allocating a new array (or is that not possible)?
  4. In Topic: Gmail API? - Researching Automation Idea

    Posted 5 Dec 2013

    Update: smtplib will most definitely fill the need. :)

    Here's hoping accessing the database with go just as smoothly!
  5. In Topic: Gmail API? - Researching Automation Idea

    Posted 4 Dec 2013

    Thank you jon.kiparsky. I will check that out. Forgot to check the python built-in libraries, guess I should have assumed that was a thing :)

My Information

Member Title:
D.I.C Head
Age:
23 years old
Birthday:
November 16, 1990
Gender:
Location:
PA, USA
Interests:
Programming. Hockey.

When I'm not programming I am playing hockey. I normally play goalie, and I am actually pretty decent.
Full Name:
Cody A. Taylor
Years Programming:
3
Programming Languages:
C#, Python, C++, Java, VB.NET, Javascript

Contact Information

E-mail:
Click here to e-mail me
Yahoo:
Yahoo  codemister99
LinkedIn:
http://www.linkedin.com/in/codemister99
Facebook:
http://www.facebook.com/codemister99

Friends

code_m hasn't added any friends yet.

Comments

Page 1 of 1
  1. Photo

    code_m Icon

    04 Nov 2013 - 12:11
    Click "Send me a message" under the profile picture.
  2. Photo

    JA94 Icon

    04 Nov 2013 - 11:42
    hey
    how do i pm?
Page 1 of 1