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
Ruby impl. Running time:O(n). Space: O(1).
# ascending order
@stream_iter=0
@stream=[1,4,2,7,9,15,11,26,96,15,3,56,25]
WIN_SIZE=3
@k_largest=@stream[0] if @stream.kind_of?(Array) && @stream.length >= 1
def has_more?
@stream.kind_of?(Array) && @stream_iter < @stream.length
end
def max_int
return nil if WIN_SIZE <= 0
return @k_largest if !has_more?
if @k_largest.nil?  @stream[@stream_iter] > @k_largest
@k_largest=@stream[@stream_iter]
end
@stream_iter+=1
@k_largest
end
@stream.each do value
puts "Max: #{max_int}"
end
puts "Max: #{max_int}"
Output:
Max: 1
Max: 4
Max: 4
Max: 7
Max: 9
Max: 15
Max: 15
Max: 26
Max: 96
Max: 96
Max: 96
Max: 96
Max: 96
Max: 96
Ruby impl. Running time: O(n*m*logm). Space:O(n).
require 'set'
def anagrams_count(array)
return 0 if array.nil?  !array.kind_of?(Array)  array.length == 0
anagrams_set=Set.new
array.each do str
sorted_str=str.chars.sort.join
anagrams_set.add(sorted_str)
end
anagrams_set.size
end
require_relative '../../../src/anagrams'
describe 'anagrams' do
context 'error input: []' do
let(:strings){[]}
it 'shall return blank' do
expect(anagrams_count(strings)).to eq(0)
end
end
context 'error input: nil' do
let(:strings){nil}
it 'shall return blank' do
expect(anagrams_count(strings)).to eq(0)
end
end
context 'error input: string' do
let(:strings){'hello'}
it 'shall return blank' do
expect(anagrams_count(strings)).to eq(0)
end
end
context 'valid input' do
let(:strings){['abc','cab','dac','beed','deb','few','acd']}
it 'shall return anagrams' do
expect(anagrams_count(strings)).to eq(5)
end
end
end

Yev
June 30, 2015 Ruby impl using Set. Running time: O(n). Space: O(n). In practice, it's more efficient to allocate enough space to a data structure in advance.
require 'set'
def two_numbers_sum_to_value_using_set(array, num)
return [] if !array.kind_of?(Array)  array.length<=1
return array if array.kind_of?(Array) && array.length==2 && array[0]+array[1]==num
set=Set.new(array)
array.any? do value
numvalue != value && set.include?(numvalue)
end
end
array=[1,2,3,4,5,9,8,7,6]
puts "Two numbers? #{two_numbers_sum_to_value_using_set(array,13)}"

Yev
June 29, 2015 Ruby impl
def kth_smallest(array,k)
return nil if k<=0  array.nil?  !array.kind_of?(Array)  array.length==0
puts "Find rank index: #{k1}"
puts
lo=0
hi=array.length1
rankIndex=nil
while rankIndex != k1 && lo<=hi
puts "Lo: #{lo}. Hi: #{hi}"
rankIndex = partition(array,lo,hi)
puts "Partitioned: #{array}. Rank index: #{rankIndex}. Rank value: #{array[rankIndex]}"
puts
lo = rankIndex+1 if rankIndex < k1
hi = rankIndex1 if rankIndex > k1
end
array[rankIndex]
end
def partition(array,lo,hi)
return 1 if lo>hi  array.nil?  !array.kind_of?(Array)  array.length==0
pivotIndex=(hilo)/2+lo
pivotValue=array[pivotIndex]
storeIndex=lo
swap(array,pivotIndex,hi)
for iter in (lo..hi1)
if array[iter] < pivotValue
swap(array,iter,storeIndex)
storeIndex+=1
end
end
swap(array,storeIndex,hi)
storeIndex
end
def swap(array,first,second)
return array if first==second  array.nil?  !array.kind_of?(Array)  array[first]==array[second]
array[first]=(array[first]^array[second])
array[second]=(array[first]^array[second])
array[first]=(array[first]^array[second])
array
end
array=[12,3,17,0,9,6,100]
k=3
puts "Array: #{array}"
puts "#{k} smallest: #{kth_smallest(array,k)}"

