Technical Interview Questions: 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.