Problem of the day: Detecting cycle in a linked list

Today I was looking at problems related to linked lists. They tend to be asked quite a lot in interviews but some of them look artificial with their complexity arising from linked lists being a poor data structure for the problem (e.g., median of a sorted linked list). The problem of the day for today is Detecting cycle in a linked list: Given a linked list, return the node where the cycle begins or null if there is no cycle. For example, in the image below, 4 should be returned.

cycle-in-linked-list

Continue reading

Advertisements

Scheduling to minimize lateness

The problem can be stated as follows :

“Given a set of n jobs all of which must be scheduled on a single resource such that all jobs arrive at time s and each job has a deadline di and a length ti, minimize the maximum lateness of the resulting schedule.”

We need to assign a start time si to each job i. Jobs are allowed to be late i.e., a job i may finish at time fi = si + ti > di. If job i is late, its lateness is defined to be li = fi – di. Otherwise, li = 0. So the objective is to find a schedule that minimizes the maximum lateness, L = maxi li.

Continue reading

Interval Partitioning Problem

The interval partitioning problem is described as follows:
Given a set {1, 2, …, n} of n requests, where ith request starts at time s(i) and finishes at time f(i), find the minimum number of resources needed to schedule all requests so that no two requests are assigned to the same resource at the same time. Two requests i and j can conflict in one of two ways:

  1. s(i) <= s(j) and f(i) > s(j)
  2. s(j) <= s(i) and f(j) > s(i)

Example: Given 3 requests with s(1) = 1, f(1) = 3, s(2) = 2, f(2) = 4, s(3) = 3, f(3) = 5, at least 2 resources are needed to satisfy all requests. A valid assignment of requests to resources is {1, 3} and {2}.

Continue reading

Interval Scheduling Problem

The interval scheduling problem is described as follows:

Given a set {1, 2, …, n} of n requests, where ith request starts at time s(i) and finishes at time f(i), find a maximum-size subset of compatible requests. Two requests i and j are compatible if they do not overlap i.e., either f(i) <= s(j) or f(j) <= s(i).

Example: Given 3 requests with s(1) = 1, f(1) = 3, s(2) = 2, f(2) = 4, s(3) = 3, f(3) = 5, the maximum-size subset of compatible requests is {1, 3}.

Continue reading