Harsh
BAN USERDirection {
UP, DOWN
}
Elevator {
Elevator id;
Direction currentDirection;
int currentLevel;
List<MovementPlan> pendingPlans;
MovementPlan currentPlan;
// Definite stop in route. Create a new plan if required.
public void addStoppage(int level) {
boolean isPossibleInCurrentPlan = currentPlan.addStop(level, currentDirection);
if (isPossibleInCurrentPlan) {
return;
}
// try to see if it can fit in other plans
for (MovementPlan plan : pendingPlans) {
isPossibleInPending = plan.addStop(level, currentDirection);
if(isPossibleInPending) return;
}
// Make a new plan. Current plan didn't work means request is of opposite direction
Direction oppositeDirection = direction.equals(UP)?DOWN:UP;
Integer firstStop = currentPlan.getLast(); // last stop there is first stop here
Set<Integer> stops = {firstStop, level};
MovementPlan newPlan = new MovementPlan(stops, oppositeDirection);
plans.add(newPlan);
}
public boolean isIdle() { // if currentPlan==null && pendingPlans.isEmpty() }
// Should keep executing asynchronously
public void move() {
while(true) {
moveTo(currentPlan.getNext());
refreshCurrentLevel();
// assuming movement completed
currentPlan.reachedNextStop();
if (currentPlan.isCompleted()) {
if (pendingPlans.isEmpty()) {
// wait for new plan
} else {
currentPlan = pendingPlans.get(0);
}
}
}
}
}
MovementPlan {
Direction direction;
Set<Integer> assignedStoppages;
public ElevationPlan(Set<Integer assignedStops, Direction direction) {
// keep assigned stops in sorted order.
// ascending if direction is UP, else descending if direction is DOWN
}
public Integer getNext() {
assignedStoppages.get(0);
}
public Integer getLast() {
assignedStoppages.get(assignedStoppages.size() -1);
}
// Adds if new stop falls in the way. Else returns false
public boolean addStop(int newStop, Direction direction) {
// is elevator moving in same direction
boolean isAlignedWithPlan = ((direction.equals(UP) && newStop > getNext())
|| (direction.equals(DOWN)&& newStop < getNext()))
if ((!isCompleted()) && this.direction.equals(direction) && isAlignedWithPlan)
assignedStoppages.add(newStop);
else
return false;
}
public Integer reachedNextStop() {
Integer next = getNext();
assignedStoppages.remove(next);
}
public boolean isCompleted() {
return assignedStoppages.isEmpty();
}
}
ExternalController {
List<Elevator> elevators;
initialize(Set<Elevator> elevators) {
// initialize
}
public void addPickRequest(int stopAtLevel, Direction direction) {
// get all current movement plans from all elevators
// Check if already assigned to one of the elevators
// else pick up next idle elevator and call addStoppage there
// else if no elevator is idle
// pick one elevator and call addStoppage there. will internally create new movement plan if necessary
}
}
At first glance, this question appeals for inheritance but before using inheritance, it is important to understand what deviations are possible from base functionality. The question doesn't clearly speak about that. If properties of class will be same, there is no need for inheritance.
Different weapons have different predefined damage. We can define Weapon class with following properties -
public class Weapon{
String name;
int damagingEffect;
int bulletsLeft;
public Weapon(name, damagingEffect, bulletsLeft) {// initialize all}
// returns damaging effect
public int fireWeapon() {
if (bulletsLeft == 0) {
throw new OutOfAmmoException(name);
}
bulletsLeft--;
return damagingEffect;
}
public void reload(int newBullets) {
bullets+= newBullets;
}
}
As the game initializes, different instances of this class can represent different weapons.
Example
Weapon gun = new Weapon("gun", 3, 100);
Weapon rocketLauncher = new Weapon("Rocket Launcher", 50, 20);
Weapon missile = new Weapon("Missile", 100, 5);
Hero is initialized with Set of Weapons. He can use one as current.
public class Hero {
Map<String, Weapon> weapons = new HashMap<String, Weapon>();
Weapon currentWeapon;
public Hero(Set<Weapon> weapons) {
for(Weapon weapon:weapons)
this.weapons.put(weapon.name(), weapon);
currentWeapon = weapons.get(0);
}
public void setCurrentWeapon(String name) {
if (!weapons.contains(name)) {
throw new NoSuchWeaponException(name);
}
currentWeapon = weapons.get(name);
}
// returns damaging effect
public int fire() {
return currentWeapon.fireWeapon();
}
public boolean isUnArmed() {
// check and return true if all weapons are out of bullets
}
}
Monster can captured in a same class.
public class Monster {
String name;
int health;
public Monster(String name, int health) {// initialize}
// returns true if dead
public boolean damageHealth(int damageEffect) {
health-=damageEffect;
return isDead();
}
public boolean isDead() {
return health<=0;
}
}
Example monsters -
Monster yeti = new Monster("Yeti", 20);
Monster dino = new Monster("Dinosaur", 40);
Then you initialize the Game, where all action is happening. Each level will have different instance of game class.
public class Game {
Hero hero;
int level;
Map<String, Monster> monsters;
enum LevelResult {WON, LOST, PLAYING};
public Game(Hero hero, Set<Monster> monsters, int level) {//initialize}
public void doEncounter(String monsterName) {
Monster monster = monsters.get(monsterName);
boolean isDead = monster.damageHealth(hero.fire());
if (monster.isDead()) {
monsters.remove(monsterName);
}
}
public void misFire() {
hero.fire(); // didn't hit any monster
}
public LevelResult getLevelResult() {
if (mosters.isEmpty()) {
return LevelResult.WON;
} else if (hero.isUnArmed()) {
return LevelResult.LOST;
} else {
return LevelResult.PLAYiNG;
}
}
}
@Rohit:
Starting from first digit, means starting from left. So, for 3,8,9 we start from 3. No. of swaps allowed is 1. So, we go to next digit and swap if it is bigger; if we swap, reduce the no. of swaps used. No. of swaps are exhausted so we stop and say this is final answer. This will change the number to 8,3,9 (the correct answer).
Consider another example -
4, 1, 9 - no. of swaps allowed - 1
First iteration will start from 4 and go till second digit (no. of swaps). Since, no change is required, we fix first position and repeat the same process from second. Since, our allowed swaps are not used, we can do next iteration
Second iteration will start from 1 and go till 9. Since, swap makes sense and we do that. No. changes ti 4, 9, 1.
@ipook : If no. are in decreasing order, can it be maximized ? Swaps will not be used and this algo will return the same no.
By saying maximize, I assume elements in array are projected as digits in a single number. Now we want to maximize that number by shuffling.
1. Starting from first digit, check next n digits. Record the position of biggest one. Here n=swapsAllowed.
2. Bubble the biggest digit to the top. Reduce n by no. of swaps. Reset n to -> n=n-(distance of biggest digit from top)
3. Move to second digit, repeat #1 with new value of n.
4. Repeat 3 until n or no. of digits are exhausted.
Time needed - O(n2). Space O(1)
If extra memory is not a problem, we can parse all digits and keep them in a decreasing order along with their indeces, in a sorted map. In that case, time will come down to O(nlogn) -[O(nlogn) for sorting, and O(n) for processing], and space will go up by O(n).
Maintain a parallel sorted array of same size in following manner.
Maintain a tail pointer. At any point, the active array is between starting element and the element at the tail.
Insertion rules
1. For a new number x do binary search in the array and position the element against the next larger element. If there is no such element, add the element in the last.
2. Print element and its predecessor and move tail pointer to this index.
Example :
Given list
7, 1, 6, 5, 8, 3, 2, 9
Element Array Action Tail Printed
7 7 Inserted 7 index1 7, null
1 1 Replaced 7 index1 1, null
6 1,6 Inserted 6 index2 6,1
5 1,5 Replaced 6 index2 5,1
8 1,5,8 Inserted 8 index3 8,5
3 1,3 Replaced 5 index2 3,1
2 1,2 Replaced 3 index2 2,1
9 1,2,9 Inserted 9 index3 9,2
Since, we are using binary search for detecting the right location of element in the sorted array, operation wouldn't cost more than logK (Where k is avg. no. of elements in the array). K will be less than n .
Use of tail index saves us from shifting operations in array. So, no added time for it.
Complexity is O(nlogK)
Repmarygaustria, Analyst at ADP
I am Mary from Los Angeles, USA. I am working as a Manager in Fragrant Flower Lawn Services company. I ...
Repjosiredhima, AT&T Customer service email at Aricent
I am an architect with three years experience planning and designing commercial buildings. I am working as principal architect on ...
RepI graduated from College with a master’s degree in arthrogryposis. After graduation I am working as a manager in ...
Repabbyherza, Animator at ASAPInfosystemsPvtLtd
I am Viola .I am A public relations consultant, a communications specialist who works as an intermediary between the public ...
Repjacksabjohne, Accountant at ABC TECH SUPPORT
Michael is a Biological Technician with 4 years of experience monitoring, characterizing, and quantifying riverine processes and habitat in the ...
Repcolettehenna, OOPS Freshers at Bosch
I am Colette , policy analyst at Sunflower Market , with 3 years of experience building and maintaining relationships with elected officials ...
Repprishamondel, Quality Assurance Engineer at Bloomberg LP
I am Prisha, a versatile self-starter and a quick learner looking for a position within your company, Netaid. My hobbies ...
RepHey, I am Margaret Salas, and I am working as a Web Developer Manager. And nowadays I am doing a ...
Repgoamgivheler, Accountant at Lava
I am working as a nurse in Bali Boer Cafarius. I enjoy relationships with patients and their families. It has ...
Coffee machine and shop are different aspects. Book speaks about writing algo for coffee machine.
- Harsh May 18, 2014In fact, you may relate it to the pizza store example given for abstract factory pattern.