Iram22
BAN USERMaintain three HashMaps
First map
KeySong ValueSinger
SecondMap
KeySong Valuecount
ThirdMap
KeySinger ValueTop Song
When a new request to play a song comes. Increment the count of current song. Check the singer of the current song and also check the top song of that singer. If the curr song and top song are not same, check if the count of curr song is greater than top song. If so, update the top song of singer
if one element is zero, find the product p of all elements except zero. Set zero as p, rest as zero.
arr=[1,3,0,2]
p=6
arr=[0,0,6,0]
if more than one element is zero, replace every element with zero
arr=[1,0,2,0,3]
arr=[0,0,0,0,0]
else
find product p of all elements
replace every element with p/element
arr=[1,3,4,2]
p=24
arr=[24,8,6,12]
Use a HashMap to map key with Count object.
class Count{
int key;
int counter;
}
HashMap<Integer,Count> map;
Use a MinHeap of size k, to store top k counts.
PriorityQueue<Count> minHeap;
When the count increases for any key, update its Count object. Check if the count for any key which is not present in Heap is greater than the minimum count in Heap, update the Heap replacing the count object.
Time Complexitynlogk
Space Complexityn+k
Use browser cache to suggest products searched by user.
For suggesting similar products bought by other users, maintain a weighted graph with products as nodes. Weight will refer to the number of customers who bought the two connected products.
Product nodes can be stored in hashmap(to search a product in graph in O(1) time).
To suggest k similar products, use a k size min heap.
Create an object for every item and map it to token. This object should store item size and container type(S/M/L).
Create 3 MinHeap (Small,Medium,Large) which represent three containers. Also maintain 3 variables which store the capacity of the 3 containers.
For any item which cannot be inserted in any of the three containers, check if the total capacity is large enough to place the current item. If yes, try to rearrange the items in containers.
For removing any item from a container, the item size should be smaller than the current item to be placed
public static void main(String[] args) {
int val[]={2,5};
int quan[]={2,3};
HashSet<Integer> set=new HashSet<Integer>();
findSum(val,quan,set,0,0);
}
private static void findSum(int[] val, int[] quan, HashSet<Integer> set, int sum,int ind) {
set.add(sum);
if(ind>=val.length) return;
for(int i=0;i<=quan[ind];i++){
sum+=val[ind]*i;
findSum(val, quan, set, sum, ind+1);
sum=val[ind]*i;
}
}

Iram22
December 11, 2016 Postorder traversal of the tree calculating the length of increasing and decreasing sequence for both left and right child
class Node{
int data;
Node left, right;
public Node(int x){
data=x;
left=right=null;
}
}
class Result{
int inc,dec;
}
public class LCSInBT {
public static int max;
public static void main(String[] args) {
Node n=new Node(6);
n.left=new Node(5);
n.left.left=new Node(3);
n.left.right=new Node(4);
n.left.left.left=new Node(2);
n.right=new Node(7);
n.right.left=new Node(8);
n.right.left.right=new Node(9);
lcs(n);
System.out.println(max);
}
private static Result lcs(Node n) {
Result res=new Result();
if(n==null){
res.dec=0; res.inc=0;
return res;
}
res.dec=1; res.inc=1;
Result l=lcs(n.left);
Result r=lcs(n.right);
if(n.left!=null){
if(n.left.data+1==n.data){
res.inc+=l.inc;
}
if(n.data+1==n.left.data){
res.dec+=l.dec;
}
}
if(n.right!=null){
if(n.right.data+1==n.data){
res.inc=Math.max(res.inc,r.inc+1);
}
if(n.right.data==n.data+1){
res.dec=Math.max(res.dec,r.dec+1);
}
}
max=Math.max(findLen(n,l,r), max);
return res;
}
private static int findLen(Node n, Result l, Result r) {
int len=0;
if(n.left!=null && n.right!=null){
if(n.data+1==n.left.data && n.data==n.right.data+1){
len=l.dec+r.inc+1;
}
else if(n.data==n.left.data+1 && n.data+1==n.right.data){
len=l.inc+r.dec+1;
}
else if(n.data+1==n.left.data){
len=1+l.dec;
}
else if(n.data==n.left.data+1){
len=1+l.inc;
}
else if(n.data+1==n.right.data){
len=1+r.dec;
}
else if(n.data==n.right.data+1){
len=1+r.inc;
}
}
return len;
}
}

Iram22
December 10, 2016 Open Chat in New Window
A min heap of size k and a variable holding topBidSoFar.
 Iram22 March 15, 2017Store the top k bids in min heap. If any bid is greater than the top of minHeap, replace min Heap top. Also if this bid is greater than the topBidSoFar, replace it.