ranganath.mr
BAN USER- 0of 0 votes
AnswersYou have a stream of numbers coming in (lets say more than a million). The numbers are between [0-999). Implement a class which can
- ranganath.mr in United States
insert(int i);
getMean();
getMedian();
in constant time O(1).| Report Duplicate | Flag | PURGE
Thumbtack SDE-3 Algorithm Data Structures
use a min heap of size n. insert first n elements.
At subsequent elements(n+1, n+2,...) check heap root, if current element is greater than root, remove the root and insert current element. repeat.
finally heap root should have kth largest
Step 1: Go over each word in Dictionary(valid word list) Build up sorted keyMap<String, List<String> - This contains sorted key and list of words Ex. key (dgo) - > {dog, god}
Step 2: sort the Given letters and slide the window of length N over this sorted array and check whether the key exists. If key exists read all the words use them in the result.
with your code - i can get list.get(0) more than n times. Nothing stops me.
- ranganath.mr February 17, 2016I dont think the code orders the elements as they appear in the original array.
a should come before b and b should appear before c.....
Assumptions:
There can be number duplicates. The numbers fit in memory
The isPresent signature is isPresent(sum, i) - If i is present in sum.
The idea is to store all the distinct numbers in a set. Store the sum as well in the set.
Since this is a online algorithm, we can loop through all the existing numbers and add to the new number and put it in the set.
when is present is called, then check the sum exists in SumSet, check i is present in storage and sum - i is present in the storage.
import java.util.HashSet;
import java.util.Set;
public class OnlineNumberPairs {
public static void main(String[] args) {
INumber number = new NumberImpl();
number.insert(-1);
number.insert(1);
number.insert(0);
number.insert(2);
number.insert(3);
number.insert(4);
number.insert(1);
System.out.println(number.isPresentInPairSum(2, 1));
System.out.println(number.isPresentInPairSum(2, 2));
System.out.println(number.isPresentInPairSum(5, 2));
System.out.println(number.isPresentInPairSum(5, 4));
}
private static interface INumber {
public void insert(int i);
public boolean isPresentInPairSum(int sum, int i);
}
private static class NumberImpl implements INumber {
private Set<Integer> storage;
private Set<Integer> sumSet;
public NumberImpl() {
storage = new HashSet<Integer>();
sumSet = new HashSet<Integer>();
}
@Override
public void insert(int i) {
storage.add(i);
for(Integer in: storage) {
sumSet.add( i + in );
}
}
public boolean isPresentInPairSum(int sum, int i) {
return sumSet.contains(sum) && storage.contains(i) && storage.contains( sum - i);
}
}
}
You are not allowed to store the numbers themselves
- ranganath.mr February 16, 2016
Repnancyhfloress, Computer Scientist at AMD
Hey there, I’m Nancy. I’m a small business owner living in Sunrise, FL 33323. I am a fan ...
RepKimRPierce, Employee at Achieve Internet
I am a customer service-oriented Travel Agent in Travel and Tourism industries. I strongly believe that the skills and abilities ...
RepI am Susan From Wasilla USA. and my strong interest in yoga and reading historical books. I have a large ...
You should consider cases where there are series of Landscape images.
- ranganath.mr March 16, 2016Ex: PPLLLLLLLLLLLLLPP.
In the above case, its OK to view a Landscape image (assuming cost of image-rotation is less than hopping many Ls)