CareerCup

The problem states that the array is unsorted, but this seems like a reasonable approach for the sorted case.

You can also start at the left side, taking the heads of each list and forming an N-wide tuple: (0, 1, 5). Sweep through the tuple values to find the min and max, which will give you the current range, and then choose the array that the min came from and advance it by one position for the next iterations. So, after considering (0,1,5), next consider (3,1,5), then (3,4,5), then (6,4,5). After (6,4,5), there is no way to advance beyond the 4, so you stop, as advancing either of the other letters is only gonna make your range wider.

Linear Python Algorithm.

(At first glance, this might appear to be N*N, but if you look at the inner loops, you can convince yourself that each inner loop can only run a linear number of times, due to the way they advance start and end.)

def doc_range(D, L):
    d = {}
    n = 0
    for c in D:
        for i in D[c]:
            d[i] = c
            n += 1
    cnts = {}
    for c in L:
        cnts[c] = 0
    start = 0
    end = -1
    letters_counted = 0
    min_len = n
    while True:
        while letters_counted < len(L):
            end += 1
            if end >= n:
                break
            c = d[end]
            if c not in cnts:
                continue
            if cnts[c] == 0:
                letters_counted += 1
            cnts[c] += 1
        if end >= n:
            break
        while True:
            c = d[start]
            if c not in cnts:
                start += 1
                continue
            cnts[c] -= 1
            if cnts[c] == 0:
                break
            start += 1
        l = end + 1 - start
        if l <= min_len:
            min_range = (start, end)
            min_len = l
        start += 1
        letters_counted -= 1
        cnts[d[start]] = 0
    return min_range

D = {}
D['a'] = [0,2,7,8]
D['b'] = [1,6]
D['c'] = [3,9]
D['d'] = [4]
D['x'] = [5,10]
L = 'acx'
print doc_range(D, L)

@Loler, yep. I like your algorithm, by the way. I just wonder if there is another way to tackle this, like maybe something that starts with the most adverse leg of the trip and then somehow divides and conquers on either side of that station.

If you have a doubly linked list, then you can do this in linear time and constant space.

With a singly linked list, you can't do this in constant space unless you're willing to pay for O(N-squared) time. To do it in linear space, you can push the node pointers corresponding to the first N/2 characters on to a stack, then pop them off as you're working through the last N/2 characters. If you don't want to maintain your own stack, you can use recursion, but there's still a stack, so it's still gonna be linear time. And, really, if you're stuck with linear time, then it might be more simple overall to just slurp all your characters into one big string, and then solve the simpler problem of finding out whether a string is palindromic.

@Loler, you are right. After digging deeper, I am now confident that I can get to the first solution in linear time (which is better than a naive approach), but like you say, if I'm "lucky" enough to get all the way around, then I'm pretty much back to where I started for finding the 2nd solution.

@Loler, I think it's linear, because each iteration is done in constant time and advances one of the pointers (either starting city or ending city). Do you have a worst case scenario in mind?

@Expressions, tell me if my logic is flawed here. Let's say that I start at city 0 and can get to city 8 without running out of gas, but then the trip from 8 to 9 puts me at a deficit. At this point I can rule out all the cities between 0 and 8 as starting points. Let's take city 4 as an example. We know that the trip from 0 to 4 is net positive, yet the trip from 0 to 9 is net negative, so the trip from 4 to 9 must also be net negative. Instead of moving the start node backward, does it make sense to move it one past the last ending city?

This is not 2^N. It's 2^(2*N), otherwise known as 4*N. Why not just solve this in 3^N, iterating through trinary numbers 0 through 3^N-1.

0 bit = use neg
1 bit = don't use
2 bit = use pos

@jay, In Python you can use tuple assignment to make this a little more concise:

prev1, prev2 = (prev2+prev1, prev1)

Also, there is an O(log N) solution that uses only integer arithmetic. See "Python O(logN) version. "

Python O(logN) version.

