Saturday, July 28, 2012

Programming Puzzles

The following links are useful for programming teasers / simple puzzles.

http://www.coderanch.com/forums/f-71/Programming
http://www.geekinterview.com/talk/brainteasers/

RTOS specifc Questions

RTOS vs GPOS 
 
GPOS:- no time boundation,task hasnt got any time limit to
finish work. 
------------------- 
An RTOS is a special case of GPOS. 
1. In RTOS every task must have a priority.
2. Pre-emption is a must feature.
3. Priority Inheritance is must otherwise priority 
inversion may cause unbounded wait.
------------------- 
RTOS:- time boundation, task has to complete work within
given time frame. For this preemtive scheduling is must.OS uses Round
Robin scheduling. 
------------------- 
GPOS USES A MONOLITHIC ARCHITECTURE WHILE 
RTOS USES A FLAT MEMORY ARCHITECTURE.  
 
 

BIT Manipulation puzzles

Convert number 2 --> 37 without using any other operator but bitwise ? 

Solution:
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
   int x = 2;
    printf("X before :%d\n",x);
    x = (x<<x<<x) |  x<<!!x | !!x ;
    printf("X After  :%d\n",x);
     getchar();
     return(0);

XOR Linked List

Write a memory efficient Doubly Linked List with the following structure

typedef struct ListNode
{     int data;
       struct ListNode *ptrdiff;
};

where ptrdiff pointer contains the difference between the pointer to the next node and the pointer to previous node.Pointer difference is calculated using XOR operation

ptrdiff= pointer to previous node  XOR  pointer to next node

XOR List Representation:
Let us call the address variable in XOR representation npx (XOR of next and previous)
Node A:
npx = 0 XOR add(B) // bitwise XOR of zero and address of B
Node B:
npx = add(A) XOR add(C) // bitwise XOR of address of A and address of C
Node C:
npx = add(B) XOR add(D) // bitwise XOR of address of B and address of D
Node D:
npx = add(C) XOR 0 // bitwise XOR of address of C and 0

Traversal of XOR Linked List:
We can traverse the XOR list in both forward and reverse direction. While traversing the list we need to remember the address of the previously accessed node in order to calculate the next node’s address. For example when we are at node C, we must have address of B. XOR of add(B) and npx of C gives us the add(D). The reason is simple: npx(C) is “add(B) XOR add(D)”. If we do xor of npx(C) with add(B), we get the result as “add(B) XOR add(D) XOR add(B)” which is “add(D) XOR 0″ which is “add(D)”. So we have the address of next node. Similarly we can traverse the list in backward direction.

Useful Links:
http://en.wikipedia.org/wiki/XOR_linked_list
http://www.linuxjournal.com/article/6828?page=0,0
http://www.geeksforgeeks.org/archives/12367

OS Boot Sequence

CPU cycle

what do you mean by CPU cycle and why is it important ?

http://en.wikipedia.org/wiki/Instruction_cycle

Implement malloc

Scan for a bit pattern in a stream of bits

We need to scan for a 16 bit word in a bit stream. It is not guaranteed to be aligned on byte or word boundaries.
There are various brute force methods; using tables and/or shifts.But what is the best way to do this ?

Qualcomm Interview Questions & Tips

The following things are important for Interviews in Qualcomm

1.Why do you want to switch company ?
Be specific in your answer.

2.Resume
Know each and everything about your resume and projects.

3.What was the most difficult technical issue that you had and how did you solve it?

4.The following topics are very important

----String Manipulation
----BIT manipulation
----C Concepts

Thursday, July 26, 2012

Insert a substring in a string

C program to insert substring into a string: This code inserts the target string into the source string.

For example if the source string is "c programming" and target string is " is amazing" (please note there is space at beginning) and if we add target string to source string at position 14 then we obtain the string "c programming is amazing". In our c code we will make a function which perform the desired task and we pass three arguments to it the source string, target string and position. You can insert the string at any valid position.

 Code:
#include <string.h>
#include <stdlib.h>
#include <iostream>

void insert_substring(char*, char*, int);
char* substring(char*, int, int);

main()
{
   char text[100], substring[100];
   int position;

   printf("Enter some text\n");
   gets(text);

   printf("Enter the string to insert\n");
   gets(substring);

   printf("Enter the position to insert\n");
   scanf("%d", &position);

   insert_substring(text, substring, position);

   printf("%s\n",text);
   system("pause");

   return 0;
}

void insert_substring(char *a, char *b, int position)
{
   char *f, *e;
   int length;

   length = strlen(a);

   f = substring(a, 1, position - 1 );     
   e = substring(a, position, length-position+1);

   strcpy(a, "");
   strcat(a, f);
   free(f);
   strcat(a, b);
   strcat(a, e);
   free(e);
}

