Thursday, April 17, 2014

Cracking the coding interview questions

The book - cracking the coding interview has list of questions. The list of questions and solutions is not comprehensive, but I guess that is the point. Coding interviews are about judging your approach to problems rather than specific solutions. I found that some of the problems were quite simple compared to the difficulty level currently in force at various companies. In particular would like to see more dynamic programming problems, but I think the author covers all the main questions, which sharpens our mind to focus on the problem solving, and is a very good starting point, which covers almost 80-90% problem solving exercises.

You can purchase the book from here:

Now lets see the index, covered in blog. Its in no way is as good as book, but I have logged these posts as my notes and faster web access.

Chapter 1 | Arrays and Strings
1.1 Implement an algorithm to determine if a string has all uniquecharacters. What if you can not use additional data structures? 

1.2 Write code to reverse a C-Style String. (C-String means that “abcd”is represented as five characters, including the null character.) 

1.3 Design an algorithm and write code to remove the duplicate characters in a stringwithout using any additional buffer. NOTE: One or two additional variables are fine.An extra copy of the array is not.FOLLOW UP Write the test cases for this method. 

1.4 Write a method to decide if two strings are anagrams or not. 

1.5 Write a method to replace all spaces in a string with ‘%20’. 

1.6 Given an image represented by an NxN matrix, where each pixel in the image is 4bytes, write a method to rotate the image by 90 degrees. Can you do this in place? 

1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row andcolumn is set to 0. 

1.8 Assume you have a method isSubstring which checks if one word is a substring ofanother. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”). 

Chapter 2 | Linked Lists
2.1 Write code to remove duplicates from an unsorted linked list.FOLLOW UP How would you solve this problem if a temporary buffer is not allowed? 

2.2 Implement an algorithm to find the nth to last element of a singly linked list. 

2.3 Implement an algorithm to delete a node in the middle of a single linked list, givenonly access to that node.EXAMPLE Input: the node ‘c’ from the linked list a->b->c->d->eResult: nothing is returned, but the new linked list looks like a->b->d->e 

2.4 You have two numbers represented by a linked list, where each node contains a singledigit. The digits are stored in reverse order, such that the 1’s digit is at the head ofthe list. Write a function that adds the two numbers and returns the sum as a linkedlist.EXAMPLE Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)Output: 8 -> 0 -> 8 

2.5 Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.DEFINITIONCircular linked list: A (corrupt) linked list in which a node’s next pointer points to anearlier node, so as to make a loop in the linked list.EXAMPLE input: A -> B -> C -> D -> E -> C (the same C as earlier)output: C 

Chapter 3 | Stacks and Queues
3.1 Describe how you could use a single array to implement three stacks. 

3.2 How would you design a stack which, in addition to push and pop, also has a functionmin which returns the minimum element? Push, pop and min should all operate inO(1) time.

3.3 Imagine a (literal) stack of plates. If the stack gets too high, it might topple.Therefore, in real life, we would likely start a new stack when the previous stack exceedssome threshold. Implement a data structure SetOfStacks that mimics this.SetOfStacks should be composed of several stacks, and should create a new stack oncethe previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() shouldbehave identically to a single stack (that is, pop() should return the same values as itwould if there were just a single stack).FOLLOW UP Implement a function popAt(int index) which performs a pop operation on a specificsub-stack. 

3.4 In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of differentsizes which can slide onto any tower. The puzzle starts with disks sorted in ascendingorder 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.© 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. 

3.5 Implement a MyQueue class which implements a queue using two stacks. 

3.6 Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions thatshould be used to write this program: push | pop | peek | isEmpty. 

Chapter 4 | Trees and Graphs
4.1 Implement a function to check if a tree is balanced. For the purposes of this question,a balanced tree is defined to be a tree such that no two leaf nodes differ in distancefrom the root by more than one.

4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes. 

4.3 Given a sorted (increasing order) array, write an algorithm to create a binary tree withminimal height. 

4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists). 

4.5 Write an algorithm to find the ‘next’ node (i.e., in-order successor) of a given node ina binary search tree where each node has a link to its parent. 

4.6 Design an algorithm and write code to find the first common ancestor of two nodesin a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is notnecessarily a binary search tree. 

4.7 You have two very large binary trees: T1, with millions of nodes, and T2, with hun-dreds of nodes. Create an algorithm to decide if T2 is a subtree of T1. 