This uses some recursive properties of the Fibonacci numbers to compute an individual number in logN time. It's the most efficient solution that I know of that doesn't use floats. It's all integer multiplication and addition.

def fib(n):
    if n == 0:
        return 0
    return fib2(n)[1]

def fib2(n):
    # returns (fib(n-1), fib(n)
    if n < 5:
        return tuple([0,1,1,2,3,5][n-1:n+1])
    x, y = fib2(n / 2)
    a = x*x + y*y
    b = (2*x+y)*y
    if n % 2 == 1:
        a, b = (b, a+b)
    return (a, b)

for i in range(20):
    print fib(i)

Also, this game can be reduced to a similar game, where the goal is draw the last coin. Basically, you set aside the final coin. So the N=7 don't-get-stuck-with-the-coin game becomes the N=6 grab-the-last-coin game. To play the grab-the-last-coin game, you want to leave your opponent with 3 coins, and then they can't grab all of them, but they have to take one, leaving you with the last winning draw.

The strategy works for other variations of this game. Let's say users can draw 9 coins max, but they're compelled to draw at least 1, and the goal is to make the last grab. If I can leave you with 10 coins in that game, then I win. Likewise, I control you if I can stick you with 20, 30, 40, 50, 60 coins, etc. The first player always win that game, as long as the starting number of coins isn't an exact multiple of 10. (If the game starts with 100 coins, then player A is already under control by B.)

This is a fine way of approaching the problem, but if you are storing the results as you emit them, then you can make Q2 and Q5 be virtual queues. In other words, don't store all upcoming Q5 values; instead, simply keep track of the head of the queue. For Q5=10,20,25,40, think of it as 5*[2,4,5,8], where [2,4,5,8] is just a subset of the numbers that you've already produced. In this case, you just store the index of "2" in the original result to know the head of the queue. When you peek at Q5, you multiple 2 by 5 to get 10. When you pop Q5, then the next element will the index of 4 in your result set. This type of reasoning basically gets you to the solution that @nitingupta180 presented.

I would generate integer ids for names and phone numbers that get entered into the mobile phone. (I know phone numbers are already integers, but the ids would be shorter.)

Then maintain two parallel maps:

name id -> phone number id
phone number id -> name id

You could implement the maps as hashes, or you could implement them as simple arrays and do binary search. If you go the array route (an array of tuples of ints), then lookups in both directions will be log N, displaying the contact list ordered by name will be O(N), and insertions/deletions/edits will be O(N), but you'll dealing with ints, so they'll be fast.

If you're mostly dealing with lookups, then a hash will be sufficient, but if you are frequently displaying contact names, then you'll want some sort of auxiliary data structure that has the names already in order (either explicitly via an array or implicitly via a binary tree).

One metaphor for this problem is that you have a mating game. You have a bunch of piece that want to mate. When two pieces mate, they create a child, and the parents die off. All pieces--single and combined--have a "survival fitness" tied to them. A piece's fitness is a measure of how well it mates with other pieces to form other nice shapes. At any stage of the mating game, you're trying to first mate off pieces with the lowest survival probability, so that you can kill them off and let their children prosper.

Before the game even starts, you can do some analysis on piece types, including small compound pieces, to create a compatibility graph, where the nodes are piece types, and the weight of the edges to other piece types indicates some sort of inclination for ideal mating.

A greedy algorithm would start with the most troublesome piece, and then iterate through the compatibility graph to find types to mate to, checking the actual bag of pieces to find out if there available mates for that type. Then marry the pieces, create the child, and kill the parents.

I'd start with some greedy algorithm that basically simulates the decisions that a human Tetris player makes. Just iterate through the shapes, and drop them to the lowest level possible. Orient each shape so that it's longest side is on the bottom, then find the lowest level that provides a long enough platform for the whole bottom to sit on top.

Adding T-shapes and L-shapes to the mix creates the necessity of having handling "holes" and plugging holes. When you encounter a T-shape or L-shape, look for a way that it can snugly fill a hole; otherwise, push it to the end of the queue.