char *substring(char *string, int position, int length)
{
   char *pointer;
   int c;

   pointer =(char*) malloc(length+1);

   if( pointer == NULL )
       exit(EXIT_FAILURE);

   for( c = 0 ; c < length ; c++ )
      *(pointer+c) = *((string+position-1)+c);      

   *(pointer+c) = '\0';

   return pointer;
}

Generate Random Numbers

#include <stdio.h>
#include <stdlib.h>
 
int main() {
  int c, n;
 
  printf("Ten random numbers in [1,100]\n");
 
  for (c = 1; c <= 10; c++) {
    n = rand()%100 + 1;
    printf("%d\n", n);
  }
 
  return 0;
} 

Find parity of an unsigned integer

Parity: Parity of a number refers to whether it contains an odd or even number of 1-bits. The number has “odd parity”, if it contains odd number of 1-bits and is “even parity” if it contains even number of 1-bits.

Main idea of the below solution is – Loop while n is not 0 and in loop unset one of the set bits and invert parity.
Algorithm: getParity(n)
1. Initialize parity = 0
2. Loop while n != 0      
      a. Invert parity 
             parity = !parity
      b. Unset rightmost set bit
             n = n & (n-1)
3. return parity

Example:
 Initialize: n = 13 (1101)   parity = 0

n = 13 & 12  = 12 (1100)   parity = 1
n = 12 & 11 = 8  (1000)   parity = 0
n = 8 & 7 = 0  (0000)    parity = 1
 
Code:
# include <stdio.h>
# define  bool int
bool getParity(unsigned int n)
{
    bool parity = 0;
    while (n)
    {
        parity = !parity;
        n      = n & (n - 1);
    }       
    return parity;
}
int main()
{
    unsigned int n = 7;
    printf("Parity of no %d = %s",  n,
             (getParity(n)? "odd": "even"));
     
    getchar();
    return 0;
}
Above solution can be optimized by using lookup table.
Time Complexity: The time taken by above algorithm is proportional to the number of bits set. Worst case complexity is O(Logn).
Uses: Parity is used in error detection and cryptography.

Representation of things in memory

How does the computer store things in Memory

You probably know that everything on a computer is stored as strings of bits (binary digits; you can think of them as lots of little on-off switches). Here I'll explain how those bits are used to represent the letters and numbers that your computer is crunching.

Word Size :-
Before we can go into this, you need to understand about the word size of your computer. The word size is the computer's preferred size for moving units of information around; technically it's the width of your processor's registers, which are the holding areas your processor uses to do arithmetic and logical calculations. When people write about computers having bit sizes (calling them, say, "32-bit" or "64-bit" computers), this is what they mean.

The computer views your memory as a sequence of words numbered from zero up to some large value dependent on your memory size. That value is limited by your word size, which is why programs on older machines like 286s had to go through painful contortions to address large amounts of memory.

Numbers

Integer numbers are represented as either words or pairs of words, depending on your processor's word size. One 64-bit machine word is the most common integer representation.
Integer arithmetic is close to but not actually mathematical base-two. The low-order bit is 1, next 2, then 4 and so forth as in pure binary. But signed numbers are represented in twos-complement notation. The highest-order bit is a sign bit which makes the quantity negative, and every negative number can be obtained from the corresponding positive value by inverting all the bits and adding one. This is why integers on a 64-bit machine have the range -263 to 263 - 1. That 64th bit is being used for sign; 0 means a positive number or zero, 1 a negative number.
Some computer languages give you access to unsigned arithmetic which is straight base 2 with zero and positive numbers only.
Most processors and some languages can do operations in floating-point numbers (this capability is built into all recent processor chips). Floating-point numbers give you a much wider range of values than integers and let you express fractions. The ways in which this is done vary and are rather too complicated to discuss in detail here, but the general idea is much like so-called ‘scientific notation’, where one might write (say) 1.234 * 1023; the encoding of the number is split into a mantissa (1.234) and the exponent part (23) for the power-of-ten multiplier (which means the number multiplied out would have 20 zeros on it, 23 minus the three decimal places).

Characters