Yev
June 26, 2015 Ruby impl. Running time: O(n). Space:O(1). Basically, it's zerosum theory.
def find_odd_occuring(array)
return nil if array.nil?  array.length==0
sum=0
array.each do value
if sum<=0
sum+=value
else
sum=value
end
end
sum
end
array = [4,7,2,2,5,3,5,7,7,3,4,5]
puts "Odd occuring: #{find_odd_occuring(array)}"

Yev
June 25, 2015 Why is it necessary to sort?
My optimized solution which the interviewer accepted:
Each object has a hashcode function, such that the array indices may act as keys in a hashtable. Then, iterate over the smaller array. During iteration, use each object's hashcode to calculate an index into the other array(e.g. hashcode % length). If found, it is a common element.
This solution has running time O(n). Space: O(1).
Ruby impl. Running time O(nm). Space: O(1).
require 'set'
def exists_path?(start_str='',end_str='',str_set=Set.new)
return true if start_str == end_str  strings_diff_by_one?(start_str, end_str)
return false if start_str.length != end_str.length
original_end_str=end_str
path=[end_str]
str_set.add(start_str)
while str_set.length > 0 && start_str != end_str &&
(found_str = find_str_with_diff_one(str_set,end_str))
str_set.delete(found_str)
end_str = found_str
path.insert(0,end_str)
end
path.length>=2 && path[0]==start_str && path[path.length1]==original_end_str
end
def strings_diff_by_one?(string1,string2)
chars_changed=0
string1.chars.each_with_index do character,index
#puts "#{character}  #{str_value[index]}"
if character != string2[index]
chars_changed+=1
end
end
chars_changed==1
end
def find_str_with_diff_one(str_set, str_value)
return nil if str_set.empty?  str_value.to_s.length==0
found_str=nil
str_set.each do str
found_str=str if strings_diff_by_one?(str,str_value)
end
return found_str
end
start_str='cog'
end_str='bad'
puts "path exists?: #{exists_path?(start_str,end_str,Set.new(['bag', 'cag','cat', 'fag','con','rat','sat','fog']))}"

Yev
June 24, 2015 It's more efficient to work backwards from the end string.
1. Eliminate words that are not the same length as the end word
2. Find words that differ by one char from end string, and remove these matched
words from search
3. Repeat (2) where end string becomes a matched word.
Linear time O(n^2). Space: O(1)
Ruby implementation. Running time: O(nk). Space overhead: O(1).
def rotate(array, n)
return [] if array.nil?
return array if n <= 0  array.length==0  n % array.length == 0
store_index=array.length1
(0...n).to_a.reverse.each do element_index
for iter in (element_index...store_index)
swap(array, iter,iter+1)
end
store_index = 1
end
array
end
def swap(array, first_index, second_index)
array[first_index]=array[first_index]^array[second_index]
array[second_index]=array[first_index]^array[second_index]
array[first_index]=array[second_index]^array[first_index]
array
end

Yev
June 23, 2015 Running time: O(nk). O(1) space overhead. Ruby implementation:
def rotate(array, n)
return [] if array.nil?
return array if n <= 0  array.length==0  n % array.length == 0
store_index=array.length1
(0...n).to_a.reverse.each do element_index
for iter in (element_index...store_index)
swap(array, iter,iter+1)
end
store_index = 1
end
array
end
def swap(array, first_index, second_index)
array[first_index]=array[first_index]^array[second_index]
array[second_index]=array[first_index]^array[second_index]
array[first_index]=array[second_index]^array[first_index]
array
end

