monica_shankar
BAN USERThe images are SHA'ed and their long ids are obtained, each user has a unique user id which is stored in dictionary order. Each user has a hash table of 10 recent image requests <Integer, Long ids>. If excess, the least recent one is deleted. This is just image retrieval hence I don't think synchronization is necessary. Please correct me if I am wrong.
- monica_shankar June 29, 2015You don't even need a stack in the first place.
- monica_shankar June 08, 2015/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package Careercup;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.lang.IllegalArgumentException;
/**
*
* @author
*/
public class CountBracketBalance {
static BufferedReader br;
static StringTokenizer st;
static int head=0,N=0,count=0;
static ArrayList<Character> queue=new ArrayList<Character>();
public static void init() throws IOException
{
if(st==null)
st=new StringTokenizer(br.readLine().replace("", " "));
}
public static void push(Character ch)
{
if(N>=queue.size()) //cases where N==arraylist.size
{
queue.ensureCapacity(queue.size()*2);
for(int i=N+1;i<queue.size();i++)
queue.add(null);
}
//stack.set(N++, ch);
queue.add(N++, ch);
}
public static Character pop()
{
if(queue.isEmpty())
{ System.err.println("Underflow operation requested, exiting");
System.exit(0); }
Character temp=queue.get(head);
queue.set(head, null);
head++;
N--;
return temp;
}
public static void main(String args[]) throws IOException
{
int maxcount=0;
br=new BufferedReader(new InputStreamReader(System.in));
init();
while(st.hasMoreTokens())
{
//push(st.nextToken().charAt(0));
String temp=st.nextToken();
push(temp.charAt(0));
}
while(N>0)
{
Character ch=pop();
if(ch=='(')
{ count++;
maxcount=Math.max(maxcount, count);}
if(ch==')')
count--;
if(count<0)
throw new IllegalArgumentException();
}
if(count!=0)
throw new IllegalArgumentException();
System.out.println(maxcount);
}
}
guilhebi, correct, it is difficult to imagine separate chaining for searching and nextfavsearch.
- monica_shankar June 01, 2015I think a bigger concern should be the order of insertion as an input with ascending order as in reality could make all operations ( search , insert , delete) O(N),, hence better to go for red black trees
- monica_shankar June 01, 2015I have come up with BST approach
it would be a binary search tree indexed by time t
1. Insert operation: same as the standard put operation. Avg case O(lg N) worst case O(N) ,, memory O(1)
2. Search operation: this is like a ceiling operation in BST where we find the node that is immediately greater than the current key value
Avg case: O(lg N) , worst case : O(N) memory: O(1)
public Node search(int t)
{
return search(root,t); // Assume that we have a pointer to the root.
}
private Node search(Node x, int t)
{
if (x==null) return null;
else if(compareTo(x.t,t)<0) // x.t less than t , focus on right
return search(x.right,t);
else if(compareTo(x.t,t)>=0)
{
Node t=min(x.left); // check to ensure that the we don't have an element which is smaller than the current element x
if(t!=null)
return t;
else
return x;
}
}
3. NextFavourite(t): similar operation as above but replace min(x.left) with minfav(x.left)
avg case : O(lg N) ,, worst case O(N) , memory O(1)
minfav(Node x)
{
Node y;
if(x==null) return null;
y=minfav(x.left);
if(y==null)
{
if(x.fav==1);
return x
else
y=minfav(x.right);
}
return y;
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package Dummy;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
/**
*
* @author
*/
public class Dummy02 {
static Stack<int[]> accesspoints=new Stack<int[]>();
public static boolean findPath(int[][] points, int[] startpt, int[] endpt)
{
int[][] pointsvisited=new int[points.length][points[0].length];
accesspoints.add(startpt);
visitpoint(points,pointsvisited,startpt);
for(int[] coord:accesspoints)
{
if((coord[0]==endpt[0])&&(coord[1]==endpt[1]))
return true;
}
return false;
}
public static void visitpoint(int[][] points, int[][] pointsvisited , int [] currentpoint)
{
if(currentpoint[0]<0||currentpoint[0]>=points.length||currentpoint[1]<0||currentpoint[1]>=points[0].length||
pointsvisited[currentpoint[0]][currentpoint[1]]==1||points[currentpoint[0]][currentpoint[1]]==1)
{
return ;
}
pointsvisited[currentpoint[0]][currentpoint[1]]=1;
accesspoints.add(currentpoint);
visitpoint(points,pointsvisited,new int[]{currentpoint[0]+1,currentpoint[1]});
visitpoint(points,pointsvisited,new int[]{currentpoint[0]-1,currentpoint[1]});
visitpoint(points,pointsvisited,new int[]{currentpoint[0],currentpoint[1]+1});
visitpoint(points,pointsvisited,new int[]{currentpoint[0],currentpoint[1]-1});
}
static BufferedReader br;
static StringTokenizer st;
public static void main(String args[]) throws IOException
{
br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the dimensions of the value matrix");
int length=nextInt();
int breadth=nextInt();
int[][] points=new int[length][breadth];
System.out.println("Enter the matrix");
for(int i=0;i<length;i++)
{
for(int j=0;j<breadth;j++)
{
points[i][j]=nextInt();
}
}
int[] startpt=new int[2];
int[] endpt=new int[2];
System.out.println("Enter the starting point");
for(int i=0;i<2;i++)
{
startpt[i]=nextInt();
}
System.out.println("Enter the coordinates of end point");
for(int i=0;i<2;i++)
{
endpt[i]=nextInt();
}
boolean value=findPath(points,startpt,endpt);
if(value)
System.out.println("There exist a path");
else
System.out.println("There exist no path");
}
public static int nextInt() throws IOException
{
return Integer.parseInt(nextToken());
}
public static String nextToken() throws IOException
{
while(st==null||!st.hasMoreTokens())
{
String line=br.readLine();
if(line==null)
return line;
st=new StringTokenizer(line.replaceAll("", " "));
}
return st.nextToken();
}
}
in input just flip for x and y
- monica_shankar May 29, 2015In a hurry, here is just the pseudocode
pseudocode
=========
1. let (a,b) be the first zero element in 2d matrix of values Value
a. If (a,b)==null, return false
b. else percolation(a,b)
//Assume that the Value matrix is 4*5 matrix as given here
a-horizontal index, b vertical index
percolation(int a, int b)
{
if(a!=3)
{
find list L=[(xa,y1),(xa,y2)....(xa,yN)] where (xa,yi)=(x(a+1)),yi)=0 // top zero, the corresponding bottom is also zero
if L==null, return false
prev a=a, prevb=b
for each coord in L:
{
if adjacent(coord,(a,b))
{
a=coord(x)+1
b=coord(y)
percolation(a,b)
}
}
if preva==a && prevb==b return false
}
else return true
}
while(A[L]<A[R]) is wrong, it should be while(L<=R)
- monica_shankar May 22, 2015Assume that we are going to declare N as the maximum value of the ball we see during the pick up times.
so we pick up k times and let the value of balls during the pick up be m1,m2,m3....mk
Without replacement:
The probability of drawing the N'ed value ball at first pick is 1/N
The probability of drawing the N'ed value ball at second pick is 1/(N-1)
The probability of drawing the N'ed value ball at third pick is 1/(N-2)
.... The probability of drawing the N'ed value ball at Kth pick is 1/(N-K)
As probability of one try does not affect the other, we use addition priciple
so with the value 1/N+1/(N-1).............1/(N-K) we can say that the maximum value of ball we pick would be the value N
With replacement:
The probability of picking the N'ed value ball at first try=1/N
The probability of picking the N'ed value ball at second try=1/N
.... The probability of picking the N'ed value ball at third try=1/N
so with probability of k/N, we can state that the maximum ball we pick would be the value N.
correct me if i am wrong somewhere, thanks!!!
@nikolay, explain your logic...
- monica_shankar May 21, 2015Nice one but
int j=input.indexOf(c,i+1);
returns the first substring occurrence
so for example "Today is a good day to sing and toddle" wouldn't work because 'T' of "Today" looks at 't' of "to" and not 't' of "toddle"
how do you store users and their 10 recent requests in an efficient manner, also isn't requests for each individual user in which case you don't need monitors
- monica_shankar June 29, 2015