Characters are normally represented as strings of seven bits each in an encoding called ASCII (American Standard Code for Information Interchange). On modern machines, each of the 128 ASCII characters is the low seven bits of an octet or 8-bit byte; octets are packed into memory words so that (for example) a six-character string only takes up two memory words. For an ASCII code chart, type ‘man 7 ascii’ at your Unix prompt.
The preceding paragraph was misleading in two ways. The minor one is that the term ‘octet’ is formally correct but seldom actually used; most people refer to an octet as byte and expect bytes to be eight bits long. Strictly speaking, the term ‘byte’ is more general; there used to be, for example, 36-bit machines with 9-bit bytes (though there probably never will be again).
The major one is that not all the world uses ASCII. In fact, much of the world can't — ASCII, while fine for American English, lacks many accented and other special characters needed by users of other languages. Even British English has trouble with the lack of a pound-currency sign.
There have been several attempts to fix this problem. All use the extra high bit that ASCII doesn't, making it the low half of a 256-character set. The most widely-used of these is the so-called ‘Latin-1’ character set (more formally called ISO 8859-1). This is the default character set for Linux, older versions of HTML, and X. Microsoft Windows uses a mutant version of Latin-1 that adds a bunch of characters such as right and left double quotes in places proper Latin-1 leaves unassigned for historical reasons.
Latin-1 handles western European languages, including English, French, German, Spanish, Italian, Dutch, Norwegian, Swedish, Danish, and Icelandic. However, this isn't good enough either, and as a result there is a whole series of Latin-2 through -9 character sets to handle things like Greek, Arabic, Hebrew, Esperanto, and Serbo-Croatian.
The ultimate solution is a huge standard called Unicode (and its identical twin ISO/IEC 10646-1:1993). Unicode is identical to Latin-1 in its lowest 256 slots. Above these in 16-bit space it includes Greek, Cyrillic, Armenian, Hebrew, Arabic, Devanagari, Bengali, Gurmukhi, Gujarati, Oriya, Tamil, Telugu, Kannada, Malayalam, Thai, Lao, Georgian, Tibetan, Japanese Kana, the complete set of modern Korean Hangul, and a unified set of Chinese/Japanese/Korean (CJK) ideographs.
Recent versions of Linux use an encoding of Unicode called UTF-8. In UTF, characters 0-127 are ASCII. Characters 128-255 are used only in sequences of 2 through 4 bytes that identify non-ASCII characters.

Sum digits of a number

1. Iterative:
The function has three lines instead of one line but it calculates sum in one line. It can be made one line function if we pass pointer to sum.
# include<stdio.h>
int main()
{
  int n = 687;
  printf(" %d ", getSum(n));
 
  getchar();
  return 0;
}
 
/* Function to get sum of digits */
int getSum(int n)
{
    int sum;
    /*Single line that calculates sum*/
    for(sum=0; n > 0; sum+=n%10,n/=10);
    return sum;
}

2. Recursive
Thanks to ayesha for providing the below recursive solution.
int sumDigits(int no)
{
  return no == 0 ? 0 : no%10 + sumDigits(no/10) ;
}
 
int main(void)
{
  printf("%d", sumDigits(1352));
  getchar();
  return 0;
}

Prime Numbers

Find all the prime numbers less than or equal to a given integer n

 
Prime Number Generation upto a specific count:
 
#include<stdio.h>
 
main()
{
   int n, i = 3, count, c;
 
   printf("Enter the number of prime numbers required\n");
   scanf("%d",&n);
 
   if ( n >= 1 )
   {
      printf("First %d prime numbers are :\n",n);
      printf("2\n");
   }
 
   for ( count = 2 ; count <= n ;  )
   {
      for ( c = 2 ; c <= i - 1 ; c++ )
      {
         if ( i%c == 0 )
            break;
      }
      if ( c == i )
      {
         printf("%d\n",i);
         count++;
      }
      i++;
   }         
 
   return 0;
}
 
