## Thursday, April 17, 2014

### Problem

In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one). You have the following constraints:
(A) Only one disk can be moved at a time.
(B) A disk is slid off the top of one rod onto the next rod.
(C) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first rod to the last using Stacks.

### Solution

Let us denote the three rods, from left to right, as src, transfer and des.
• 1 disk only: move from src to des. done.
• 2 disks(top to bottom: 1->2): move 1 from src to transfer, move 2 from src to des, move 1 from transfer to des.
• 3 disks: ‘magically(recursively)’ move {1,2} from src to transfer, move 3 from src to des, ‘magically(recursively)’ move {1,2} from transfer to des.
• n disks: recursively move the top n-1 disks from src to transfer, move n from src to des, recursively move the n-1 disks from transfer to des.
For n disks, we need 2^n-1 steps at minimum to finish the game.
```public class TowerOfHanoiWithStack {

private Stack<Object>[] stacks = new Stack;
private Object[] disks;

public TowerOfHanoiWithStack(Object[] disks) {
stacks = new Stack<Object>();
stacks = new Stack<Object>();
stacks = new Stack<Object>();
this.disks = disks;
for (Object o : disks)
stacks.push(o);
}

public void solve() {
solveRecursively(0, 2, 1, disks);
}

public void solveRecursively(int sourceIndex, int desIndex,
int transferIndex, Object[] disks) {
Stack<Object> source = stacks[sourceIndex];
Stack<Object> des = stacks[desIndex];

Object[] sub_disks = null;
if (disks.length > 1) {
sub_disks = new Object[disks.length - 1];
System.arraycopy(disks, 0, sub_disks, 0,
disks.length - 1);
solveRecursively(sourceIndex, transferIndex,
desIndex, sub_disks);
}
Object t = source.pop();
des.push(t);
System.out.println("Move " + t + " from " +
sourceIndex + " to " + desIndex);

if (disks.length > 1)
solveRecursively(transferIndex, desIndex,
sourceIndex, sub_disks);
}
}
```

References

### Problem

Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
Example
Next higher number for 3 is 5. i.e. (00000011 => 00000101)
Likewise next lower number of 5 is 3.

### Solution

Method 1 - Adding or subtracting 1 until we have same number of 1s
For the next largest, keep adding 1 to the number until find the number that has same number of 1 bits. For the next smallest, keep decreasing 1.
```public static int findNextSmallest(int number) {
int result = number - 1;
while (Integer.bitCount(result) != Integer.bitCount(number))
result--;
return result;
}

public static int findNextLargest(int number) {
int result = number + 1;
while (Integer.bitCount(result) != Integer.bitCount(number))
result++;
return result;
}
```

Definitely gonna work but terribly boring. We know this is not what the interviewer expects, he wants some bit manipulation.

Method 2- Change the bits

For getting the next higher number
• Traverse from right to left i.e. LSB to MSB. Once we’ve passed a 1, turn on the next 0. We’ve now increased the number by 2^i. Yikes!
Example: xxxxx011100 becomes xxxxx111100.
• Turn off the one that’s just to the right side of that. We’re now bigger by 2^i - 2^(i-1).
Example: xxxxx111100 becomes xxxxx101100
• Make the number as small as possible by rearranging all the 1s to be as far right as possible:
Example: xxxxx101100 becomes xxxxx100011
For the next smaller number
We can do something like this.
```int getNextSmaller(int num) {
return ~getNextLarger(~num);
}
```
i.e. follow the above algorithm for number's complement.

