Maximum sum sub-array

Here is a slightly more complicated one:

Q. Given an integer array containing N positive and negative numbers, find the sub-array having the largest sum in linear time O(N) using constant space O(1).

Want some hint?

 You need to keep track of both the maximum sum so far and the maximum sum for including an element. 

My solution (in Java):

    int[] largestSum(int... a) {
        int start = 0, end = -1, curstart = 0, last = 0, sum = Integer.MIN_VALUE;

        for (int i = 0;i < a.length; i++) {
            last += a[i];
            sum = Math.max(last, sum);

            if (sum == last) {
                start = curstart;
                end = i;
            }
            if (last < 0) {
                last = 0;
                curstart = i + 1;
            }
        }
        return Arrays.copyOfRange(a, start, end + 1);
    }
Advertisements

Multiplies all except itself

That’s another simple algorithmic challenge.

Q. Given an array of integers A of size N > 1, produce an output array B of size N with B[i] = A[1]*A[2]…*A[i – 1]*A[i + 1]…*A[N], that is multiplies all elements in A except A[i] itself. Do it in linear time O(N) without using division.

Please think about it first before looking at my answer and I hope there is a better one than mine.

My solution (written in Java):

void mul(int[] a, int[] b) {
    // Compute b[i] = a[0]a[1]...a[i]
    b[0] = a[0];
    for (int i = 1; i < a.length; i++) {
        b[i] = b[i - 1] * a[i];
    }
    // Compute result, with v = a[n - 1]a[n - 2]...a[i] after loop i
    int v = 1;
    for (int i = a.length - 1; i > 0; i--) {
        b[i] = b[i - 1] * v;
        v *= a[i];
    }
    b[0] = v;
}

Detect duplicates

Trying to start a new category to archive some algorithmic problems that I come across. Let’s start with a very simple one.

Q. Given an array of N elements in which each element is an integer between 1 and N, detect if there are any duplicates in linear time O(n) and constant space O(1).

Please think about it being looking at my code.

My solution (in Java):

// If we are allowed to modify the array, it can be as simple as the following.
boolean detectDup(int[] a) {
    for (int i = 0; i < a.length; i++) {
        int d = Math.abs(a[i]) - 1;
        if (a[d] < 0) {
            return true;
        }
        a[d] = -a[d];
    }
    return false;
}

I am lucky to get the new layout

Though a little bit off topic, looks like it starts rolling out.

Adding ping() function to PDO

Recently helped my colleague to add the missing mysqli_ping() function to PDO object in PHP. If anyone missed it, here it is:

class NPDO {
    private $pdo;
    private $params;

    public function __construct() {
        $this->params = func_get_args();
        $this->init();
    }

    public function __call($name, array $args) {
        return call_user_func_array(array($this->pdo, $name), $args);
    }

    // The ping() will try to reconnect once if connection lost.
    public function ping() {
        try {
            $this->pdo->query('SELECT 1');
        } catch (PDOException $e) {
            $this->init();            // Don't catch exception here, so that re-connect fail will throw exception
        }

        return true;
    }

    private function init() {
        $class = new ReflectionClass('PDO');
        $this->pdo = $class->newInstanceArgs($this->params);
    }
}

Stupid programming

Just come across a stupid piece of JS program today in some web site:

function preselectSS(what)
{
  if (what == 1) document.getElementById("selSS").selectedIndex = 0;
  else if (what == 2) document.getElementById("selSS").selectedIndex = 1;
  else if (what == 3) document.getElementById("selSS").selectedIndex = 2;
  else document.getElementById("selSS").selectedIndex = 3;
}

Isn’t it a lot nicer to write it as

function preselectSS(what) {
    document.getElementById("selSS").selectedIndex = (what > 0 && what <= 3) ? (what - 1) : 3;
}

The world is full of stupid programmers writing stupid programs.

Cross domain connection manager with same calling mechanism as YUI

Update: The same functionality is now provided by the Yahoo! YUI Get Utility.

Update 2: Since the domain I used to host the file is not longer exist, I just paste the JS at the end of the post.

The YUI connection manager use XMLHttpRequest to make remote call, hence calling cross domain URL is prohibited by the browser security model. This class is to solve this situation without the need to setup any server side proxy, while maintaining the same calling mechanism as the YUI connection manager.

Script source: http://rockstonesand.com/js/crossdomainmanager.js

Minified version: http://rockstonesand.com/js/crossdomainmanager_min.js

Usage: Same as YUI connection manager

Functions supported:

asyncRequest, isCallInProgress, abort

Example:
Client side:

<script src="http://rockstonesand.com/js/crossdomainmanager_min.js"></script>
<script>
// Same callback object definition as YUI connection manager
var callback = {
    success: function(obj) {
        var response = obj.responseText;
        // Do UI updates
    },
    failure: function(obj) {
    }
};
var txId = CrossDomainConnect.asyncRequest(
   "http://api.flickr.com/services/feeds/photos_public.gne?lang=en-us&format=json",
   callback,
   "jsoncallback");
</script>

Limitations:

  • Only GET method is supported, as it uses script tag hack
  • The target server side script must support an additional “callback” parameter for the connection manager to specify a callback function. Continue reading