Visual Studio Project Settings/What Macros are defined/ Where is my output/ What are my project configurations

What Macros are defined/ Where is my output/ What are my project configurations
- Click on Project -> Project Name Properties
- Configuration Properties
- General -> here you will define the output or out, intermediate directories.
- C/C++ -> preprocessor Here you can check the Preprocessors which are defined for your project
- Linker-> General Here you can check the output file name. e.g dll file location and its name. Out directory as I already told is defined in the general macro

What all happens when I press F5
- Go to Configuration properties -> Debugging
- Command will tell you what paths you are setting
- Command arguments what all program you wan to run and what are the arguments
- It can be python script you want to pick with some arguments

how to create a visual studio Normal C/CPP project

Create new Project

Then select Visual C++ -> General -> Empty Project

Reverse the Linked List in K pairs

Problem description and solution can be found at
http://geeksforgeeks.org/?p=8014

Main points here.

1)reverse the first K pairs by normal reverse technique.
2)one pointer will contain last element of the reversed list
3)special check for first time.. to change root and master prev node.
4) special check to end the list

Monolithic and microlithic kernel

http://welovec.blogspot.in/2011/04/difference-between-monolithic-and.html

Nothing to cram, funda is simple as their names. Mono means everthing in kernel space.
Micro means very minimal in kernel space.

Mono what goes into the kernel (kernel space)
Process management, memrory management, file system, i/o services etc. e.g Linux kernel;

Micro Kernels what goes into the kernel
very minimal support for the process management goes into the kernel, everything else all above mentioned things are implemented in user space.

These services in user space are called as servers. kernel communicates with them with message passing(IPC). e.g QNX





The main disdvantage of monolithic kernels is the dependency between system components - a bug might crash the entire system - and the fact that large kernels also

become difficult to mantain.

Other disadvantages are the kernel size, lack of extensibility and the bad maintainability. Bug-fixing or the addition of new features means a recompilation of the whole

ernel. This is time and resource consuming because the compilation of a new kernel can take severalhours and alot of memory. Everytime someone adds a new feature or

xes a bug, it means recompilation of the whole kernel.

Copy a linked list with next and arbit pointer

http://geeksforgeeks.org/?p=1155

Look at method Number 3.
The funda here is to insert new node in between the nodes of original ist in way like this

1-2-3-4-__

1-1-2-2-3-3-4-4__

The new node instered have random pointer as zero.

Now in second pass we will link the arb pointer as this

copyList->arbit = org->arb->next. this would work and we would reach to the replica of org node. as in our new node orgList next pointer is the node which will be our final node in the new list.


not in third pass. to modify correct the next pointer

like cop->next = copy->next->next
and org ->next = org->next->next.


set the last pointer of the org list to the zero.

Implement a stack where, getMinValue() operation is of O(1)

Main source of the article

http://www.rawkam.com/?p=1337

The problem statement is: Implement a stack where, getMinValue() operation is of O(1).

Solution :
1st Soultion : maintain two stacks. First stack is the normal one. Second stack top will always contain the minimum value at the point. So when ever you need min value simply take it form the second stack top element.

Push Operation
aprat from normal operation on first stack
Add the element to second stack if top most element of the second stack is less then the current element.

Pop Operation
First stack normal pop up will be done.
Check if the poped element is same as the top element in the second stack. then remove that element from the second stack as well.

Pros and Cons: Pros are all three operations ie. push pop and getMinValue are of O(1). But the flip side is that the it requires more space.


2nd Solution:
Mainin the pointer minPoiner, and you need to modify the pointer when doing Pop operation.in Pop operation may require traversal of the entire stack to find the next min value.

pros : NO extra space, but the Pop operation is O(n).



3rd solution :
Modify the stack node structure itself. add one field that points to the next min element.
Funda is like this. first each node will have an extra field called next min.
node {
next;
data;
nextMin;
}

Plus as usal there would be one pointer Min Pointer which will point to the current min value element.

Push operation
if current pusehed element is less then the earlier maintained min value. Definatly you need to modify the Min Pointer but you also need to do one more thing. like

top->nextMin = Old Min
Min = new min.

Pop Operation
Very simple if current poped node is the min node simply put the min node to top->next min node.


Please note that this can be little deseptive, as this nextMin we will not use for all the nodes.

Both push pop and get min are of order O(1)

Doubly Linked list using one Pointer

Problem : The question is to implement the doubly linked list. But you should maintain only one pointer per node.

Solution :
Remember how to swap the two numbers without using any third variable. XOR funda.

Same thing is applied here.
Suppose list is as below
A - B -C

What we will do is, we will main the address difference of the previous and next node in the current node in the link field.

e.g in case of B

node->link = A XOR C.

so when you want to traverse from left to right, you need left pointer .

and can find Address of c as A XOR node->link == A XOR A XOR C =c

similarly you can go back to the right to left, only thing is you need address of the right node here to traverse.


some additional info
1) You need to maintain two extra node here. start and end. start -> left = NULL
and similarly end -> right = NULL

2) you need additional node info here to travel to next node. e.g need address of A if you want to go from B to C

reference link is at

http://www.linuxjournal.com/article/6828?page=0,0

Find repeated array

Problem: You have any array n+2. It has elements from 1 to n and two other elements are repeated. We need to find the repeated elements. Solution should not more then O(n) complexity

Hint: If you use the array value as the index to jum to some location. So the location where you are reaching after the jump should be visited only once. If you reach there more then one way, it means the key by which you are coming here already used.

Largest Sum Sub array

Problem statement : You have an arrya having both postive and negative number. You have to find a sequence having maximum sum.
Program should be not more then O(n) complexity