4.8 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree - it does not have to start at the root. 

Chapter 5 | Bit Manipulation
5.1 You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write amethod to set all bits between i and j in N equal to M (e.g., M becomes a substring ofN located at i and starting at j).EXAMPLE:Input: N = 10000000000, M = 10101, i = 2, j = 6Output: N = 10001010100 

5.2 Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binaryrepresentation. If the number can not be represented accurately in binary, print “ERROR” 

5.3 Given an integer, print the next smallest and next largest number that have the samenumber of 1 bits in their binary representation.

5.4 Explain what the following code does: ((n & (n-1)) == 0). 

5.5 Write a function to determine the number of bits required to convert integer A to integer B. Input: 31, 14 Output: 2 

5.6 Write a program to swap odd and even bits in an integer with as few instructions aspossible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc). 

5.7 An array A[1…n] contains all the integers from 0 to n except for one numberwhich is missing. In this problem, we cannot access an entire integer in A witha single operation. The elements of A are represented in binary, and the onlyoperation we can use to access them is “fetch the jth bit of A[i]”, whichtakes constant time.Write code to find the missing integer. Can you do it in O(n) time? 

Chapter 6 | Brain Teasers
6 1  Add arithmetic operators (plus, minus, times, divide) to make the following expression true: 3 1 3 6 = 8 You can use any parentheses you’d like

6 2  There is an 8x8 chess board in which two diagonally opposite corners have been cut off You are given 31 dominos, and a single domino can cover exactly two squares Can you use the 31 dominos to cover the entire board? Prove your answer (by providing an example, or showing why it’s impossible)

6 3  You have a five quart jug and a three quart jug, and an unlimited supply of water (but no measuring cups) How would you come up with exactly four quarts of water?NOTE: The jugs are oddly shaped, such that filling up exactly ‘half’ of the jug would be impossible

6 4  A  bunch  of  men  are  on  an  island  A  genie  comes  down  and  gathers  everyone  together and places a magical hat on some people’s heads (i e , at least one person has a hat) The hat is magical: it can be seen by other people, but not by the wearer of the hat himself To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hatFOLLOW UP Prove that your solution is correct

6 5  There is a building of 100 floors If an egg drops from the Nth floor or above it will break If it’s dropped from any floor below, it will not break You’re given 2 eggs Find N, while minimizing the number of drops for the worst case

6 6  There are one hundred closed lockers in a hallway A man begins by opening all one hundred  lockers  Next,  he  closes  every  second  locker Then  he  goes  to  every  third locker and closes it if it is open or opens it if it is closed (e g , he toggles every third locker) After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?

Chapter 7 | Object Oriented Design
7.1  Design the data structures for a generic deck of cards Explain how you would subclass it to implement particular card games

7.2  Imagine you have a call center with three levels of employees: fresher, technical lead (TL), product manager (PM) There can be multiple employees, but only one TL or PM An incoming telephone call must be allocated to a fresher who is free If a fresher can’t handle the call, he or she must escalate the call to technical lead If the TL is not free or not able to handle it, then the call should be escalated to PM Design the classes and data structures for this problem Implement a method getCallHandler()

7.3  Design a musical juke box using object oriented principles

7.4  Design a chess game using object oriented principles

7.5  Design the data structures for an online book reader system

7.6  Implement a jigsaw puzzle Design the data structures and explain an algorithm to solve the puzzle

7.7  Explain how you would design a chat server In particular, provide details about the various  backend  components,  classes,  and  methods  What  would  be  the  hardest problems to solve?

7.8  Othello is played as follows: Each Othello piece is white on one side and black on the other When a piece is surrounded by its opponents on both the left and right sides, or both the top and bottom, it is said to be captured and its color is flipped On your turn, you must capture at least one of your opponent’s pieces The game ends when either user has no more valid moves, and the win is assigned to the person with the most pieces Implement the object oriented design for Othello

7.9  Explain the data structures and algorithms that you would use to design an in-memory file system Illustrate with an example in code where possible

7.10  Describe the data structures and algorithms that you would use to implement a garbage collector in C++

Chapter 8 | Recursion
8.1 Write a method to generate the nth Fibonacci number. 