Java code
```public static boolean GetBit(int n, int index) {
return ((n & (1 << index)) > 0);
}

public static int SetBit(int n, int index, boolean b) {
if (b) {
return n | (1 << index);
} else {
int mask = ~(1 << index);
}
}

public static int GetNext_NP(int n) {
if (n <= 0)
return -1;
int index = 0;
int countOnes = 0;

// Find first one.
while (!GetBit(n, index))
index++;

// Turn on next zero.
while (GetBit(n, index)) {
index++;
countOnes++;
}
n = SetBit(n, index, true);

// Turn off previous one
index--;
n = SetBit(n, index, false);
countOnes--;

// Set zeros
for (int i = index - 1; i >= countOnes; i--) {
n = SetBit(n, i, false);
}

// Set ones
for (int i = countOnes - 1; i >= 0; i--) {
n = SetBit(n, i, true);
}

return n;
}

public static int GetPrevious_NP(int n) {
if (n <= 0)
return -1; // Error

int index = 0;
int countZeros = 0;

// Find first zero.
while (GetBit(n, index))
index++;

// Turn off next 1.
while (!GetBit(n, index)) {
index++;
countZeros++;
}
n = SetBit(n, index, false);

// Turn on previous zero
index--;
n = SetBit(n, index, true);
countZeros--;

// Set ones
for (int i = index - 1; i >= countZeros; i--) {
n = SetBit(n, i, true);
}

// Set zeros
for (int i = countZeros - 1; i >= 0; i--) {
n = SetBit(n, i, false);
}

return n;
}
```

References

## Tuesday, April 15, 2014

### Can two threads call a synchronized method and normal method at the same time?

Problem
You are given a class with synchronized method A, and a normal method C. If you have two threads in one instance of a program, can they call A at the same time? Can they call A and C at the same time?
Solution:
Java provides two ways to achieve synchronization: synchronized method and synchronized statement.

• Synchronized method: Methods of a class which need to be synchronized are declared with “synchronized” keyword. If one thread is executing a synchronized method, all other threads which want to execute any of the synchronized methods on the same objects get blocked.

Syntax: method1 and method2 need to be synchronized
```public class SynchronizedMethod {
// Variables declaration
public synchronized T Method1() {
// Statements
}
public synchronized T method2() {
// Statements
}
// Other methods
}
```

T is return type.
• Synchronized statement: It provides the synchronization for a group of statements rather than a method as a whole It needs to provide the object on which these synchronized statements will be applied, unlike in a synchronized method

Syntax: synchronized statements on "this" object
```synchronized(this) {
// statement 1
// ...
// statement N
}
```
i) If you have two threads in one instance of a program, can they call A at the same time?
Not possible; read the above paragraph.
ii) Can they call A and C at the same time?
Yes. Only methods of the same object which are declared with the keyword synchronized can't be interleaved

References

### Problem

Suppose we have the following code:
```class Foo {
public:
A(.....); // If A is called, a new thread will be created
// and the corresponding function will be executed.
B(.....); // same as above
C(.....); // same as above
}
Foo f;
f.A(.....);
f.B(.....);
f.C(.....);
```

i) Can you design a mechanism to make sure that B is executed after A, and C is executed after B?
ii) Suppose we have the following code to use class Foo We do not know how the threads will be scheduled in the OS:
```Foo f;
f.A(.....);
f.B(.....);
f.C(.....);
f.A(.....);
f.B(.....);
f.C(.....);
```

Can you design a mechanism to make sure that all the methods will be executed in sequence?

### Solution

i) Can you design a mechanism to make sure that B is executed after A, and C is executed after B?
```Semaphore s_a(0);
Semaphore s_b(0);
A {
//
s_a.release(1);
}
B {
s_a.acquire(1);
//
s_b.release(1);
}
C {
s_b.acquire(1);
//
}
```

ii) Can you design a mechanism to make sure that all the methods will be executed in sequence?
```Semaphore s_a(0);
Semaphore s_b(0);
Semaphore s_c(1);
A{
s_c.acquire(1);
//
s_a.release(1);
}
B{
s_a.acquire(1);
//
s_b.release(1);
}
C{
s_b.acquire(1);
//
s_c.release(1);
}
```

Thanks

References

### Problem

Design a class which provides a lock only if there are no possible deadlocks.

### Solution

Deadlock will occur with a lock only if the locks can be held in a circular fashion; that is, if you define an ordering < on locks such that A < B only if lock A can be held with lock B also held, then<  is not a strict partial ordering. For example, if thread 1 tries to acquire lock A and then lock B, while thread 2 tries to acquire lock B and then lock A, then A < B and B < A, so < is not a strict partial ordering. Indeed, deadlock can occur if threads 1 and 2 each get locks A and B, respectively, then try to acquire the other lock.