Yev
June 23, 2015 In Ruby:
require 'thread'
def valid_move?(matrix=[], start_pt)
start_pt[0] >= 0 &&
start_pt[0] < matrix.length &&
start_pt[1] >= 0 &&
start_pt[1] < matrix.length
end
def mark_visited(visited, point)
visited[point[0]..point[1]]=true
end
def visited?(visited, point)
visited[point[0]..point[1]]
end
def move_left(start_pt)
[start_pt[0],start_pt[1]1]
end
def move_right(start_pt)
[start_pt[0], start_pt[1]+1]
end
def move_up(start_pt)
[start_pt[0]1,start_pt[1]]
end
def move_down(start_pt)
[start_pt[0]+1,start_pt[1]]
end
def exists_path_recursive?(matrix, start_pt, end_pt, visited,level)
puts "Level: #{level}"
puts "Start point: #{start_pt}"
puts "End point: #{end_pt}"
return true if start_pt == end_pt
if !valid_move?(matrix, start_pt)
puts "Invalid move: #{start_pt}"
return false
elsif visited?(visited,start_pt)
puts "Already visited: #{start_pt}"
return false
end
puts "Mark visited: #{start_pt}"
mark_visited(visited,start_pt)
puts "Visited: #{visited}"
return exists_path?(matrix, move_left(start_pt),end_pt,visited,level+1) 
exists_path?(matrix, move_right(start_pt),end_pt,visited,level+1) 
exists_path?(matrix, move_up(start_pt),end_pt,visited,level+1) 
exists_path?(matrix, move_down(start_pt),end_pt,visited,level+1)
end
def exists_path_nonrecursive?(matrix, start_pt,end_pt, visited)
queue = Queue.new
queue << start_pt
puts "Queue size: #{queue.length}"
puts
while !queue.empty?
point = queue.pop
puts "Queue size after pop: #{queue.length}"
if visited?(visited,point)
puts "Already visited #{point}"
puts
next
end
mark_visited(visited,point)
puts "Visited: #{visited}"
return true if point == end_pt
if valid_move?(matrix,move_left(point))
puts "Move left: #{move_left(point)}"
queue << move_left(point)
puts "Queue size after push: #{queue.length}"
end
if valid_move?(matrix,move_right(point))
puts "Move right: #{move_right(point)}"
queue << move_right(point)
puts "Queue size after push: #{queue.length}"
end
if valid_move?(matrix,move_up(point))
puts "Move up: #{move_up(point)}"
queue << move_up(point)
puts "Queue size after push: #{queue.length}"
end
if valid_move?(matrix,move_down(point))
puts "Move down: #{move_down(point)}"
queue << move_down(point)
puts "Queue size after push: #{queue.length}"
end
puts
end
return false
end
matrix=[
[0,0,1,0,1],
[0,0,0,0,0],
[0,1,1,1,1],
[0,1,1,0,0],
[0,0,1,0,0]
]
start_pt=[4,1]
end_pt=[0,3]
visited={}
puts "Exists path? #{exists_path_nonrecursive?(matrix,start_pt,end_pt,visited)}"

Jack
May 29, 2015 By minimizing ab and bc, ca will implicitly be minimized. O(n) running time, and O(1) space...
static int findMin(int[] nums){
int min=nums[0];
for(int iter=1;iter<nums.length;iter++){
if(nums[iter]<min){
min=nums[iter];
}
}
return min;
}
static int findMax(int[] nums){
int max=nums[0];
for(int iter=1;iter<nums.length;iter++){
if(nums[iter]>max){
max=nums[iter];
}
}
return max;
}
static int[] minimize(int A[], int B[], int C[]){
int aMin=findMin(A),
bMin=findMin(B),
cMin=findMin(C);
int aMax=findMax(A),
bMax=findMax(B),
cMax=findMax(C);
int[] result=new int[3];
int sum1 = Math.abs(cMinbMin)+Math.abs(aMinbMin);
int sum2 = Math.abs(cMaxbMax)+Math.abs(aMaxbMax);
if(sum1<sum2){
result[0]=aMin;
result[1]=bMin;
result[2]=cMin;
}
else{
result[0]=aMax;
result[1]=bMax;
result[2]=cMax;
}
return result;
}