There are many logic to check prime numbers, one given below is more 
efficient then above method.
for ( c = 2 ; c 
//only checking from 2 to square root of number is sufficient. 

Program for Prime Number or not:

#include<stdio.h>
main()
{
   int n, c = 2;
 
   printf("Enter a number to check if it is prime\n");
   scanf("%d",&n);
 
   for ( c = 2 ; c <= n - 1 ; c++ )
   {
      if ( n%c == 0 )
      {
         printf("%d is not prime.\n", n);
  break;
      }
   }
   if ( c == n )
      printf("%d is prime.\n", n);
 
   return 0;
}
 
Prime Numbers Less than a number:
 
#include <stdio.h>
#include <iostream>
int main()
{
   int n,i=1,j,c;
   printf("Enter Number Of Terms");
   printf("Prime Numbers Are Following\n");
   scanf("%d",&n);
   while(i<=n)
   {
      c=0;
      for(j=1;j<=i;j++)
      {
              if(i%j==0)
        c++;
       }
           if(c==2)
           printf("%d\n",i);
           i++;
        }
        system("pause");
        return 0;
}



 
Efficient Method for Prime Numbers:

We can use Sieve of Eratosthenes method:
  • Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
  • Initially, let p equal 2, the first prime number.
  • Strike from the list all multiples of p less than or equal to n. (2p, 3p, 4p, etc.)
  • Find the first number remaining on the list after p (this number is the next prime); replace p with this number.
  • Repeat steps 3 and 4 until p2 is greater than n.
  • All the remaining numbers in the list are prime.

    void GeneratePrimes(int N)
    { bitset<1000> b;
    for(int i = 2; i < N; i )
         { if(!b[i])
                  { //Mark all multiples of i to 1 as there are not prime numbers int k = 2;
                  while((i * k) < N){ b[i * k] = 1; k ; }
         }
      for(int i = 2; i < N; i )
             { if(!b[i]) cout << i << " "; }
    }
 
Links:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Division without using '/' operator

Perform divide operation without using '/' operator and give the most efficient solution.

Strategy:
Algorithm to divide two numbers using shifting the binary number to the left.

Let us divide x by y
  int by2(int x): x << 1 // do left shift of x to divide it by 2

divide(x,y):
    if(x=0):
       return (q,r)=(0,0)

    (q,r) = divide (by2(x),y)
    q=2*q, r=2*r

    if x is odd 
       r=r+1

    if(r>=y)
       r=r-y, q=q+1

    return (q,r)
by2(x) shift binary x to the left by 1 bit and as a result divides the number by two. At the same time q and r is multiplied by 2 because we are effectively dividing x by 2. If x is odd then we need to add 1 to the remainder.
Over the period of time the remainder will grow and when it̢۪s value crosses y we need to add 1 to the quotient because in effect quotient has increased by 1.

Algorithms Learning / Interview Questions

The following Links are very useful for learning and preparing for interviews regarding Algos.

Learning---------
http://www.cs.berkeley.edu/~vazirani/algorithms.html

Interviews Specific-----------
Algo Geeks

Subsets without consecutive elements

Consider a set S of the first 10 natural numbers.Find the number of subsets that do not contain consecutive elements.

Strategy:
The question is based on pure calculation and some combinatorics.
Subsets of length 0 = 1
Subsets of length 1 = 10
These two cases are straight forward.
Subsets of length 2 =
number of ways we can pick two numbers out of 10 - number of ways in which we can pick two adjacent numbers
10 C 2 - 9
45-9=36
Subsets of length 3 =
the number of ways we can pick 3 numbers out of 10 - number of ways we can pick 3 numbers having 2 adjacent numbers - number of combinations where all 3 are adjacent i.e.
10 C 3 - 56 - 8
the latter case is simple but think over why number of combinations that have two adjacent numbers are 56, there are two special cases to be considered, one where adjacent numbers are in between like 5,6 and the other where they are at boundary i.e. 0,1
similarly
Subsets of length 4 = 35
Subsets of length 5 = 6
We cannot go beyond this because then we will have atleast 2 adjacent numbers.
The total comes out to be 144

OS Interview Questions

I will update questions and links to go through OS specific interview questions in this post.

Wednesday, July 25, 2012

IPC Mechanisms III --Signals & Pipes

Discuss Signals and Pipes as IPC methods

Useful Links:
http://tldp.org/LDP/tlk/ipc/ipc.html

Deadlock

Discuss Deadlock in OS.


Deadlock Definition

A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause (including itself).
Waiting for an event could be:
  • waiting for access to a critical section
  • waiting for a resource Note that it is usually a non-preemptable (resource). pre-emptable resources can be yanked away and given to another.

Conditions for Deadlock


  • Mutual exclusion: resources cannot be shared.
  • Hold and wait: processes request resources incrementally, and hold on to what they've got.
  • No preemption: resources cannot be forcibly taken from processes.
  • Circular wait: circular chain of waiting, in which each process is waiting for a resource held by the next process in the chain.

Strategies for dealing with Deadlock


  • ignore the problem altogether ie. ostrich algorithm it may occur very infrequently, cost of detection/prevention etc may not be worth it.
  • detection and recovery
  • avoidance by careful resource allocation
  • prevention by structurally negating one of the four necessary conditions.

Deadlock Prevention


Difference from avoidance is that here, the system itself is build in such a way that there are no deadlocks.
Make sure atleast one of the 4 deadlock conditions is never satisfied.
This may however be even more conservative than deadlock avoidance strategy.
  • Attacking Mutex condition
    • never grant exclusive access. but this may not be possible for several resources.
  • Attacking preemption
    • not something you want to do.
  • Attacking hold and wait condition
    • make a process hold at the most 1 resource at a time.
    • make all the requests at the beginning. All or nothing policy. If you feel, retry. eg. 2-phase locking
  • Attacking circular wait
    • Order all the resources.
    • Make sure that the requests are issued in the correct order so that there are no cycles present in the resource graph.

      Resources numbered 1 ... n. Resources can be requested only in increasing order. ie. you cannot request a resource whose no is less than any you may be holding.

    Deadlock Avoidance


    Avoid actions that may lead to a deadlock.
    Think of it as a state machine moving from 1 state to another as each instruction is executed.

    Safe State

    Safe state is one where
    • It is not a deadlocked state
    • There is some sequence by which all requests can be satisfied.
    To avoid deadlocks, we try to make only those transitions that will take you from one safe state to another. We avoid transitions to unsafe state (a state that is not deadlocked, and is not safe)
     eg.
    Total # of instances of resource = 12 
    (Max, Allocated, Still Needs)
    P0 (10, 5, 5) P1 (4, 2, 2) P2 (9, 2, 7)     Free = 3    - Safe
    The sequence  is a reducible sequence
    the first state is safe.
    
    What if P2 requests 1 more and is allocated 1 more instance?
    - results in Unsafe state
    
    So do not allow P2's request to be satisfied.
     
    

    Banker's Algorithm for Deadlock Avoidance

    When a request is made, check to see if after the request is satisfied, there is a (atleast one!) sequence of moves that can satisfy all the requests. ie. the new state is safe. If so, satisfy the request, else make the request wait.

    How do you find if a state is safe


    
        n process and m resources
        Max[n * m]
        Allocated[n * m]
        Still_Needs[n * m]
        Available[m]
        Temp[m]
        Done[n]
    
    while () {
       Temp[j]=Available[j] for all j
       Find an i such that 
           a) Done[i] = False
           b) Still_Needs[i,j] <= Temp[j]
       if so {
           Temp[j] += Allocated[i,j] for all j
           Done[i] = TRUE}
       }
       else if Done[i] = TRUE for all i then state is safe
       else state is unsafe
    }
    

    Detection and Recovery


    Is there a deadlock currently?
    One resource of each type (1 printer, 1 plotter, 1 terminal etc.)
    • check if there is a cycle in the resource graph. for each node N in the graph do DFS (depth first search) of the graph with N as the root In the DFS if you come back to a node already traversed, then there is a cycle. }
    Multiple resources of each type
    • m resources, n processes
    • Max resources in existence = [E1, E2, E3, .... Em]
    • Current Allocation = C1-n,1-m
    • Resources currently Available = [A1, A2, ... Am]
    • Request matrix = R1-n,1-m
    • Invariant = Sum(Cij) + Aj = Ej
    • Define A <= B for 2 vectors, A and B, if Ai <= Bi for all i
    • Overview of deadlock detection algorithm,

      Check R matrix, and find a row i such at Ri < A.
      If such a process is found, add Ci to A and remove process i from the system.
      Keep doing this till either you have removed all processes, or you cannot remove any other process.
      Whatever is remaining is deadlocked.


      Basic idea, is that there is atleast 1 execution which will undeadlock the system

    Recovery


    • through preemption
    • rollback
      • keep checkpointing periodically
      • when a deadlock is detected, see which resource is needed.
      • Take away the resource from the process currently having it.
      • Later on, you can restart this process from a check pointed state where it may need to reacquire the resource.
    • killing processes
      • where possible, kill a process that can be rerun from the beginning without illeffects