So, a class can create a deadlock, by acquiring the control of the entire set of related locks that might be involved in such deadlocks. It can then, for example, require they be taken in some specific order (e.g. alphabetic ordering based on a name associated with each lock, arbitrary unique integers hardcoded in the source).

For our solution, we implement a wait / die deadlock prevention scheme.

Wait-die scheme: It is a non-preemptive technique for deadlock prevention. When transaction Ti requests a data item currently held by Tj, Ti is allowed to wait only if it has a timestamp smaller than that of Tj (That is Ti is older than Tj), otherwise Ti is rolled back (dies)
For example:
Suppose that transaction T22, T23, T24 have time-stamps 5, 10 and 15 respectively. If T22 requests a data item held by T23 then T22 will wait. If T24 requests a data item held by T23, then T24 will be rolled back.
(definition taken from code bank.)

Java code
```class MyThread extends Thread {
long time;
ArrayList<Resource> res = new ArrayList<Resource>();

public ArrayList<Resource> getRes() {
return res;
}

@Override
public void run() {
// Run infinitely
time = System.currentTimeMillis();
int count = 0;
while (true) {
if (count < 4) {
if (Question.canAcquireResource(this, Question.r[count])) {
count++;
+ Question.r[count - 1].getId()
+ "] acquired by thread: [" + this.getName()
+ "]");
try {
sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
} else {
}
}
}

public long getTime() {
return time;
}

public void setRes(ArrayList<Resource> res) {
}

super(name);
}
}
```

Thanks
References

### Problem

Implement a singleton design pattern as a template such that, for any given class Foo, you can call Singleton::instance() and get a pointer to an instance of a singleton of type Foo Assume the existence of a class Lock which has acquire() and release() methods How could you make your implementation thread safe and exception safe?

### Solution

Here is the code in cpp:
```using namespace std;
// Place holder for thread synchronization lock
class Lock {
public:
Lock() { // placeholder code to create the lock
}
~Lock() { // placeholder code to deallocate the lock
}
void AcquireLock() { // placeholder to acquire the lock
}
void ReleaseLock() { // placeholder to release the lock
}
};

// Singleton class with a method that creates a new instance
// of the * class of the type of the passed in template
// if it does not already exist.
template <class T> class Singleton {
private:
static Lock lock;
static T* object;
protected:
Singleton() { };
public:
static T * instance();
};
Lock Singleton::lock;

T * Singleton::Instance() {
// if object is not initialized, acquire lock
if (object == 0) {
lock.AcquireLock();
// If two threads simultaneously check and pass the first "if"
// condition, then only the one who acquired the lock first
// should create the instance
if (object == 0) {
object = new T;
}
lock.ReleaseLock();
}
return object;
}

int main() {
// foo is any class defined for which we want singleton access
Foo* singleton_foo = Singleton<Foo>::Instance();
return 0;
}
```

Thanks

References

### Problem

How can you measure the time spent in a context switch?

### Solution

This is a tricky question, but let’s start with a possible solution.

A context switch is the time spent switching between two processes (e.g., bringing a waiting process into execution and sending an executing process into waiting/terminated state). i.e.  it is the computing process of storing and restoring the state (context) of a CPU so that execution can be resumed from the same point at a later time.

There are three potential triggers for a context switch:

Most commonly, within some scheduling scheme, one process needs to be switched out of the CPU so another process can run. This context switch can be triggered by the process making itself unrunnable, such as by waiting for an I/O or synchronization operation to complete. On a pre-emptive multitasking system, the scheduler may also switch out processes which are still runnable. To prevent other processes from being starved of CPU time, preemptive schedulers often configure a timer interrupt to fire when a process exceeds its time slice. This interrupt ensures that the scheduler will gain control to perform a context switch.

#### Interrupt handling

Modern architectures are interrupt driven. This means that if the CPU requests data from a disk, for example, it does not need to busy-wait until the read is over; it can issue the request and continue with some other execution. When the read is over, the CPU can be interrupted and presented with the read. For interrupts, a program called an interrupt handler is installed, and it is the interrupt handler that handles the interrupt from the disk.

