Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

Archives for October 2015

Solving UVa 11402 with Segment Trees

By Duncan Smith Leave a Comment Oct 28 5

Pirate

UVa 11402: Ahoy, Pirates! is one of the most challenging of the uHunt starred problems I have come across so far, for a few reasons:

  • The problem is designed to be solved using a segment tree. This is a data structure that comes up in competitive programming, but isn’t covered in the standard algorithms textbooks (e.g., Sedgewick or CLRS). So I studied it for the first time in preparation for solving this problem.
  • A static segment tree like the one described in Wikipedia, is not sufficient. Solving this problem requires a segment tree that implements lazy propagation so that updates can be made efficiently.
  • As an extra challenge, the problem author added the requirement for an “invert” operation. This adds some implementation complexity and means a generic segment tree implementation won’t work.
  • Java solutions seem to run very close to the time limit, which is a generous five seconds for this problem. Even an efficient solution that addresses the previous points may nevertheless need some additional performance tweaking to run fast enough.

Read on for solutions to these issues, and an explanation of how to go about coding a solution.

« Continue »

Cal and Scott’s Top Performer Course

By Duncan Smith Leave a Comment Oct 21 0

Bubble

In an earlier post, I mentioned a pilot course I took a couple of years ago on applying deliberate practice to various types of jobs. Well that original pilot, and a subsequent pilot in 2014, has resulted in a course called Top Performer (not an affiliate link). As part of the homework for the second pilot, I came up with the idea for Project 462 and this blog. So as people are considering the course this week, I thought I would add my thoughts to the mix.

« Continue »

Software Methodologies for Very Small Teams

By Duncan Smith Leave a Comment Oct 14 0

Bootstrap DNA

When I was working on my undergraduate degree in Computing and Software Systems, I took a class in software engineering. The purpose of this class was to introduce us to the range of real-world processes that professionals use to develop software, processes that didn’t often come up in our academic work. That goal turned out to be a tall order for a three-month class, given the scope it tried to cover. It might have been more effective to pick one process and use it for a group project. Nevertheless, one exercise I remember from the class is matching software development processes to types of projects.

Here’s the type of question I’m talking about, from a University of New Brunswick class assignment:

Giving reasons for your answer based on the type of system being developed, suggest the most appropriate generic software process model that might be used as a basis for managing the development of the following systems:

a) A system to control anti-lock braking in a car

b) A virtual reality system to support software maintenance

c) A university accounting system that replaces an existing system

d) An interactive travel planning system that helps users plan a journey with the lowest environment impact

« Continue »

Using Integers and Longs in Java

By Duncan Smith Leave a Comment Oct 7 0

101010

Programming puzzles frequently involve manipulation of integers. And even problems that are mainly about string manipulation, character sets, or floating point arithmetic need integers for array indexes and counters. So it pays to know how to use them. In this article, I’m going to cover some of the quirks of integers and longs as implemented in Java.

« Continue »

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • LeetCode 1288: Remove Covered Intervals January 20, 2021
  • LeetCode 227: Basic Calculator II January 13, 2021
  • A Project for 2021 January 6, 2021
  • Lessons from the 2020 LeetCode Monthly Challenges December 30, 2020
  • Quora: Are Math Courses Useful for Competitive Programming? December 23, 2020
  • Quora: Are Take-Home Assignments a Good Interview Technique? December 17, 2020
  • Quora: Why Don’t Coding Interviews Test Job Skills? December 9, 2020
  • Quora: How Much Time Should it Take to Solve a LeetCode Hard Problem? December 2, 2020
  • Quora: Quantity vs. Quality on LeetCode November 25, 2020
  • Quora: LeetCode Research November 18, 2020
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2021 Duncan Smith