Consider shapes that fit nicely together. Two troublesome Ls can be joined together to make a rectangle. You can preprocess your list in advance to try to pair up Ls.

Eventually, you'll want some kind of backtracking scheme. You provisionally place a piece, but maybe subsequent pieces can't plug the holes it creates. If so, roll back and try another piece.

Definitely not a trivial problem.

B always wins. B responds with the opposite play of A, so that after B's first turn there are 4 coins, then after B's second turn there is 1 coin. B's strategy is the same for 10, 13, 16, etc.

A wins the variations on N=8 and N=9 by leaving 7 coins on the table after the first turn.

Barry, I almost made the exact same comment that you did, but the question does state "ignore any whitespace or punctuation." So, if you take the formulation at face value, you can't simply whitelist alphas, since there are plenty of non-alpha characters that pass the criteria (namely, digits). Good thing to clarify with the interviewer, of course.

You can make your code a little more concise by changing your inner "while" statements to be "if" statements and use "continue" when they evaluate to true (after either incrementing start or end, respectively). If you do this, you can avoid the "start <= end" checks.

This sounds like nitpicking, but the deeper benefit is that you could reason about the outer loop more easily. If every time through the loop the code only ever adjusts the pointers by one (or returns), it's a little easier for a reader to reason their way through your code, not only in terms of correctness, but also in terms of O(N) time.

Having said that, it's a nice, solid, clear implementation.

Your code runs in O(N squared) time and uses O(N) storage. It can be solved almost as easily in O(N) time and O(1) space. Maintain two string indexes, one moving forward from the front and one moving backward from the end, and keep comparing them until you have a mismatch, at which point you can immediately return false. Terminate and return true if and when the pointers meet.

(It runs in O-squared time, because inside your O(N) loop each call to "c1 = c1 + c" has to copy O(N) characters, due to Java using immutable strings.)

Why do you created sorted_dictionary in advance instead of just sorting the word in your for loop or your isContained() function? Seems like a lot of wasted storage.

Nice use of while/else. If you want to get really idiomatic with Python, create a generator that yields the length of all valid words and consume that with the built in max() method. Here's a sketch:

def yo():
    yield 1
    yield 3
    yield 2

print max(yo())

This is a nice answer from a theoretical complexity and robustness standpoint, but it's wildly inefficient. For every character you're reading, you're incurring memory overhead and runtime overhead. If you think about what malloc()'s doing under the hood, it's a pretty expensive operation.

@Anonyomous, you're basically describing a "successor" function, which is always an interesting way to think about problems involving combinations and permutations, and which leads to "odometer" algorithms. Basically, for all the subsets that can produce 55, you know that they have some sort of natural ordering, and if you're given one of the subsets, then there should be a deterministic way to perturb its elements in a minimal way to get the next result.

In this problem, you've already described the basic mechanism to some degree. Start by trying to perturb the second to last element, but it might be "stuck," as you say. In that case, you have to perturb the third to last element instead. And, of course, for every number you perturb in one direction, perturb another number in the opposite direction.

This is the best way to do this. You can think of i and j as chasing pointers, where i's value is waiting to be doubled and j's value is waiting to be quintupled. After a while your array will look something like this:

1
2
4
5
8 j
10
16 i
20
25
?? k

i is pointing to 16, which means it's queuing up 2*16 == 32
j is pointing to 8, which means it's queuing up 5*8 == 40.

On the next pass, 32 will be smaller, so that's you're next result, and then i will advance to 20, thereby queuing up 40.

On the next pass, you'll have a tie.

@nitingupta180, nicely done.

Simple Python Version.

def test():
    assert [] == list(smooth_2_5(0))
    assert [1] == list(smooth_2_5(1))
    assert [1,2,4] == list(smooth_2_5(3))
    assert [1,2,4,5,8,10,16,20] == list(smooth_2_5(8))

