Technical Interview Questions: 2015

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:

Initialize two pointers first and second. First will point to head, second will point to first->next
Increment pointer first to first->next and second to second->next->next.
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.

On some compilers:

int is 4 bytes
long int 4 bytes
double int 8 bytes
float = 4 bytes
long float = 4 bytes
char = 1 bytes

signed and unsigned will not affect the size. They will affect the value range
Pointer always has same size regardless of where it is pointing.
Example of Enum:

enum color{Black,white};
color c = white;
cout<<c<<endl; //c will have the value 0 or 1 for black or white respectively.

break; breaks the inner loop only not the outer loop.
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).

fabs: Computes the absolute value of a floating point no.
abs: Computes the absolute for the integers
exp: To compute e^x, where x is a floating point value
sqrt: Finds the sqrt

Max and Min functions are present in the algorithm library.
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.
void as a data type is not supported
Dynamic memory is allocated from system heap
If you call break before returning a value then a junk value is returned.

This pointer basics

this pointer stores the address of the class instance, to enable pointer access of the members to the member functions of the class.
this pointer is not counted for calculating the size of the object.
this pointers are not accessible for static member functions.
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:

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

Raw Iterations:

For example if the input array is 10, 30, 20, 30.
Then this algorithm will set a[10] to 1, a[20] to 1 and a[30] to 2.
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:

Time complexity is O(n) since we iterate through the input array twice.
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

Find products of all locations of an array except its own location

In this algorithm we are asked to find the product of all elements in the array expect the location where the counter is pointing currently.

For example:

If array looks like this 1, 2, 3, 4, 5 where 1 is at location 0, 2 is at location 1 and so on.
The the product array will look like: 120, 60, 40, 30, 25.
120 is the product of 2 * 3, * 4 * 5
60 is the product of 1 * 3 * 4 * 5 and so on.

Approach:

We will first find the product of all elements by going through the entire array. Then at each location we will divide the value found at that location.
For example: 120 is product of 1 * 2 * 3 * 4 * 5
For location 0 we will do 120/1 so at location 0 we have 120.
For location 1 we will do 120/2 so at location 1 we will have 60
For location 2 we will do 120/3 so at location 1 we will have 40

Algorithm:

Initialize a variable product = 1;
Initialize a variable i at 0
Multiply product with a[i] and increment i by 1.
Repeat step 3 till end of array a is reached.
Initialize a variable i at 0
Do product/a[i] and increment i by 1. Store the result in a array location.
Repeat step 6 till end of array a is reached.

Implementation:

 void arr(int a[MAX])
{
 int product = 1;

 for(int i=0;i < MAX;i++)
   product = product * a[i];

 for(int i=0;i < MAX;i++)
   a[i] = product/a[i];
}

int main()
{
 int a[4] = {1,2,3,4};

 for(int i=0;i < 4;i++)
   std::cout <<  a[i] <<  "\t";
 arr(a);

 std::cout <<  std::endl;

 for(int i=0;i < 4;i++)
   std::cout <<  a[i] <<  "\t";

 getch();
 return 0;
}

Complexity:
O(n) for the time complexity since we iterate through the entire array twice.
O(1) for space complexity.

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
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

How will you reverse a string

Reversing a string is a simple operation and it is often asked in telephonic interviews or first round of interviews. If input string is 'Hello World' then reversed string will look like 'dlroW olleH'. If the string is stored in an array then the operation is very simple because we just need to swap the characters at two pointers.

Algorithm:

Initialize two pointers one at location 0 and other at length of the string. Let's name them i and j.
If location of i is less than or equal to location of j then swap the characters at location i and j.
Increment i counter.
Decrement j counter.
Repeat steps 2, 3, 4 till the condition in step 2 is met.

Implementation

reverseString()
{
 String names[] = {"a","b","c","d","e","f"};
 int i=0,j=5;
 String temp;

 while(i<=j)
 {
    temp = names[i];
    names[i] = names[j];
    names[j] = temp;
    i++;
    j--;
 }
}