When an interrupt occurs, the hardware automatically switches a part of the context (at least enough to allow the handler to return to the interrupted code). The handler may save additional context, depending on details of the particular hardware and software designs. Often only a minimal part of the context is changed in order to minimize the amount of time spent handling the interrupt. The kernel does not spawn or schedule a special process to handle interrupts, but instead the handler executes in the (often partial) context established at the beginning of interrupt handling. Once interrupt servicing is complete, the context in effect before the interrupt occurred is restored so that the interrupted process can resume execution in its proper state.

#### User and kernel mode switching

When a transition between user mode and kernel mode is required in an operating system, a context switch is not necessary; a mode transition is not by itself a context switch. However, depending on the operating system, a context switch may also take place at this time.

The operating system must bring the state information of waiting processes into memory and save the state information of the running process.
So, roughly context switch happens because:
1. User process enters the kernel via system call or a trap (e.g. page fault) and requested data (e.g. file contents) is not yet available, so the kernel puts said user process into sleep state and switches to another runnable process.
2. Kernel detects that given user process consumed its full time quanta (this happens in code invoked from timer interrupt.)
3. Data becomes available for higher current priority process that is presently sleeping (this happens from code invoked from/around IO interrupts.)

In order to solve this problem, we would like to record timestamps of the last and first instruction of the swapping processes. The context switching time would be the difference in the timestamps between the two processes.

Let’s take an easy example: Assume there are only two processes, P1 and P2.
P1 is executing and P2 is waiting for execution. At some point, the OS must swap P1 and P2 — let’s assume it happens at the Nth instruction of P1. So, the context switch time for this would be Time_Stamp(P2_1) – Time_Stamp(P2_N)
Easy enough.

The tricky part is this: how do we know when this swapping occurs? Swapping is governed by the scheduling algorithm of the OS. We can not, of course, record the timestamp of every instruction in the process.
Another issue: there are many kernel level threads which are also doing context switches, and the user does not have any control over them.
Overall, we can say that this is mostly an approximate calculation which depends on the underlying OS. One approximation could be to record the end instruction timestamp of a process and start timestamp of a process and waiting time in queue.
If the total timeof execution of all the processes was T, then the context switch time = T – (SUM for all processes (waiting time + execution time)).

Reference

### Problem

What’s the difference between a thread and a process?

### Solution

Both processes and threads are independent sequences of execution.
Lets focus on difference - process vs threads.

Threads (of the same process) run in a shared memory space. A thread is the entity within a process that can be scheduled for execution. All threads of a process share its virtual address space and system resources. Processes run in separate memory spaces.
• exception handlers,
• a scheduling priority,
• a unique thread identifier, and
• a set of structures the system will use to save the thread context until it is scheduled.
A process has
• executable code,
• open handles to system objects,
• a security context,
• a unique process identifier,
• environment variables,
• a priority class,
• minimum and maximum working set sizes,
• and at least one thread of execution.

A process can be thought of as an instance of a program in execution. Each process is an independent entity to which system resources (CPU time, memory, etc.) are allocated and each process is executed in a separate address space. One process cannot access the variables and data structures of another process. If you wish to access another process’ resources, inter-process communications have to be used such as pipes, files, sockets etc.

A thread uses the same stack space of a process. A process can have multiple threads. A key difference between processes and threads is that multiple threads share parts of their state. Typically, one allows multiple threads to read and write the same memory (no processes can directly access the memory of another process). However, each thread still has its own registers and its own stack, but other threads can read and write the stack memory.

A thread is a particular execution path of a process; when one thread modifies a process resource, the change is immediately visible to sibling threads.

References

## Monday, April 14, 2014

### Problem

You have an API to predict stock values of a particular share,
The API is
`StockPrediction predict(int stockid);`

where
```class StockPrediction{
Date time:
float value;
}```

using this API develop another API which will suggest the best selling time and buying time of a share (you have to call the predict API N number of times and from the StockPredictions provide the best buy time and sell time for the stock)

`BestTiming getBestTiming(int stockid);`

where
```class BestTiming{
StockPrediction bestselltime:
}```

Example
Input

