Saturday, 26 July 2014

Puzzle 1--- Fill the boxes from 1 to 8

You have to fill the boxes from 1 to  8 such that no two adjacent elements are closed to each other either horzintonally vertically or diagonally. Below are the constraints.







Not Possible

                                      




Possible

                                       



Solution                                         .
                                        

Saturday, 19 July 2014

Find largest number obtained by changing the bits of a given number

For Example : 5 is represented in binary as 101 but the largest number can be 6(110)
Input   :A number n
Output: Largest number


#include <iostream>
#include <cmath>
using namespace std;
int FindLargest ( int n )
{
    int one=0,t=0,final=0;
    while ( n!=0 )
    {
        if ( n&1==1 )
        {
            one++;
            t++;
            n=n>>1;
        }
        else
        {
            t++;
            n=n>>1;
        }
    }
    for ( int i=t-1; i>=t-one; i-- )
    {
        final+=pow ( 2.0,i );
    }
    return final;
}
int main()
{
    int n;
    cin>>n;

    cout<<FindLargest ( n );

    getchar();

}


Please comment if you find anything incorrect.

Friday, 18 July 2014

Memory Leaks

1 Understand the operator basics. The C++ operator "new" allocates heap memory. The "delete" operator frees heap memory. For every "new," you should use a "delete" so that you free the same memory you allocated:

char* str = new char [30]; // Allocate 30 bytes to house a string.

delete [] str; // Clear those 30 bytes and make str point nowhere.

2 Reallocate memory only if you've deleted. In the code below, str acquires a new address with the second allocation. The first address is lost irretrievably, and so are the 30 bytes that it pointed to. Now they're impossible to free, and you have a memory leak:

char* str = new char [30]; // Give str a memory address.

// delete [] str; // Remove the first comment marking in this line to correct.

str = new char [60]; /* Give str another memory address with
                                                    the first one gone forever.*/

delete [] str; // This deletes the 60 bytes, not just the first 30.

3 Watch those pointer assignments. Every dynamic variable (allocated memory on the heap) needs to be associated with a pointer. When a dynamic variable becomes disassociated from its pointer(s), it becomes impossible to erase. Again, this results in a memory leak:

char* str1 = new char [30];

char* str2 = new char [40];

strcpy(str1, "Memory leak");

str2 = str1; // Bad! Now the 40 bytes are impossible to free.

delete [] str2; // This deletes the 30 bytes.

delete [] str1; // Possible access violation. What a disaster!

4. Be careful with local pointers. A pointer you declare in a function is allocated on the stack, but the dynamic variable it points to is allocated on the heap. If you don't delete it, it will persist after the program exits from the function:

void Leak(int x){

char* p = new char [x];

// delete [] p; // Remove the first comment marking to correct.

}

5.Pay attention to the square braces after "delete." Use "delete" by itself to free a single object. Use "delete" [] with square brackets to free a heap array. Don't do something like this:

char* one = new char;

delete [] one; // Wrong

char* many = new char [30];

delete many; // Wrong!

6. If the leak yet allowed - I'm usually seeking it with deleaker

Wednesday, 16 July 2014

Software Development- Things to Take care


  1. Always do Code Reviews, as it helps catch bugs in early stages of development.

Monday, 14 July 2014

new and delete



  1.  Syntax: void*  operator new(size_t size);
      Three forms of using new
    • T* p = new T
    • T* p = new T(value)
    • T* p = new T[size]                                                                
  2. new is an operator to Allocate memory for an object or array of objects of type-name from the free store and returns a suitably typed, nonzero pointer to the object.The pointer returned is cast to the data type implicitly
  3. When new is used to allocate memory for a C++ class object, the object's constructor is called after the memory is allocated.Invokes default constructor on all the objects in case of an array of objects
  4. If unsuccessful, new returns zero or throws an exception.You can change this default behavior by writing a custom exception-handling routine and calling the  _set_new_handler run-time library function with your function name as its argument.
  5. To allocate and then frees a two-dimensional array of characters of size by 10.                                            char (*pchar)[10] = new char[dim][10];                                                                                        delete [] pchar;
  6. The type-name cannot contain constvolatile, class declarations, or enumeration declarations. Therefore, the following expression is illegal.
  7. The new operator does not allocate reference types because they are not objects.
  8. The new operator cannot be used to allocate a function, but it can be used to allocate pointers to functions. The following example allocates and then frees an array of seven pointers to functions that return integers.                                                                                                            int (**p) () = new (int (*[7]) ());                                                                                            delete *p;