Complexity:
The time complexity of this algorithm is O(n) since we have to go through all the locations of the array or string. The space complexity is O(1) since we didn't need additional space for this.

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
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

Serialization and Deserialization in Java

Imagine that you have to send a java object to someone via a network or you want to store it in the db or in memory. If you are looking to perform any of these operations then Serialization will help you.
Serialization will transform the object to bytes so that it can be stored in the DB or memory or sent via a network. Deserialization on the other hand, will transform the bytes to the object.

In java Serialization and Deserialization can be achieved by implementing 'Serializable' interface. It is a Marker interface in which the implementing class don't have to implement any functions of the interface.

In the following example 'Student' object contains name and id. Since the object is implementing 'Serializable' interface we can define 2 methods that will serialize and deserialize.

 //Define a class that needs to be serialized and de-serialized
public class Student implements Serializable {
    String sName;
    int sId;
}

Following serializeStudent method will write the object to the file stream that is named as 'Student.ser'. Similarly, deserializeStudent method will read the file stream and convert it to the Student object.

Implementation:

   
//Serialize it 
public class serializeStudent {
   Student s = new Student();
   s.sName = “jack”;
   s.sId = 1;

   try {
       FileOutputStream fs = new FileOutputStream(“Student.ser”);
       ObjectOutputStream os = new ObjectOutputStream(fs);
       os.writeObject(s);
       os.close();
      }
}

 //DeSerialize it
public void deserializeStudent {
   FileInputStream fin = new FileInputStream(“FileName”);
   ObjectInputStream ion = new ObjectInputStream(fin);
   Student sObject = (student)oin.readObject();
}


You might also like:


Java Concepts

Java String concepts

Immutable classes in Java

Remove duplicates from the array

Telephonic phone technical interview questions

Telephonic phone technical interview questions - Part 2

Jersey Package Dependencies

Observable and Observer Interface

Servlet Filter

Servlet Client Request

Spring dependencies for Maven

Java String Operations

Telephonic interview Technical Questions

Question 1: Find top n queries.

This problem is best solved with hash map. However, there are iterative approaches too. Take a look at the 2 solutions below.

There are 3 approaches:

Let’s say there is a file and queries are stored in it with their date.
Get the queries till a specific date and sort them in descending order.
Top n entries will be your top n.

2nd Approach

Calculate hash code of each query.
In a hash map, put the hash code as the key value and its count as hash value.
Once all queries are covered, the one with top n largest hash values will be top n queries.

Space complexity: O(n)

Time complexity: O(n.logn)

Disadvantage: If there are millions of queries, you will have to calculate its hash code and store it before hand. Hashmap’s size might increase in value too.

Question 2: How will you find a random element between a range min to max

