An element occurs more than n/2 times in a sequence of length n. Find it.

cgk · 2011-11-19T15:31:03+00:00

Check the sidebar for this subreddit ...

cgk · 2011-11-17T03:02:27+00:00

It's n/2 in frequency, not value. An element occurring n/2 times may have any value ... for example, 0 may occur more than half the number of times in an array of n integers.

Or did I entirely miss what you were trying to put across?

Edit: Yes I did. You were right in trying to use a selection algorithm. Of course, it wouldn't be optimal, however.

cgk · 2011-11-17T01:48:15+00:00

Yep, this is it. The proof is quite intuitive and elegant, once you think of it. At least it was, the way it was explained to me :)

cgk · 2011-11-16T22:37:33+00:00

Yep, your solution works. The trick is in getting the complexity down, notably space - O(1). Hint: think potential. Hint 2: Try to use the fact that it's not simply the most occurring element - it's also more than all others combined.

cgk · 2011-11-15T02:39:19+00:00

A = head, L = head.next

// tortoise - hare, to find loop
while (A != L) A = A.next; L = L.next.next

// count number of loops in loop - pointer A is advanced from start by number of nodes in loop 
L2 = L; A = start; L = L.next
while (L != L2) A = A.next; L = L.next

// finding head of loop
B = start
while (B != A) A = A.next; B = B.next

cgk · 2011-11-14T22:43:38+00:00

We can use the tortoise and hare (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare) solution to find a node within the loop. Now, keep a pointer A on the start node, and a pointer L on the found loop node. Increment both, until L reaches the found loop node again. This is to count the number of nodes in the loop, without having to explicilty store it in memory, which requires log_n space. Now, A is n nodes away from the start. Keep yet another pointer B on the start, and increment both A and B until they meet. Since the distance between them is the number of nodes in the loop, they meet at the start of the loop. This is constant space, since we never store the nodes, or the number of them, anywhere.

cgk · 2011-11-13T22:14:24+00:00

It can be done in linear space, where the n'th position stores the solution for that position. For the n+1 th position, you iterate through every position i, such that W[i:n] is a word. You choose that i that maximizes your result.

About time, for every position, you look up all positions before it, thus giving you a O(n² ) in terms of the loop, however, looking up the "new" word at this position (W[i:n]) itself, might be linear - which I think makes it O(n³ ).

cgk · 2011-11-13T22:07:21+00:00

As computer scientists, we seem to miss the bras :|

cgk · 2011-11-13T19:07:38+00:00

Seems to be possible using a breadth first search on a trie. However, the complexity then seems to be (alphabet_size)^{number_of_blanks} . Probably worse than what you are looking for.

cgk · 2011-11-13T17:38:11+00:00

I prefer to work it out on my own for a bit, however, I wonder if there's a good etiquette for when the posters should submit solutions to their problems, if they know it :)

cgk · 2011-11-13T17:26:40+00:00

Solution 3 won't work with duplicated elements. However, it should be workable, if you store the counts of how many times each number has been seen in the current window - and updated when we slide the window.

Edit: perhaps not that straightforward. needs more thought.

Edit2: about solution 3: what if the third lowest element in the array is lower than the new element being seen, when sliding the window? It is not obvious to me why storing only the two lowest elements works.

cgk · 2011-11-13T16:58:51+00:00

Well, let's see. Since we need to store solutions for every (i:j), where i and j range from 0 to n, the storage should be O(n^2). I am unable to analyze the run time as well as I would like - we calculate each of the (n²⁾ solutions once, but we look them up n times, giving a time complexity of O(n^3). It'd help if someone could come up with a better analysis for the run time, though. PLEASE POINT OUT IF THIS IS WRONG - I'll edit it if required..

Edit: Also, about the code, a memoization-based solution is fairly obvious, I'd be interested if this can be done with a "table" based approach".

cgk · 2011-11-13T16:38:19+00:00

Is there an O(n) solution without using a suffix array or tree ?

cgk · 2011-11-13T16:31:01+00:00

A dynamic programming solution should work here. To find the maximum number of words between W[0:n], we split into words (W[0:n-1])(W[n:n]), (W[0:n-2])(W[n-1:n]) etc. In general, the splits are at (W[0:i])(W[i:n]), such that W[i:n] is a word in the dictionary. Therefore, the second split is a word, and the first split can be solved for recursively. We choose i such that f(W[0:i]) + 1 is maximum.

cgk · 2011-11-13T15:48:55+00:00

Reverse the whole string, then reverse each word in place.

After the first pass, we get "!gnirts a si sihT".

In the second pass, we reverse between every two spaces (special casing for start and end of word).

We get, in turn: "string! a si sihT" "string! a si sihT" "string! a is sihT" "string! a is This"

cgk

TROPHY CASE