8.2 Imagine a robot sitting on the upper left hand corner of an NxNgrid. The robot can only move in two directions: right and down. Howmany possible paths are there for the robot?FOLLOW UP Imagine certain squares are “off limits”, such that the robot cannot step on them.Design an algorithm to get all possible paths for the robot. 

8.3 Write a method that returns all subsets of a set. 

8.4 Write a method to compute all permutations of a string. 

8.5 Implement an algorithm to print all valid (e.g., properly openedand closed) combinations of n-pairs of parentheses.EXAMPLE:input: 3 (e.g., 3 pairs of parentheses)output: ()()(), ()(()), (())(), ((())) 

8.6 Implement the “paint fill” function that one might see on manyimage editing programs. That is, given a screen (represented by a 2dimensional array of Colors), a point, and a new color, fill in thesurrounding area until you hit a border of that color. 

8.7 Given an infinite number of quarters (25 cents), dimes (10 cents),nickels (5 cents) and pennies (1 cent), write code to calculate thenumber of ways of representing n cents. 

8.8 Write an algorithm to print all ways of arranging eight queens ona chess board so that none of them share the same row, column or diagonal. 

Chapter 9 | Sorting and Searching
9.1 You are given two sorted arrays, A and B, and A has a large enoughbuffer at the end to hold B. Write a method to merge B into A insorted order.

9.2 Write a method to sort an array of strings so that all the anagrams are next to each other. 

9.3 Given a sorted array of n integers that has been rotated an unknownnumber of times, give an O(log n) algorithm that finds an element inthe array. You may assume that the array was originally sorted inincreasing order.EXAMPLE:Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)Output: 8 (the index of 5 in the array) 

9.4 If you have a 2 GB file with one string per line, which sortingalgorithm would you use to sort the file and why? 

9.5 Given a sorted array of strings which is interspersed with emptystrings, write a method to find the location of a given string.Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”,“”, “”, “dad”, “”, “”] will return 4Example: find “ballcar” in[“at”, “”, “”, “”, “”, “ball”, “car”, “”,“”, “dad”, “”, “”] will return -1 

9.6 Given a matrix in which each row and each column is sorted, write amethod to find an element in it. 

9.7 A circus is designing a tower routine consisting of people standingatop one another’s shoulders. For practical and aesthetic reasons,each person must be both shorter and lighter than the person belowhim or her. Given the heights and weights of each person in thecircus, write a method to compute the largest possible number ofpeople in such a tower.EXAMPLE:Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)Output: The longest tower is length 6 and includes from top to bottom: (56, 90)(60,95) (65,100) (68,110) (70,150) (75,190) 

Chapter 10 | Mathematical
10 1  You have a basketball hoop and someone says that you can play 1 of 2 gamesGame #1: You get one shot to make the hoopGame #2: You get three shots and you have to make 2 of 3 shotsIf p is the probability of making a particular shot, for which values of p should you pick one game or the other?

10 2  There are three ants on different vertices of a triangle What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle?Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon

10.3  Given two lines on a Cartesian plane, determine whether the two lines would intersect

10.4  Write a method to implement *, - , / operations You should use only the + operator

10.5  Given two squares on a two dimensional plane, find a line that would cut these two squares in half

10 6 .Given a two dimensional graph with points on it, find a line which passes the most number of points

10.7  Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7

Chapter 11 | Testing
11.1  Find the mistake(s) in the following code:1  unsigned int i;2  for (i = 100; i <= 0; --i)3    printf(“%d\n”, i);

11.2  You are given the source to an application which crashes when it is run After running it ten times in a debugger, you find it never crashes in the same place The application is single threaded, and uses only the C standard library What programming errors could be causing this crash? How would you test each one?

11.3  We have the following method used in a chess game: boolean canMoveTo(int x, int y) x and y are the coordinates of the chess board and it returns whether or not the piece can move to that position Explain how you would test this method

11.4  How would you load test a webpage without using any test tools?

11.5  How would you test a pen?

11.6  How would you test an ATM in a distributed banking system?

Chapter 12 | System Design and Memory Limits
12.1 If you were integrating a feed of end of day stock priceinformation (open, high, low,and closing price) for 5,000companies, how would you do it? You are responsible forthe development, rollout and ongoing monitoring and maintenanceof the feed. Describe the different methods you considered andwhy you would recommend your approach. The feed is delivered onceper trading day in a comma-separated format via an FTP site. Thefeed will be used by 1000 daily users in a web application. 