def smooth_2_5(n):
    if n == 0:
        return
    queue = [1]
    cnt = 0
    while True:
        result = queue.pop(0)
        yield result
        n -= 1
        if n == 0:
            return
        if result*2 not in queue: queue.append(result*2)
        if result*5 not in queue: queue.append(result*5)
        queue.sort()

test()

Python Blow-Your-Mind Version.

Google "activestate python hamming numbers" for more explanation. This code is a minor adaptation:

from itertools import tee, chain, islice, groupby
from heapq import merge

def hamming_numbers():
    def deferred_output():
        for i in output:
            yield i

    result, p2, p5 = tee(deferred_output(), 3)
    m2 = (2*x for x in p2)
    m5 = (5*x for x in p5)
    merged = merge(m2, m5)
    combined = chain([1], merged)
    output = (k for k, v in groupby(combined))
    return result


if __name__ == '__main__':
    print(list(islice(hamming_numbers(), 10)))

Yet another C approach (fully runnable).

This is pretty simple, but note the check for (t < s) may be more wasteful than simply overwriting *t with its own value. There's no harm in that, and you would avoid a conditional.

#include <stdio.h>

void remove_commas(char *s) {
    char *t;
    char c;

    for (t = s; c = *s; ++s) {
        if (c == ',') continue;
        if (t < s) *t = c;
        ++t;
    }
    *t = '\0';
}

int main(int argc, char **argv) {
    char arr[] = "1,234,34,54";
    remove_commas(arr);
    printf("%s\n", arr);
    return 0;
}

Another way to slice this is to do sort of a breadth-first search. First make a hash of all the common 2-grams across all the lists, pruning as you march down the lists. For each 2-gram, keep a cache of locations within each list. (If the list of 2-grams is empty, just have special case code to find a single character in all strings.)

Then when you go the 3-gram phase, start with all the 2-grams for the first list, and find their 3rd character. Let's say you start with ce and the first occurrence of ce in the first list is followed by x, giving you the 3-gram of cex. If "ex" is not in the map of 2-grams common to all lists, then you'll know that cex won't be in all lists either (for obvious reasons), so you can prune immediately. Otherwise, push it on to the list of working 3-grams, and then keep proceeding through the 2-grams for list one. In processing the second list, update the working list of 3-grams, then at the end, sweep all the 3-grams that only showed up in both of the first two lists. Keep continuing in this fashion until you can't extend any of the n-grams.

Simple Recursion in Python

def subsets(low, high, n, target):
    def f(low, n, target, prefix):
        if low >= high:
            return
        if n == 1:
            if low <= target < high:
                yield prefix + [target]
            return
        for i in range(low, high):
            cnt = 0
            for result in f(i+1, n-1, target-i, prefix + [i]):
                yield result
                cnt += 1
            if cnt == 0:
                break

    for result in f(low, n, target, []):
        yield result

for ans in subsets(10, 100000, 4, 55):
    print ans

Here's a pseudopolynomial solution that updates counts:

from collections import defaultdict

def num_subsets(a, target):
    a = map(abs, a)
    a.sort()
    counts = defaultdict(int)
    counts[0] = 1
    for elem in a:
        new_counts = defaultdict(int)
        for k in counts:
            new_counts[k+elem] += counts[k]
            new_counts[k-elem] += counts[k]
            new_counts[k] += counts[k]
        counts = new_counts
    return counts[target]

arr = [-5, 1, 2, 3, 4, 6, 7, 8]
target = 12
print num_subsets(arr, target)

@JDev, That seems fairly understandable. This is my take on it, where I try to make it very explicit that I'm iterating through all 3**N possibilities:

def subsets(a, target):
    a = map(abs, a)
    for i in range(3 ** len(a)):
        bits = []
        n = i
        for j in range(len(a)):
            # make the bits collate nicely by
            # inserting at the front
            bits.insert(0, n % 3)
            n /= 3

        result = []
        sum = 0
        for j, bit in enumerate(bits):
            if bit == 0:
                result.append(-1*a[j])
                sum += -1 * a[j]
            elif bit == 2:
                result.append(1*a[j])
                sum += a[j]
        if sum == target:
            yield result