Useful Links:
http://www.personal.kent.edu/~rmuhamma/OpSystems/Myos/deadlockIntro.htm
cs.gmu.edu/~menasce/cs471/slides/ch8.pdf
https://www.cs.drexel.edu/~bmitchel/course/mcs720/deadlock.pdf

Kernel Types

Discuss about the following types of kernels used for different operating system architechtures

1.Monolithic Kernel

2.Micro Kernel

3.Exo Kernel

Useful Links:

http://en.wikipedia.org/wiki/Monolithic_kernel

Monday, July 23, 2012

Print the integers that are greater than the average of that array

Given an array of integers print the integers that are greater than the average of that array

DNA Sequence Pattern Match/ String Search Problem

The DNA double helix consists of a long strand of four bases: adenine (abbreviated A), cytosine (C), guanine (G) and thymine (T). Thus, it can be represented as a long string containing the characters A, C, G, and T. The field of bio-informatics involves storing and searching of DNA sequence data. What is a good data structure to facilitate storage and string match/search operation on this kind of data? Write a class that stores the DNA sequence and implement a method which takes another DNA sub-sequence and returns the position of this sub-sequence in the first DNA sequence.

There are several linear time string matching algorithms. See http://en.wikipedia.org/wiki/String_searching_algorithm for a list of such algorithms.
Often a data structure called Suffix Tree or PAT tree is used in DNA sequencing applications in the field of Bio-informatics. A Suffix tree data structure facilitates string match/search in O(m) complexity, where m is the length of the sub-string. It takes an initial O(n) time required to build the suffix tree.
One concern with suffix tree is the high amount of space/memory needed. But, with a small alphabet ( only 4 characters in the DNA search problem ) , its not too bad. More over, there are some advanced techniques that can be used to further reduce the storage requirements.
A thorough treatment of suffix trees can be found here