12.2 How would you design the data structures for a very largesocial network (Facebook,LinkedIn, etc)? Describe how you woulddesign an algorithm to show the connection, or path, between twopeople (e.g., Me -> Bob -> Susan -> Jason -> You).

12.3 Given an input file with four billion integers, provide analgorithm to generate an integer which is not contained in thefile. Assume you have 1 GB of memory.FOLLOW UP What if you have only 10 MB of memory?

12.4 You have an array with all the numbers from 1 to N, where N isat most 32,000. The array may have duplicate entries and you donot know what N is. With only 4KB of memory available, how wouldyou print all duplicate elements in the array? 

12.5 If you were designing a web crawler, how would you avoid getting into infinite loops? 

12.6 You have a billion urls, where each is a huge page. How do you detect the duplicate documents? 

12.7 You have to design a database that can store terabytes of data.It should support efficient range queries. How would you do it? 

Chapter 13 | C++
13.1 Write a method to print the last K lines of an input file using C++.
13.2 Compare and contrast a hash table vs. an STL map. How is a hashtable implemented?If the number of inputs is small, what datastructure options can be used instead of a hash table?
13.3 How do virtual functions work in C++?
13.4 What is the difference between deep copy and shallow copy? Explainhow you would use each.
13.5 What is the significance of the keyword “volatile” in C?
13.6 What is name hiding in C++?
13.7 Why does a destructor in base class need to be declared virtual?
13.8 Write a method that takes a pointer to a Node structure as aparameter and returns a complete copy of the passed-in datastructure. The Node structure contains two pointers to other Nodestructures.
13.9 Write a smart pointer (smart_ptr) class.

Chapter 14 | Java
14.1  In terms of inheritance, what is the effect of keeping a constructor private?

14.2  In Java, does the finally block gets executed if we insert a return statement inside the try block of a try-catch-finally?

14.3  What is the difference between final, finally, and finalize?

14.4  Explain the difference between templates in C++ and generics in Java

14.5  Explain what object reflection is in Java and why it is useful

14.6  Suppose you are using a map in your program, how would you count the number of times the program calls the put() and get() functions?

Chapter 15 | Databases
15.1 Write a method to find the number of employees in each department.
15.2 What are the different types of joins? Please explain how theydiffer and why certain types are better in certain situations.
15.3 What is denormalization? Explain the pros and cons.
15.4 Draw an entity-relationship diagram for a database with companies,people, and professionals (people who work for companies).
15.5 Imagine a simple database storing information for students’ grades.Design what this database might look like, and provide a SQL queryto return a list of the honor roll students (top 10%), sorted bytheir grade point average. 

Chapter 16 | Low Level
16.1 Explain the following terms: virtual memory, page fault, thrashing.

16.2 What is a Branch Target buffer? Explain how it can be used in reducing bubble cycles in cases of branch misprediction

16 3  Describe direct memory access (DMA) Can a user level buffer / pointer be used by kernel or drivers?

16 4  Write a step by step execution of things that happen after a user presses a key on the keyboard Use as much detail as possible

16.5 Write a program to find whether a machine is big endian or littleendian. 

16 6  Discuss how would you make sure that a process doesn’t access an unauthorized part of the stack

16 7  What are the best practices to prevent reverse engineering of DLLs?

16 8  A device boots with an empty FIFO queue In the first 400 ns period after startup, and in each subsequent 400 ns period, a maximum of 80 words will be written to the queue Each write takes 4 ns A worker thread requires 3 ns to read a word, and 2 ns to process it before reading the next word What is the shortest depth of the FIFO such that no data is lost?

16 9  Write an aligned malloc & free function that takes number of bytes and aligned byte (which is always power of 2)EXAMPLEalign_malloc (1000,128) will return a memory address that is a multiple of 128 and that points to memory of size 1000 bytes aligned_free() will free memory allocated by align_malloc 

16.10 Write a function called my2DAlloc which allocates a two dimensionalarray. Minimize the number of calls to malloc and make sure that thememory is accessible by the notation arr[i][j]. 

Chapter 17 | Networking
17.1 Explain what happens, step by step, after you type a URL into abrowser. Use as much detail as possible. 

17.2 Explain any common routing protocol in detail. For example: BGP,OSPF, RIP.

17.3 Compare and contrast the IPv4 and IPv6 protocols.

