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

Read More

Solve Towers of Hanoi using stack

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/tower-of-hanoi/. 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...

Read More

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

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-the-nearest-numbers-that-have-same-number-of-1s-for-an-integer/. 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...

Read More

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

Read More

Scheduling method calls in sequence

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

Read More

Design a class which provides a lock if no deadlocks

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

Read More

Thread safe and exception safe singleton design pattern

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() { //...

Read More

How to measure the time spent in a context switch

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: Multitasking Most...

Read More

Differences between thread and process

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

Read More

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

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) Your API can be BestTiming getBestTiming(int stockid); where class BestTiming{ StockPrediction bestselltime: ...

Read More

Design a vending machine like coffee vending machine

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/ood/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,...

Read More

Maximum product sub-array

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

Read More

Set cover

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} Answer: 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...

Read More

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

Read More

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

Read More

Stone thrown from the boat

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

Read More

3 Fastest horses among 25 running on 5 tracks

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

Read More

Number of rectangles in MxN matrix.

Problems Count number of squares in chessboard? Count number of rectangles in MXN rectangle 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...

Read More