Store a stream of numbers along with the counts

Given a stream of numbers, suggest a data structure to store the numbers in the stream along with their number of occurrences.

Solution: Before solving any problem make sure you lay down all the assumptions you are making and validate them with the interviewer.

Assumptions here:
  • The numbers are 32 bit integers.
  • The size of the set (cardinality) is very small compared to the possible number of integers (lets say 100 numbers)
  • Design for faster lookup
Since the size of the set is small, a data structure like an array of integers 2^32 in size will be a waste of space, even though the insert and lookup is going to be O(1). A hashtable would have a similar issue. A linked list would solve the memory issue by storing only the numbers that were present in the set but the look up suffers ( O(n) ). We would like the look up to be better than O(n).

So we've looked at an array, linked list, hashtable and none seem to solve it. Linked list looked promising but look up was O(n). Can we improve the lookup in a linked list? First of all, whats better than O(n)? O(log n), right? What data structure does that remind you of? A Binary Search Tree!!

Lets explore if we can utilize a Binary Search Tree here. So, if we started inserting numbers in a Binary Search Tree, each insertion would cost us O(log n). There are n number of insertions, so inserting all the numbers is going to be O(n log n). When we insert each number we also store the count at the node. So if a number is inserted for the first time we create a node in the tree and store the number itself and also the count (1 for the 1st occurrence). Any subsequent occurrence will not create a new node. Instead, we'll find the corresponding node and just update the count. So by the time we are done processing all the numbers we'll have a nice binary search tree with all the numbers and their occurrences.

Now the comes the look up part. Look up in a Binary Search Tree is O(log n). Any time we are presented a number and asked for the number of occurrences we can look up (or not ) the number and get its count.

If we were to design for faster insert we'd be better off using an unsorted linked list. Insert would have been O(1) (just insert at the end) and look up would be O(n). So for a small n this wouldn't be terribly bad.

Note: There is another data structure called the skip list which is a layered linked list type data structure which has O(log n) look up and insert. The linked list in the skip list is a sorted list and that would make our insert O(n log n).

Question 2:
Find Duplicates in a million number

Sunday, July 15, 2012

Union and Intersection of two Linked Lists

Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elements in output lists doesn't matter.
Example:
Input:
   List1: 10->15->4->20
   lsit2:  8->4->2->10
Output:
   Intersection List: 4->10
   Union List: 2->8->20->4->15->10
http://www.geeksforgeeks.org/union-and-intersection-of-two-linked-lists/

Intersection:  Using Hashset
But of course you can do much better.
Now, if you have a HashSet (or other near-O(1)) data structure available then this is what you can do:
Iterate over one list. Add each element to the set. Iterate over the second list. If the element is in the set then add it to the result list.
Solution: O(n)

Intersection of two sorted Lists:
http://www.geeksforgeeks.org/intersection-of-two-sorted-linked-lists/

List getIntersection(int[] a, int[] b){
    int apos = 0, bpos = 0
    List intersection
    while apos < a.length && bpos < b.length:
        if a[apos] == b[bpos]:
            intersection.add(a[apos])
            apos++, bpos++
        else:
            if a[apos] < b[bpos]:
                apos++
            else:
                bpos++
    return intersection 
}

Efficiency is O(m + n).

C Operator Questions

#include<stdio.h>
int main(){
    float a=0.7;d
    if(a<0.7){
         printf("C");
    }
    else{
         printf("C++");
    }
    return 0;
}

0.7 is double constant (Default). Its binary value is written in 64 bit.

Binary value of 0.7 = (0.1011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 )

Now here variable a is a floating point variable while 0.7 is double constant. So variable a will contain only 32 bit value i.e.
a = 0.1011 0011 0011 0011 0011 0011 0011 0011 while
0.7 = 0.1011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011....
It is obvious a < 0.7

2.Rule :- ++ is pre increment operator so in any arithmetic expression it first increment the value of variable by one in whole expression then starts assigning the final value of variable in the expression.