Jack
September 12, 2014 Java already has implemented Mergesort.
Runtime complexity: On avg, nlogn.
Space complexity: O(n).
static int[] removeDups(final int[] array)
{
int[] copyArray = array.clone();
Arrays.sort(copyArray);
int[] newArray=new int[array.length];
int endMarker=0;
newArray[0]=copyArray[0];
endMarker++;
for(int i=1;i<copyArray.length;i++)
{
if(copyArray[i]!=copyArray[i1])
{
newArray[endMarker++]=copyArray[i];
}
}
newArray=null;
copyArray=null;
int[] resultArray=new int[endMarker];
for(int i=0;i<endMarker;i++)
{
resultArray[i]=copyArray[i];
}
return resultArray;
}

Jack
March 29, 2013 Bubble sort isn't even worth mentioning, unless the list is very small; It's an archaic algorithm and almost every other other algorithm performs better. Since the list is a linked list, you don't get the benefits of locality. If the list is close to being sorted, use Insertion sort. Otherwise, for a large list, use an "external sorting" algorithm, e.g. mergesort.
 Jack February 20, 20131. Enqueue: push onto Stack A.
2. Dequeue: push all elements from (1) onto Stack B. Pop topelement from Stack B until empty. If Enqueue is necessary, push onto Stack A while Stack B is not empty.
3. When stack B is empty, push elements from stack A to Stack B.
4. and so on...
Since an extra buffer is prohibited, choose the smaller of the two arrays as the container:
static Integer[] commonNums(final Integer[] array1,final Integer[] array2)
{
boolean isArray1Shorter=array1.length<=array2.length?true:false;
int len = isArray1Shorter?array1.length:array2.length;
int ci=0;
for(int i1=0,i2=0;i1<len && i2<len;)
{
if(isArray1Shorter && array1[i1]==array2[i2])
{
array1[ci++]=array1[i1];
i1++;
i2++;
}
else if(!isArray1Shorter && array1[i1]==array2[i2])
{
array2[ci++]=array2[i1];
i1++;
i2++;
}
else if(array1[i1]<array2[i2])
{
i1++;
}
else if(array1[i1]>array2[i2])
{
i2++;
}
}
if(isArray1Shorter)
{
array1[ci]=null;
return array1;
}
else
{
array2[ci]=null;
return array2;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Autogenerated method stub
Integer a[] = {1,1,3,4,6,9};
Integer b[] = {1,1,3,4,5,9};
final Integer[] commonNums = commonNums(a,b);
for(Integer val: commonNums)
{
if(val!=null)
{
System.out.print(val+" ");
}
else
break;
}
System.out.println();
}

Jack
February 19, 2013 Following is a solution in O(n) running time.
1. If Node A is a parent of Node B, return Node A regardless if Node B exists, and visaversa.
2. If node A/B not found, return null.
3. Else, do LCS.
Disclaimer: this is rather tricky to do in an inperson interview without a debugger ;o)
static Node findLCA(final Node root, final Node nodeA, final Node nodeB,final SearchResult searchResult)
{
/**
* base case
*/
boolean foundA=false,foundB=false;
if(root==null  nodeA==null  nodeB==null)return null;
else if(nodeA==nodeB)return nodeA;
if(searchResult.node!=null && searchResult.foundA && searchResult.foundB)
{
return searchResult.node;
}
else if(root.equals(nodeA)  root.equals(nodeB))
{
return root;
}
if(root.left!=null)
{
Node foundNode = findLCA(root.left,nodeA,nodeB,searchResult);
if(searchResult.node!=null && searchResult.foundA && searchResult.foundB)return searchResult.node;
else if(foundNode!=null)
{
foundA=foundAfoundNode.equals(nodeA);
foundB=foundBfoundNode.equals(nodeB);
}
if(foundA && foundB)
{
searchResult.node=root;
searchResult.foundA=true;
searchResult.foundB=true;
return root;
}
}
if(root.right!=null)
{
Node foundNode = findLCA(root.right,nodeA,nodeB,searchResult);
if(searchResult.node!=null && searchResult.foundA && searchResult.foundB)return searchResult.node;
else if(foundNode!=null)
{
foundA=foundAfoundNode.equals(nodeA);
foundB=foundBfoundNode.equals(nodeB);
}
if(foundA && foundB)
{
searchResult.node=root;
searchResult.foundA=true;
searchResult.foundB=true;
return root;
}
}
if(foundA)
return nodeA;
else if(foundB)
return nodeB;
else
return null;
}
static class SearchResult
{
Node node;
boolean foundA,foundB;
}
static class Node implements Comparable<Node>{
Node left;
Node right;
Integer value;
public int compareTo(Node o) {
return value.compareTo(o.value);
}
public boolean equals(Object o){
Node target = (Node)o;
return this.compareTo(target)==0;
}
public String toString()
{
return "Node("+value+")";
}
}