```stock value -  10   |   12   |    7   |    8    |  24  |  35  |   1  |   9
time        -  9am  |  9.30  |   9.45 |   10am  | 11am | 12am |  3am |  4am
```

Output: buy the stock at 7 rs at 9.45 and sell it for 35 rupees at 12am

(hint: go for the best solution which uses only three variable to get this result)

### Solution

We have discussed the similar problem here.
Fill array b with entries s.t. b = a-a .... b[n-1] = a[n]-a[n-1].
Now apply Kadane's Sub sequence sum algorithm on B and Find the indices.
Time O(n), Space O(n).

### Design a vending machine like coffee vending machine

• VendingMachine - possibly an abstract class
• DrinkMachine, SnackMachine, and classes extending VendingMachine
• VendingProduct - an abstract class?
• Drink, other classes extending VendingProduct
• Coke, other classes extending Drink
• &c, &c.
But I'm sure you can figure that out pretty easily. The nuts and bolts of the machine will take place in some kind of utility class, with methods to accept bills and coins, calculate change, etc.

Also, Getting the coffee will be got from the factory:
```public class CoffeeVendingMachine extends VendingMachine{
private Milk milk;
private Sugar sugar;
public Coffee getCoffee(CoffeeTypeEnum coffeeType){
prepareCoffee(coffeeType);
}
private void prepareCoffee(CoffeeTypeEnum coffeeType{
//internal process for coffee making
}
}
```

Note that prepareCoffee is private method, as users don't want to know how coffee is made.

Here is the basic class diagram for vending machine(borrowed from programsfromca):
Note that VendingMachine composes SelectionPanel, Controller, Product and so on.

References

## Problem

Given an integer array with negative numbers and zero find the subarray with maximum product, i.e. find the contiguous array elements that produce maximum product.
Also find the sub array.

Example
For 7 -3 -1 2 -40 0 3 6, the max subarray product = -1 * 2 * -40 = 80
For -3 7 2 0 -5 7 -2 -2 2, the maximum subarraproduct = -5 * 7 * -2 = 70

## Solution

Wherever there is 0 that splits the array into subarrays. We need to find the maximum product of these subarrays individually and return the largest product. Inside this subproblem if there are even number of negative elements then maximum product is the complete product of the array. If there are odd number of negative elements, then make two subarrays once leaving the leftmost negative element and once leaving the rightmost negative element. The maximum of these two products will be returned.

java code
```// Returns the product of max product subarray.  Assumes that the
//   given array always has a subarray with product more than 1
public static int maxSubarrayProduct(int arr[])
{
int n = arr.length;
// max positive product ending at the current position
int maxEndingHere = 1;

// min negative product ending at the current position
int minEndingHere = 1;

// Initialize overall max product
int maxSoFar = 1;

// Traverse throught the array.
// Following values are maintained after the ith iteration:
//  maxEndingHere is always 1 or some positive product ending with arr[i]
//  minEndingHere is always 1 or some negative product ending with arr[i]
for (int i = 0; i < n; i++)
{
// If this element is positive, update maxEndingHere. Update
//   minEndingHere only if minEndingHere is negative
if (arr[i] > 0)
{
maxEndingHere = maxEndingHere*arr[i];
minEndingHere = Math.min(minEndingHere * arr[i], 1);
}

// If this element is 0, then the maximum product cannot
//   end here, make both maxEndingHere and minEndingHere 0
//   Assumption: Output is alway greater than or equal to 1.
else if (arr[i] == 0)
{
maxEndingHere = 1;
minEndingHere = 1;
}

// If element is negative. This is tricky
//   maxEndingHere can either be 1 or positive.
//   minEndingHere can either be 1
//   or negative.
//   next minEndingHere will always be prev. maxEndingHere * arr[i]
//   next maxEndingHere will be 1 if prev minEndingHere is 1, otherwise
//   next maxEndingHere will be prev minEndingHere * arr[i]
else
{
int temp = maxEndingHere;
maxEndingHere = Math.max (minEndingHere * arr[i], 1);
minEndingHere = temp * arr[i];
}

// update maxSoFar, if needed
if (maxSoFar <  maxEndingHere)
maxSoFar  =  maxEndingHere;
}

return maxSoFar;
}
```