Sunday, 13 July 2014

Qt


  1. Signals and slots are used for communication between objects.They are alternative to the callback technique
  2.  A signal is emitted when a particular event occurs. 
  3.  A slot is a function that is called in response to a particular signal.
  4. All classes that contain signals or slots must mention Q_OBJECT at the top of their declaration. They must also derive (directly or indirectly) from QObject.
  5. The signature of a signal must match the signature of the receiving slot. (In fact a slot may have a shorter signature than the signal it receives because it can ignore extra arguments.) Since the signatures are compatible, the compiler can help us detect type mismatches. Signals and slots are loosely coupled: A class which emits a signal neither knows nor cares which slots receive the signal. Qt's signals and slots mechanism ensures that if you connect a signal to a slot, the slot will be called with the signal's parameters at the right time. Signals and slots can take any number of arguments of any type. They are completely type safe.

Important Links

  1. https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Memory_leak.html
  2. http://www.quora.com/How-can-I-prepare-for-interviews-in-any-big-software-company-like-Google-Facebook-Amazon-Microsoft-DE-Shaw-Salesforce-Flipkart-Expedia-Morgan-Stanley-Goldman-Sachs-Adobe-eBay-Walmart-LinkedIn-etc
  3. http://www.hongkiat.com/blog/linux-commands-to-avoid/
  4. http://www.codeproject.com/Articles/5660/Unit-testing-with-CPPUnit
  5. http://igoro.com/archive/what-really-happens-when-you-navigate-to-a-url/
  6. http://katyscode.wordpress.com/2013/05/17/introduction-to-multi-threaded-multi-core-and-parallel-programming-concepts/
  7. http://www.geeksforgeeks.org/multiple-inheritance-in-c/
  8. http://www.geeksforgeeks.org/when-do-we-pass-arguments-by-reference-or-pointer/
  9. http://www.geeksforgeeks.org/object-slicing-in-c/
  10. http://www.geeksforgeeks.org/g-fact-25/
  11. http://www.geeksforgeeks.org/when-do-we-use-initializer-list-in-c/
  12. http://www.geeksforgeeks.org/function-overloading-in-c/
  13. http://www.geeksforgeeks.org/function-overloading-and-const-functions/
  14. http://www.geeksforgeeks.org/does-overloading-work-with-inheritance/ 
  15. http://bigocheatsheet.com/

Virtual Functions-- Facts

1.Whenever virtual function is called using base class reference or pointer it cannot be inlined (because call is resolved at runtime), but whenever called using the object (without reference or pointer) of that class, can be inlined because compiler knows the exact class of the object at compile time.
2.#include<iostream>
using namespace std;
class Base {
public:
    virtual int fun(int i) { cout << "Base::fun(int i) called"; }
};
class Derived: public Base {
private:
    int fun(int x)   { cout << "Derived::fun(int x) called"; }
};
int main()
{
    Base *ptr = new Derived;
    ptr->fun(10);
    return 0;
}
Output:
 Derived::fun(int x) called 
In the above program, private function “Derived::fun(int )” is being called through a base class pointer, the program works fine because fun() is public in base class. Access specifiers are checked at compile time and fun() is public in base class. At run time, only the function corresponding to the pointed object is called and access specifier is not checked. So a private function of derived class is being called through a pointer of base class.           
3. Virtual functions can be private and can be overridden by the derived class. For example, the following program compiles and runs fine.
#include<iostream>
using namespace std;
class Derived;
class Base {
private:
    virtual void fun() { cout << "Base Fun"; }
friend int main();
};
class Derived: public Base {
public:
    void fun() { cout << "Derived Fun"; }
};
int main()
{
   Base *ptr = new Derived;
   ptr->fun();
   return 0;
}
Output:

Derived fun()

