Time Complexity

 

1. Time Complexity cheat sheet

2. What is Red black tree ?

3. What are uses of Red black tree ?

  • Most of the self-balancing BST library functions like map and set in C++ (OR TreeSet and TreeMap in Java) use Red-Black Tree.
  • It is used to implement CPU Scheduling Linux. Completely Fair Scheduler uses it.
  • Besides they are used in the K-mean clustering algorithm for reducing time complexity.
  • Moreover, MySQL also uses the Red-Black tree for indexes on tables.


6. Comparison of AVL and red black tree ?

  • The AVL tree and other self-balancing search trees like Red Black are useful to get all basic operations done in O(log n) time.
  • The AVL trees are more balanced compared to Red-Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred.
  • And if the insertions and deletions are less frequent and search is the more frequent operation, then AVL tree should be preferred over Red Black Tree.
    Since it is dangerous to use, what is its special case where this cast can be specials to use.

The C++ standard guarantees the following:

static_casting a pointer to and from void* preserves the address. That is, in the following, a, b and c all point to the same address:

int* a = new int();
void* b = static_cast<void*>(a);
int* c = static_cast<int*>(b);
reinterpret_cast only guarantees that if you cast a pointer to a different type, and then reinterpret_cast it back to the original type, you get the original value. So in the following:

int* a = new int();
void* b = reinterpret_cast<void*>(a);
int* c = reinterpret_cast<int*>(b);
a and c contain the same value, but the value of b is unspecified. (in practice it will typically contain the same address as a and c, but that's not specified in the standard, and it may not be true on machines with more complex memory systems.)

For casting to and from void*, static_cast should be preferred.

Casting can be done between two unrelated class, the below is the example.

#include <iostream>
using namespace std;
class A
{
public:
void fun()
{
cout<<"A::fun()"<<endl;
}
};

class B
{
public:
void fun()
{
cout<<"B::fun()"<<endl;
}
};

int main()
{
B *b = new B();
A *a = reinterpret_cast<A*>(b);
a->fun();
return 0;
}

Refer the youtube link




Comments

Post a Comment

Popular posts from this blog

Design Pattern and Architecture in C++

Image
 Design Pattern Singleton Pattern Factory Design Pattern Template Design Pattern Observer Design Pattern Observer code Example - easier one to refer Link Facade Design Pattern Command Pattern Object Pool design pattern Visitor pattern How to choose correct technology for your project ? What is Factory pattern ? It helps you to centralize the object creation process and by doing so it decouples concrete classes from your clients and you know with that you have a better architecture right now. Factory pattern uses inheritance for object creation. What is Abstract pattern ? Abstract pattern sits on the top of factory pattern and uses factory pattern to create objects. Abstract Factory patterns work around a super-factory which creates other factories. This factory is also called as factory of factories. This type of design pattern comes under creational pattern as this pattern provides one of the best ways to create an object. #include <iostream> using namespace std; class Butto...
Read more

Google Test (gtest) Notes

  A good unit test: Is able to be fully automated has full control over all the pieces running(Uses mocks or fakes to achieve this isolation when needed Can run in any order Runs fast Test a single logical concepts in system Is readable is maintainable Runs in memory(no DB or File access ) How to run it ? ccmake localmake /sdev/user/bin/run_ut Mock Objects Each unit test case test a single logical solution That is, test the behavior of a single function in a single scenario But many functions call other functions with their own complex behavior The complex behavior make it hard to test a single logical solution It is also difficult to get the called function to exhibit bad whether behavior So instead of calling the actual calling those other functions we call test doubles One particular kind of test double is mock What is Mock ? A Mock check that the double is called as expected It substitutes a behavior for the function that would be called EXPECT_CALL Mac...
Read more