Time Complexity: O(n)
Auxiliary Space: O(1)

Dry running the algo
Consider the array A = {1, -2, -3, 0, 7, -8, -2}.
Initially we will take maxSoFar, maxEndingHere and minEnding here as 1, as we have to multiply by the number. Also, we have to reset maxEndingHere and minEndingHere to 1, whenever we encounter 0.

Now, we iterate over the array
i=0, a[i] > 0 implies we have to multiply maxEndingHere=1*1 = 1, minEndingHere = 1.Finally maxSoFar stays the same.

i = 1, a[i] = -2 < 0 which implies temp= maxEndingHere = 1. MaxEndingHere = max(-2* 1, 1) =1 , and maxEndingHere =  1 * -2 = -2

i = 2, maxEndingHere = 6, minEndingHere = -3, maxSoFar = 6

i = 3 , maxEndingHere = 1, minEndingHere = 1, maxSoFar = 6

and so on.

References

### Problem

There are few sets with some numbers. And you are given an array of numbers. Find combination of sets with minimum number of sets, union of which have all these numbers.

Example
input sets:
A = [1,2,3]
B = [2,5,8]
C = [1,4,5]
D = [3,5,8]

Array to find:
{3,4,8}

C + D

### Solution

Set cover is NP-hard, so, no polynomial algorithm is known to exist for it.

When you abstract away from the specifics of the problem, it is an integer program (IP). So, you can use any general purpose IP solver such as the one provided in MS-Excel. All general integer programming problems are solved using branch-and-bound method. So, you do not need one specifically for Set Covering alone. All you need to do is to formulate the set covering problem as an integer program and provide it to the solver which should take care of the rest. Folks on SO are unlikely to have a ready-made code available to share with you. Integer Programming/Linear Programming (which forms the basis for integer programming) codes are quite detailed and specialized.

Basically, look at all combinations of 1 set, then 2 sets, etc. until they form a cover.
```for size in 1..|S|:
for C in combination(S, size):
if (union(C) == U) return C
```
where `combination(K, n)` returns all possible sets of size `n` whose elements come from `K`.

```interface Filter<T> {
boolean matches(T t);
}
public static void main(String... args) throws IOException {
Integer[][] arrayOfSets = {
{1, 2, 3, 8, 9, 10},
{1, 2, 3, 4, 5},
{4, 5, 7},
{5, 6, 7},
{6, 7, 8, 9, 10},
};
Integer[] solution = {1,2,3,4,5,6,7,8,9,10};

List<Set<Integer>> listOfSets = new ArrayList<Set<Integer>>();
for (Integer[] array : arrayOfSets)
final Set<Integer> solutionSet = new LinkedHashSet<Integer>(Arrays.asList(solution));

Filter<Set<Set<Integer>>> filter = new Filter<Set<Set<Integer>>>() {
public boolean matches(Set<Set<Integer>> integers) {
for (Set<Integer> ints : integers)
return union.equals(solutionSet);
}
};

Set<Set<Integer>> firstSolution = shortestCombination(filter, listOfSets);
System.out.println("The shortest combination was "+firstSolution);
}

private static <T> Set<T> shortestCombination(Filter<Set<T>> filter, List<T> listOfSets) {
final int size = listOfSets.size();
if (size > 20) throw new IllegalArgumentException("Too many combinations");
int combinations = 1 << size;
List<Set<T>> possibleSolutions = new ArrayList<Set<T>>();
for(int l = 0;l<combinations;l++) {
for(int j=0;j<size;j++) {
if (((l >> j) & 1) != 0)
}
}
// the possible solutions in order of size.
Collections.sort(possibleSolutions, new Comparator<Set<T>>() {
public int compare(Set<T> o1, Set<T> o2) {
return o1.size()-o2.size();
}
});
for (Set<T> possibleSolution : possibleSolutions) {
if (filter.matches(possibleSolution))
return possibleSolution;
}
return null;
}
```

References

## Friday, April 11, 2014

### Create the REV function from Swap

We have a function REV(“string”,m,n).This function is capable of reversing the caharacters in the string from mth location to nth location. e.g. REV(“abcd”,2,3); the output will be acbd We need to swap a string from a position,e.g. SWAP(“abcdefg”,4)  output needs to be efgabcd.
How can the REV function used do this.

Solution
ANS : L = string length,N= position given in SWAP function.
SWAP(“abcdefg”,4) = REV(REV(REV(“abcdefg”,N+1,L),1,N),1,L).

### Is there multiply function in 8085 microprocessor

There is no multiplication instruction in the 8085 - I believe that was added in the 8086 & 8088 version of the series.

This has the entire instruction set for the 8085:

These operations are equivilent to multiplying by 2:

1) Shift left by 1 (shifting left by n is multiplying by 2^n)
2) Add the value to itself once.

Other than that you can write a loop to add the number to itself 'n' times.

Or, if you don't need to generalize you can use the following algorithm:

to multiply an 8 bit value (x) by 3:

.....0 x7 x6 x5 x4 x3 x2 x1 x0 --- (x * 1)
+ x7 x6 x5 x4 x3 x2 x1 x0 0 ---- (x * 2) (x << 1)
--------------------------------------...

to multiply by 5:

.....0...0 x7 x6 x5 x4 x3 x2 x1 x0 ---- (x * 1)
+ x7 x6 x5 x4 x3 x2 x1 x0...0...0 ---- (x * 4) (x << 2)
--------------------------------------...

The "."s are just to get the spacing right

Here is a site with a general bit serial algorithm:

Ooops, I didn't realize there wasn't a shift instruction either.

You can use RAL (rotate left with carry). That will rotate the high order bit to the carry flag and the carry flag to the low order bit. If you need to have the result be greater than 8 bits, you can use the carry flag to shift the bit values into another byte.

If I remember right, the 8085 is a 8 bit processor.
This is how you would shift an 8 bit value, yielding a 16 bit result:

STC
CMC
LDA [a]
RAL
STA [a]
LDA [a+1]
RAL
STA [a+1]

I'm actually more familiar with the 8088/6 and later processors. After looking at the instruction set in more detail, I believe the RAL will not only rotate the high order bit throuh the carry flag, but also rotate the carry flag to the low order bit. That's why you need to clear the carry flag before starting. Since there is no clear carry instruction, the way I did it above was to set the carry flag, then compliment it. Also, it doesn't appear that the RAL instruction allows you to rotate more than one bit at a time.

References

### Problem

Will there be any change in water level/height of floating part of the boat if stones are dropped into the pond from a floating boat?
Follow up - What if you are given empty 2L bottle and chained under the boat?

### Solution

There is maybe a little physics needed here...

When an object is floating be it because it is something less dense than water, say polystyrene, or because it is in a boat, say a brick and the whole boat is less dense than water, then it displaces in the water it's own mass. For example a 10 Kg lump of lead on a boat will force the boat to sink by a volume equivalent to 10Kg of water. Hence displacing 10Kg of water. Or indeed forcing the water level to raise by an amount equivalent to 10Kg of water. (Like when you get in the bath.)

When an object sinks in water it necessarily displaces it's own volume.

So when the brick is in the boat it is displacing it's own mass equivalence in water. When the brick is thrown over the side it is displacing it's own volume in water.

So which of these is greater?

Well we know the brick to be more dense than water because it sinks. So the volume of water equivalent to the mass of the brick is greater than the volume of the brick. And so less water is displaced after than before. Hence...

Water level will go down

The opposite would happen if you were chained to the bottom and pulled an empty two-liter bottle under the water.  First, it's only displacing water equal to its weight, because it's floating.  But then when you pull it under water, it's displacing water equal to its volume, which is much more.  Then the water level rises.

### Problem

There are 25 horses and only five tracks in a race (i.e., you can race 5 horses at a time). There is no stop clock !! Assume that there are no ties.
1: What is the minimum number of races needed to determine the 3 fastest horses in order from fastest to slowest ?
Follow Up minimum number of races needed to find
1:....... to rank all of them from fastest to slowest ?
2:....... to find the top k fastest horses ?

### Solution :

