A reader submitted the interview questions he was asked. More C/C++ questions will be added here, as people keep sending us a set of 2-3 questions they got on their job itnerview.
Q1: Tell how to check whether a linked list is circular.
A: Create two pointers, each set to the start of the list. Update each as follows:
while (pointer1) {
pointer1 = pointer1->next;
pointer2 = pointer2->next; if (pointer2) pointer2=pointer2->next;
if (pointer1 == pointer2) {
print ("circular\n");
}
}
Q2: OK, why does this work?
If a list is circular, at some point pointer2 will wrap around and be either at the item just before pointer1, or the item before that. Either way, it’s either 1 or 2 jumps until they meet.
How can you quickly find the number of elements stored in a a) static array b) dynamic array ?
Why is it difficult to store linked list in an array?
How can you find the nodes with repetetive data in a linked list?
Write a prog to accept a given string in any order and flash error if any of the character is different. For example : If abc is the input then abc, bca, cba, cab bac are acceptable but aac or bcd are unacceptable.
This is a C question that I had for an intern position at Microsoft: Write out a function that prints out all the permutations of a string. For example, abc would give you abc, acb, bac, bca, cab, cba. You can assume that all the characters will be unique. After I wrote out my function, he asked me to figure out from the code how many times the printf statement is run, and also questions on optimizing my algorithm.
What’s the output of the following program? Why?
#include <stdio.h>
main()
{
typedef union
{
int a;
char b[10];
float c;
}
Union;
Union x,y = {100};
x.a = 50;
strcpy(x.b,"hello");
x.c = 21.50;
printf("Union x : %d %s %f \n",x.a,x.b,x.c );
printf("Union y :%d %s%f \n",y.a,y.b,y.c);
}
Given inputs X, Y, Z and operations | and & (meaning bitwise OR and AND, respectively)
What is output equal to in
output = (X & Y) | (X & Z) | (Y & Z)
77 Comments on Interview questions on C/C++
//Answer for is Circular link list
//start and p initially the given pointer
While(p)
if(start==(p=p->next))
printf(”Circular”);
printf(”not a circular”);
#What say
I tried to solve the question using the approach given by Hari :)
“Write a prog to accept a given string in any order and flash error if any of the character is different. For example : If abc is the input then abc, bca, cba, cab bac are acceptable but aac or bcd are unacceptable.
Tech Interviews comment by Hari ”
#include
#include
void main()
{
char s[10],dup[10];
int sum_org=0,sum_dup=0;
printf(”\nEnter the string “);
scanf(”%s”,s);
sum_org=parse_sum(s);
printf(”\nEnter the duplicate string :”);
scanf(”%s”,dup);
sum_dup=parse_sum(dup);
if(sum_org==sum_dup)
printf(”\nAllowed duplication”);
else
printf(”\nNot same !!”);
}
int parse_sum(char *s)
{
char temp,*c;
int equi,sum=0;
c=s;
while(*c!=”)
{
temp=*c;
equi=temp;
sum=sum+equi;
c++;
}
return sum;
}
Code for printing out all permutaions of a string, gurantee to work correctly:
#include
#include
#include
//recursive function to permute a string
void permute(char permulist[], int start, int n)
{
char templist[100];
char tempchar;
int i;
if (start == n-1)
{
for (i=0; i>str;
n = strlen(str);
permute(str,0,n);
return 0;
}
test program for comment 53 (print out permutations)
int main()
{
char str[100];
int n;
cout>str;
n = strlen(str);
permute(str,0,n);
system(”PAUSE”);
return 0;
}
The followint header files should be included in Comment 53 and 54:
iostream.h
stdlib.h
string.h
sorry, this website wipes out the character “
can anyone tell how to find the common node in a circular list without flagging?? in o(n) time
can anyone tell how to find the common node in a circular list without flagging?? in o(n) time
Please elaborate the question. It is not clear. What is a common node in cicular list???
Hi friends this is the best solution to find Circular Linklist in O(n).
// Best solution
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}
also see this site
http://ostermiller.org/find_loop_singly_linked_list.html
how can i find the tenth prime number after the decimal point in e…ie e=2.71….(i need the tenth prime aftr the decimal)…my prog wont wrk…
What is output equal to in
output = (X & Y) | (X & Z) | (Y & Z)
if any of the two of {X,Y,Z} are true then the expression is true.
hello everybody,
i want to know why is the sizeof empty class is 1.
i.e. class abc{ };
cout
Hi,
one of the frequentr question reg Copy constructor..
syntax for Copy constructor:
classname(const classname &obj)
{
….
}
what will happen if u haapen to remove the reference used.. say
classname(const classname obj)
{
….
}
ANS:
if not used without reference , it will end in infinite loop…bcoz again (as per the stmt) again it tries to create a obj which inturn invokes again the same function and again the same thing continues…making it an infinite loop
here I give a soln which is able to find whether link list is circular or not in O(n) time
take two pointers as start1 & start2
set start1 & start2 at any node which is in the given linklist
here I give a soln which is able to find whether link list is circular or not in O(n) time
take two pointers as start1 & start2
set start1 at any node which is in the given linklist such
start2 = start1;
while(start2->next!=start1&&start2->next!=NULL)
start2=start2->next;
if(start2->next=start1)
printf(”circular”);
else
printf(”not circular)
The following code works (tested):
void isCircularList(nodePtr head, nodePtr curr, bool &circ) {
if (head) {
if ( curr && (curr->next == head) )
circ = true;
else {
if (curr)
isCircularList(head, curr->next, circ);
else
circ = false;
}
}
}
Write a prog to accept a given string in any order and flash error if any of the character is different. For example : If abc is the input then abc, bca, cba, cab bac are acceptable but aac or bcd are unacceptable.
The most efficient and scalable way would be:
1. sort the original string.
2. sort the input string.
3. if(strcmp(original_string, input_string))
printf(”Error”);
-Pralhad
main()
{
printf(”hello friends”);
}
without using void function in main and %d in printf we can print a mesg similarly in c++ can also we can do
but there are only few simple programs only why we can all that is bec there exist a rule fr which we have to be defined fr structure, pointers, arrays etc
bool isCircular( node * head, node * current ) throws exception
{
if( head == NULL )
throw new exception( "NULL reference passed!");
if( current == NULL)
throw new exception( "NULL reference passed!");
for( ; ; )
{
//Check if we have reached the dead - end.
if( current->next == NULL )
return false;
else
{
//Check if we have reached the Head (circular)
if( current->next == head )
return true;
else //iterate
current = current->next;
}
}
//Point not reached.
}
//Use it like:
try
{
bool is_circular = isCircular( head, head );
}
catch( exception e)
{
cout
Mike Mountrakis
http://www.illumine.gr
For the array size:
unsigned log getSize( Cell_t array [])
{
return sizeof(array)/sizeof( Cell_t);
}
Mike Mountrakis
http://www.illumine.gr
Hi all,
What i am thinking the best solution to find the loop in a sigly linked list by O(n) complexity u can implement by this logic ..
bool is_circular()
{
node *sNode, *f1Node, *f2Node;
node startNode;
sNode = f1Node = f2Node = &startNode;
while(sNode && f1Node = f2Node.next && f2Node = f1Node.next)
{
if (sNode == f1Node || sNode == f2Node)
return true; // means loop found
sNode = sNode.next;
}
}
void * ptr,*ptr2;
ptr=begining;
while(ptr->next!=null)//fix the element
{
ptr2=ptr->next;
if(ptr2==ptr)//elemnet has its own address
{
coutnext;
}
ptr=ptr->next;
}
Easy way to detect the circle in the Link List.
Using C++ string class.
unsigned int LinkList :: detect_circle_string () const
{
   struct node *t = head ;
   char buf [10] ;
   string ptr = " " ;
   size_t found ;
   for ( ; t ; t=t->next )
   {
       sprintf ( buf, " %u ", t ) ;
       found = ptr.find ( string(buf) ) ;
       if ( found!=string::npos )
       {
           cout << "Circle Detected At : " << t->data << " Address : " << (unsigned int) t ;
           return (unsigned int ) t ;
       }
       ptr += buf ;
   }
}
Write a prog to accept a given string in any order and flash error if any of the character is different. For example : If abc is the input then abc, bca, cba, cab bac are acceptable but aac or bcd are unacceptable.
—for this we can multiply the ascii values of each character in original string and compare it with that of duplicate string… the working code is as:-
#include
#include
#include
void main()
{
int i,n1,n2,mul1=1,mul2=1,sum=0;
char str1[15],str2[15];
clrscr();
printf(”Enter the length of string\n”);
scanf(”%d”,&n1);
printf(”Enter the original string\n”);
for(i=0;i<n1;i++)
{
scanf(”%s”,&str1[i]);
mul1*=str1[i];
}
printf(”Enter the length of duplicate string\n”);
scanf(”%d”,&n2);
if(n1!=n2)
{
printf(”ERROR different\n”);
exit(0);
}
printf(”Enter the duplicate string\n”);
for(i=0;i<n2;i++)
{
scanf(”%s”,&str2[i]);
mul2*=str2[i];
}
if(mul1==mul2)
printf(”SAME\n”);
else
printf(”Different ERROR\n”);
getch();
}
Hi.
This is my permutation func.
void
permutate( string s, int n=0 ){
static int len=s.length();
if( n == len-2 ){
cout << s << endl;
swap(s[len-2],s[len-1]);
cout << s << endl;
}
else{
for( int i=n ; i<len ; ++i ){
permutate(s,n+1);
swap(s[n],s[i+1]);
}
}
}
It is based on simple fact, that to perform permutation of a n-element set, you should:
0.If your set has only 2 elements, you can simply print them, then swap them, and print them again. End.
1. print (save, whatever) the value of first element
2. permute the rest of the set (means elements from 2, …, n )
3. Swap the first element with all the next elements, and repeat the procedure.
It’s clear, that this algorithm performs T(n) = n*T(n-1) steps, which is exactly n!
T(1) = 1 of course.
Or maybe I’m wrong? Hope not:P
Regards from Poland!
Got a question that extends on the detecting circular linked list question:
Given the constraints that you cannot modify the struct (or class) of the elements, and that you have to remove the loop in the cyclic linked list in O(n) time and O(1) space, how would you do it?
By removing the loop, I mean something like:
_______________________________
__ __ __ _| __ __ __ _|
| | -> | | -> | | -> | | -> | | -> | | -> | | -> | |
       –
Ans:
You know how to make them meet. (By two pointers, one runs twice faster then the usual).
Once they meet cut the list. Its looks like this :
—–|————-
——-|
OR
——-|———
—|
now run two normal pointers from anchor and from the place cut was made.
Count the lengths.Once you know we lengths go over the longer so the lengths will be equal. Now run the two pointers and every step check if the pointers are equal.
Look like
—*———–|——
———- |
or
—|————–
——*—|
When you find the common link. cut one
of the list and copy to the end.