Jack
February 19, 2013 For constantlength array, select algorithm works well.
For continuous stream, it is unknown how much to allocate for the array ahead of time. Array allocation at runtime is very expensive. Hence, use a BST and keep a count of the total number of elements N. Then, when it is needed to find the median, do inorder traversal for the N/2th element; worstcase O(N), bestcase O(logN).
public static String compress(final String str) {
final StringBuilder builder = new StringBuilder();
if ((str == null)  str.isEmpty()) {
return "0";
}
builder.append(str.charAt(0));
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == str.charAt(i  1)) {
count++;
} else {
builder.append(count);
builder.append(str.charAt(i));
count = 1;
}
}
builder.append(count);
return builder.toString();
}

Jack
February 18, 2013 Assumption: number is an integral 64 bits.
Insertion sort in descending order. With long int of 64 bits, the max positive value possible is 9223372036854775807, which is 19 digits. Insertion sort may do element copies. For example, if all the elements are sorted in descending order except the first element, then insertion sort needs to shift N1 elements. In contrast, using quicksort, the number of copy operations is logn.
public static void sort(final List<Integer> digits) {
for (int i = 1; i < digits.size(); i++) {
int storeIndex = i;
int valueToInsert = digits.get(i);
while ((storeIndex > 0) &&
(valueToInsert > digits.get(storeIndex  1))) {
digits.set(storeIndex, digits.get(storeIndex  1));
storeIndex;
}
digits.set(storeIndex, valueToInsert);
}
}

Jack
February 17, 2013 public static boolean search(int target, int startL, int startR,
int[][] array, int len) {
for (int i = startL; i < array.length; i++) {
for (int k = startR; k < len; k++) {
if (target == array[i][k]) {
return true;
} else if ((k == (len  1)) && (target < array[i][k])) {
len;
break;
} else if ((k == (len  1)) && (target > array[i][k])) {
startR = k;
break;
}
}
}
return false;
}

Jack
February 12, 2013 Convert first into binary. From binary, do octal. From binary, do hex. O(n) time each. For octal/hex conversion, create a map such that a["001"] = 1, a["111"]=7 for octal, and for hex b["1111"]="f". O(1) memory, O(n) to convert decimal to binary. Then, O(n) to map the bits to octal or hex using map.
 Jack February 09, 2013The bigger the table, the less # of collisions. It's naive and wasteful to create a count array of size Long.MAX_VALUE for two numbers like 1 and Long.MAX_VALUE. Instead, create multiple buckets(each a hashtable) partitioned by value. The number of buckets to create can be determined experimentally.
 Jack September 13, 2012Open Chat in New Window
I noticed the solution has to be the lastk integers, like a sliding window. Hence, this max_int function could be tweaked to first run on a range from stream[0] to stream[win_size1]. Then, if the max int is within the window(i.e. stream_iter), compare the max int with the new integer found and set max int accordingly. Otherwise, if the new integer found is greater than max int, set the new integer as the max int.
 Yev July 02, 2015