arr = [-5, 1, 2, 3, 4, 6, 7, 8]
target = 12
for solution in subsets(arr, target):
    print solution

P.S. The solution I described is way over-engineered for most practical uses cases. Instead of building your own paging scheme, it's usually wise just to call realloc() in optimistic increments. Nine times out of ten, realloc() won't have to move memory around, and even when it does, it's fast and amortized over the long run. For some OS'es, the memory model is probably some kind of virtualized paging scheme, so if you followed my initial advice, you'd be building a paging system on top of a paging system, which is just dumb.

I'm guessing the interviewer was wanting to handle an arbitrarily large sequence of characters, and you can't preallocate infinite memory, and you also don't want to incur excessive reallocs() not overly granular mallocs(). What I'd do here is allocate 100 bytes of memory at a time, and connect those chunks with a linked list, where you insert each new chunk at the front. You basically have a stack of stacks, where the outer stack is a linked list and then inner stacks are array based. To produce the string in reverse, pop the arrays off the linked list in forward order (er, forward through the linked list, which is backward in terms of insertion order), and iterate the arrays backward.

When an element enters the queue from the back, it can knock out all the smaller elements in front of it, because those elements are also older than it. Since every new element enters the queue at its proper position in terms of bigness/smallness, you are guaranteed that the queue preserves order.

An element may eventually reach the front of the queue, even though it's too old to actually count for anything, but @nitingupta180 handles that by just dropping them on the floor when they reach the front if they're too old. I suppose you will occasionally have multiple elements at the front of the queue that need to be dropped, but this will be balanced by occasions where the front element is young enough.

I agree with @jay, but I could just be lacking imagination. It's pretty easy to construct tricky scenarios for k=5:

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
11 12 13 14 15 80 90 100 70 60 6 7 8 9 10

My hunch is that if you design a data structure that performs well on the former, it's probably gonna churn on the latter, and vice versa.

Oops, you can also solve the original problem with 6-4-1, but hopefully you get the idea. Introducing the additive inverses leads to solutions where the same original number gets represented twice (once for both signs), when it should have been represented zero times, and you end up wasting precious CPU to sift through the duplicated scenarios that only exist because you crufted up the array in the first place.

@JDev, See my comment to @zyfo2. You are not only turning a 3^N problem into a (2*2)^N problem, but you're also incurring a lot of work to sift through redundant solutions. Let's say 4 is not part of the ultimate answer. You'll get a bogus solution that has 4 and -4 from zyfo2's hacky solution before the post-processing step. And it gets even worse. Consider a target of 1 and the input [1,4,6]. The only valid solution to the original problem is [1], but you'll have to exclude [1,4,-4], [1,6, -6], and [1,4,-4,6,-6] in your post-processing. It gets even nastier for [1,-4,4,6].

This is basically the game Othello.

If the blue and red tiles are already given, then you iterate though the red tiles, then find the lengths of spokes from the red square in terms of blue tiles. There will either be four or eight spokes, depending on whether the game accommodates diagonals.

For a long running game, you can maintain a data structure that has the color of each square and the length of the spokes from that square, for both colors. (If the board is small enough, you should just recompute on the fly). If you have Othello rules and flip a whole run of colors, you have to obviously update the data structure for each cell flipped, which means propagating out through the spokes for each cell flipped.

My gut says that the interviewer isn't testing your knowledge of data structures and algorithms with this question; it's more about showing basic coding nuts and bolts.

This is an odometer problem. Skip over the null digits (0 and 5). For the rest of the digits, populate the odometer with the first character for each digit. Then start rolling the odometer. Start with the digit on the end and go to its next character. If you reach the end of that digit's list, go back to the first character for that digit (and all previous digits) and roll the next digit's character. When you overflow the last digit's character, you are done.

