Printing India's Map using C !

I found this piece of code on stackoverflow. This prints the map of India in '!'. Have a look here http://codepad.org/UKwPb77f

#include "stdio.h"

main()
{
    int a,b,c;
    int count = 1;

    for (b = c = 10; 
    a = "- FIGURE?, UMKC,XYZHello Folks,\
    TFy!QJu ROo TNn(ROo)SLq SLq ULo+\
    UHs UJq TNn*RPn/QPbEWS_JSWQAIJO^\
    NBELPeHBFHT}TnALVlBLOFAkHFOuFETp\
    HCStHAUFAgcEAelclcn^r^r\\tZvYxXy\
    T|S~Pn SPm SOn TNn ULo0ULo#ULo-W\
    Hq!WFs XDt!"[b+++21]; )
      for(; a-- > 64 ; )
        putchar ( ++c=='Z' ? 
                             c = c / 9 : 
                             33 ^ b & 1  );

    return 0;
}

         !!!!!!                                                     
                    !!!!!!!!!!                                                 
                     !!!!!!!!!!!!!!!                                           
                       !!!!!!!!!!!!!!                                          
                     !!!!!!!!!!!!!!!                                           
                      !!!!!!!!!!!!                                             
                      !!!!!!!!!!!!                                             
                        !!!!!!!!!!!!                                           
                        !!!!!!!!                                               
                        !!!!!!!!!!                                             
                       !!!!!!!!!!!!!!                                          
                     !!!!!!!!!!!!!!!!                                          
                    !!!!!!!!!!!!!!!!                                  !!!!!    
                  !!!!!!!!!!!!!!!!!!!                               !!!!!!!!!! 
                 !!!!!!!!!!!!!!!!!!!!!!!                 !         !!!!!!!!!!  
            !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!              !!     !!!!!!!!!!!!    
           !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!        !!      !!!!!!!!       
            !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!      
             !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!       
              !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!  !!!!!!!!!!!!       
       !!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!        !!!!!!        
      !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!      !!!!!         
          !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!        !!!          
        !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!        !          
          !!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!                       
           !!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!                         
                  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!                          
                 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!                           
                  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!                               
                  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!                               
                  !!!!!!!!!!!!!!!!!!!!!!!!!!!!                                 
                  !!!!!!!!!!!!!!!!!!!!!!!!!!                                   
                  !!!!!!!!!!!!!!!!!!!!!!!!!                                    
                   !!!!!!!!!!!!!!!!!!!!!!!!                                    
                    !!!!!!!!!!!!!!!!!!!!                                       
                    !!!!!!!!!!!!!!!!!!!                                        
                     !!!!!!!!!!!!!!!!                                          
                      !!!!!!!!!!!!!!!!                                         
                      !!!!!!!!!!!!!!!                                          
                       !!!!!!!!!!!!!!                                          
                        !!!!!!!!!!!!                                           
                        !!!!!!!!!!!!                                           
                        !!!!!!!!!!!!                                           
                          !!!!!!!!                                             
                          !!!!!!                                               
                           !!!!    

Swapping the odd and even position in a linked list

A simple and intuitive solution to the problem !! It might not be very efficient but it does certainly work.


node* swap(node *head)
{
    node dummy;
    node *prev, *curr, *u, *tmp;

    if (head==NULL) return head;

    prev=&dummy;
    for(curr=head; curr!=NULL && curr->next!=NULL; ) {
        u = curr->next;
        tmp = u->next;
        prev->next = u;
        u->next = curr;
        prev = curr;
        curr = tmp;
    }
    prev->next = curr;
    return dummy.next;
}

void print(const node *head)
{
    for(const node *p=head; p; p=p->next)
        printf("%d ", p->val);
    putchar('\n');
}

Linked List Insert nth problem

A linked list problem for inserting a node after the nth index !!

InsertNth() Solution


void InsertNth(struct node** headRef, int index, int data)
if (index == 0)
   Push(headRef, data);                       // position 0 is a special case...
else {
  struct node* current = *headRef;
   int i;
     for (i=0; i<index-1; i++) {
     assert(current != NULL); // if this fails, index was too big
     current = current->next;
      }
Push(&(current->next), data);
}
}

Problem on Bit Manipulation

Write a function to determine the number of bits required to convert integer X to integer Y.
Input: 31, 14
Output: 2


This problem seems to be quite complex, however is actually rather simple. Think about finding out which bits in two numbers are different. Simple: with an XOR.
Each 1 in the XOR will represent one different bit between X and Y. Then we can simply count the number of bits that are 1.

 public static int swapRequired(int x, int y)
{
 int counter = 0;
 for (int z = x ^ y; z!= 0; z= z>>1) {
 counter += c & 1;
 }
 return counter;
 }

Reverse a Linked List

This question is one of the most repeated ones across Google, Microsoft, Amazon and a few more. The thing which makes it a good question is that after you scratch your head and give them an algorithm they either ask you to optimize it for the boundary cases (which is fine for most of the candidates) or they ask you to do it the other way round.