Hint: Though problem looks complex. Its logic lies if any time your temp Sum becomes less then 0, it will not contribute to the MaxSum

Difference between RTOS and GPOS (General Purpose Operating Systems)

Google directs to this page a lot. So I am rewriting this post so that most of you can benefit. I had read a lots of articles to compose this material. There is not short-cut for a good answer. If you want to really know the topic spend 10-20 mins to read and understand it. I have tried to go from layman terms to more technical stuff.

Are ROTSs really fast ?

Many Embedded interviewer ask this question. And most naive answer you could come up with is 'ROTS are fast'.
Well, never use these words. More appropriate answer would be ROTS are deterministic. RTOS gauratee you that particular operation would complete at the worst this much time. This is the very basic criteria of being a RTOS.



Why even bother for RTOS, have better hardware and use GPOS to gain Speed/determinism.
Its all about money, if you can save even 25 cents on one embedded device hardware, and embedded devices are sold in millions of units (say memory card) Companies can make millions of dollars.

Another  major criteria is QoS(Quality of service) If you are playing on video and video stream is not in order, the whole purpose of having video facility is spoiled. RTOS has QoS assurance.

Properties and services of RTOS
a) Task Scheduling
GPOS, the scheduler uses a fairness policy to dispatch threads and processes onto the CPU. This ensurers the fairness with which programs are executed. But it gives no gaurntee that the high priroirty thread will be given preference to the lower priority one.
In some cases the OS may decay the priority (or dyanamically adjust)of the thread in order to achive fairness.



b)Dispatch Latency :
It does not have any upper bound. In General, the more the number of threads the more time GPOS takes to schedule and start executing the the thread . In highly time constraints RTOS system this delay could be devise.In RTOS however if high priority process is ready to run it will start executing 'very soon'. All it tells is, the Algorithms of ROTS kernel should be deterministic and should be able to perform even if no of resources are more.

c) Preemptive Kernel
This is one big difference. For most of the GPOS, the OS kernel is not preemptive. Consequently, a high-priority user thread can never preempt a kernel call, but must wait for the entier call to complete, even if the call was invoked by the lowerest priority proecess.

In ROTS other hand, kernel opreations are preemptive. It means low priority task will be preemted even if its executing any system call.
There would be some delays some times, but a carefully designed RTOS will have those delays very small. And one more important point, even for these delatils the upper bound of delay time would be well defined.

To achieve this goal, the RTOS kernel must be simple and as elegant as possible.
Only services with a short execution path should be included in the kernel itself. Any operations that require significant work (for instance, process loading) must be assigned to external processes or threads.Such an approach helps ensure that there is an upper bound on the longest nonpreemptible code path through the kernel.In a few

GPOSs, such as Linux 2.6, some degree of preemptibility has been added to the kernel. However, the intervals during which preemption may not occur are still much longer than those in a typical RTOS,  the length of any such preemption interval will depend on the longest critical section of any modules incorporated into the kernel (for example,networking and file systems). Moreover, a preemptive kernel does not address other conditions that can impose unbounded latencies, such as the loss of priority information that occurs when a client invokes a driver or other system service

d) Priority Inversion Problem
This is problem which can arrive in preemptive priority based scheduling. RTOS must handle this. Google it, Mars Path finder robot has this problem.


How RTOS are deterministic?

As doctor in movie 'I, Robot' says to Will Smith "Now, that's the right question"

Preemption is very important criteria which I explained earlier, Kernel should have enough preemptive points from where it can return. GPOS are usually not preemptive. 

So from where other Latency Comes?

a) Non preemptive Kernel Latency

This is the way a thread/task executes


Low priority thread starts ---- calls a system call.
In between a high priority thread comes,
If your kernel is non-preemptive until system call finishes your high priority thread would not get to execute. So preemptive kernel is must. If kernel is preemptive you can determine the worst time where High priority thread would start execution.

b) Kernel Latency

This is how embedded system works. 'Something' in embedded system wants some task to be done. This something could be a 'sensor input' or a key press.Normally this 'something' is hardwired to processor with a line.
It means, say temperature sensor says, initiate the cooling process. It dump a signal to the processor. Normally, in OS terminology, we call this kind of signals interrupt.
After a interrupt occurs following action are taken by OS

a) Interrupt intiated
b) A interrupt handler is found
c) Interrupt is handled
d) Makes the task runnable
e)Task is scheduled
f) Task, yeah dears actual RTOS task runs here.

So here would be total kernel latency = Interrupt Latency(b) + handler duration(c) + Scheduler latency(d) +  Scheduler duration(e)

All above mentioned latencies should be deterministic and minimal

i) Interrupt Handler Latency : How fast is your interrupt handler.
Fast Interrupt Handler : In this type of interrupt handling all other interrupts are masked. This may cause jitters in RTOS env. Normally you can miss interrupts during this kind. So its kind of NO for RTOS.
Regular Interrupt Handling: Disable only current interrupt. That's kind of recommended approach.
To sum up interrupt latency comes from
1. Disabling of interrupts (spin lock etc)
2. Bad driver using Fast interrupt mode
3. Process the high priority interrupt first. i.e interrupt handling preemption. 
So RTOS interrupt handling mechanism should take of above points.

ii) Scheduler Duration
Scheduler should be able to pick and start executing a task in O(1) kind of mechanism. Many schedular algorithms are O(n)
Virtual memory is also kind of no to RTOS. Creation of new address space for each task and managing it takes time.
Memory allocation schemes : SLOB/SLOB allocator ???? :-). Its a different topic alltogether.



Please Note:
I am also scribing about RTOS called MQX. Those posts will tell more detailed concepts of RTOS.