You don't seem to be accounting for negative numbers at all. Try transcribing this to Java:

f(target, list) = f(target-head, rest) + f(target, rest) + f(target+head, rest)
f(0, []) = 1
f(target != 0, []) = 0

I think the magic here is that once an element is compared to a younger member in the queue and found lacking, you can mark it as a "permanent loser." By the time an element works itself through the queue, it will likely have earned the "permanent loser" status, and you can pop it off the queue with no ceremony (zero time). A few elite nodes will work their way entirely through the queue without being displaced by younger elements, and their retirement will cause a flurry of successors to duke it out for the throne, but this power struggle is amortized by all the previous permanent losers retiring without ceremony. Also, the power struggle will cause roughly half of the participants to permanently retire, knowing that they already lost a younger element that will out-survive them by definition of the queue's inherent properties.

My metaphor for this is that you have a league of 1000 fighters or so, and they have constant fighting ability throughout their career. Fighting ability is transitive. Also, the most experienced fighter always retires first, but you have a variable influx of new fighters.

99.9% of fighters are not elite. They come into the league, try to fight the most elite fighter, and lose. Their record goes to 0 and 1. Severely embarrassed, they don't waste their time fighting other inferior fighters; they instead get on the waiting list to become the next most elite fighter after the most elite fighter retires.

Soon, a non-elite fighter retires with no hoopla, and he's not on active waiting lists either. Then another non-elite fighter retires again with no hoopla. And another. And another. All the non-elite fighters have lost to somebody younger in their career, and that younger fighter has already been crowned or similarly defeated.

Finally, an elite fighter retires. During his reign since the latest elite fighter retired, maybe 100 new fighters have come into the league, lost to him, and stayed on the waiting list. There are a whole bunch of fighters who have only lost to the retiring elite fighter, and they establish a fighting ladder to find the new successor. Losers who lose to older fighters get to stay on the waiting list, but if an older fighter loses, he is deemed to be a permanent loser, because the younger fighter will always be around to beat them. Only one fighter remains undefeated after the ladder works out, and he's the new elite guy. Fighter who lost to older fighters don't get elite status, but they stay on the waiting list.

My intuition says this system fairly keeps one fighter in the elite position, and it minimizes the need for unnecessary fights, but I'm not sure it's even amortized O(1) fights.

Look at "counting sort" in wikipedia. I edited my answer to say 50k, not 500k--sorry, the I miscounted the zeros (dyslexia). There are perfectly valid solutions that run in the 10k size array (in-place heapsort, in-place quicksort, etc.), but many of them run in NlogN time, which is inferior to a counting sort for a small range of numbers. Like I said, I think the interviewer chose the numbers cleverly, because the counting sort might not actually beat the in-place sorts in terms of actual time, and the counting sort is obviously inferior in terms of space usage (but usually time is constrained more than space).

Every time X or Y moves, look at all eight spokes from the new position (N/S/W/E/NE/SE/SW/NW), and determine if any of the new spoke lengths will reach exactly 3, 6, or 8. Depending on whether it's X or Y, update the running score appropriately. For X reaching 6 marks, my interpretation is that you only incrementally increase the score by 2 points, but you should clarify with the interviewer.

For a large value of N, considering caching spoke lengths in all eight directions for any given point. You will only need to maintain values at the endpoints. If you place an X southwest of a square that also has an X, read the cache to determine the neighbor's northeasterly spoke length, rather than iterating all the way to the end of the segment.

For sorting numbers between 1 and 50,000, the interviewer might have expected you to produce an O(50k)-time solution. Initialize an array from 1 to 50,000 with zeros. Iterate through your numbers and update the appropriate buckets. Then go through the 50k-sized array and emit the numbers in order, using the bucket counts to determine how many values you emit. I think the interviewer is kind of clever, because the 5:1 ratio of max-value to N is in the range where a traditional O(NlogN) might actually be faster.

