Ok so I was looking into possible interview questions for a job and I saw one was the problem of how to find the largest subsequence of integers in an array of positive and potentially negative integers.
For example, given the set of numbers:
2, -1, 3, 5, -10, 4, 8, -1,10, 2
the largest subsequence would be
4,8, -1,10,2 since it adds up to 23.

One way of doing this is a brute force, check all subsequences using a doubly nested loop and keeping track of the greatest subsequence in a variable. However this exibits slow performance as it iterates over the length of the list array n^2 times, then it calculates the sum on each iteration.

Here is my solution (I'll write up how it works later, if its not too obvoius)

function largest_subseq($seq) {
  $max = -999999999999;
  $sum = $start = $end = $tmpstart = $tmpend = 0;
  for ($i=0; $i<count($seq); $i++) {
    $sum = $seq[$i] + $sum;
    if ($sum > 0) {
      $tmpend = $i;
    } else if ($sum <= 0 && $max > 0) {
      $tmpstart = $i+1;
      $tmpend = $tmpstart;
      $sum = 0;
    }
    if ($sum > $max) {
      $max = $sum;
      if ($sum < 0) {
        $start=$end=$i;
      } else {
        $end = $tmpend = $i;
        $start = $tmpstart;
      }
    }
    if($sum <0 && $max <0) {
      $sum = 0;
    }
  }
  return array($start, $end);
}

Just call it like this:

$seq = array(1, 3, 4, 10,22, -8,-33, 22,17, 2, 9, -49, 25, 5,8);
list($start,$end) = largest_subseq($seq);

It works perfect as far as I can tell, even if all the integers are negative.

Another question which was not nearly as difficult but took me a few minutes to figure out was this one:

you are familiar with the ? operator x ? y : z, you want to implement that in a function: int cond(int x, int y, int z); using only ~, !, ^, &, +, |, <<, >> no if statements, or loops or anything else, just those operators, and the function should correctly return y or z based on the value of x. You may use constants, but only 8 bit constants. You can cast all you want. You are not supposed to use extra variables, but in the end, it will not really matter, using vars just makes things cleaner. You should be able to reduce your solution to a single line in the end though that requires no extra vars.

My solution (in c):

int cond(int x, int y, int z) {
return (y*(!!x) + ((!x*z)));
}

Oops, after my implementation I re-read the directions. Looks like * is not in the allowed list of operators. Oh darn, I'll have to come up with a valid solution.. I'm sure this one would have scored me half credit at least ;-)

Give it a try:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cond(int x, int y, int z);
int main() {
  int a = cond(0,5,4); //4
  int b = cond(1,2,3); //2
  int c = cond(1,0,2); //0
  int d = cond(0,0,4); //4
  int e = cond(0,5,0); //0
  printf("%d, %d, %d, %d, %d \n", a,b,c,d,e);
}