I am going to give you both, recursive as well as an iterative solution. For both the techniques :

Initially call the method as : head = reverseList(head,NULL)


Iterative :

Node *Reverse (Node *p)
{
   Node *pr = NULL;
   while (p != NULL)
   {
      Node *tmp = p->next;
      p->next = pr;
      pr = p;
      p = tmp;
   }
   return pr;
}
-----------------------------------------------------------------------
Recursive:

Node *reverseList(Node *current, Node *parent)
{
        Node *revHead;
   if(current == null)
      revHead = parent;
   else
   {
      revHead = reverseList(current->next,current);
      current->next = parent;      
   }
   return revHead;
}

Easy-4

void main()

{

int *mptr, *cptr;

mptr = (int*)malloc(sizeof(int));                               //Output: some garbage values

printf(“%d”,*mptr);

int *cptr = (int*)calloc(sizeof(int),1);                      // Output=0

printf(“%d”,*cptr);

}

The above statements return garbage values and a zero in the next.

So much for understanding a small difference between malloc() and calloc().

See the differences in arguments and the returned values.

A few simple logical questions !

1.) 

Multiplying a number by 7 without using * and + operators.

NewNum = Num << 3;                      // multiplied by 2^3 = 8

NewNum = NewNum - Num;             // 8 – 1 = 7

2.)

Finding the last character of any String.

                              (OR)

Write a function that finds the last instance of a character in a string


char *lastChar(char *String, char ch)
{
char *cStr = NULL;


// traverse the entire string


while(*String ++ != NULL ) 
{
if(*String==ch) 
cStr = String;
}
return cStr;
} 

C Output Type Question

main( )
{
static int a[ ] = {0,1,2,3,4};
int *p[ ] = {a,a+1,a+2,a+3,a+4};
int **ptr = p;
ptr++;
printf(“\n %d  %d  %d”, ptr-p, *ptr-a, **ptr);
*ptr++;
printf(“\n %d  %d  %d”, ptr-p, *ptr-a, **ptr);
*++ptr;
printf(“\n %d  %d  %d”, ptr-p, *ptr-a, **ptr);
++*ptr;
printf(“\n %d  %d  %d”, ptr-p, *ptr-a, **ptr);
}

Try to find the output !!
This question is seemingly quite unconventional, but try it out without using a compiler, and then compare your results with:


1 1 1
2 2 2
3 3 3
3 4 4

Acyclic Linked-List Detection Algorithm

Write a function that takes a pointer to the head of a list and determines whether the list is cyclic or acyclic. Your function should return false if the list is acyclic and true if it is cyclic. You may not modify the list in any way.

int determineTermination( node *head )
        { 
           node *fast, *slow;
           fast = slow = head; 
                  while( true )
                       {
                           if( !fast || !fast->next ) 
                              return false; 
                           else if( fast == slow || fast->next == slow ) 
                              return true; 
                           else 
                              {
                                 slow = slow->next; 
                                 fast = fast->next->next; 
                              }
                        }
        }


Leave your comments below the post.
Happy coding :)

Microsoft Moderate Programming Question

An important interview as well as optimised solution for finding the largest sub array sum in an array which may contain 0, positive and negative integers.


#include<stdio.h>
main()
{
int sumtillnow=0,sum=0,i=0;
int a[7]={-1,11,13,12,-90,23,5};
for(i=0;i<7;i++)
{
sumtillnow+=a[i];
if(sumtillnow>sum)
 sum=sumtillnow;
if(sumtillnow<0)
 sumtillnow=0;
 }
printf("%d",sum);
}

One line of code for finding out whether a number is power of 2 or not

(An obnoxious looking piece of code) 

If the following LOC returns true, find out what is x here ?

if((x&&!(x&(x-1))==1)) 

Study the Bit-wise operators well, many problems and contests have questions which become quite easy if these are used !!
 The above code is a simple one line test for testing if a variable entered or passed is a power of 2.

Print your Name without the semicolon in a C program

Okay.. this question used to be quite a favorite at coding championships 4-5 years back. The question seemed tough as all programming books start with the statement that "All statements in ' XYZ ' language end with a ( ; ) semicolon, except for a few conditional, looping and other control structure constructs. Actually the problem lies in the fact that we try to use standalone printf() statements in our solutions.
Here's a solution for it :

main()
{
 if(printf("MY NAME")) {}
 else {}
}

Easy-2

This is second in line with the easy posts.. after a while we shall move onto more tricky ones.. A problem a day keeps the Alzheimer's away.

void main()
{
static int i=i++, j=j++, k=k++;
printf(“i = %d j = %d k = %d”, i, j, k);
}

Guess the output !!

Easy-1

There are numbers from 1 to N in an array, out of these, one of the number gets duplicated and one is missing. 

The task is to write a program to find out the duplicate number.

(example: 1 2 3 3 4 5)

Already Solved the question in your head ?? Take this.. : No using any auxiliary space like arrays.