The second question was about finding the best sort for arrays and linked lists. For arrays, quicksort and heapsort are pretty comparable, because they can both be done in place in O(NlogN) time. For linked lists, you can cheat by copying the linked list into an array in linear time, but linked lists also play really nice with quicksort. Pop the head off the list, and use that as a pivot. Partition the lows and highs into two new linked lists. Recursively sort the other linked lists, then chain them back together.

Here's the key piece of a linked list based quicksort:

LIST quicksort(LIST list) {
    if (!list.head) return list;
    PNODE head = list.head;
    char *pivot = head->value;
    LIST smalls;
    smalls.head = NULL;
    smalls.tail = NULL;
    LIST bigs;
    bigs.head = NULL;
    bigs.tail = NULL;
    PNODE p;
    PNODE p_next;

    for (p = head->next; p; p = p_next) {
        p_next = p->next;
        p->next = NULL;

        if (strcmp(p->value, pivot) > 0) {
            bigs = append_node(bigs, p);
        }
        else {
            smalls = append_node(smalls, p);
        }
    }
    head->next = NULL;
    bigs = quicksort(bigs);
    smalls = quicksort(smalls);
    return concat(append_node(smalls, head), bigs);
}

Also, Model/Viewer/Controller is your friend for this problem:

model = matrix of (X/Y/None) values
view = code that draws the board and displays notifications (Alice Won!)
controller = code that prompts users for their next entries

The model for tic-tac-toe is dead simple. The view and controller is where this problem gets interesting, because depending on your notion of MVC, some responsibilities will be a bit blurry as to whether they go into the controller or the view.

The key thing on this type of question is not to freeze up. Get something on the whiteboard:

1) You want to draw the board. Have a DrawBoard class (or function).
2) You have players. Have a Player class.
3) Players take turns. Have a GamePlay class.
4) You need to keep track which moves have been made. Have a Game class.
5) You need to decide if somebody won. Have a GameEvaluate class.

Get something out there, then work with the interviewer to simplify things. Do you really need a special GameEvaluate class? Maybe a Game object can supply the method that says whether a game is over. Seems like a reasonable responsibility for the game class. But maybe the actual calculation drives out a simple Matrix class.

The key thing here is to be flexible and brainstorm.

Also, don't let the full complexity of the problem overwhelm you. Before you figure out how to orchestrate players taking turns, simplify the problem. Say that you just read the player's answers from a file, fill in the grid, and then say who won. If you can figure out how to model that, you have a good foundation for the rest of the problem.

P.S. Most of the discussion on this actually happened in the thread started by @tpcz at the (current) top of the page.

@eugene, Sorry that this thread is kind of scattered, but there are several solutions under consideration:

1) With a totally naive but simple solution, you iterate all N-squared solutions and compute each square in O(N) time for N cubed time. While slow as heck, this is easy to read.

2) In the center-inward and center-outward approaches, you go about examining you ranges in a way that allows each left-hand sum to be computed easily from the prior left-hand sum by just adding one element. This is a nice solution, because it's N-squared and requires no extra data structures. Its only drawback is that you have to search the solution space exhaustively.

3) If you suspect that there are valid solutions for long substrings, you can modify the N-cubed solution to examine long substrings first, so that you can exit as soon as you find your conditions satisfied. This is still N-cubed for the worst case, but it's linear-N for the best case.

4) You can modify solution #3 to use a cache for partial sums. This was my original solution, which I found unsatisfactory for several reasons.

5) Lastly, you can precompute the S() function to make all subsequent sum conditions be constant time. Then you proceed through the O(N*N) possible answers in order of reverse length, which allows you to exit early as soon as your find left == right.

@zyfo2, If you approach this problem directly, it's 3 to the N, so e.g. 5 values leads to 243 cases to consider. If you try to force the square peg into the round hole and add five additive inverses to your set, now you have 1024 cases to consider, many of which aren't even valid and lead to an awkward post-processing step in the case where your initial elements repeat the same absolute value. Just solve this directly.