CareerCup

public static int solve(String strA, String strB){
        final Set<Character> chars = strB.chars().distinct().mapToObj(e -> (char)e).collect(Collectors.toSet());

        if(chars.stream().anyMatch(aChar -> !strA.contains(aChar.toString()))) return -1;
        else if(strA.equals(strB)) return 1;
        else if(strA.contains(strB)) return 1;

        boolean isSubstr = true;

        for (int i = 0; i < strB.length() && strB.length() % strA.length() == 0; i++)
            if (strB.charAt(i) != strA.charAt(i % strA.length())) isSubstr = false;

        if (strB.length() % strA.length() == 0 && isSubstr) return strB.length() / strA.length();

        int index = strB.indexOf(strA);
        String leftFragment = "", rightFragment = "";

        if(index>0) leftFragment = strB.substring(0, index);

        index = strB.lastIndexOf(strA);

        if(index > 0) rightFragment = strB.substring(index + strA.length(), strB.length());

        if(!leftFragment.isEmpty()){
            strB = strA.substring(0, strA.indexOf(leftFragment)) + strB;
        }
        if(!rightFragment.isEmpty()){
            strB = strB + strA.substring(strA.indexOf(rightFragment)+1);
        }

        if(strA.indexOf(leftFragment) == 0) return -1;
        else if(strA.indexOf(rightFragment) == strA.length()-1) return -1;

        isSubstr = true;

        for (int i = 0; i < strB.length() && strB.length() % strA.length() == 0; i++)
            if (strB.charAt(i) != strA.charAt(i % strA.length())) isSubstr = false;


        return isSubstr ? strB.length()/strA.length() : -1;
    }

public static List<Integer> sublist(final List<Integer> nums, final int size){
        if(size == nums.size()) return nums;
        else if( size == 0) return Collections.emptyList();
        else if (size == 1) return Arrays.asList(nums.get(new Random().nextInt(nums.size())));

        final List<Integer> sublist = new LinkedList<>();
        final Random rand = new Random();

        int selectIndex = -1;

        while (sublist.size() < size){
            int randomDelta = 0;

            final int itemsRemaining = size - sublist.size();
            final int lowestPos = nums.size() - itemsRemaining;

            while (randomDelta == 0 || selectIndex + randomDelta > lowestPos)
                randomDelta = rand.nextInt(nums.size() - selectIndex);

            selectIndex += randomDelta;
            sublist.add(nums.get(selectIndex));
        }

        return sublist;
    }

final Map<String, Integer> counts = new HashMap<>();
        final Map<Set<String>, Map<String, Integer>> subCounts = new HashMap<>();

        items.forEach(aSet -> {
            final Map<String, Integer> aSubCounts = new HashMap<>();

            aSet.forEach(item -> {
                if (!subCounts.containsKey(item)) aSubCounts.put(item, 0);

                aSubCounts.put(item, aSubCounts.get(item) + 1);

                if (!counts.containsKey(item)) counts.put(item, aSubCounts.get(item));

                else if (counts.containsKey(item) && aSubCounts.get(item) > counts.get(item))
                    counts.put(item, aSubCounts.get(item));
            });

            if (counts.isEmpty()) counts.putAll(aSubCounts);
            subCounts.put(aSet, aSubCounts);
        });

        final TreeMap<Integer, Set<String>> score = new TreeMap<>();

        items.forEach(aSet -> {
            int missing = 0;

            for (String item : aSet) missing += counts.get(item) - subCounts.get(aSet).get(item);
            score.put(missing, aSet);
        });

        return score.get(score.lastKey());
    }

public static int multiply(int i1, int i2) {
        boolean isPositive = false;

        if(i1==0 || i2==0) return 0;

        if(i1<0 & i2<0) isPositive=true;
        else if(i1>0 & i2>0) isPositive=true;

        if(i1<0) i1 = ~i1+1;
        if(i2<0) i2 = ~i2+1;

        int acc = i1;

        for(int i=2; i <= i2; i++) acc = add(acc, i1);
        return isPositive ? acc : ~acc+1;
    }

public static int add(int i1, int i2){
        final int mask = 1;

        int subsum=0, result=0, pos=0;
        boolean carryOver=false;

        while(i1>=0 || i2>=0){
            final int digitA = i1 & mask, digitB = i2 & mask;

            /*
                0 ^ 0 = 0
                0 ^ 1 = 1
                1 ^ 0 = 1
                1 ^ 1 = 0
             */

            subsum = digitA ^ digitB;

            if(carryOver) subsum ^= 1;

            carryOver = (carryOver && (digitA == 1 || digitB == 1)) |
                    (!carryOver && digitA == digitB && digitB == 1);

            i1 >>= 1; i2 >>= 1;
            subsum <<= pos;
            pos++;
            result |= subsum;

            if(i1 == i2 && i2 == 0 && !carryOver) break;;
        }

        return result;
    }