Call a standard random function of Math library. x = Math.Random();
Calculate the range: range = max - min;
Add 1 to range since max value will be excluded. range = range + 1;
Calculate sum by multiplying a random number to the range. sum = x * range (
Add min to sum to shift it to the start of min value. Random Element = sum + min.

Question 3: If you are given 2 binary trees how will you output them in ascending order.

Traverse them in order and store the values in 2 arrays.
Apply merge sort on them. It will output the array values in ascending order.

Question 4: Find if a point lies inside a triangle

To solve this, we will be using property of triangle were area of 3 triangles is equal to one

If the area of all 3 is equal to a bigger triangle then the point lies inside it.

Area((x1,y1) (x2,y2) (x,y)) + Area((x1,y1) (x3,y3) (x,y)) + Area((x1,y1) (x2,y3) (x,y) = Area((x1,y1) (x2,y2) (x3,y3)).

Find Area of triangle:

A1 = (x1 * (y2-y3) + x2 * (y1-y3) + x3 * (y1-y2))/2.0;

Question 5: How to find out if a number is multiple of 3 without using divide operator

Find number of odd bits that are set.
Find number of even bits that are set.
Find difference. If the difference is a multiple of 3 then the number is 3’s multiple

Question 6: Function to check if singly LL is palindrome

Get the middle of the linked list.
Reverse the second half of the LL.
Iterate the first half and second half. Compare elements one by one. If element comparison matches then proceed to next element. Or else break.
If you reach end of both LL then it is a palindrome.

Question 7: Good Design Principles

It should be highly cohesive and loosely coupled
DRY (Don't Repeat Yourself) - Put Common values to public final constant
Don't put common code at one place for unrelated things.
Make variables private then update or change access modifier to protected or public
Follow open closed design principle: Open for extension, closed for modification
Follow IOC: Inversion Of Control. Dependency injection through some config instead of adding it in the code.
Favor composition over inheritance

Question 8: 4 OO Principles:

Abstraction
Polymorphism
Encapsulation
Inheritance

Question 9: BFS vs DFS

BFS should be avoided for the larger trees since it uses large amount of memory to tack all children of current node. DFS has lower memory requirements.

Question 10: Sorting Algos

If you have small number of elements then use insertion sorn.
If elements are > 100 then use Heap, merge, quicksort,
If elements are > 5000 then use external memory sorting algorithm.
nlogn algorithms are not stable since order is not maintained.
If you have uniform or random distribution then use bucket sort.
If you know the range of elements to be sorted then use counting sort.
For very large number of elements use multi-way merge sort or load the data into B-Tree and do inorder traversal.

Question 11: Searching Algos

Linear Search
Binary Search
Use self-organizing lists. Recently accessed elements moves to the front.

Question 12: What are dynamic arrays?

When array grows in size & reaches it capacity then its capacity is increased.
If size threshold is reached then its size is increased till its capacity is reached.

Question 13: B-Trees

Each node contains multiple elements/values
Internal node contains values.
Insertion, deletion, lookup are O(logn)
Use in case of range queries.

Question 14: Difference between HashSet, HashMap, HashTable:

HashSet has no mapping of the key value pairs. The elements are just added to it. They are not added in any order.
HashMap has the mapping of the key value pair. It is unsynchronized and hence, gives a better performance. It allows null for key value pairs. You can add null key value pairs, you will not get the NullPointerException.
HashTable is the mapping of the key value pair. Synchronized so only thread can operate on it. It doesn’t all null for the key value pair. It will return NullPointerException if we have such values.

Question 15: How to get 10 largest elements from the array?

We can use insertion sort 10 times and the top 10 elements will come up. It will be 10 * n complexity.
Or we could construct the min heap and then extract the top 10 elements out of it.
Or sort the file and then tail -10. This means the sorted file will contain the 10 largest elements at the bottom part.

Question 16: If we have an array of numbers and all of them are appearing even no. of times bult only one appear odd number of times. How will you find it?

Solution: xor all the numbers. The odd counted number will be the output.

2n+1 numbers are given and 2n are unique. Only one is not. So xor all the numbers and then result will be one number that was excluded.

Algorithmic approach: Sort->O(nlogn) and keep a count = 2n. For every new element load the counter and when you are scanning that particular element decrement the counter by 1. For element with count = 2n+1 the counter will be decremented to -1. Hence, we found the element.

Telephonic phone technical interview questions

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

Common Design Questions

Here is the list of common design questions that are asked in technical interviews.

Design a parking garage
Design a deck of cards
Design an aeroplane reservation system.
How would you design a chat system
Design Game of Life
Design Chess Game
Design a system for a parking lot
Design a poker game
Design a Farm with Object Oriented Concepts
Design a restaurant reservation system.
Design a JukeBox
Design a file system
Design a recommendation system
Design the Boggle Game. (Given a 4x4 character matrix, output all possible words by moving through the matrix)

Technical Interview Questions

Pages

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

Points to remember for C and C++ phone interviews

List of Puzzles

Find binomial co-efficient

Counting sort

Find products of all locations of an array except its own location

How will you reverse a string

Serialization and Deserialization in Java

Telephonic interview Technical Questions

Common Design Questions

NoSQL

Search This Blog