Yev
BAN USERFinancial Software Engineer
 0of 0 votes
AnswersProblem:
 Yev in United States for Antimoney laundering
8 balls, where 7 have equal weight, one does not. Find minimum times to use a scale to find ball that is not equal weight.
Interviewer answer: weight 6 balls. Choose balls from lighter side. Total two attempts. This is the average case but not the best case.
This is not true in all cases and the interviewer did not see this...
Best case:
Pick two balls. One may weight less, so the lighter ball is found with one attempt. This is the best case.
Worst case: If first two balls are equal, weight 6 balls. Choose balls from lighter side. Weight again. Total three attempts. Report Duplicate  Flag  PURGE
BMO Harris Bank Software Developer Algorithm  0of 0 votes
AnswersGiven a 2dimensional square matrix, rotate the matrix clockwise. Imagine concentric circles. Input from stdin: first line is length, subsequent lines are rows of the matrix. Output the matrix to stdout. This was one of the questions. You have 2 hrs to complete it.
 Yev in United States Report Duplicate  Flag  PURGE
Amazon Software Engineer Java  0of 0 votes
AnswersSuppose you have strings read in from a stream, e.g., '()(,)(())'. Detect if the parenthesis pair up correctly.
 Yev in United States
Part 1: How would you use threads to solve the problem?
Part 2: He then gave me an iterative solution and asked how the problem can be done distributively across multiple components. Report Duplicate  Flag  PURGE
Here Software Developer Algorithm  1of 1 vote
AnswersGiven a hashmap, HashMap<String,List<String>> with the following data:
 Yev in United States
A: B,C
B: X Y
X: Z
Y: Z
Expected output is an array of the dependencies. I initially started with Breadhfirst search for simplicy, which had running O(V+'E') and space O(V). The interviewer said depthfirst search is better; I don't see how DFS is better, because it requires recursion.
Part2: He then said my solution is functionally correct and then introduced a circular dependency and asked how to resolve it. I said using a visited hashset will detect a circular dep. He said it's not quite right and there a few approaches. Report Duplicate  Flag  PURGE
Here Software Developer Java  0of 0 votes
AnswersGiven a string of english characters. Find the character that appears only once. I used arr[256] to store a count of each character. Then, iterate over the array to find the first nondup, a[iter+'a']==1. The interviewer thought that storing a[iter]='x' (dup) and a[iter]=<index> was a better solution to avoid running a second pass over the string. In my mind, I disagreed using the array index, one can find the character that appears only once. The interviewer persisted, and told me to think about it.
 Yev in United States Report Duplicate  Flag  PURGE
Here Software Developer Java  0of 0 votes
AnswersSuppose you have a 2 stream of integers. How would you randomly select a sample of size N, with equal probability?
 Yev in United States Report Duplicate  Flag  PURGE
Spins Software Engineer Algorithm  0of 0 votes
AnswersImplement a bowling game. First person took 40 mins to make sure I understood the scoring of bowling. Got stuck on coding an openframe/strike/openframe and time ran out with the second interviewer.
 Yev in United States
class Frame
def initialize
@rolls=[]
end
def roll(pins_down)
end
def score
end
end
class Game
attr_reader :frames
def initialize
@frames=[]
end
def score
end
end Report Duplicate  Flag  PURGE
Centro Software Developer Ruby  0of 0 votes
AnswersDescribe the different ways to determine if an integer is a power of 2.
 Yev in United States
He was looking for a solution other than dividing by 2.
I suggested initially log2X. They said it has some rounding issues in certain environments. I continued to doing bitwise arithmetic. Report Duplicate  Flag  PURGE
Vail Systems Software Engineer / Developer Coding  0of 0 votes
AnswersInput: String array. The output of the method should be the String value out of the array passed in that contains the least number of numeric characters. If two Strings have the same number of numeric characters, return the longest String. If two Strings have the same number of numeric characters and are the same length, return the String that appears first in the input array. If the array is empty, return null.
 Yev in United States for Products Report Duplicate  Flag  PURGE
GrubHub Software Engineer / Developer Java  0of 0 votes
AnswersWrite a function that takes 2 arguments: a binary tree and an integer N, it should return the Nth element in the inorder traversal of the binary tree. I asked the interviewer if I could use a 3rd argument to store the result; he said okay.
 Yev in United States Report Duplicate  Flag  PURGE
Facebook Software Engineer / Developer Algorithm  0of 0 votes
AnswersGiven a node in a BST, find the next biggest node. Node can be left child, right, root, etc. Code this.
 Yev in United States Report Duplicate  Flag  PURGE
Highbridge Capital Java Developer Algorithm  0of 0 votes
AnswersWrite Preorder traversal of a BST, iteratively using a Stack?
 Yev in United States Report Duplicate  Flag  PURGE
Highbridge Capital Java Developer Algorithm  0of 0 votes
AnswersWhat is Serial ID corresponding to serialization?
 Yev in United States Report Duplicate  Flag  PURGE
Highbridge Capital Java Developer Java  0of 0 votes
AnswersWhen/why would you not use the final keyword?
 Yev in United States for Risk Metrics Report Duplicate  Flag  PURGE
Highbridge Capital Java Developer Java  0of 0 votes
AnswersWhat is volatile?
 Yev in United States for Risk Metrics Report Duplicate  Flag  PURGE
Highbridge Capital Java Developer Java  0of 0 votes
AnswersWhat lock does the thread acquire if you call a synchronized object/static method?
 Yev in United States for Risk Metrics Report Duplicate  Flag  PURGE
Highbridge Capital Java Developer Java  0of 0 votes
AnswersIf you had to make a List immutable, would you extend List or ArrayList?
 Yev in United States for Risk Metrics Report Duplicate  Flag  PURGE
Highbridge Capital Java Developer Application / UI Design  0of 0 votes
AnswersWhat are the cons of making every object Serializable?
 Yev in United States for Risk Metrics Report Duplicate  Flag  PURGE
Highbridge Capital Java Developer Java  0of 0 votes
AnswersWhere/when would you use final?
 Yev in United States for Risk Metrics Report Duplicate  Flag  PURGE
Highbridge Capital Java Developer Java  0of 0 votes
AnswersWhat's the difference between a Hash Table & Hash Map? How would you handle a collision where key/hash are different, and visaversa?
 Yev in United States for Risk Metrics Report Duplicate  Flag  PURGE
Highbridge Capital Java Developer Data Structures
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;
}

Yev
August 30, 2020 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());
}

Yev
August 29, 2020 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;
}

Yev
August 26, 2020 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();
}

Yev
August 26, 2020 This solution is more spaceefficient. 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());
}

Yev
August 25, 2020 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
(rowStartlength+2..rowStart).to_a.reverse.each do rowIndex
#puts "#{rowIndex}#{colStart}=#{rowIndex1}#{colStart}"
matrix[rowIndex][colStart]=matrix[rowIndex1][colStart]
end
#puts
# top
(colStartlength+2..colStart).to_a.reverse.each do colIndex
#puts "#{rowStartlength+1}#{colIndex}=#{rowStartlength+1}#{colIndex1}"
matrix[rowStartlength+1][colIndex]=matrix[rowStartlength+1][colIndex1]
end
#puts
# left
(rowStartlength+1...rowStart).each do rowIndex
#puts "#{rowIndex}#{colStartlength+1}=#{rowIndex+1}#{colStartlength+1}"
matrix[rowIndex][colStartlength+1]=matrix[rowIndex+1][colStartlength+1]
end
#puts
# bottom
(colStartlength+1...colStart).each do colIndex
#puts "#{rowStart}#{colIndex}=#{rowStart}#{colIndex+1}"
matrix[rowStart][colIndex]=matrix[rowStart][colIndex+1]
end
#puts
matrix[rowStart][colStart1]=start_position_val
#puts
end
def rotate(matrix)
return if base_rotate(matrix)
length=matrix.length
circleIndex=length1
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
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 higherorder 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.
 Yev September 03, 2015Ruby. 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,col1)
row>=0 && col>=0 && col1<matrix.length && !visited?(row,col1)
end
def up?(matrix,row,col)
mark_visited(row,col) if block?(matrix,row1,col)
row>=0 && col>=0 && row1<matrix.length && !visited?(row1,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,row1,col,path_length+1)
end
# left?
if left?(matrix,row,col)
longest_paths_found << longest_path(matrix,row,col1,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
This is a tricky problem indeed. However, this is a shortestpath 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?
 Yev July 24, 2015My closest answer, in the 15 or so mins left, is follows:
1. Get a psuedorandom 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 numbermodulusk 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.
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_ordinal1);
//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 rihtshift 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));
}
}

Yev
July 12, 2015 Fixed to cover usecase scenarios and basecases. 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 monotonicallyincreasing 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 maxsofar, then save indices of maxsofar
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_curr1);
}
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}
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
Ruby impl. Using stack to capture stackframes of depthfirst 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
Ruby impl. Assumption: tree contains only natural numbers. Hence, the tree can be pruned if the sum is exceeded. Algo is depthfirst 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.length1index].name.to_i}"
print ' > ' if index < path.length1
end
Output:
* 1
+ 2
 > 4
 +> 5
++ 3
> 6
+> 7
1 > 3 > 6
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_iter1]
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_iter1]
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
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_iter1]
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_size1
@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
Correction: if the max int is not in the sliding window, then need to find the largest int in the sliding window. Since win_size1 ints have already been accessed, it should be possible to compare the new found integer with the 2ndlargest integer from the prior window. This can be done with two vars, max and max_second in constant time.
 Yev July 02, 2015Open Chat in New Window
 Yev August 30, 2020