Space: O(n)
Running time: O(n)

public static String printCommas(String str) {
        final StringBuilder builder = new StringBuilder();

        for(int i=str.length()-1,group=1; i>=0; i--, group++){
            builder.append(str.charAt(i));

            if(group % 3 == 0) {
                builder.append(",");
                group=0;
            }
        }

        return builder.reverse().toString();
    }

This solution is more space-efficient. Running time O(n).

public static String add(String s1, String s2) {
        int len = Math.max(s1.length(), s2.length()) + 1;
        final StringBuilder result = new StringBuilder(len);

        int carryOver=0;
 

        for(int s1Iter = s1.length()-1, s2Iter = s2.length()-1; s1Iter>=0 || s2Iter>=0; s1Iter--, s2Iter--){
            final int s1Val = s1Iter >=0 ? s1.charAt(s1Iter)-'0': '0', s2Val = s2Iter >=0 ? s2.charAt(s2Iter)-'0' : '0';
            final int subsum = s1Val + s2Val + carryOver;

            result.append(subsum % 2);
            carryOver = subsum/2;
        }

        if(carryOver==1) result.append(carryOver);

        return reverse(result.toString());
    }

Also, if the odd ball is one of the first four balls, two attempts is very likely

I believe the problem is missing one important factor. The order in which the "odd" ball is picked...

If first or second, weight two balls. If 3rd-8th, weight 6 balls initially. Hence, it depends on chance of having odd ball in hand

Running time: O(n). Space: O(1)

listA=[2,5,5,5]
listB=[2,2,3,5,5,7]

def find_common(listA,listB)
  common_elements=[]
  
  iterA,iterB=0,0
  
  while iterA < listA.length && iterB < listB.length
    
    if listA[iterA] == listB[iterB]
      common_elements << listA[iterA]
      iterA+=1
      iterB+=1
    elsif listA[iterA] < listB[iterB]
      iterA+=1
    else
      iterB+=1
    end
  end
  
  common_elements
end

print find_common(listA,listB)

Output:
[2, 5, 5]

Here's a solution in Ruby. Running time O(n), space O(1)

matrix1=[
  [1, 2],
  [3, 4]
]

matrix2=[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [1, 2, 3, 4],
  [5, 6, 7, 8]
]

