Find a cycle in the linked list OR Find out if the linked list is cyclic or not

It is a very common question in the interviews. Most times it is asked during white board interviews but sometimes it can be asked during phone interviews.

Following diagram is a linked list without cycle:



Following diagram is a Linked list with cycle:


To find a cycle in the linked list, we will use two pointers. Pointer first and second. In the first iteration, first pointer will point to the next. Second pointer will point to first's next. Following diagram demonstrates this:


After first iteration, first pointer will point to second node, and second pointer will point to second->next->next. Since it contains 3 nodes, after first iteration both the first and second pointer will point to the second node.



Algorithm:

1. Initialize two pointers first and second. First will point to head, second will point to first->next
2. Increment pointer first to first->next and second to second->next->next.
3. Repeat step 2 till second pointer reaches null or meets the first pointer

Complexity:
Time complexity: It will be O(n) since it will traverse through n nodes to find the cycle or reach the cycle's end.

Space complexity: It will be O(1) since constant space is required during algorithm execution.

Implementation:

 
int find_cycle()
{
 node *first, *second;
 first = head;
 second = head;

 //Moving one pointer at the speed of 1 and other at the speed of 2
 while(second->link!=NULL)
 {
  first = first->link;
  second = second->link->link;

  if(first->data == second->data)
  {
   std::cout<<"\nCycle present\t"<link == NULL)
   return NULL;
 }

 //Detecting the start of the cycle.
 first = head;
 while(first!=second)
 {
  first = first->link;
  second = second->link;
 }

 std::cout<<"\nCycle present at:"<data<<"\n";
}

You might also like:

Find White Spaces in Character Array

Find a character in the String

Number is prime or not

Finding Absolute Value

Notes on Sorting and Searching Algorithms

Common String Functions

Reverse a String

Product of all array location expect its own

Find a binomial co-efficient

Remove duplicates from the array

Telephonic phone technical interview questions

Telephonic phone technical interview questions - Part 2

Counting sort algorithm

B-Tree

Points to remember for C and C++ phone interviews

If you are new to technical interviews then you will notice that during phone interviews, conceptual and small questions are asked to gauge the abilities of an individual. Following is the list of some C and C++ questions that can be asked during technical phone interviews. This list shouldn't be referred if your basics of C and C++ are not clear. If you are programming in C or C++ from some time then you might be able to understand most of the points pretty quickly. Hope you find it useful.

1. On some compilers:
1. int is 4 bytes
2. long int 4 bytes
3. double int 8 bytes
4. float = 4 bytes
5. long float = 4 bytes
6. char = 1 bytes
2. signed and unsigned will not affect the size. They will affect the value range
3. Pointer always has same size regardless of where it is pointing.
4. Example of Enum:
1. enum color{Black,white};
2. color c = white;
3. cout<<c<<endl; //c will have the value 0 or 1 for black or white respectively.
5. break; breaks the inner loop only not the outer loop.
6. These all math functions work on: double, float, long double. Since, these functions work on the floating point numbers, we have to use typecasting (int).
1. fabs: Computes the absolute value of a floating point no.
2. abs: Computes the absolute for the integers
3. exp: To compute e^x, where x is a floating point value
4. sqrt: Finds the sqrt
7. Max and Min functions are present in the algorithm library.
8. Memory allocated by malloc, calloc, realloc might not be compatible with the one allocated by new. So manipulation is needed. Hence, malloc and delete & new and free cannot be used interchangeably.
9. void as a data type is not supported
10. Dynamic memory is allocated from system heap
11. If you call break before returning a value then a junk value is returned. 

This pointer basics

1. this pointer stores the address of the class instance, to enable pointer access of the members to the member functions of the class.
2. this pointer is not counted for calculating the size of the object.
3. this pointers are not accessible for static member functions.
4. this pointers are not modifiable. 

Example:

class A
{
  int i;
  public:
  int get()
  {
    return this->i;
  }

  void set(int k)
  {
    this->i = k;
  }
};

Shallow copy 

Shallow copy will just copy one pointer to another pointer
Ex:

void shallow_copy(test *s,test *t)
{
  s->ptr = t->ptr;
}

Deep Copy

Deep copy will allocate the space for the target then using memcpy to copy the value from the source to the target.
Ex:

void deep_copy(test *s,test *t)
{
   t->ptr = (char*)malloc(sizeof(s) + 1);
   memcpy(t->ptr,s->ptr,strlen(s->ptr)+1);
}

Name hiding

Name hiding occurs when:
There is overloading in the base class and inheritance involved.

Ex:

  base:
  display();
  display(int i);

  derived:
  display();

derived_instance.display(1); //It will not work since it will confuse the compiler

How does delete work

delete p: It will delete the memory for single character

delete []p: It will delete the memory for an array

Different ways to access pointers

*(p+i)
*(i+p)
p[i]
i[p]

Why do we use pointer to a pointer in BST?



Because we have the nodes and the traversal in the form of the pointers.
To traverse we need a pointer.

List of Puzzles

It is very common these days to be asked a couple of puzzles during technical interviews. Following is a list of few puzzles that can be asked during your interview. These puzzles are not solved and the list is compiled just to provide you an overview of what might be asked. You can search on the web about different puzzles and there solution.

Question 1:

There is a disk on a turntable. Half of it is black, and the other half is white. It is rotating at constant speed, but it's rotating fast so that you can't see whether it's clockwise or counterclockwise. You also have a set of stationary sensors you can install anywhere which can tell whether the color of a spot has changed from black to white, or vice versa.
What is the minimum number of sensors needed to find out which way the disk is rotating?
What is the best, average, worst time to figure out the direction?
If you use more sensors, can you improve the best, average, worst time?
How can you accomplish that?
If you are given only one sensor, how can you find out the direction, assuming you can change one constraint of the problem?

Question 2:

You have a pile of coins. One of them is counterfeit, and its weight is different from the other coins. All of the other coins weigh the same. You are given a balance. How would you find the counterfeit coin?

Question 3:

There are three buckets with a label each: oranges, apples, oranges + apples. The labels are guaranteed to be wrong, make minimum draws from the buckets and find out which bucket contains what?

Question 4:

Two airline companies, Kingfisher and Jet airways want to do a merger. Design a database migration scheme, so that no inconsistencies and redundancies. Assume suitable data and brief on the problems you might face.

Question 5:

Come up with an architecture for determining how many users are currently playing a game online. How do you scale it up and out? Where are the points of failure? Scale to 10M. Scale to 100M. Scale to 1B.

Question 6:

With two probes, determine the [clockwise/counterclockwise] direction that a plate with 2 different colors (split along a diameter) is spinning.

Find binomial co-efficient

Finding a binomial co-efficient means finding a certain combination. It is represented as nCk, which means finding k possibilities from n outcomes.

Background:
nCk = (n!) / ((n-k)! k!)
For ex: 4C2 will be 4!/(2! . 2!) = 6
So from 4 elements, there are 6 ways to pick up 2 elements. So if elements are a, b, c, d; they can be picked up as:
a, b
a, c
a, d
b, c
b, d
c, d

Approach:
4C2 = 4!/2! * 2! = (1 * 2 * 3 * 4)/ ((1 * 2) * (1 * 2))
So in numerator we are multiplying 1, 2, 3, 4. And in denominator we are multiplying 1*2, 1*2
So our numerator is something which we have to multiple to result and our denominator is something that we have to divide from result.

How to implement it:
If 4 > 4-2 then b = 4-2 = 2
i starts from 0 and goes till < b = 2.
Iteration 1: result = 1 -> result = result * (4-0) = 1 * 4. result = result / 1 = 4
Iteration 2: result = 4 -> result = result * (4-1) = 4 * 3 = 12. result = result/2 = 6

So in each iteration we are multiplying and dividing at the same time. However, we are multiplying starting from n, n-1, n-2 and so on.  And we are dividing with 1, 2, 3..till n-k. Hence the algorithm will be like the following:

Algorithm:
1) If b > n-b then b = n-b.
2) Initialize result to 1 and i to 0.
3) Perform result = result * (n-i) and result = result/(i+1)
4) Increment i by 1.
5) Repeat steps 3, 4 till i <b.

 
int findBinomialCoefficient(int b, int n) 
{
 int result = 1;
 
 if(b > n-b)
  b = n-b;

 for(int i=0; i < b; i++) 
 {
  result *= (n-i);
  result /= (i+1);
 }
 return result; 
}

You might also like:

Find White Spaces in Character Array

Find a character in the String

Number is prime or not

Finding Absolute Value

Notes on Sorting and Searching Algorithms

Common String Functions

Reverse a String

Product of all array location expect its own

Find a cycle in the Linked List

Find a binomial co-efficient

Remove duplicates from the array

Telephonic phone technical interview questions

Telephonic phone technical interview questions - Part 2

Counting sort algorithm

B-Tree

Counting sort

Counting sort will sort the elements of the array on the basis of its array position. It will set the value of array position to 1 and 0 if the element is present or not.

For example if element 10 is present then this sort method will set a[10] to 1. By default a[10] will be set to 0. Then the array a is read one by one. If a[i] is set to 1, then the value will be outputted to entered into a final array. So the output/final array will contain sorted elements.

Algorithm:

1. Initialize i to 0
2. Set count[a[i]] to 1(Set the value at location a[i] to 1).
3. Repeat step 2 till i reaches n-1.
4. Initialize i to 0 again
5. If count[i] is not 0 then initialize j to 0 and output count[i].
6. Repeat step 5 till j < length of(count[i])
7. Repeat steps 5 and 6 till i reaches count.length.

Raw Iterations: 

1. For example if the input array is 10, 30, 20, 30. 
2. Then this algorithm will set a[10] to 1, a[20] to 1 and a[30] to 2.
3. Then it will iterate a from i = 0 to 30 and will output 10, 20, 20, 30

 
public static int a[] = {1,2,8,5,3,6,4,10};
public static int count[] = new int[100];

for(int i=0; i < a.length; i++) 
{
 count[a[i]]++;
}

int k = 0;
for(int i=0; i < count.length; i++) 
{
 if(count[i] != 0)
 {
  for(int j=0;j < count[i]; j++) 
  {
   a[k++] = i;
  }
 }
}

Complexity:

1. Time complexity is O(n) since we iterate through the input array twice.
2. Space complexity is O(n) since we need additional space to store the number of times the element is repeated.

You might also like:
Find White Spaces in Character Array
Find a character in the String
Number is prime or not
Finding Absolute Value
Notes on Sorting and Searching Algorithms
Common String Functions
Reverse a String
Product of all array location expect its own
Find a cycle in the Linked List
Find a binomial co-efficient
Remove duplicates from the array

Telephonic phone technical interview questions

Telephonic phone technical interview questions - Part 2
Counting sort algorithm
B-Tree