AlgoAlgae
BAN USER- 3of 3 votes
AnswersCode for computing a^b and optimize it.
- AlgoAlgae in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer
Suffix tree is a good data structure for pattern matching. Look it up for thorough concept but in a nut shell, suffix tree stores all suffixes of a given string. for example : Algorithm has suffix : Algorithm, lgorithm, gorithm,...,hm,m. To build this tree takes O(n) time, n being length of string.
Now for checking if string(m) is substring of string(n), we do a string search on the suffix tree built earlier. this takes O(m) time. total O(n+m)
Since we only need to tell if edit distance is 1 or not, we can leave out the computation of edit distance and do a comparison to identify the distance. break immediately on the first sign of distance being > 1. Calculating edit distance is a recurrance problem and atleast O(nm). telling if distance is 1 or not can be done in O(m), m being the length of shorter string.
1. Compare String a and b. if size(a) = size(b) or size(a)+1=size(b) or size(b)+1=size(a)
then we can go ahead else edit distance is not 1.
2. have a counter set to 0
have i pointing to first char of a and j pointing to first char of b
if ( (i==size(a) or j==size(b)))
then stop prcessing and check counter
if(counter==1)
then edit distance is 1 else not
if(charAt(i) == charAt(j))
increment i and j
else
increment counter. if counter==2 break , else increment i and j
Once you determined the distance is not 1 in first pass, do the same operation as above backwards. This time if we find the edit to be greater than 1 then edit distance is not 1.
this is O(m) where m is length of shorter string. n=m if both string are of same length.
Edit distance is interesting topic but to cater only to this question, I believe this is more efficient.
set a pointer i to first array A and j to second array B.
setup a counter to 0
in a loop--
compare A[i] and B[j]
if(A[i] = B[j])
increment counter. if(counter == n) then result = A[i] or B[j]. else increment i and j
if(A[i] < B[j])
increment counter. if(counter == n) then result = A[i]. else increment i
if(B[j] < A[i])
increment counter. if(counter == n) then result = B[j]. else increment j.
--
This will take care of assigning same rank to integers that are equal.
There are some more conditions to take care of
1. i > A size
compare subsequent integers in B and dont increment counter if they are equal. Once you find unequal subsequent integers, increment counter and check if the counter is n. in which case the first integer (smalled one) of the two being compared is the answer.
(same goes with j > B size, which ever runs out first)
2. you ran out of both A and B and counter is still not n, in which case there is no answer
space O(1)
time O(n)
what if the arrays are sorted in desc order or one is ascending the other is descending? the only difference in such cases will be if you are incrementing or decrementing i / j. In any case, i and j need to point to the smallest integer before starting comparisons.
Have min-max heap on each server.
Have 1 min-max heap to maintain all the medians from each server. Basically you are finding median of medians.
retrieval of median from min-max heap is constant time.
However, there is maintainance overhead. for every update in any of the server(s), you have to update the final find heap.
Have two pointers i and k. increment k from start till end but start incrementing i when k reaches N.
Once the file reading is completed, start printing the lines pointed by i till k-1.
package com.project.euler;
import java.io.File;
import java.io.RandomAccessFile;
import java.util.ArrayList;
import java.util.List;
public class FileReader {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
try {
RandomAccessFile raf = new RandomAccessFile(new File("C:\\GameDevelopment\\eclipse\\artifacts.xml"), "r");
List<String> lines = new ArrayList<String>();
int N = 10;
int i=0,k=0;
String str;
while((str = raf.readLine())!=null){
if(k>=N){
i++;
}
lines.add(str);
k++;
}
while(i<k){
System.out.println(lines.get(i++));
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
Having 5 variables to hold greatest positive int, 2 subsequent positive int and 2 greatest negative int.
populating all in one pass. If there is no positive int or no positive sum,printing 0.
time O(n), space constant
package com.project.euler;
public class MaxProduct {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {0, -1, 3, 100, -70, -5};//{1, 3, 5, 2, 8, 0, -1, 3};
int greatestPositiveInt = 0,maxPos1 = 0,maxPos2 = 0, maxNeg1 = 0, maxNeg2 = 0;
for(int i : a){
if(i>0){
if(greatestPositiveInt<i){
if(greatestPositiveInt!=0)
maxPos1 = greatestPositiveInt;
greatestPositiveInt = i;
}else{
if(maxPos1<i){
if(maxPos1!=0)
maxPos2 = maxPos1;
maxPos1 = i;
}else{
if(maxPos2<i){
maxPos2 = i;
}
}
}
}else{
if(i<0){
if(maxNeg1>i){
if(maxNeg1!=0)
maxNeg2 = maxNeg1;
maxNeg1 = i;
}else{
if(maxNeg2>i){
maxNeg2 = i;
}
}
}
}
}
if(maxPos1*maxPos2 > maxNeg1*maxNeg2)
System.out.println(maxPos1*maxPos2*greatestPositiveInt);
else{
System.out.println(maxNeg1*maxNeg2*greatestPositiveInt);
}
}
}
Not sure whats the point of question. All the answers here are good enough. Tried to do it a different way.
package com.project.euler;
public class StrangeFib {
public static String result = "";
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
fib(1,1);
System.out.println(result);
}
public static void fib(int n,int m){
if(n+m>1000)
return;
result = result + n+", "+m+", # ";
fib(n+2*m,(n+m)+(n+2*m));
}
}
1. split the input string on "//". anything to right of "//" is a comment. Hence work on the 0th element after split.
2. split on "/*"
3. First element is always valid. for subsequent elements check if it contains "*/", if yes then the second part is valid else the whole element is a comment.
public void printNonComments(){
while(true){
String result = "";
String str = getNextLine();
String[] a = str.split("//");
str = a[0];
a = str.split("/\\*");
int i=1;
for(String s1 : a){
if(s1.contains("*/")){
String[] b = s1.split("\\*/");
result = result + b[1] + " ";
}else{
if(i==1)
result = result + s1 + " ";
}
i++;
}
System.out.println(result.trim());
}
}
Its actually pretty straight forward. Even sum can either be obtained by adding 2 odd or 2 even numbers. So determine how many even and odd number in the array. That is simple.
And then to find total even sums of two numbers, all you need is a simple formula.
package com.google.practice;
public class EvenSum {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr = {1,2,5,3,6,7,1,4,0,-4,1,-2,1,0,1};
int oddCount=0,evenCount=0;
for(int i=0;i<arr.length;i++){
if(arr[i]%2==0)
evenCount++;
else
oddCount++;
}
System.out.println(((evenCount-1)*(evenCount)/2)+((oddCount-1)*(oddCount)/2));
}
}
have two pointers. one that always points to zero and other looking for non zero element.
track the count of swaps. If zero pointer is not pointing to zero element, increment count and move ahead.
Space : O(1)
Time : O(n)
package com.project.euler;
public class NoZero {
public static void main(String[] arg){
int[] arr = {0,0,-1,1,0,2,3,0,0,5};//{1,0,2,0,0,3,4};
int count = 0;
for(int i=1,j=0;i<arr.length;i++){
if(arr[j]!=0){
j++;
count++;
if(i==arr.length-1 && arr[i]!=0)
count++;
}else{
if(arr[i]!=0){
int tmp = arr[i];
arr[i]=arr[j];
arr[j]=tmp;
j++;
count++;
}
}
}
System.out.print("Updated array : ");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
System.out.println("No. of non Zero elements : "+count);
}
}
Ouch that hurt :). lets try this. ofcourse its easier said than done, but here's what I think.
1. Design a UI to display two boards. one for player other for opponent.
2. Allow user to place ship before game starts. For every placement, you are making an ajax call to updare player board object.
3. provide a button for user to start playing.
4. once user clicks the button, submit the request to servlet
5. maintain a available players and occupied players list in an object. this class could be a singleton. or you could maintain to database if you want to maintain user base.
6. If the user is first to click the button, generate a key/sessionid and assign it to user. And wait for opponent.
7. When opponent clicks button, check for available user having a key/sessionid. If not found do step 6, else assign same key/sessionid to opponent and move both players to occupied list and redirect them to same url.
8. now every click in the board, send co-ordinates to servlet by making an ajax call, Blacken the co-ordinate for both the boards. For every request made, you are going to alternate enable/disable hits for players using response from ajax call.
9. have session timeout set incase one or both users close their browser.
10. For tracking the game, you can use the code above.
At any time, available player list will have zero or one player in waiting.
result for 4 queries
1. [Hampton Inn at a distance of 5.0990195135927845, Maharaja Inn at a distance of 5.385164807134504, Maharaja Inn at a distance of 6.082762530298219, Dalia Inn at a distance of 7.0]
2. [Maharaja Inn at a distance of 7.0710678118654755, Maharaja Inn at a distance of 8.48528137423857, Dalia Inn at a distance of 9.899494936611665]
3. [Maharaja Inn at a distance of 1.4142135623730951, Maharaja Inn at a distance of 2.8284271247461903, Hampton Inn at a distance of 4.123105625617661, Dalia Inn at a distance of 4.242640687119285]
4. [Holiday Inn at a distance of 0.0, Quality Inn at a distance of 2.23606797749979, Dalia Inn at a distance of 2.8284271247461903, Astre Inn at a distance of 3.0, Hampton Inn at a distance of 4.123105625617661, Maharaja Inn at a distance of 4.242640687119285]
Here is a little better version. looks a little scary but logic is trivial. using distance and slope of each hotel to match with user location +/- radius. updating only a subset of original directory. Although my subsequent sorts are on subset, I still do that one time sort on complete hotel list after pre-processing. Hence O(n log n).
package com.google.practice;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
//To store hotel information
class Hotel implements Comparable<Hotel>{
private String name=null;
private int x;
private int y;
private double distance;
private double slope = 999;
public Hotel(String name,int x,int y){
this.name = name;
this.x = x;
this.y = y;
this.computeDistance(0,0);
Origin.getInstance().hotels.add(this);
}
@Override
public int compareTo(Hotel h) {
// TODO Auto-generated method stub
return Double.compare(this.distance, h.distance);
}
//intial distance from [0,0]
protected void computeDistance(int x,int y){
if(this.x==x){
this.distance = Math.abs(this.y-y);
}else if (this.y==y){
this.distance = Math.abs(this.x-x);
if(x==0 && y==0)
this.slope=0;
}else {
int a = Math.abs(this.x-x);
int b = Math.abs(this.y-y);
this.distance = Math.sqrt(a*a+b*b);
if(x==0 && y==0)
this.slope = (this.y-y)/(this.x-x);
}
}
public String toString(){
return this.name+" at a distance of "+this.distance;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
public double getSlope() {
return slope;
}
public void setSlope(double slope) {
this.slope = slope;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
class Origin{
private int x=0,y=0;
private static Origin _org = new Origin();
protected List<Hotel> hotels = new ArrayList<Hotel>();
private Origin(){};
//recalculate distance from user co-ordinates
public List<Hotel> updateOrigin(int x,int y,HotelDirectory d){
this.x = x;
this.y = y;
for(Hotel h : hotels){
h.computeDistance(this.x,this.y);
}
Collections.sort(d.hotelDirectory);
return d.hotelDirectory;
}
//recalculate distance from user co-ordinates for specific hotel
public List<Hotel> updateOrigin(int x,int y,HotelDirectory d,String name){
this.x = x;
this.y = y;
List<Hotel> tmp = d.hotelDirectoryByHotel.get(name);
for(Hotel h : tmp){
h.computeDistance(this.x,this.y);
}
Collections.sort(tmp);
d.hotelDirectoryByHotel.put(name, tmp);
return tmp;
}
public static Origin getInstance(){
return _org;
}
}
class HotelDirectory{
private static HotelDirectory _hDir = new HotelDirectory();
public List<Hotel> hotelDirectory = new ArrayList<Hotel>();
public Map<String,List<Hotel>> hotelDirectoryByHotel = new HashMap<String,List<Hotel>>();
private HotelDirectory(){};
public void addHotel(String name, int x,int y){
Hotel h = new Hotel(name,x,y);
this.addHotel(h);
}
public void addHotel(Hotel h){
this.hotelDirectory.add(h);
updateHotelWise(h);
}
private void updateHotelWise(Hotel h){
List<Hotel> tmp;
if(hotelDirectoryByHotel.containsKey(h.getName())){
tmp = hotelDirectoryByHotel.get(h.getName());
}else{
tmp = new ArrayList<Hotel>();
}
tmp.add(h);
hotelDirectoryByHotel.put(h.getName(), tmp);
}
public void removeHotel(Hotel h){
this.hotelDirectory.remove(h);
}
public static HotelDirectory getInstance(){
return _hDir;
}
public List<Hotel> getNearestHotels(int x, int y, int radius){
List<Hotel> nearestHotels;
double userDistance;
double maxDistance,minDistance,maxSlope,minSlope;
if(x==0){
userDistance = y;
}else if (y==0){
userDistance = x;
}else {
userDistance = Math.sqrt(x*x+y*y);
}
minDistance = userDistance - radius;
maxDistance = userDistance + radius;
if(y==0)
maxSlope = 999;
else
maxSlope = y/(x-radius);
if(x==0)
minSlope = 0;
else
minSlope = y/(x+radius);
nearestHotels = findHotels(minDistance,maxDistance,minSlope,maxSlope);
if(nearestHotels==null){
System.out.println("You are in no man's land");
return null;
}else{
List<Hotel> tmp = new ArrayList<Hotel>();
for(Hotel h:nearestHotels){
Hotel hTmp = new Hotel(h.getName(),h.getX(),h.getY());
hTmp.computeDistance(x, y);
tmp.add(hTmp);
}
Collections.sort(tmp);
return tmp;
}
}
public List<Hotel> findHotels(double minDistance,double maxDistance,double minSlope,double maxSlope){
List<Hotel> hotelsDistance = new ArrayList<Hotel>();
List<Hotel> hotelsSlope = new ArrayList<Hotel>();
boolean isLow=false,isHigh=false;
if(Double.compare(minDistance, hotelDirectory.get((hotelDirectory.size()-1)/2).getDistance())==1)
isHigh = true;
else
isLow = true;
int pos = binarySearch(0,hotelDirectory.size()-1,minDistance,isLow,isHigh,0);
if(pos==0){
for(Hotel h : hotelDirectory){
if(Double.compare(h.getDistance(), maxDistance)==1)
break;
if(Double.compare(h.getSlope(), minSlope)==1 && Double.compare(h.getSlope(), maxSlope)==-1){
hotelsSlope.add(h);
}
hotelsDistance.add(h);
}
if(!hotelsSlope.isEmpty())
return hotelsSlope;
if(hotelsSlope.isEmpty() && !hotelsDistance.isEmpty())
return hotelsDistance;
else if(hotelsSlope.isEmpty() && hotelsDistance.isEmpty())
return hotelDirectory.subList(0, hotelDirectory.size()/4);
}else if(pos==hotelDirectory.size()-1){
return hotelDirectory.subList((hotelDirectory.size()*3)/4, hotelDirectory.size()-1);
}else{
int l=pos-1,r=pos+1;
if(Double.compare(hotelDirectory.get(pos).getSlope(), minSlope)==1 && Double.compare(hotelDirectory.get(pos).getSlope(), maxSlope)==-1)
hotelsSlope.add(hotelDirectory.get(pos));
hotelsDistance.add(hotelDirectory.get(pos));
while((l>(int)minDistance || r<(int)maxDistance)){
if(l>(int)minDistance && l>=0){
if(Double.compare(hotelDirectory.get(l).getSlope(), minSlope)==1 && Double.compare(hotelDirectory.get(l).getSlope(), maxSlope)==-1)
hotelsSlope.add(hotelDirectory.get(l));
hotelsDistance.add(hotelDirectory.get(l));
l--;
}else{
l=-1;
}
if(r<(int)maxDistance && r<=hotelDirectory.size()-1){
if(Double.compare(hotelDirectory.get(r).getSlope(), minSlope)==1 && Double.compare(hotelDirectory.get(r).getSlope(), maxSlope)==-1)
hotelsSlope.add(hotelDirectory.get(r));
hotelsDistance.add(hotelDirectory.get(r));
r++;
}else{
r=-1;
}
if(l==-1 && r==-1)
break;
}
if(!hotelsSlope.isEmpty())
return hotelsSlope;
else
return hotelsDistance;
}
return null;
}
public int binarySearch(int low, int high,double minDistance,boolean isLow,boolean isHigh,int last_pos){
int mid = (low+high)/2;
if(low>high)
return last_pos;
if((int)minDistance==(int)hotelDirectory.get(mid).getDistance())
return mid;
last_pos = mid;
if(isLow && (int)minDistance>(int)hotelDirectory.get(mid).getDistance())
return last_pos;
if(isHigh && (int)minDistance<(int)hotelDirectory.get(mid).getDistance())
return last_pos;
if((int)minDistance>(int)hotelDirectory.get(mid).getDistance())
binarySearch(mid+1,high,minDistance,isLow,isHigh,last_pos);
else
binarySearch(low,mid-1,minDistance,isLow,isHigh,last_pos);
return last_pos;
}
}
public class HotelFinder {
public static HotelDirectory directory;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
buildHotelDirectory();
System.out.println(directory.hotelDirectory);
System.out.println(directory.getNearestHotels(3, 10, 0));
System.out.println(directory.getNearestHotels(10, 10, 5));
System.out.println(directory.getNearestHotels(6, 6, 5));
System.out.println(directory.getNearestHotels(1, 1, 5));
}
public static void buildHotelDirectory(){
directory = HotelDirectory.getInstance();
directory.addHotel("Holiday Inn", 1, 1);
directory.addHotel("Quality Inn", 2, 3);
directory.addHotel("Astre Inn", 1, 4);
directory.addHotel("Dalia Inn", 3, 3);
directory.addHotel("Maharaja Inn", 4, 4);
directory.addHotel("Hampton Inn", 2, 5);
directory.addHotel("Maharaja Inn", 5, 5);
Collections.sort(directory.hotelDirectory);
}
}
Another better idea I have is
1. consider the origin to be any corner point enclosing a country. So all the hotels in the country will lie in one quadrant.
2. Compute initial distance of all hotels from this origin, store in a list and sort.
3. for every user query, we can also accept max radius. compute user distance from origin. Now, subtract radius value from user distance and do a binary search on list for this value. Once you find a value, copy that and all subsequent hotel values until user distance plus radius.
4. Now you have list of all nearest hotels. Compute the distance of these hotels from user, store it a PQ or list, sort if you use list and display.
Will post the solution by tomorrow.
Not sure what datastructure we could use, so I just made one up. A hotel directory containing list of all hotels and also map of type of hotel, example all Holiday Inn locations.
I could have used priority queue as well, especially if we are to limit the number of nearest hotels to be displayed.
I have a hotel object, which can store all the information pertaining to a hotel. The directory list is initially sorted based on distance from origin (0,0).
For every user query, the distances of all hotels are updated and sorted. Again with PQ, that would be done as the updates are happening. For specific hotel query, I would do the same thing to the list stored against the hotel name and not all the hotels.
package com.google.practice;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
//To store hotel information
class Hotel implements Comparable<Hotel>{
private String name=null;
private int x;
private int y;
private double distance;
public Hotel(String name,int x,int y){
this.name = name;
this.x = x;
this.y = y;
this.computeDistance(0,0);
Origin.getInstance().hotels.add(this);
}
@Override
public int compareTo(Hotel h) {
// TODO Auto-generated method stub
return Double.compare(this.distance, h.distance);
}
//intial distance from [0,0]
protected void computeDistance(int x,int y){
if(this.x==x){
this.distance = Math.abs(this.y-y);
}else if (this.y==y){
this.distance = Math.abs(this.x-x);
}else {
int a = Math.abs(this.x-x);
int b = Math.abs(this.y-y);
this.distance = Math.sqrt(a*a+b*b);
}
}
public String toString(){
return this.name+" at a distance of "+this.distance;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
class Origin{
private int x=0,y=0;
private static Origin _org = new Origin();
protected List<Hotel> hotels = new ArrayList<Hotel>();
private Origin(){};
//recalculate distance from user co-ordinates
public List<Hotel> updateOrigin(int x,int y,HotelDirectory d){
this.x = x;
this.y = y;
for(Hotel h : hotels){
h.computeDistance(this.x,this.y);
}
Collections.sort(d.hotelDirectory);
return d.hotelDirectory;
}
//recalculate distance from user co-ordinates for specific hotel
public List<Hotel> updateOrigin(int x,int y,HotelDirectory d,String name){
this.x = x;
this.y = y;
List<Hotel> tmp = d.hotelDirectoryByHotel.get(name);
for(Hotel h : tmp){
h.computeDistance(this.x,this.y);
}
Collections.sort(tmp);
d.hotelDirectoryByHotel.put(name, tmp);
return tmp;
}
public static Origin getInstance(){
return _org;
}
}
class HotelDirectory{
private static HotelDirectory _hDir = new HotelDirectory();
public List<Hotel> hotelDirectory = new ArrayList<Hotel>();
public Map<String,List<Hotel>> hotelDirectoryByHotel = new HashMap<String,List<Hotel>>();
private HotelDirectory(){};
public void addHotel(String name, int x,int y){
Hotel h = new Hotel(name,x,y);
this.addHotel(h);
}
public void addHotel(Hotel h){
this.hotelDirectory.add(h);
updateHotelWise(h);
}
private void updateHotelWise(Hotel h){
List<Hotel> tmp;
if(hotelDirectoryByHotel.containsKey(h.getName())){
tmp = hotelDirectoryByHotel.get(h.getName());
}else{
tmp = new ArrayList<Hotel>();
}
tmp.add(h);
hotelDirectoryByHotel.put(h.getName(), tmp);
}
public void removeHotel(Hotel h){
this.hotelDirectory.remove(h);
}
public static HotelDirectory getInstance(){
return _hDir;
}
}
public class HotelFinder {
public static HotelDirectory directory;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
buildHotelDirectory();
System.out.println(directory.hotelDirectory);
System.out.println(Origin.getInstance().updateOrigin(3, 1,directory));
System.out.println(Origin.getInstance().updateOrigin(2, 7,directory));
System.out.println(Origin.getInstance().updateOrigin(10, -1,directory));
System.out.println(Origin.getInstance().updateOrigin(-5, 10,directory));
System.out.println(Origin.getInstance().updateOrigin(-5, 10,directory,"Maharaja Inn"));
System.out.println(Origin.getInstance().updateOrigin(3, 10,directory,"Maharaja Inn"));
}
public static void buildHotelDirectory(){
directory = HotelDirectory.getInstance();
directory.addHotel("Holiday Inn", 1, 1);
directory.addHotel("Quality Inn", 2, 3);
directory.addHotel("Astre Inn", 1, 4);
directory.addHotel("Dalia Inn", 3, 3);
directory.addHotel("Maharaja Inn", 4, 4);
directory.addHotel("Hampton Inn", 2, 5);
directory.addHotel("Maharaja Inn", 5, 5);
Collections.sort(directory.hotelDirectory);
}
}
Here is the update. Small change in main method and a rearrange method. helpPoorTeacher method remains same.
public static void main(String[] args) {
// TODO Auto-generated method stub
int noOfGreedyBs = 4;
int[] childRanking = new int[noOfGreedyBs];
//childRanking[0]=Integer.MIN_VALUE;
childRanking[0] = 1;childRanking[1] = 3;childRanking[2] = 7;childRanking[3] = 5;//childRanking[4] = 5;//childRanking[5] = 6;
//childRanking[childRanking.length-1]=Integer.MAX_VALUE;
int[] childLaddu = new int[noOfGreedyBs+2];
childLaddu[0] = 0;
for(int i=1;i<noOfGreedyBs+1;i++)
childLaddu[i]=1;
childLaddu[childLaddu.length-1] = 0;
Arrays.sort(childRanking);
childRanking = rearrange(childRanking);
System.out.println(helpPoorTeacher(childRanking,childLaddu));
}
public static int[] rearrange(int[] childRanking){
int[] tmp = new int[childRanking.length+2];
tmp[0] = Integer.MAX_VALUE;
int i=0,j,k=1;
j = childRanking.length%2==0?childRanking.length/2:childRanking.length/2+1;
for(;i<childRanking.length/2;i++,j++){
tmp[k++] = childRanking[i];
if(j<childRanking.length)
tmp[k++] = childRanking[j];
}
tmp[k] = Integer.MAX_VALUE;
return tmp;
}
I get it. It doesnt work for odd number of students.
Here is the updated helpPoorTeacher method :
public static int helpPoorTeacher(int[] childRanking, int[] childLaddu){
if(childRanking.length<=2)
return 0;
int f=1,b=childLaddu.length-2;
int prev=0,next=0;
prev = childRanking[0];
next = childRanking[childRanking.length-1];
while(f<childRanking.length-1){
int fCurrent = childRanking[f];
int bCurrent = childRanking[b];
if(fCurrent==Integer.MAX_VALUE)
break;
if(f==b && (fCurrent>prev||bCurrent>next)){
if(childLaddu[f-1]==childLaddu[b+1]){
childLaddu[f]=childLaddu[f-1]+1;
}else{
if(childLaddu[f-1]>childLaddu[b+1]){
childLaddu[f]=childLaddu[f-1]+1;
}else{
childLaddu[b]=childLaddu[b+1]+1;
}
}
}else{
if(fCurrent>prev){
childLaddu[f]=childLaddu[f-1]+1;
}
if(bCurrent>next){
childLaddu[b]=childLaddu[b+1]+1;
}
}
prev = childRanking[f];
next = childRanking[b];
f++;
b--;
}
int totalLaddu = 0;
for(int k=0;k<childLaddu.length;k++){
System.out.println(childLaddu[k]);
totalLaddu = totalLaddu + childLaddu[k];
}
return totalLaddu;
}
input :
5
Rank : 1 3 2 5 7
Laddus : 1 2 1 2 3
Total : 9
input :
5
Rank : 1 3 7 5 7
Laddus : 1 2 3 1 2
Total : 9
input :
4
Rank : 1 3 7 5
Laddus : 1 2 3 1
Total : 7
Here is the problem with your solution. Its no different than all the solutions provided before you. Except for your solution works only for 3 strings. If we go by your logic where we are to believe there can only be 3 strings, all the solutions provided above will also have O(n) complexity. Write a nested loop or write a loop n times, both are same but the later is a programmatic catastrophe.
- AlgoAlgae June 17, 2014Time complexity : Theta(nm) where n is number of strings and m is average length of strings.
package com.google.practice;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class CommonChars {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
List<String> arr = new ArrayList<String>();
arr.add("aghkafgklt");
arr.add("dfghako");
arr.add("qwemnaarkf");
findCommon(arr);
}
public static void findCommon(List<String> arr){
Set<Character> tmp1 = new TreeSet<Character>();
Set<Character> tmp2 = new TreeSet<Character>();
//Place all chars from first string in tmp1
for(char c:arr.get(0).toCharArray())
tmp1.add(c);
//Parse through all the strings.
for(String s:arr){
for(char c:s.toCharArray()){
if(tmp1.contains(c))
tmp2.add(c);
}
tmp1.clear();
tmp1.addAll(tmp2);
tmp2.clear();
}
System.out.println(tmp1.size()+" : "+tmp1);
}
}
This is just to give an idea. A skeleton you can improve on. There are lot of improvements we can do here. Dynamic ship count and type selection, providing proper access modifiers and setters getters, have separate ship classes for each type if you want, provide utility for each player to enter their placement choices via console etc.
import java.util.Set;
import java.util.TreeSet;
enum Ship{
Large,Medium,Small;
}
enum Orientation{
Vertical,Horizontal;
}
class Coordinate implements Comparable<Coordinate>{
private int x;
private int y;
public Coordinate(int x,int y){
this.x = x;
this.y = y;
}
@Override
public int compareTo(Coordinate c) {
// TODO Auto-generated method stub
if(this.x==c.x && this.y==c.y)
return 0;
return 1;
}
}
class Board{
public String playerName;
private int[][] board = new int[20][20];
public boolean gameOver = false;
private int s1 = 2;
private int s2 = 2;
private int s3 = 1;
Set<Coordinate> taken = new TreeSet<Coordinate>();
int remainingShips = 5;
public Board(String name){
this.playerName = name;
}
public void placeShip(Ship s,int x,int y,Orientation o) throws Exception{
if(remainingShips==0)
throw new Exception("No more ship left");
Set<Coordinate> tmp = new TreeSet<Coordinate>();
switch(s){
case Large: if(s3==0)
throw new Exception("No more large ship left");
if(o==Orientation.Horizontal){
if(x+5>19){
throw new Exception("cannot place ship there");
}
for(int i=0;i<5;i++){
Coordinate c = new Coordinate(x+i,y);
if(taken.contains(c))
throw new Exception("cannot place over another ship");
tmp.add(c);
}
}else{
if(y+5>19){
throw new Exception("cannot place ship there");
}
for(int i=0;i<5;i++){
Coordinate c = new Coordinate(x,y+i);
if(taken.contains(c))
throw new Exception("cannot place over another ship");
tmp.add(c);
}
}
taken.addAll(tmp);
tmp.clear();
--s3;
break;
case Medium : if(s2==0)
throw new Exception("No more medium ship left");
if(o==Orientation.Horizontal){
if(x+3>19){
throw new Exception("cannot place ship there");
}
for(int i=0;i<3;i++){
Coordinate c = new Coordinate(x+i,y);
if(taken.contains(c))
throw new Exception("cannot place over another ship");
tmp.add(c);
}
}else{
if(y+3>19){
throw new Exception("cannot place ship there");
}
for(int i=0;i<5;i++){
Coordinate c = new Coordinate(x,y+i);
if(taken.contains(c))
throw new Exception("cannot place over another ship");
tmp.add(c);
}
}
taken.addAll(tmp);
tmp.clear();
--s2;
break;
case Small : if(s1==0)
throw new Exception("No more small ship left");
if(o==Orientation.Horizontal){
if(x+3>19){
throw new Exception("cannot place ship there");
}
for(int i=0;i<3;i++){
Coordinate c = new Coordinate(x+i,y);
if(taken.contains(c))
throw new Exception("cannot place over another ship");
tmp.add(c);
}
}else{
if(y+3>19){
throw new Exception("cannot place ship there");
}
for(int i=0;i<5;i++){
Coordinate c = new Coordinate(x,y+i);
if(taken.contains(c))
throw new Exception("cannot place over another ship");
tmp.add(c);
}
}
taken.addAll(tmp);
tmp.clear();
--s1;
break;
}
}
public boolean bombard(int x,int y, String name){
Coordinate c = new Coordinate(x,y);
if(this.board[x][y]==1){
System.out.println("already hit, try again");
return true;
}
this.board[x][y]=1;
if(taken.contains(c)){
taken.remove(c);
}
if(taken.size()==0){
System.out.println(name+" WINNER");
this.gameOver=true;
}
return false;
}
}
public class BattleShipGame {
public static void main(String[] arg){
Board player1 = new Board("A");
Board player2 = new Board("B");
try {
player1.placeShip(Ship.Large, 0, 0, Orientation.Horizontal);
player1.placeShip(Ship.Medium, 1, 1, Orientation.Vertical);
player1.placeShip(Ship.Medium, 4, 5, Orientation.Horizontal);
player1.placeShip(Ship.Small, 11, 12, Orientation.Vertical);
player1.placeShip(Ship.Small, 19, 7, Orientation.Horizontal);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
try {
player2.placeShip(Ship.Large, 0, 0, Orientation.Horizontal);
player2.placeShip(Ship.Medium, 1, 1, Orientation.Vertical);
player2.placeShip(Ship.Medium, 4, 5, Orientation.Horizontal);
player2.placeShip(Ship.Small, 11, 12, Orientation.Vertical);
player2.placeShip(Ship.Small, 19, 7, Orientation.Horizontal);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
int turn = 0;
while(!player1.gameOver && !player2.gameOver){
if(turn==0){
while(player2.bombard(5, 5, player1.playerName)){}
}else{
while(player1.bombard(5, 5, player2.playerName)){}
}
turn = (turn+1)%2;
}
}
}
O(n) solution.
package com.google.practice;
public class LadduKhor {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int noOfGreedyBs = 4;
int[] childRanking = new int[noOfGreedyBs+2];
childRanking[0]=Integer.MAX_VALUE;
childRanking[1] = 1;childRanking[2] = 2;childRanking[3] = 1;childRanking[4] = 1;
childRanking[childRanking.length-1]=Integer.MAX_VALUE;
int[] childLaddu = new int[noOfGreedyBs+2];
childLaddu[0] = 0;
for(int i=1;i<noOfGreedyBs+1;i++)
childLaddu[i]=1;
childLaddu[childLaddu.length-1] = 0;
System.out.println(helpPoorTeacher(childRanking,childLaddu));
}
//Parse through the line from both end. Give 1 laddu token more than previous child has if previous child has lower ranking.
//Once parse is done. Poor teacher can exchange token for real laddu.
public static int helpPoorTeacher(int[] childRanking, int[] childLaddu){
if(childRanking.length<=2)
return 0;
int f=1,b=childLaddu.length-2;
int prev=0,next=0;
prev = childRanking[0];
next = childRanking[childRanking.length-1];
while(f<childRanking.length-1){
int fCurrent = childRanking[f];
int bCurrent = childRanking[b];
if(fCurrent==Integer.MAX_VALUE)
break;
if(fCurrent>prev){
childLaddu[f]=childLaddu[f-1]+1;
}
if(bCurrent>next){
childLaddu[b]=childLaddu[b+1]+1;
}
prev = childRanking[f];
next = childRanking[b];
f++;
b--;
}
int totalLaddu = 0;
for(int k=0;k<childLaddu.length;k++){
totalLaddu = totalLaddu + childLaddu[k];
}
return totalLaddu;
}
}
Agree with Nikhil. But you can also do it with just one hashmap.
1. Declare a directory map Map<String,List<String>>
Key can be either number or name.
2. Parse through the original directory. If name already exist in map, add number to value list, else create new arraylist and add number and store against the name. Also make another entry with number as key and name as value.
Once you map is populated, retrieval is O(1). Most of these type of questions are based on preprocessing. When you get question involving huge data, consider preprocessing.
For topological sort, you need you make sure you work on DAG. if there is any cycle, then there is no solution to this problem.
source = Identify vertex with no incoming edges.
Topological_Sort(source)
perform DFS, if you encounter already visited vertex and if parent is same, set visited parent to visiting vertex.
Do this untill you have no vertex to visit.
Using priorityQueue for caching. HashMap to maintain keyset and perform faster put and get operation. setting priority based on the time of use.
package com.amazon.practice;
import java.util.Calendar;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
class LRU<K,V> implements Comparable<LRU<K,V>>{
private long recentUseTime = Calendar.getInstance().getTimeInMillis();
private K key;
private V value;
@Override
public int compareTo(LRU<K, V> arg0) {
// TODO Auto-generated method stub
return Double.compare(this.recentUseTime, arg0.recentUseTime);
}
public void setPriority(long p){
this.recentUseTime = p;
}
public LRU(K key, V value){
this.key = key;
this.value = value;
}
public V getValue(){
return this.value;
}
public K getKey(){
return this.key;
}
public void setValue(V v){
this.value = v;
}
public void setKey(K k){
this.key = k;
}
public String toString(){
return "[ "+this.key+" - "+this.value+" ]";
}
}
class LRUCache<K,V>{
private Queue<LRU<K,V>> cache = new PriorityQueue<LRU<K,V>>();
private Map<K,LRU<K,V>> keySet = new HashMap<K,LRU<K,V>>();
public void put(K key,V value){
if(this.keySet.containsKey(key)){
(this.keySet.get(key)).setPriority(Calendar.getInstance().getTimeInMillis());
this.cache.remove(this.keySet.get(key));
this.cache.add(this.keySet.get(key));
}else{
LRU<K,V> lruNode = null;
if(this.cache.size()==10){
lruNode = this.cache.peek();
}
if(lruNode!=null){
keySet.remove(lruNode.getKey());
lruNode.setPriority(0);
lruNode.setKey(key);
lruNode.setValue(value);
}else{
lruNode = new LRU<K,V>(key,value);
this.cache.add(lruNode);
}
this.keySet.put(key, lruNode);
}
}
public V get(K key){
return (this.keySet.get(key)).getValue();
}
public void printCache(){
Iterator<LRU<K,V>> it = cache.iterator();
System.out.println();
while(it.hasNext())
System.out.print(it.next().toString());
System.out.println();
}
}
public class LRUCacheTest {
public static void main(String[] arg){
LRUCache<String,String> cache= new LRUCache<String,String>();
cache.put("one", "one");
cache.put("two", "two");
cache.put("three", "three");
cache.put("four", "four");
cache.put("five", "five");
cache.put("six", "six");
cache.put("seven", "seven");
cache.put("eight", "eight");
cache.put("nine", "nine");
cache.put("ten", "ten");
cache.printCache();
cache.put("eleven", "eleven");
cache.printCache();
cache.put("seven", "seven");
cache.printCache();
cache.put("eleven", "eleven");
cache.printCache();
}
}
small correction in findSequenceBoundary() else block.
else{
if(len>maxSeqLen){
m.min = minBoundary;
m.max = maxBoundary;
maxSeqLen = len;
}
minBoundary = a[maxUpdatePos];
len = i - maxUpdatePos + 1;
minUpdatePos = maxUpdatePos;
maxUpdatePos = i;
maxBoundary = a[i];
}
Sorry I missed N log N requirement for solution. Here is the solution. Let me know if it fails for any input.
package com.amazon.practice;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class MinMax{
public int min;
public int max;
}
public class SeqProblemNlogN {
public static void main(String[] arg){
int[] array = {6,10,6,7,8,9,0};//{1,2,1,0,2,1,1,2,2};
int[] arrayTmp = new int[array.length];
//O(n) to copy the array in tmp array
for(int i=0;i<array.length;i++){
arrayTmp[i] = array[i];
}
//O(nlogn) to sort
Arrays.sort(arrayTmp);
//O(n) to find the sequence boundaries using tmp array
MinMax m = findSequenceBoundary(arrayTmp);
//O(n) to create result sequence
System.out.println(findOriginalSeq(array,m));
//Time Complexity : O(n log n)
}
public static MinMax findSequenceBoundary(int[] a){
int maxSeqLen = Integer.MIN_VALUE;
int minBoundary=a[0],maxBoundary=a[1],len=1,maxUpdatePos=1,minUpdatePos=0;
MinMax m = new MinMax();
for(int i=1;i<a.length;i++){
if(Math.abs(minBoundary-a[i])<=1){
if(Math.abs(minBoundary-a[i])==1 && maxBoundary!=a[i]){
maxBoundary = a[i];
maxUpdatePos = i;
}
len++;
}else{
if(len>maxSeqLen){
m.min = minBoundary;
m.max = maxBoundary;
maxSeqLen = len;
minBoundary = a[maxUpdatePos];
len = i - maxUpdatePos + 1;
minUpdatePos = maxUpdatePos;
maxUpdatePos = i;
maxBoundary = a[i];
}
}
}
if(len>maxSeqLen){
m.min = minBoundary;
m.max = maxBoundary;
}
return m;
}
public static List<Integer> findOriginalSeq(int[] a, MinMax m){
List<Integer> seq = new ArrayList<Integer>();
for(int i=0;i<a.length;i++){
if(a[i]==m.min || a[i]==m.max)
seq.add(a[i]);
}
return seq;
}
}
I prefer time over space. I personally don't worry too much about space. I bought 2TB drive for 60 bucks recently :). Good deal. Suffix tree search is faster than BM but yes, it takes additional one time effort to build it and the algorithm to build is complex.
- AlgoAlgae December 03, 2014