17.4 What is a network / subnet mask? Explain how host A sends amessage / packet to host B when: (a) both are on same networkand (b) both are on different networks.Explain which layer makes the routing decision and how.

17.5 What are the differences between TCP and UDP? Explain how TCPhandles reliable delivery (explain ACK mechanism), flow control(explain TCP sender’s / receiver’s window) and congestion control.

Chapter 18 | Threads and Locks
18.1 What’s the difference between a thread and a process?

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

18.3 Implement a singleton design pattern as a template such that, forany 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?

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

18.5 Suppose we have the following code:…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.Can you design a mechanism to make sure that all the methods will be executed in sequence?

18.6 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?

Chapter 19 | Moderate
19.1 Write a function to swap a number in place without temporary variables. 

19.2 Design an algorithm to figure out if someone has won in a game of tic-tac-toe.

19.3 Write an algorithm which computes the number of trailing zeros in n factorial.

19.4 Write a method which finds the maximum of two numbers. You shouldnot use if-else or any other comparison operator. 

19.5 The Game of Master Mind is played as follows:The computer has four slots containing balls that are red ®,yellow (Y), green (G) or blue (B). For example, the computer mighthave RGGB (e.g., Slot #1 is red, Slots #2 and #3 are green, Slot #4is blue).You, the user, are trying to guess the solution. You might, forexample, guess YRGB. When you guess the correct color for thecorrect slot, you get a “hit”. If you guess a color that exists butis in the wrong slot, you get a “pseudo-hit”. For example, theguess YRGB has 2 hits and one pseudo hit.For each guess, you are told the number of hits and pseudo-hits.Write a method that, given a guess and a solution, returns thenumber of hits and pseudo hits.

19.6  Given an integer between 0 and 999,999, print an English phrase that describes the
integer (eg, “One Thousand, Two Hundred and Thirty Four”)

19.7 You are given an array of integers (both positive and negative).Find the continuous sequence with the largest sum. Return the sum.
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i e , {3, -2, 4} )

19.8 Design a method to find the frequency of occurrences of any givenword in a book.

19.9  Since XML is very verbose, you are given a way of encoding it where each tag gets
mapped to a pre-defined integer value The language/grammar is as follows:
Element --> Element Attr* END Element END [aka, encode the element
tag, then its attributes, then tack on an END character, then
encode its children, then another end tag]
Attr --> Tag Value [assume all values are strings]
END --> 01
Tag --> some predefined mapping to int
Value --> string value END
Write code to print the encoded version of an xml element (passed in as string)
Is there anything else you could do to (in many cases) compress this even further?

19.10 Write a method to generate a random number between 1 and 7, given amethod that generates a random number between 1 and 5 (i.e.,implement rand7() using rand5()). 

19.11 Design an algorithm to find all pairs of integers within an array which sum to a specified value. 

Chapter 20 | Hard
20.1 Write a function that adds two numbers. You should not use + or anyarithmetic operators. 

20.2 Write a method to shuffle a deck of cards. It must be a perfectshuffle - in other words, each 52! permutations of the deck has tobe equally likely. Assume that you are given a random numbergenerator which is perfect. 

20.3 Write a method to randomly generate a set of m integers from anarray of size n. Each element must have equal probability of beingchosen. 

20.4 Write a method to count the number of 2s between 0 and n. 

20.5 You have a large text file containing words. Given any two words,find the shortest distance (in terms of number of words) betweenthem in the file. Can you make the searching operation in O(1) time?What about the space complexity for your solution?

20.6 Describe an algorithm to find the largest 1 million numbers in 1billion numbers. Assume that the computer memory can hold all onebillion numbers. 

20.7 Write a program to find the longest word made of other words in alist of words.EXAMPLE Input: test, tester, testertest, testing, testingtester Output: testingtester 

20.8 Given a string s and an array of smaller strings T, design a methodto search s for each small string in T. 

20.9 Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated. 

20.10 Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

20.11 Imagine you have a square matrix, where each cell is filled witheither black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels. 

20.12 Given an NxN matrix of positive and negative integers, write codeto find the submatrix with the largest possible sum.