Divided into 5 groups, each 5 horses and have 5 races.
first 5 preliminary races
We run five races with five horses. The five winners race in a sixth race while the 4th and fith place finishers are eliminated from further consideration, as we have to anyways take first 3.
Now we are left with 15 horses.

6th race
Take all the fastest horses from each group and race them. The sixth race show horse is faster than all the horses that participated in the preliminary races where the 4th and 5th place horses participated and they are eliminated from further consideration. So, now we have 12 horses left, because we know who is the fastest horse, and 4th and 5th horses are removed, so 15 - 1 -2 = 12.

The other horses in the preliminary race where the 6th race show horse participated are also eliminated.

The slow horses in the preliminary race in competition of 4th and 5th horse in the 6th race are also eliminated since there are at least three remaining horses that are faster.
So, horses who lost to 4th and 5th horse of race 6 are removed, so 12 - 4 = 8

Throw the last one horse of the second fast group. 7 horse left
Throw the last two horse of the third fast group. 5 horse left
Now, lets have the last race

7th race
Take first 2, from this race, and we have our 3 fastest.

minimum number of races needed to find
1:....... to rank all of them from fastest to slowest ?
2:....... to find the top k fastest horses ?

* min number of races to rank all of them

1. I can re-phrase this question to ask the min number of races to get 25 fastest horses.
2. You need 6 races to get the fastest ranked (steps 1 thru 3).
3. After that every race will give you the next fastest.
4. We can continue this till we have got the 20 fastest horses. After that we just need 1 race to rank the remaining 5.

total = 6 (to get rank 1) + 19 (to get rank 2-20) + 1 (to get rank 21-25) = 26

* min number of races to get k fastest horse

sol:-
5 + k (for k <= 20 )
26 (otherwise)

### Problems

1. Count number of squares in chessboard?
2. Count number of rectangles in MXN rectangle
3. Squares in rectangle
Lets answer them 1 by 1.

### Solution

Number of squares in chessboard having 8X8 grid.
There are four 7x7 squares, one aligned with each corner.   There are nine 6x6 squares, etc.  So the sum of the first 8 squares 1+4+9+16+25+36+47+64=204 is the answer.  In general, the sum of the first n squares is given by the formula
(2n3+3n2+n)/6

Now lets move to next.
Number of rectangles in MXN rectangle
The answer to this question is the same as the answer to another question:
How many ways can I draw two horizontal lines and two vertical lines through an array of (m+1) by (n+1) dots?
(Think of the dots formed at the corners of the little squares within the rectangle)
The two horizontal lines can be drawn C(m+1,2) ways, and the two vertical lines can be drawn C(n+1,2) ways, so the total number of rectangles within an m x n rectangle is
C(m+1,2) C(n+1,2)

Squares within rectangle
How many squares can be found within an m x n rectangle?  (m > n)
To answer this question, start with an n x n square, and then you know the number of squares in this portion of it from the first section:
(2n3+3n2+n)/6
Now, consider adding one row of squares at the bottom, making it an n+1 by n rectangle.  Think of the dots formed at the corners of the little squares you added to make the bottom row.   Now, for every pair of newly-added dots, you can find one new square.  So the number of new squares you can find in the now larger rectangle is the number of pairs of n+1 dots, which is C(n+1,2).  If you need convincing, there's another way to think of it.  By adding a new row of n little squares, you can now find within the large rectangle one new n x n square, two new n-1 x n-1 squares, three new n-2 x n-2 squares, etc.  So the number of new squares added this way is the sum of the first n counting numbers, which is C(n+1,2).

Now, add another row of squares at the bottom, making it an n+2 by n rectangle.  This adds the same number of new squares, C(n+1,2).

Now I'm sure you see the picture.  The number of squares that can be found within an m x n rectangle (m > n) is given by this formula:
(2n3+3n2+n)/6 + (m-n) C(n+1,2)
References
http://2000clicks.com/mathhelp/CountingRectangles.aspx

### Problem :

Two women apply for a job. They are identical. They have the same mother, father and birthday. The interviewer asks, "Are you twins?" to which they honestly reply, "No".
How is this possible?

### Solution :

Because they were triplets.