Compiler will treat this expression j = ++i+++i+++i; as
i = ++i + ++i + ++i;

Initial value of i = 5 due to three pre increment operator final value of i=8.
Now final value of i i.e. 8 will assigned to each variable as shown in the following figure:


So, j=8+8+8
j=24 and
i=8
3.#include<stdio.h>
void main(){
    int x;
    x=10,20,30;
    printf("%d",x);
    return 0;
Precedence table:

Operator
Precedence
Associative
 =
More than ,
Right to left
 ,
Least
Left to right

Since assignment operator (=) has more precedence than comma operator .So = operator will be evaluated first than comma operator. In the following expression
x = 10, 20, 30
First 10 will be assigned to x then comma operator will be evaluated.
4.
#include<stdio.h>
int main(){
    int a;
    a=015 + 0x71 +5;
    printf("%d",a);
    return 0;
}
015 is octal number its decimal equivalent is = 5 * 8 ^ 0 + 1 * 8 ^ 1 = 5 + 8 = 13
0x71 is hexadecimal number (0x is symbol of hexadecimal) its decimal equivalent is = 1 * 16 ^ 0 + 7 * 16 ^ 1 = 1 + 112 = 113
So, a = 13 + 113 + 5 = 131
5.
#include<stdio.h>
int main(){
    float a;
    (int)a= 45;
    printf("%d,a);
    return 0;
}
After performing any operation on operand it always return some constant value.

(int) i.e. type casting operator is not exception for this. (int) a will return one constant value and we cannot assign any constant value to another constant value in c.

(int)a = 45; is equivalent to
3456 = 45 ( Here 3456 in any garbage value of int(a)).

Saturday, July 14, 2012

C Arrays Questions


#include<stdio.h>
enum power{
    Dalai,
    Vladimir=3,
    Barack,
    Hillary
};
void main(){
    float leader[Dalai+Hillary]={1.f,2.f,3.f,4.f,5.f};
    enum power p=Barack;
    printf("%0.f",leader[p>>1+1]);
}

Output:2

Size of an array can be enum constantan.
Value of enum constant Barack will equal to Vladimir + 1 = 3 +1 = 4
So, value of enum variable p  = 4
leader[p >> 1 +1]
= leader[4 >> 1+1]
=leader[4 >> 2]   //+ operator enjoy higher precedence than >> operator.
=leader[1]  //4>>2 = (4 / (2^2) = 4/4 = 1
=2

#include<stdio.h>
void main(){
    int const SIZE=5;
    int expr;
    double value[SIZE]={2.0,4.0,6.0,8.0,10.0};
    expr=1|2|3|4;
    printf("%f",value[expr]);
}

Size of any array in c cannot be constantan variable.

Structure & Bit Fields

Both C and C++ allow integer members to be stored into memory spaces smaller than the compiler would ordinarily allow. These space-saving structure members are called bit fields, and their width in bits can be explicitly declared. Bit fields are used in programs that must force a data structure to correspond to a fixed hardware representation and are unlikely to be portable.
The syntax for declaring a bit field is as follows:
>>-type_specifier--+------------+--:--constant_expression--;---><
                   '-declarator-'
 
 
A bit field declaration contains a type specifier followed by an optional declarator, a colon, a constant integer expression that indicates the field width in bits, and a semicolon. A bit field declaration may not use either of the type qualifiers, const or volatile.
C The C99 standard requires the allowable data types for a bit field to include qualified and unqualified _Bool, signed int, and unsigned int. In addition, this implementation supports the following types.
  • int
  • short, signed short, unsigned short
  • char, signed char, unsigned char
  • long, signed long, unsigned long
  • long long, signed long long, unsigned long long
In all implementations, the default integer type for a bit field is unsigned.
C++ C++ extends the list of allowable types for bit fields to include any integral type or enumeration type.
In either language, when you assign a value that is out of range to a bit field, the low-order bit pattern is preserved and the appropriate bits are assigned.
Bit fields with a length of 0 must be unnamed. Unnamed bit fields cannot be referenced or initialized. A zero-width bit field can cause the next field to be aligned on the next container boundary where the container is the same size as the underlying type of the bit field.
Mac OS X Bit fields are also subject to the align compiler option. Each of the align suboptions gives a different set of alignment properties to the bit fields. For a full discussion of the align compiler option and the #pragmas affecting alignment, see XL C/C++ Compiler Reference.
The following restrictions apply to bit fields. You cannot:
  • Define an array of bit fields
  • Take the address of a bit field
  • Have a pointer to a bit field
  • Have a reference to a bit field
The following structure has three bit-field members kingdom, phylum, and genus, occupying 12, 6, and 2 bits respectively:
struct taxonomy {
     int kingdom : 12;
     int phylum : 6;
     int genus : 2;
     };
Alignment of Bit Fields
If a series of bit fields does not add up to the size of an int, padding can take place. The amount of padding is determined by the alignment characteristics of the members of the structure.
The following example demonstrates padding, and is valid for all implementations. Suppose that an int occupies 4 bytes. The example declares the identifier kitchen to be of type struct on_off:
struct on_off {
                  unsigned light : 1;
                  unsigned toaster : 1;
                  int count;            /* 4 bytes */
                  unsigned ac : 4;
                  unsigned : 4;
                  unsigned clock : 1;
                  unsigned : 0;
                  unsigned flag : 1;
                 } kitchen ;
The structure kitchen contains eight members totalling 16 bytes. The following table describes the storage that each member occupies:

Member Name Storage Occupied
light 1 bit
toaster 1 bit
(padding -- 30 bits) To the next int boundary
count The size of an int (4 bytes)
ac 4 bits
(unnamed field) 4 bits
clock 1 bit
(padding -- 23 bits) To the next int boundary (unnamed field)
flag 1 bit
(padding -- 31 bits) To the next int boundary
All references to structure fields must be fully qualified. For instance, you cannot reference the second field by toaster. You must reference this field by kitchen.toaster.
The following expression sets the light field to 1:
  kitchen.light = 1;
When you assign to a bit field a value that is out of its range, the bit pattern is preserved and the appropriate bits are assigned. The following expression sets the toaster field of the kitchen structure to 0 because only the least significant bit is assigned to the toaster field:
  kitchen.toaster = 2;
 
Reference Links:
http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/
index.jsp?topic=%2Fcom.ibm.vacpp6m.doc%2Flanguage%2Fref%2Fclrc03defbitf.htm
 
http://c-faq.com/struct/bitfields.html

C String Questions

1.void main(){
   char *str=NULL;
   strcpy(str,"cquestionbank");
   printf("%s",str);
}
We cannot copy any thing using strcpy function to the character pointer pointing to NULL.

C Evaluation Order Questions

1.void main(){
  int i=4,x;
  x=++i + ++i + ++i;
  printf("%d",x);
}
In ++a, ++ is pre increment operator. In any mathematical expression pre increment operator first increment the variable up to break point then starts assigning the final value to all variable.
Step 1: Increment the variable I up to break point.


Step 2: Start assigning final value 7 to all variable i in the expression.



So, i=7+7+7=21
2.void main(){
  int a=10;
  printf("%d %d %d",a,a++,++a);
} 
In c printf function follows cdecl parameter passing scheme. In this scheme parameter is passed from right to left direction.


So first ++a will pass and value of variable will be a=10 then a++ will pass now value variable will be a=10 and at the end a will pass and value of a will be a=12. 

C Datatype Questions

 1.void main(){
   int i=320;
   char *ptr=(char *)&i;
   printf("%d",*ptr);
}

As we know size of int data type is two byte while char pointer can pointer one byte at time.
Memory representation of int i=320


So char pointer ptr is pointing to only first byte as shown above figure.
*ptr i.e. content of first byte is 01000000 and its decimal value is 64.
2.void main(){
char c=125;
    c=c+10;
    printf("%d",c);
}

As we know char data type shows cyclic properties i.e. if you will increase or decrease the char variables beyond its maximum or minimum value respectively it will repeat same value according to following cyclic order:
So,
125+1= 126
125+2= 127
125+3=-128
125+4=-127
125+5=-126
125+6=-125
125+7=-124
125+8=-123
125+9=-122
125+10=-121

3.
void main(){
   float a=5.2;
  if(a==5.2)
     printf("Equal");
  else if(a<5.2)
     printf("Less than");
  else
     printf("Greater than");
}

5.2 is double constant in c. In c size of double data is 8 byte while a is float variable. Size of float variable is 4 byte.
So double constant 5.2 is stored in memory as:
101.00 11001100 11001100 11001100 11001100 11001100 11001101
Content of variable a will store in the memory as:
101.00110 01100110 01100110
It is clear variable a is less than double constant 5.2
Since 5.2 is recurring float number so it different for float and double. Number likes 4.5, 3.25, 5.0 will store same values in float and double data type.
Note: In memory float and double data is stored in completely different way

3.
void main(){
char c='\08';
printf("%d",c);
}

In c any character is starting with character ‘\’ represents octal number in character. As we know octal digits are: 0, 1, 2, 3, 4, 5, 6, and 7. So 8 is not an octal digit. Hence ‘\08’ is invalid octal character constant.


Reference Links: