Linked List Interview Question and Answers

Have you been asked how to remove duplicates, find the nth element,reverse, sort and merge ... linked list in the interview Or figuring how to perform functions similar to the above. Here is a document named "LinkedListProblems" of Stanford CS Education Library which gives a quick review of linked list basics followed by 18 linked list problems, basic through advanced, with solution code in C/C++.The problems are: Count, GetNth, DeleteList, Pop, InsertNth, SortedInsert, InsertSort, Append, FrontBackSplit, RemoveDuplicates, MoveNode, AlternatingSplit, ShuffleMerge, SortedMerge, SortedIntersect, Reverse, and RecursiveReverse.

Also are you looking for some great tree list recursion problems or looking  to brush up your knowledge about binary trees. Check these two document  "The Great Tree List Recursion Problem" and "Binary Trees".

Hope this helps you.

Solutions to C Puzzles 8

I thought the following program was a perfect C program. But on compiling, I found a silly mistake.
Can you find it out (without compiling the program :-) ?

#include

void OS_Solaris_print()
{
        printf("Solaris - Sun Microsystems\n");
}

void OS_Windows_print()
{
        printf("Windows - Microsoft\n");

}
void OS_HP-UX_print()
{
        printf("HP-UX - Hewlett Packard\n");
}

int main()
{
        int num;
        printf("Enter the number (1-3):\n");
        scanf("%d",&num);
        switch(num)
        {
                case 1:
                        OS_Solaris_print();
                        break;
                case 2:
                        OS_Windows_print();
                        break;
                case 3:
                        OS_HP-UX_print();
                        break;
                default:
                        printf("Hmm! only 1-3 :-)\n");
                        break;
        }

        return 0;
}

Solution:

Error at void OS_HP-UX_print and OS_HP-UX_print(). The 

function name should not contain "-" as it is invalid.

What do you think would be the output of the following 

program and why? (If you are about to say "f is 1.0", I 

would say check it out again)
#include 

int main()
{
        float f=0.0f;
        int i;

        for(i=0;i<10;i++)
                f = f + 0.1f;

        if(f == 1.0f)
                printf("f is 1.0 \n");
        else
                printf("f is NOT 1.0\n");

        return 0;
}

Solution:

f is NOT 1.0
 

Explanation: The value of f after the loop completion will 

be 1.000000. This is the precision set by the compiler. If 

you want the output as "f is 1.0" replace the if statement 

with if(abs(f - 1.0)==0).
 

Interview Puzzels:1

100 Closed Lockers
Suppose you are in a hallway lined with 100 closed lockers. You begin by opening all 100 lockers. Next, you close every second locker. Then you go to every third locker and close it if it is open or open it if it is closed (call this toggling the locker). Continue toggling every nth locker on pass number n. After your hundredth pass of the hallway, in which you toggle only locker number 100, how many lockers are open? 

Solution:
10
Lockers #1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.
Explanation:
Each of these numbers are perfect squares. This problem is based on the factors of the locker number. Each locker is toggled by each factor; for example, locker #40 is toggled on pass number 1, 2, 4, 5, 8, 10, 20, and 40. That's eight toggles: open-closed-open-closed-open-closed-open-closed.

The only way a locker could be left open is if it is toggled an odd number of times. The only numbers with an odd number of factors are the perfect
squares. Thus, the perfect squares are left open.

For example, locker #25 is toggled on pass number 1, 5, and 25 (three toggles): open-closed-open.If n is the number then the number of open doors is floor(sqrt(n)) so if n=60 then sqrt(60) =6.92 floor(6.92) is 6.So the answer is 6
 

Solutions to C Puzzles 7

#include
int main()
{
int a=10;
switch(a)
{
case '1':
printf("ONE\n");
break;
case '2':
printf("TWO\n");
break;
defa1ut:
printf("NONE\n");
}
return 0;
}

If you expect the output of the above program to be NONE, I would request you to check it out!!

Solution:

Nothing gets printed. Bcs check the spelling of "defa1ut".
"The condition of a switch statement is a value. The case says that if it has the value of whatever is after that case then do whatever follows the colon. The break is used to break out of the case statements.Default is optional" Since none of the value is matched against case and no case has value 10 and compiler doesn't recognize "default" keyword above, nothing gets printed.

Explain the output of the following C program (No, the output is not 20).

#include
int main()
{
int a=1;
switch(a)
{   int b=20;
case 1: printf("b is %d\n",b);
break;
default:printf("b is %d\n",b);
break;
}
return 0;
}

Solution:
b is 9873931(some random junk value) since b is not initialized. the statement
int b=20; doesn't get executed bcs inside switch the execution starts from
case/default(if no case) block.