Solve Towers of Hanoi using stack


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.  


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[3];
    private Object[] disks;
    public TowerOfHanoiWithStack(Object[] disks) {
        stacks[0] = new Stack<Object>();
        stacks[1] = new Stack<Object>();
        stacks[2] = new Stack<Object>();
        this.disks = disks;
        for (Object o : disks)
    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();
        System.out.println("Move " + t + " from " +
                sourceIndex + " to " + desIndex);
        if (disks.length > 1)
            solveRecursively(transferIndex, desIndex,
                    sourceIndex, sub_disks);


Find the nearest numbers that have same number of 1s for an integer


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


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))
    return result;
public static int findNextLargest(int number) {
    int result = number + 1;
    while (Integer.bitCount(result) != Integer.bitCount(number))
    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);
        return n & mask;
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))
    // Turn on next zero.
    while (GetBit(n, index)) {
    n = SetBit(n, index, true);
    // Turn off previous one
    n = SetBit(n, index, false);
    // 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))
    // Turn off next 1.
    while (!GetBit(n, index)) {
    n = SetBit(n, index, false);
    // Turn on previous zero
    n = SetBit(n, index, true);
    // 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;


Tuesday, April 15, 2014

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

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?
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


Scheduling method calls in sequence


Suppose we have the following code:
class Foo {
    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;

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;

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


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 {
B {
C {

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);



Design a class which provides a lock if no deadlocks


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


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;
    public void run() {
        // Run infinitely
        time = System.currentTimeMillis();
        int count = 0;
        while (true) {
            if (count < 4) {
                if (Question.canAcquireResource(this, Question.r[count])) {
                    <span class="skimlinks-unlinked">res.add(Question.r</span>[count]);
                    <span class="skimlinks-unlinked">System.out.println("Resource</span>: ["
                            + Question.r[count - 1].getId()
                            + "] acquired by thread: [" + this.getName()
                            + "]");
                    try {
                    } catch (InterruptedException e) {
            } else {
                <span class="skimlinks-unlinked">this.stop</span>();
    public long getTime() {
        return time;
    public void setRes(ArrayList<Resource> res) {
        <span class="skimlinks-unlinked">this.res</span> = res;
    MyThread(String name) {


Thread safe and exception safe singleton design pattern


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?


Here is the code in cpp:
using namespace std;
// Place holder for thread synchronization lock
class Lock {
    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 { 
    static Lock lock;
    static T* object; 
    Singleton() { }; 
    static T * instance(); 
Lock Singleton::lock;
T * Singleton::Instance() {
// if object is not initialized, acquire lock 
    if (object == 0) {
// 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; 
    return object; 
int main() {
// foo is any class defined for which we want singleton access 
    Foo* singleton_foo = Singleton<Foo>::Instance();
    return 0;



How to measure the time spent in a context switch


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


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)).


Differences between thread and process


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


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

Thread Process
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.
 In addition, each thread maintains
  • exception handlers, 
  • a scheduling priority, 
  • thread local storage, 
  • 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
  • a virtual address space, 
  • 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. 
The thread context includes the thread's set of machine registers, the kernel stack, a thread environment block, and a user stack in the address space of the thread's process. Threads can also have their own security context, which can be used for impersonating clients. Each process is started with a single thread, often called the primary thread, but can create additional threads from any of its threads.

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.


Monday, April 14, 2014

Suggest the selling time and buying time of a share based on stock price prediction


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

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)

Your API can be
BestTiming getBestTiming(int stockid);

class BestTiming{
   StockPrediction bestselltime:
   StockPrediction bestbuytime:


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)


We have discussed the similar problem here.
Fill array b with entries s.t. b[0] = a[1]-a[0] .... 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

Broadly, think about what objects are involved in a 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){
   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.


Sunday, April 13, 2014

Maximum product sub-array


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.

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


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] 
            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.

Github link -


Set cover


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.

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

Array to find:

C + D


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)
        listOfSets.add(new LinkedHashSet<Integer>(Arrays.asList(array)));
    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) {
            Set<Integer> union = new LinkedHashSet<Integer>();
            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++) {
        Set<T> combination = new LinkedHashSet<T>();
        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;


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.

 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:

LDA [a]
STA [a]
LDA [a+1]
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.


Stone thrown from the boat


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?


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

Follow up answer
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.  

3 Fastest horses among 25 running on 5 tracks


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.

Follow Up questions
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

5 + k (for k <= 20 )
26 (otherwise)

Answer 1 : 7 races

Number of rectangles in MxN matrix.


  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.


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

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:
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)

Aren't you twins?

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.