Cracking the coding interview questions

 Posted on April 17, 2014  (Last modified on August 7, 2020)  |  24 minutes  |  Kinshuk Chandra

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. [Read More]
kodeknight  Page  CrackingTheCodingInterview 

Solve Towers of Hanoi using stack

 Posted on April 17, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

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. [Read More]
kodeknight  CrackingTheCodingInterview  stack 

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

 Posted on April 17, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

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. [Read More]
kodeknight  CrackingTheCodingInterview  bits 

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

 Posted on April 15, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

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. [Read More]
kodeknight  Threads and Locks  CrackingTheCodingInterview 

Scheduling method calls in sequence

 Posted on April 15, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

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: [Read More]
kodeknight  Threads and Locks  CrackingTheCodingInterview 

Thread safe and exception safe singleton design pattern

 Posted on April 15, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

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. [Read More]
kodeknight  Threads and Locks  CrackingTheCodingInterview 

How to measure the time spent in a context switch

 Posted on April 15, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

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. [Read More]
kodeknight  Threads and Locks  CrackingTheCodingInterview 

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

 Posted on April 14, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

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) [Read More]
kodeknight  inmobi  stock  Dynamic Programming  DP 

Maximum product sub-array

 Posted on April 13, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

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 [Read More]
kodeknight  contiguous  Dynamic Programming  DP  product 

Set cover

 Posted on April 13, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

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. [Read More]
kodeknight  inmobi