What would be the output of the following C program?
(Is it a valid C program?)
#include 
int main()
{
int i=43;
printf("%d\n",printf("%d",printf("%d",i)));
return 0;

Solution:
4321

printf returns the number of digits/characters it printed.So this
printf("%d",i) gets executed first and prints 43 and the function printf returns 2
and similarly other 2 printf's print 2 1


I thought the following C program is perfectly valid (after reading about
the comma operator in C).
But there is a mistake in the following program, can you identify it?

#include 

int main()
{
int a = 1,2;
printf("a : %d\n",a);
return 0;
}

Solution:

error in the line int a = 1,2;

Here the declaration and definition is happening at the same time and hence compiler
associates/initializes a to 1 but for 2 it considers as variable and since it
is a not a valid variable(variable names cannot start with digits) it throws
out an error.

Solutions to C Puzzles 6

Given a string s1 and a string s2, write  a snippet to say whether s2 is a
rotation of s1 using only one call to strstr routine?

(eg given s1 = ABCD and s2 = CDAB, return  true,
     given s1 = ABCD, and s2 = ACBD , return false)

#include
#include

int main ()
{
char *pStr1, *pStr2,*ptempString,*ptr;

pStr1 = "ABCD";
pStr2 = "DABC";
printf("Str1 = \"%s\"\n", pStr1);
printf("Str2 = \"%s\"\n\n", pStr2);

if ((ptempString = malloc(2* strlen(pStr2)+2)) == NULL) {
puts("Memory allocation error!");
exit(0);
}
strcpy(ptempString,pStr2);
strcat( ptempString, pStr2);


if((ptr=strstr(ptempString,pStr1)))
{
puts("true");
}
else
{
puts("false");
}


}

Solutions to C Puzzles 5

What's the  "condition" so that the following code
snippet  prints both HelloWorld !

if  "condition"
     printf ("Hello");
else
     printf("World");

Solution:


#include 
int main()
{
 int x=0;
    if  (5<(printf ("Hello"))) 
 { 
 printf ("Hello"); 
 else       
 printf("World");   
 }  
}

Solutions to C Puzzles 4

What is the potential problem with the following C program?

  #include 
int main()
{
   char str[80];
   printf("Enter the string:");
   scanf("%s",str);
   printf("You entered:%s\n",str);

   return 0;
}

Solution:

Buffer overflow problem. Since C doesn't do bound checking, anyone can fill more
than 80 characters. Hackers might use this to overwrite the return address and
cause malicious activities.

What is the output of the following program?
#include 
int main()
{
        int i;
        i = 1,2,3;
        printf("i:%d\n",i);
        return 0;
}

Solution:
i: 1


What is the output of the following program?
#include 
int main()
{
    int cnt = 5, a;

    do {
        a /= cnt;
    } while (cnt --);

    printf ("%d\n", a);
    return 0;
}


Solution:

Division by 0 exception.


In the while loop, first the condition is checked and then the value is decremented.
i.e first the existing value of cnt is used to check the truthfulness of while loop
and then the value of cnt is decremented before the execution enters the body of
the loop. Hence when cnt is 1, while return true but the value of cnt at a/=cnt
would be 0 and hence causes run time error.

What is the output of the following program?
#include 
int main()
{
    int i = 6;
    if( ((++i < 7) && ( i++/6)) || (++i <= 9))
        ;
    printf("%d\n",i);
    return 0;
}

Solution:
8

Only ((++i < 7) && ( i++/6)) this gets executed. here first the value is tested and
then incremented.
(++i < 7) this is true bcs 6<  style="color:#008b8b;">i++/6) is true
bcs 7/6 is 1 and now i=8. Since if includes ||(or) if once condition is true,
the remaining condition won't be checked.

What is the output of the following, if the input provided is:

Life is beautiful
#include 
int main()
{
    char dummy[80];
    printf("Enter a string:\n");
    scanf("%[^a]",dummy);
    printf("%s\n",dummy);
    return 0;
}

Solution:
Life is be


in the above scanf statement, it accepts the input from the stdin(standard input)
till it  encounters character "a"( small a)

Solutions to C Puzzles 3

What's the expected output for the following program and why?

enum {false,true};

int main()
{
      int i=1;
      do
      {
              printf("%d\n",i);
              i++;
              if(i < 15)
                      continue;
      }while(false);
      return 0;
}

Solution:

1

It prints 1 and quits.
Reason is continue statement brings/takes the execution to the beginning of the loop.
do while is nothing but while loop apart from the first iteration in which the
condition is not checked. Hence when continue is executed, execution to while
statement which returns false and hence quits the while loop.

Solutions to C Puzzles 2

2)The expected output of the following C program is to print the elements in the array. But when actually run, it doesn't do so.

  #include

#define TOTAL_ELEMENTS (sizeof(array) / sizeof(array[0]))
int array[] = {23,34,12,17,204,99,16};

int main()
{
   int d;

   for(d=-1;d <= (TOTAL_ELEMENTS-2);d++)
       printf("%d\n",array[d+1]);

   return 0;
}

Find out what's going wrong.

Solution:
Sizeof Operator's return type is unsigned. When signed variable is compared with unsigned variable/value, the signed variable is promoted to unsigned.

So in the above case d=-1 and which be be promoted to unsigned value which become huge compared to (TOTAL_ELEMENTS-2) hence the condition will result in false and the loop won't be executed.

SO nothing gets printed.

Solutions to C Puzzles

I will be posting solution to the questions posted on http://www.gowrikumar.com/ site.

1)
What is the output of the following program?

#include 
int main()
{
int i;
i = 10;
printf("i : %d\n",i);
printf("sizeof(i++) is: %d\n",sizeof(i++));
printf("i : %d\n",i);
return 0;
}


Solution:

10
4
10

Reason the value of i at the second printf is still 10 is because
operation performed inside the sizeof operator doesn't change the
value of i.

The 'sizeof' operator is used to determine the amount of space any
data-element/datatype occupies in memory