matrix3=[
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

def base_rotate(matrix)
  return matrix if matrix.length == 0 || matrix.length == 1
  nil
end

def rotate_with_sublength(matrix,sublength,circleIndex)
  length=sublength
  rowStart=circleIndex
  colStart=circleIndex
  start_position_val=matrix[rowStart][colStart]
  
  #puts "Length: #{length}. row start: #{rowStart}. col start: #{colStart}. Start pos val: #{start_position_val}"
  
  # right
  (rowStart-length+2..rowStart).to_a.reverse.each do |rowIndex|
    #puts "#{rowIndex}#{colStart}=#{rowIndex-1}#{colStart}"
    matrix[rowIndex][colStart]=matrix[rowIndex-1][colStart]
  end
  #puts
  
  # top
  (colStart-length+2..colStart).to_a.reverse.each do |colIndex|
    #puts "#{rowStart-length+1}#{colIndex}=#{rowStart-length+1}#{colIndex-1}"
    matrix[rowStart-length+1][colIndex]=matrix[rowStart-length+1][colIndex-1]
  end
  #puts
  
  # left
  (rowStart-length+1...rowStart).each do |rowIndex|
    #puts "#{rowIndex}#{colStart-length+1}=#{rowIndex+1}#{colStart-length+1}"
    matrix[rowIndex][colStart-length+1]=matrix[rowIndex+1][colStart-length+1]
  end
  #puts
  
  # bottom
  (colStart-length+1...colStart).each do |colIndex|
    #puts "#{rowStart}#{colIndex}=#{rowStart}#{colIndex+1}"
    matrix[rowStart][colIndex]=matrix[rowStart][colIndex+1]
  end
  #puts
  
  matrix[rowStart][colStart-1]=start_position_val
  
  #puts
end

def rotate(matrix)
  return if base_rotate(matrix)
  
  length=matrix.length
  circleIndex=length-1
  
  while length >= 2
    rotate_with_sublength(matrix,length,circleIndex)
    length-=2
    circleIndex-=1
  end
end

def print_matrix(matrix)
  matrix.each do |row|
  row.each do |value|
    print value.to_s+' '
  end
  
  puts
  end
  
  puts
end

puts "original matrix"
print_matrix(matrix2)
rotate(matrix2)
puts "Rotated matrix"
print_matrix(matrix2)

Output:

original matrix
1 2 3 4
5 6 7 8
1 2 3 4
5 6 7 8

Rotated matrix
5 1 2 3
1 2 6 4
5 3 7 8
6 7 8 4

1 2 3 4
5 6 7 8
1 2 3 4
5 6 7 8

becomes

5 1 2 3
1 2 6 4
5 3 7 8
6 7 8 4

Length as in the dimension. Should be rotated like concentric circles:

1 2
3 4

becomes

3 1
4 2

No complexity constraints listed, but I assumed this could be done in O(n) time, O(1) space. My ideal approach is to traverse each position in the matrix, move the value in higher-order in the concentric circle relative to its own position, then stop when the original position is reached. When an element is moved, set it's position to null, temporarily save the next position's value and replace it with the moved value. When the original position is reached, there should be a null value to replace with the last popped value.

Correction
0,2 = 0,0

This isn't correct

In addition, it doesn't do complete clockwise rotation. Need to rotate matrices inside matrix.

This doesn't look right. First iteration produces.
Length 3
(0,2) = (2,0)

Ruby. DFS. Running time: O(|V|+|E|). Space: O(|V|)

matrix=[
  [0,0,0,0],
  [1,1,0,1],
  [1,1,1,1],
  [1,1,1,0]
]

@visited={}

def visited?(row,col)
  @visited.has_key?(row.to_s.to_sym) && @visited[row.to_s.to_sym].has_key?(col.to_s.to_sym) &&
  @visited[row.to_s.to_sym][col.to_s.to_sym]
end

def mark_visited(row,col)
  @visited[row.to_s.to_sym]={} if !@visited.has_key?(row.to_s.to_sym)
  @visited[row.to_s.to_sym][col.to_s.to_sym]=true
  #puts "[mark_visited] Visited: #{@visited}"
end

def left?(matrix,row,col)
  mark_visited(row,col) if block?(matrix,row,col+1)
  row>=0 && col>=0 && col+1<matrix.length && !visited?(row,col+1)
end

def right?(matrix,row,col)
  mark_visited(row,col) if block?(matrix,row,col-1)
  row>=0 && col>=0 && col-1<matrix.length && !visited?(row,col-1)
end

def up?(matrix,row,col)
  mark_visited(row,col) if block?(matrix,row-1,col)
  row>=0 && col>=0 && row-1<matrix.length && !visited?(row-1,col)
end

def down?(matrix,row,col)
  mark_visited(row,col) if block?(matrix,row+1,col)
  row>=0 && col>=0 && row+1<matrix.length && !visited?(row+1,col)
end

def block?(matrix,row,col)
  row>=0 && col>=0 && row<matrix.length && col<matrix.length && matrix[row][col]==0
end

def longest_path(matrix,row,col,path_length)  
  longest_paths_found=[]

  #puts "[longest_path] Visited: #{@visited}"
  #puts "[longest_path] curr pos: #{row},#{col}"
  mark_visited(row,col)
  
  # down?
  if down?(matrix,row,col)
    longest_paths_found << longest_path(matrix,row+1,col,path_length+1)
  end
  
  # up?
  if up?(matrix,row,col)
    longest_paths_found << longest_path(matrix,row-1,col,path_length+1)
  end
  
  # left?  
  if left?(matrix,row,col)
    longest_paths_found << longest_path(matrix,row,col-1,path_length+1)
  end
    
  # right?
  if right?(matrix,row,col) 
    longest_paths_found << longest_path(matrix,row,col+1,path_length+1)
  end
  
  
  return longest_paths_found.max if !longest_paths_found.empty?
  path_length+1
end

puts "longest_path: #{longest_path(matrix,1,0,1)}"

Output:
longest_path: 5

There's a pattern here. First, sort the integers using count sort(linear time). Then, use the pattern...

A0 <= A1
A2 <= A1

A2 <= A3
A4 <= A3

A4 <= A5
A6 <= A5

----
1 2 3 4 5 6

A0=1
A2=2
A1=3
-----
A3=5
A2=2
A4=4
-----
A5=6
A4=4
A6=5

This is a tricky problem indeed. However, this is a shortest-path problem, of which are several solutions. There are at least 2 common algos, one of which is Dijkstra. For simplicity, you can use DFS to find the min path. It would have linear running time O(|V|+|E|), and storage O(|V|). When you find a new path, compare the distance of the new path to the old path. Anyhow, that's how I would start. What'd you think?

Will this work for ')()('? The sum at the end is -1 + 1 - 1 + 1 = 0. Will this detect properly nested format?

My closest answer, in the 15 or so mins left, is follows:

1. Get a psuedo-random positive integer
2. Check if it's even. If so, replace in a stored array. Otherwise, skip.

Interviewer said this was better than my first approach of using the number-modulus-k to store into the array where the last int has 100% prob of being sampled. He said each number has 50% chance, which seemed uniformly random, but not ideal in all cases.

Good to know, thanks!

A few solutions I have in mind...

1. Use counting sort. O(n+k), where n is the size of the input and k is the max key length(can use hashcode func). To find k top words, iterate result array to find top k elements, O(k). Overall running time: O(n+k). Additional space: O(k). Space overhead may be large depending on the max key value.

2. BST of size n. Running time: O(nlogn). Space of O(n) may be less than space allocation in (1).

3. For small input, Insertion sort would suffice. If already sorted, O(n) time to find top K elements. Otherwise, O(n^2) worse case. This algo is ideal if the input is already close to being sorted. Otherwise, it's quadratic running time. Space: O(1).

Refactored.

public class IdentifySetBit {
	public static int octet_ordinal(int num){
		if(num/256 == 0){
			return 1;
		}
		else if((num>>>8)/256==0){
			return 2;
		}
		else if((num>>>16)/256==0){
			return 3;
		}
		else
		{
			return 4;
		}
	}
	
	public static int find_set_bit(int num){
		int octet_ordinal=octet_ordinal(num);
		int shift_count = 8*(octet_ordinal-1);
		
		//System.out.println("Octet: "+octet_ordinal);
		//System.out.println("Shift count: " + shift_count);
		
		if((num>>>shift_count) / 256 == 0){
			switch(num>>>shift_count){
			case 1: return 1+shift_count;
			case 2: return 2+shift_count;
			case 4: return 3+shift_count;
			case 8: return 4+shift_count;
			case 16: return 5+shift_count;
			case 32: return 6+shift_count;
			case 64: return 7+shift_count;
			case 128: return 8+shift_count;
			}
		}
		
		return -1;
	}
	
	public static void main(String[] args) {
		int num=1;
		
		for(int iter=1;iter<=32;iter++){
			System.out.println("Set bit for " + num+": " + find_set_bit(num));
			num <<= 1;
		}
	}

}

Output:
Set bit for 1: 1
Set bit for 2: 2
Set bit for 4: 3
Set bit for 8: 4
Set bit for 16: 5
Set bit for 32: 6
Set bit for 64: 7
Set bit for 128: 8
Set bit for 256: 9
Set bit for 512: 10
Set bit for 1024: 11
Set bit for 2048: 12
Set bit for 4096: 13
Set bit for 8192: 14
Set bit for 16384: 15
Set bit for 32768: 16
Set bit for 65536: 17
Set bit for 131072: 18
Set bit for 262144: 19
Set bit for 524288: 20
Set bit for 1048576: 21
Set bit for 2097152: 22
Set bit for 4194304: 23
Set bit for 8388608: 24
Set bit for 16777216: 25
Set bit for 33554432: 26
Set bit for 67108864: 27
Set bit for 134217728: 28
Set bit for 268435456: 29
Set bit for 536870912: 30
Set bit for 1073741824: 31
Set bit for -2147483648: 32

Fix: use unsigned riht-shift operator

public class IdentifySetBit {
	public static int find_set_bit(int num){
		
		if(num / 256 == 0){
			switch(num){
			case 1: return 1;
			case 2: return 2;
			case 4: return 3;
			case 8: return 4;
			case 16: return 5;
			case 32: return 6;
			case 64: return 7;
			case 128: return 8;
			}
		}
		
		else if((num>>>8) / 256 == 0){
			switch(num>>>8){
			case 1: return 1+8;
			case 2: return 2+8;
			case 4: return 3+8;
			case 8: return 4+8;
			case 16: return 5+8;
			case 32: return 6+8;
			case 64: return 7+8;
			case 128: return 8+8;
			}
		}
		else if((num>>>16) / 256 == 0){
			switch(num>>>16){
			case 1: return 1+16;
			case 2: return 2+16;
			case 4: return 3+16;
			case 8: return 4+16;
			case 16: return 5+16;
			case 32: return 6+16;
			case 64: return 7+16;
			case 128: return 8+16;
			}
		}
		
		else if((num>>>24) / 256 == 0){
			switch(num>>>24){
			case 1: return 1+24;
			case 2: return 2+24;
			case 4: return 3+24;
			case 8: return 4+24;
			case 16: return 5+24;
			case 32: return 6+24;
			case 64: return 7+24;
			case 128: return 8+24;
			}
		}
		
		return -1;
	}

Output:
Set bit for 1: 1
Set bit for 2: 2
Set bit for 4: 3
Set bit for 8: 4
Set bit for 16: 5
Set bit for 32: 6
Set bit for 64: 7
Set bit for 128: 8
Set bit for 256: 9
Set bit for 512: 10
Set bit for 1024: 11
Set bit for 2048: 12
Set bit for 4096: 13
Set bit for 8192: 14
Set bit for 16384: 15
Set bit for 32768: 16
Set bit for 65536: 17
Set bit for 131072: 18
Set bit for 262144: 19
Set bit for 524288: 20
Set bit for 1048576: 21
Set bit for 2097152: 22
Set bit for 4194304: 23
Set bit for 8388608: 24
Set bit for 16777216: 25
Set bit for 33554432: 26
Set bit for 67108864: 27
Set bit for 134217728: 28
Set bit for 268435456: 29
Set bit for 536870912: 30
Set bit for 1073741824: 31
Set bit for -2147483648: 32

public static void main(String[] args) {
		int num=1;
		
		for(int iter=1;iter<=32;iter++){
			System.out.println("Set bit for " + num+": " + find_set_bit(num));
			num <<= 1;
		}
	}

Output:
Set bit for 1: 1
Set bit for 2: 2
Set bit for 4: 3
Set bit for 8: 4
Set bit for 16: 5
Set bit for 32: 6
Set bit for 64: 7
Set bit for 128: 8
Set bit for 256: 9
Set bit for 512: 10
Set bit for 1024: 11
Set bit for 2048: 12
Set bit for 4096: 13
Set bit for 8192: 14
Set bit for 16384: 15
Set bit for 32768: 16
Set bit for 65536: 17
Set bit for 131072: 18
Set bit for 262144: 19
Set bit for 524288: 20
Set bit for 1048576: 21
Set bit for 2097152: 22
Set bit for 4194304: 23
Set bit for 8388608: 24
Set bit for 16777216: 25
Set bit for 33554432: 26
Set bit for 67108864: 27
Set bit for 134217728: 28
Set bit for 268435456: 29
Set bit for 536870912: 30
Set bit for 1073741824: 31
Set bit for -2147483648: 32

Java impl.

public class IdentifySetBit {
	public static int find_set_bit(int num){
		
		if(num / 256 == 0){
			switch(num){
			case 1: return 1;
			case 2: return 2;
			case 4: return 3;
			case 8: return 4;
			case 16: return 5;
			case 32: return 6;
			case 64: return 7;
			case 128: return 8;
			}
		}
		
		else if((num>>8) / 256 == 0){
			switch(num>>8){
			case 1: return 1+8;
			case 2: return 2+8;
			case 4: return 3+8;
			case 8: return 4+8;
			case 16: return 5+8;
			case 32: return 6+8;
			case 64: return 7+8;
			case 128: return 8+8;
			}
		}
		else if((num>>16) / 256 == 0){
			switch(num>>16){
			case 1: return 1+16;
			case 2: return 2+16;
			case 4: return 3+16;
			case 8: return 4+16;
			case 16: return 5+16;
			case 32: return 6+16;
			case 64: return 7+16;
			case 128: return 8+16;
			}
		}
		
		else if((num>>24) / 256 == 0){
			switch(num>>24){
			case 1: return 1+24;
			case 2: return 2+24;
			case 4: return 3+24;
			case 8: return 4+24;
			case 16: return 5+24;
			case 32: return 6+24;
			case 64: return 7+24;
			case 128: return 8+24;
			}
		}
		
		return -1;
	}
	
	public static void main(String[] args) {
		System.out.println("Set bit: " + find_set_bit(1));
		System.out.println("Set bit: " + find_set_bit(4));
		System.out.println("Set bit: " + find_set_bit(16));
		System.out.println("Set bit: " + find_set_bit(32));
		System.out.println("Set bit: " + find_set_bit(64));
		System.out.println("Set bit: " + find_set_bit(128));
		System.out.println("Set bit: " + find_set_bit(256));
		System.out.println("Set bit: " + find_set_bit(1024));
	}

}

Fixed to cover use-case scenarios and base-cases. I think that's the really tricky part of this problem, more than the coding itself.

public class MaxContiguousSum {

	static class ValueObject{
		protected final int max_so_far,start,end;
		
		public ValueObject(int max_so_far, int start, int end){
			this.max_so_far=max_so_far;
			this.start=start;
			this.end=end;
		}
		
		public String toString(){
			return "{max_so_far: "+max_so_far+", start: "+start+", end: "+end+"}";
		}
	}
	

	
	public static ValueObject maxSubArraySum(int a[]){
		if(null==a || a.length==0){
			return null;
		}
		else if(a.length==1){
			return new ValueObject(a[0], 0, 0);
		}
		
		int max_so_far=a[0], i, start_curr=0, end_curr=0, start_prev=0, end_prev=0;
		int curr_max=a[0];
		
		//5,-1,7
		for(i=1; i < a.length; i++){
			// contiguous monotonically-increasing sum
			if(curr_max + a[i] >= curr_max){
				curr_max += a[i];
				end_curr=i;
			}
			
			// If monotonically decreasing and next element is greater, then skip to next element
			// If curr_max decreased, then skip to next element
			if(curr_max+a[i] < a[i] || curr_max + a[i] < curr_max){
				start_curr=i;
				end_curr=i;
				curr_max=a[i];
			}
			
			// Current sum is greater than max-so-far, then save indices of max-so-far
			if(curr_max > max_so_far){
				start_prev=start_curr;
				end_prev=end_curr;
				max_so_far=curr_max;
			}
		}
		
		return new ValueObject(max_so_far, start_prev, end_prev);
	}
	
	public static void main(String[] args) {
		int array[]={1,2,3,-4,-2,-6,8,-1,-3};
		System.out.println("Result: "+maxSubArraySum(array));
	}

}

Output:
Result: {max_so_far: 6, start: 0, end: 2}

Fix:

public static ValueObject maxSubArraySum(int a[]){
		int max_so_far=a[0], i, start_curr=0, end_curr=0;
		int curr_max=a[0];
		
		for(i=1; i < a.length; i++){
			if(a[i] > curr_max+a[i]){
				start_curr=i;
				end_curr=i;
			}
			
			curr_max = Math.max(a[i], curr_max+a[i]);
			
			max_so_far = Math.max(max_so_far,curr_max);
			end_curr++;
		}
		
		return new ValueObject(max_so_far, start_curr, end_curr-1);
	}

Output:
Result: {max_so_far: 8, start: 6, end: 8}

Java impl

public class MaxContiguousSum {

	static class ValueObject{
		protected final int max_so_far,start,end;
		
		public ValueObject(int max_so_far, int start, int end){
			this.max_so_far=max_so_far;
			this.start=start;
			this.end=end;
		}
		
		public String toString(){
			return "{max_so_far: "+max_so_far+", start: "+start+", end: "+end+"}";
		}
	}
	
	public static ValueObject maxSubArraySum(int a[]){
		int max_so_far=a[0], i, start_curr=0, end_curr=0;
		int curr_max=a[0];
		
		for(i=1; i < a.length; i++){
			if(a[i] > curr_max+a[i]){
				start_curr=i;
				end_curr=i;
			}
			
			curr_max = Math.max(a[i], curr_max+a[i]);
			
			max_so_far = Math.max(max_so_far,curr_max);
			end_curr++;
		}
		
		return new ValueObject(max_so_far, start_curr, end_curr);
	}
	
	public static void main(String[] args) {
		int array[]={1,2,3,-4,-2,-6,8,-1,-3};
		System.out.println("Result: "+maxSubArraySum(array));
	}

}

Output:
Result: {max_so_far: 8, start: 6, end: 9}

Curiously, is it possible to do better than O(nlogn) and constant space? If the input is immutable, then the problem is more complex

Correction: subtract one when a new element is found, iterating from index 0

Using a BST adds storage as auxiliary info, where the elements are already known in the input. Hence, using a BST does not optimize the algo.

I think it would be simplest to sort the array: bound below by nlogn due to comparison. Then, the max surpasser is found by iterating from index 0 and subtracting by one until a new element is found: O(n). The total running time would be O(nlogn).

It may be possible to leverage combinatorics to simplify the algo. Although, it's very easy to be in error. Would be helpful to create several test cases to verify...

1,3,5,7,9 odds
2,4,6,8 evens

Assume the max length of an unsigned int is 6. Sum the following:
4^6 # 0 odds, 4 evens in each position
(5 2)*2!*(6 2)*(4^4) # 2 odds in 2 positions, evens in 4 positions
(5 4)*4!*(6 4)*(4^2) # 4 odds in 4 positions, evens in 2 positions
(5^6) # all odds, 5 odds in each position

looks like this algo assumes the list is sorted

Ruby impl. Using stack to capture stack-frames of depth-first search. Running time: O(|V|+|E|). Space: O(|V|).

require 'tree'
require 'ds'

root_node = Tree::TreeNode.new("1", 1)
child1 = Tree::TreeNode.new("2",2)
child2 = Tree::TreeNode.new("3",3)
grandchild1=Tree::TreeNode.new("4",4)
grandchild2=Tree::TreeNode.new("5",5)
grandchild3=Tree::TreeNode.new("6",6)
grandchild4=Tree::TreeNode.new("7",7)
child1 << grandchild1
child1 << grandchild2
child2 << grandchild3
child2 << grandchild4
root_node << child1
root_node << child2
root_node.print_tree

module Iterator
  def next
    nil
  end
  
  def has_next?
    false
  end
end

class TreeIterator
  include Iterator
  
  def initialize(root_node)
    @stack=DS::Stack.new
    @stack.push(root_node)
  end
  
  def next
    node = @stack.pop
    
    node.children.each do |child|
      @stack.push(child)
    end
    
    node
  end
  
  def has_next?
    !@stack.empty?
  end
end

class MyTree
  def initialize(root_node)
    @root_node=root_node
  end
  
  def iterator
    TreeIterator.new(@root_node)
  end
end

iterator = MyTree.new(root_node).iterator

while iterator.has_next?
  print "#{iterator.next.name}"
  print ' -> ' if iterator.has_next?
end

Output:
* 1
|---+ 2
| |---> 4
| +---> 5
+---+ 3
|---> 6
+---> 7

1 -> 3 -> 7 -> 6 -> 2 -> 5 -> 4

* 1
|---+ 2
|    |---> 4
|    +---> 5
+---+ 3
    |---> 6
    +---> 7

1 -> 3 -> 6

Ruby impl. Assumption: tree contains only natural numbers. Hence, the tree can be pruned if the sum is exceeded. Algo is depth-first search: O(|V|+|E|)

require 'tree'

root_node = Tree::TreeNode.new("1", 1)
child1 = Tree::TreeNode.new("2",2)
child2 = Tree::TreeNode.new("3",3)
grandchild1=Tree::TreeNode.new("4",4)
grandchild2=Tree::TreeNode.new("5",5)
grandchild3=Tree::TreeNode.new("6",6)
grandchild4=Tree::TreeNode.new("7",7)
child1 << grandchild1
child1 << grandchild2
child2 << grandchild3
child2 << grandchild4
root_node << child1
root_node << child2
root_node.print_tree

def find_path_sum(node, accumulator, target_sum,path)
  return false if node.nil? || node.content.to_i + accumulator > target_sum
  
  if node.content.to_i + accumulator == target_sum
    path << node
    return true
  end

  node.children.any? do |child|
    find_path_sum(child,accumulator+node.content.to_i,target_sum,path) && path<<node
  end
end


path=[]
find_path_sum(root_node,0,10,path)

puts

puts "No path" if path.length==0

path.each_with_index do |node,index|
  print "#{path[path.length-1-index].name.to_i}"
  
  print ' -> ' if index < path.length-1
end

Output:
* 1
|---+ 2
| |---> 4
| +---> 5
+---+ 3
|---> 6
+---> 7

1 -> 3 -> 6

Is it only natural integers? If so, the tree could be pruned for efficiency. Otherwise, every path must be searched until a sum is found using depth-first search: O(|V|+|E|)

O(nlogk)

BST will increase running time to O(klogn). Sorting does not add any value to the solution because each element is accessed at least once.

Deque is unnecessary because the elements are inserted in one end and extracted from the other end

Modified Ruby impl to use queue and hashet. Running time: O(n). Space: O(k).

require 'singleton'
require 'thread'
require 'set'

class StreamSimulator
  include Singleton
  
  def initialize
    @stream_iter=0
    @stream=[1,4,2,7,9,15,11,26,96,15,3,56,25]
  end
  
  def has_more?
    @stream_iter < @stream.length
  end
  
  def fetch_next_int
    if has_more?
      @stream_iter+=1
      @stream[@stream_iter-1]
    end
  end
end

class SlidingWindow
  def initialize(win_size, stream)
    @win_size=win_size
    @stream=stream
    @k_largest=nil
    @largest_position=0
    @window=SizedQueue.new(@win_size)
    @window_lookup=Set.new
  end

  def largest_int
    @k_largest
  end
  
  def within_window?(value)
    @window_lookup.include?(value)
  end

  def set_largest_int
    @k_largest=nil if !within_window?(@k_largest)
    @k_largest=current_value if @k_largest.nil? || current_value > @k_largest
  end
  
  def win_size
    @win_size
  end

  def fetch_next_int
    if @window.size == win_size
      @window_lookup.delete(@window.pop)
    end
     
    @input=@stream.fetch_next_int
    @window.push(@input)
    @window_lookup.add(@input)
    @input
  end
  
  def current_value
    @input
  end
  
  def find_max_int  
    return nil if win_size <= 0
    return largest_int if !@stream.has_more?
   
    fetch_next_int
    set_largest_int
    largest_int
  end
end

sliding_win=SlidingWindow.new(3,StreamSimulator.instance)

while StreamSimulator.instance.has_more?
  puts "Max int: #{sliding_win.find_max_int}"
end

Output:
Max int: 1
Max int: 4
Max int: 4
Max int: 7
Max int: 9
Max int: 15
Max int: 15
Max int: 26
Max int: 96
Max int: 96
Max int: 96
Max int: 56
Max int: 56

Corrected Ruby impl...

require 'singleton'

class StreamSimulator
  include Singleton
  
  def initialize
    @stream_iter=0
    @stream=[1,4,2,7,9,15,11,26,96,15,3,56,25]
  end
  
  def has_more?
    @stream_iter < @stream.length
  end
  
  def fetch_next_int
    if has_more?
      @stream_iter+=1
      @stream[@stream_iter-1]
    end
  end
end

class SlidingWindow
  def initialize(win_size, stream)
    @win_size=win_size
    @stream=stream
    @buffer=Array.new(@win_size)
    @buffer_iter=0
    @current_iter=0
    @k_largest=nil
    @largest_position=nil
  end
  
  def end_of_window?
    @buffer_iter + 1 % win_size == 0
  end

  def largest_int
    @k_largest
  end

  def set_largest_int
    if largest_int.nil? || current_value > largest_int
      @k_largest=current_value
      @largest_position=@current_iter
    end
  end
  
  def win_size
    @win_size
  end
  
  # rotating buffer
  def fetch_next_int 
     # if window has slided and largest int was not the last input read in the prev window
    if @buffer_iter==0 && @largest_position != 1
      @largest_position=nil 
      @k_largest=nil 
    end
    
    @buffer[@buffer_iter]=@stream.fetch_next_int
    @current_iter=@buffer_iter
    @buffer_iter=(@buffer_iter+=1) % win_size
  end
  
  def current_value
    @buffer[@current_iter]
  end
  
  def find_max_int  
    return nil if win_size <= 0
    return largest_int if !@stream.has_more?
   
    fetch_next_int
    set_largest_int
    largest_int
  end
end

sliding_win=SlidingWindow.new(3,StreamSimulator.instance)

while StreamSimulator.instance.has_more?
  puts "Max int: #{sliding_win.find_max_int}"
end

Output:
Max int: 1
Max int: 4
Max int: 4
Max int: 7
Max int: 9
Max int: 15
Max int: 11
Max int: 26
Max int: 96
Max int: 15
Max int: 15
Max int: 56
Max int: 25

Additional data structures are unnecessary and may run out of memory due to the length of the stream

Just noticed it's actually not sliding...

Here's the correct Ruby impl. Running time: O(n)

require 'singleton'

class StreamSimulator
  include Singleton
  
  def initialize
    @stream_iter=0
    @stream=[1,4,2,7,9,15,11,26,96,15,3,56,25]
  end
  
  def has_more?
    @stream_iter < @stream.length
  end
  
  def fetch_next_int
    if has_more?
      @stream_iter+=1
      @stream[@stream_iter-1]
    end
  end
end

class SlidingWindow
  def initialize(win_size, stream)
    @win_size=win_size
    @stream=stream
    @buffer=Array.new(@win_size)
    @buffer_iter=0
    @current_iter=0
    @k_largest=nil
    @largest_position=nil
  end
  
  def end_of_window?
    @buffer_iter + 1 % win_size == 0
  end

  def largest_int
    @k_largest
  end

  def set_largest_int
    if largest_int.nil? || current_value > largest_int
      @k_largest=current_value
      @largest_position=@current_iter
    end
  end
  
  def win_size
    @win_size
  end
  
  # rotating buffer
  def fetch_next_int 
    @buffer[@buffer_iter]=@stream.fetch_next_int
    @current_iter=@buffer_iter
    @buffer_iter=@buffer_iter+=1 % win_size
    
     # if window has slided and largest int was not the last input read in the prev window
    if @buffer_iter==0 && @largest_position != win_size-1
      @largest_position=nil 
      @k_largest=nil 
    end
  end
  
  def current_value
    @buffer[@current_iter]
  end
  
  def find_max_int  
    return nil if win_size <= 0
    return largest_int if !@stream.has_more?
   
    fetch_next_int
    set_largest_int
    largest_int
  end
end

sliding_win=SlidingWindow.new(3,StreamSimulator.instance)

while StreamSimulator.instance.has_more?
  puts "Max int: #{sliding_win.find_max_int}"
end

Output:
Max int: 1
Max int: 4
Max int: 4
Max int: 7
Max int: 9
Max int: 15
Max int: 15
Max int: 26
Max int: 96
Max int: 96
Max int: 96
Max int: 96
Max int: 96

The original solution was historical max int. Needs to be max int in a sliding window.

Correction: if the max int is not in the sliding window, then need to find the largest int in the sliding window. Since win_size-1 ints have already been accessed, it should be possible to compare the new found integer with the 2nd-largest integer from the prior window. This can be done with two vars, max and max_second in constant time.