4.Deleting a derived class object using a pointer to a base class that has a non-virtual 
destructor results in undefined behavior. To correct thissituation, the base class should be 
defined with a virtual destructor. Making base class destructor virtual guarantees that the 
object of derived class is destructed properly, i.e., both base class and derived  class 
destructors are called.

5. How does compiler do this magic of late resolution?
Compiler maintains two things to this magic: virtualFuns vtable: A table of function pointers. It is maintained per class. vptr: A pointer to vtable. It is maintained per object (See this for an example).
Compiler adds additional code at two places to maintain and use vptr. 1) Code in every constructor. This code sets vptr of the object being created. This code sets vptr to point to vtable of the class. 2) Code with polymorphic function call . Wherever a polymorphic call is made, compiler inserts code to first look for vptr using base class pointer or reference (In the above example, since pointed or referred object is of derived type, vptr of derived class is accessed). Once vptr is fetched, vtable of derived class can be accessed. Using vtable, address of derived derived class function show() is accessed and called.

References:
1. http://www.geeksforgeeks.org/virtual-functions-and-runtime-polymorphism-in-c-set-1-introduction/ 
2. http://www.geeksforgeeks.org/g-fact-37/
3. http://www.geeksforgeeks.org/can-virtual-functions-be-private-in-c/
4. http://www.geeksforgeeks.org/what-happens-when-more-restrictive-access-is-given-in-a-derived-class-method-in-c/
5. http://www.geeksforgeeks.org/inline-virtual-function/
 

this Pointer

1.The ‘this’ pointer is passed as a hidden argument to all nonstatic member function calls and is available as a local variable within the body of all nonstatic functions.
2.‘this’ pointer is a constant pointer that holds the memory address of the current object.
3.‘this’ pointer is not available in static member functions as static member functions can be called without any object (with class name).
4. For a class X, the type of this pointer is ‘X* const’. Also, if a member function of X is declared as const, then the type of this pointer is ‘const X *const’.
5.  The type of this depends upon function declaration. If the member function of a class X is declared const, the type of this is const X* , if the member function is declared volatile, the type of this is volatile X* , and if the member function is declared const volatile, the type of this is const volatile X*

References:
1. http://www.geeksforgeeks.org/this-pointer-in-c/

dynamic_cast in C++


  • dynamic_cast< > is used to cast one polymorphic type to another type within its
    inheritance chain
  • dynamic_cast< > performs a safe “downcast”
  • dynamic_cast< > operations must be used on polymorphic pointers or references only.
  • An incompatible pointer cast returns NULL. 
  • An incompatible reference cast throws a bad_cast exception.
  • If you use dynamic_cast<> in the wrong place, you will get a compiler error.
  • You cannot dynamic_cast<> a void *.
  • You cannot dynamic_cast<> any nonpolymorphic type.
  • If you have a non-polymorphic class hierarchy, use static_cast<>.
  •  #include <iostream>

    class Base
    {
    public:
        Base() { }
        virtual ~Base() { } //Virtual Destructor

        virtual void hello()
        {
            std::cout << "in Base";
        }
    };

    class Derived : public Base
    {
    public:
        void hello()
        {
            std::cout << "in Derived";
        }
    };

    int main()
    {
        Base* basePointer = new Derived();
        Derived* derivedPointer = NULL;

        //To find whether basePointer is pointing to Derived type of object
        derivedPointer = dynamic_cast<Derived*> ( basePointer );


        if ( derivedPointer != NULL )
        {
            std::cout << "basePointer is pointing to a Derived class object"; //Identified
        }
        else
        {
            std::cout << "basePointer is NOT pointing to a Derived class object";
        }

        //Requires virtual destructor
        delete basePointer;
        basePointer = NULL;

        return 0;
    }
  • RTTI (Run-time type information): Dynamically determining object's type.                       Two RTTI operations                                                                                                                              1. typeid() functions--- used for generic types                                                                   2. dynamic_cast ------- for polymorphic types                              
  • RTTI (Run-time type information) is available only for the classes which have at least one virtual function.  
  • For typeid(), always #include <typeinfo.h>.
  • typeid() resolves polymorphic types for objects only, not pointers.
  • dynamic_cast<>-ing works for pointers and references to polymorphic types, not object types
  • typeid call is the one place in C++ where you can dereference a nullpointer with well-defined behavior, which implies that it can throw an exception( std::bad_typeid exception).

Important Programming Syntax

1. Copy Constructor:
                                 Test(const Test &t) // class name Test
2.Assignment Operator
                Test& operator = (const Test &t) // class name Test

Friday, 11 July 2014

UML

1.Use case diagrams
  •  Determining the user requirements. New use cases often generate new requirements.
  • Communicating with clients. The simplicity of the diagram makes use case diagrams a good way for designers and developers to communicate with clients.
  • Generating test cases. Each scenario for the use case may suggest a suite of test cases.
2. Class diagrams:
  • Class diagrams are the backbone of Object Oriented methods. So they are used frequently.
  • Class diagrams can have a conceptual perspective and an implementation perspective.During the analysis draw the conceptual model and during implementation draw the implementation model.
3. Interaction diagrams (Sequence and/or Collaboration diagrams):
  • When you want to look at behavior of several objects within a single use case. If you want to look at a single object across multiple use cases then use statechart diagram as described below.
4. State chart diagrams:
  • Statechart diagrams are good at describing the behavior of an object across several use cases. But they are not good at describing the interaction or collaboration between many objects. Use interaction and/or activity diagrams in conjunction with the statechart diagram to communicate complex operations involving multi-threaded programs etc.
  •  Use it only for classes that have complex state changes and behavior. For example: the User Interface (UI) control objects, Objects shared by multi-threaded programs etc.
5. Activity diagram:
  • Activity and Statechart diagrams are generally useful to express complex operations.The great strength of activity diagrams is that they support and encourage parallel behavior. An activity and statechart diagrams are beneficial for workflow modeling with multi- threaded programming. 

Thursday, 10 July 2014

Interview Tips

1. Technical skills alone are not sufficient for you to perform well in your interviews and progress in your career.
2. Your technical skills must be complemented with business skills (i.e. knowledge/ understanding of the business, ability to communicate and interact effectively with the business users/customers, ability to look at things from the user’s perspective as opposed to only technology perspective, ability to persuade/convince business with alternative solutions, which can provide a win/win solution from users’ perspective as well as technology perspective), ability to communicate effectively with your fellow developers, immediate and senior management, ability to work in a team as well as independently, problem solving/analytical skills, organizational skills, ability to cope with difficult situations like stress due to work load, deadlines etc and manage or deal with difficult people, being a good listener with the right attitude.
3. If you have "I know it all attitude", it will adversely affect affect your ability to be a good listener, ability to look at things in a different perspective, ability to work well in a team and consequently your progression in your career.
4.Pick your recent projects and enthusiastically brief on it. Interviewer will be looking for how passionate
you are about your past experience and achievements. Also is imperative that during your briefing, you
demonstrate on a high level(without getting too technical) how you applied your skills and knowledge in some of the key areas like Design Patterns,Design issues,Performance issues, Multithreading etc.
5. 90% of the interview questions are asked based on your own resume. So in my view it is also very beneficial to mention how you demonstrated your knowledge/skills by stepping through a recent project on your resume.
6. The general rule for interviews is to use the STAR model.
  • S - Describe the situation you were in
  • T - Explain the task, providing enough info so that the interviewer understands the problem.
  • A - Describe the action you took to solve the problem.
  • R - What were the results of your actions
7.  What are your Strengths:

  • Taking initiatives and being pro-active: You can illustrate how you took initiative to fix a transactional issue, a performance problem or a memory leak problem.
  • Design skills: You can illustrate how you designed a particular application using OO concepts.
  • Problem solving skills: Explain how you will break a complex problem into more manageable sub-sections and then apply brain storming and analytical skills to solve the complex problem. Illustrate how you went about identifying a scalability issue or a memory leak problem.
  • Communication skills: Illustrate that you can communicate effectively with all the team members, business analysts, users, testers, stake holders etc.
  • Ability to work in a team environment as well as independently: Illustrate that you are technically sound to work independently as well as have the interpersonal skills to fit into any team environment.
  • Hard working, honest, and conscientious etc are the adjectives to describe you.

8. Weaknesses:

Select a trait and come up with a solution to overcome your weakness. Stay away from personal qualities and concentrate more on professional traits for example:

  • I pride myself on being an attention to detail guy but sometimes miss small details. So I am working on applying the 80/20 principle to manage time and details. Spend 80% of my effort and time on 20% of the tasks, which are critical and important to the task at hand.
  • Some times when there is a technical issue or a problem I tend to work continuously until I fix it without having a break. But what I have noticed and am trying to practice is that taking a break away from the problem and thinking outside the square will assist you in identifying the root cause of the problem sooner.

9. Where do you see yourself after 2-5 years
  • Next 2-3 years to become a senior developer or a team lead.
  • Next 3-5 years to become a solution designer or an architect.     

Singleton Pattern

1. A singleton is a class that can be instantiated only one time. Repeated calls always return the same instance. Ensures that a class has only one instance, and provide a global point of access.
2. 

Wednesday, 9 July 2014

OOPS

1. The Object Oriented Programming Languages directly represent the real life objects like Car,Account,Customer etc. The features of the OO programming languages like polymorphism, inheritance and encapsulation (PIE) make it powerful.
2. The key benefits of OOPS are:


  • Re-use of previous work: using implementation inheritance and object composition.
  • Real mapping to the problem domain: Objects map to real world and represent vehicles, customers, products etc: with encapsulation.
  • Modular Architecture: Objects, systems, frameworks etc are the building blocks of larger systems.

The increased quality and reduced development time are the by-products of the key benefits discussed above.
3. Inheritance("is-a) relationship is UniDirectional. Eg :  House is a Building but Building is not a house.
4. Composition is "has-a" relationship. Eg: House has a bathroom.
5. Problem with class inheritance is that the subclass becomes dependent on the parent class implementation.
This makes it harder to reuse the subclass, especially if part of the inherited implementation is no longer desirable and hence can break encapsulation. Also a change to a superclass can not only ripple down the inheritance hierarchy to subclasses, but can also ripple out to code that uses just the subclasses making the design fragile by tightly coupling the subclasses with the super class. But it is easier to change the interface/implementation of the composed class.
6. Encapsulation – refers to keeping all the related members (variables and methods) together in an object. Specifying member variables as private can hide the variables and methods. Objects should hide their inner workings from the outside view. Good encapsulation improves code modularity by preventing objects interacting with each other in an unexpected way, which in turn makes future development and refactoring efforts easy.

7. Abstract classes let you define some default behavior and force subclasses to provide any specific behavior.
8. Overloading deals with multiple methods in the same class with the same name but different method signatures. Overloading lets you define the same operation in different ways for different data.
9. Overriding deals with two methods, one in the parent class and the other one in the child class and has the same name and  signatures. Overriding lets you define the same operation in different ways for different object types.
10. Serialization is a process of reading or writing an object. It is a process of saving an object’s state to a sequence of bytes, as well as a process of rebuilding those bytes back into a live object at some future time.
common use of serialization is to use it to send an object over the network or if the state of an object needs to be persisted to a flat file or a database.
11. Polymorphism: The same message sent to different objects, results in behavior that is dependent on the nature of the object receiving the message.
12. Abstraction : is the process where ideas are distanced from the concrete implementation of the objects. The concrete implementation will change but the abstract layer will remain the same.
Let us look at an analogy:
When you drive your car you do not have to be concerned with the exact internal working of your car (unless you are a mechanic). What you are concerned with is interacting with your car via its interfaces like steering wheel, brake pedal, accelerator pedal etc. Over the years a car’s engine has improved a lot but its basic interface has not changed (i.e. you still use steering wheel, brake pedal, accelerator pedal etc to interact with your car). This means that the implementation has changed over the years but the interface remains the same. Hence the knowledge you have of your car is abstract.

13. Loose coupling: The process of making objects independent of each other rather than dependent of one another.Loosely coupled objects are easier to reuse and change.
14. A class which declares or inherits a virtual function is called a polymorphic class 


Monday, 7 July 2014

MultiThreading Basics

  1. A thread has its own program counter (PC), a register set, and a stack space. Threads are not independent of one other like processes as a result threads shares with other threads their code section, data section and OS resources like open files and signals.
  2.  In a multi-threaded application each thread will have its own stack but will share the same heap. This is why care should be taken in your code to avoid any concurrent access issues in the heap space. 
  3. The stack is thread-safe because each thread will have its own stack with say 1MB RAM allocated for each thread but the heap is not thread-safe unless guarded with synchronization through your code.
  4. A process is an execution of a program but a thread is a single execution sequence within the process. A process can contain multiple threads. A thread is sometimes called a lightweight process.
  5. Without synchronization, it is possible for one thread to modify a shared object while another thread is in the process of using or updating that object’s value. This often causes dirty data and leads to significant errors. The disadvantage of synchronization is that it can cause deadlocks when two threads are waiting on each other to do something. Also synchronized code has the overhead of acquiring lock, which can adversely affect the performance
  6. Synchronization Example: If you imagine an application in which one thread (the producer) writes data to a file while a second thread (the consumer) reads data from the same file. In this example the concurrent threads share the same resource file. Because these threads share the common resource file they should be synchronized. Also these two threads should communicate with each other because the consumer thread, which reads the file, should wait until the producer thread, which writes data to the file and notifies the consumer thread that it has completed its writing operation.
  7. Process-based multitasking handles the concurrent execution of programs. Thread-based multitasking deals with the concurrent execution of pieces of the single program.
  8. The principal advantage of multithreading is that it enables you to write very efficient programs because it lets you utilize the idle time that is present in most programs.If all shared data is read-only, there’s no problem, because the data read by one thread is unaffected by whether or not another thread is reading the same data. However, if data is shared between threads, and one or more threads start modifying the data, there’s a lot of potential for trouble. In this case, you must take care to ensure that everything works out OK. 
  9. Suppose you’re buying tickets to see a movie at the cinema. If it’s a big cinema, multiple cashiers will be taking money, so more than one person can buy tickets at the same time. If someone at another cashier’s desk is also buying tickets for the same movie as you are, which seats are available for you to choose from depends on whether the other person actually books first or you do. If there are only a few seats left, this difference can be quite crucial: it might literally be a race to see who gets the last tickets.This is an example of a race condition: which seats you get (or even whether you get tickets) depends on the relative ordering of the two purchases.
  10. Critical section is group of instructions/statements or region of code that need to be executed atomically, such as accessing a resource (file, input or output port, global data, etc.).
  11. A simple solution to critical section can be thought as shown below
    acquireLock();
    Process Critical Section
    releaseLock();
  12. A thread must acquire a lock prior to executing critical section.
  13. A reentrant function is one that can safely be executed in parallel by multiple threads of execution.
  14. A Reentrant Function shall satisfy the following conditions,
    • Should not call another non-reentrant function
    • Should not access static life time variables (static/extern)
    • Should not include self modifying code

  15. Every thread safe function is reentrant, but the converse need not be true. A thread safe function can be called from multiple threads even when the function accessing shared data.
  16. A mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It means there will be ownership associated with mutex, and only the owner can release the lock (mutex).
  17. Semaphore is signaling mechanism.
  18. It makes application more responsive as computations are done in different  thread.
  19. Multithreaded programming is also a useful paradigm for performing time-consuming operations without freezing the user interface of an application.
  20. Process-based multitasking handles the concurrent execution of programs. Thread-based multitasking deals with the concurrent execution of pieces of the same program.The principal advantage of multithreading is that it enables you to write very efficient programs because it lets you utilize the idle time that is present in most programs. 

Static and Dynamic Libraries

Static
Dynamic
Static libraries are compiled into the program itself.
Shared libraries are compiled separately and referenced by the program
Program Size increases 
Program size is smaller but shared libraries are required at the runtime.
Every program has its own static library
Shared library has only one copy and referenced by different programs

  • Libraries donot contain main method.

Saturday, 5 July 2014

Algorithms- Things to Remember

  1. Height of a node is number of edges on longest path from node to leaf.Height of leaf is 0.
  2. Depth of a node is number of edges from node to root of the tree. Depth of root is 0.           
  3.  Maximum number of edges that can exist in Directed Acyclic Graph is n(n-1)/2
  4.  Insertion into BST  takes O(nlogn) time.