SDE - 1 Hike interview experience | Anonymous

Interview rounds

Round

Medium

Face to Face

Duration60 minutes

Interview date24 Apr 2015

Coding problem3

Technical Interview round with questions on DSA.

1. Running Median

Hard

46m average time

50% success

0/120

Asked in companies

You are given a stream of 'N' integers. For every 'i-th' integer added to the running list of integers, print the resulting median.

Print only the integer part of the median.

Problem approach

To solve this question, the concept of heaps can be used. Two heaps can be maintained: a max heap for storing lower half of the numbers and a min heap for storing greater half of the numbers.
Process each element one by one :
1 To add an element to one of the heaps:
Condition : Check if next item is smaller than maxHeap root add it to maxHeap,else add it to minHeap
Step 2: Balance the heaps (after this step heaps will be either balanced or one of them will contain 1 more item)
Condition : If number of elements in one of the heaps is greater than the other by more than 1, remove the root element from the one containing more elements and add to the other one
Step 3: Now to calculate median:
If the heaps contain equal amount of elements;
median = (root of maxHeap + root of minHeap)/2
Else
median = root of the heap with more elements

The time complexity of this approach would be O(nlogn) and auxiliary space complexity is O(n).

Try solving now

2. Pair Sum in BST.

Easy

15m average time

85% success

0/40

Asked in companies

You are given a Binary Search Tree (BST) and a target value ‘K’. Your task is to return true if there exist two nodes in the given BST such that the sum of their values is equal to the given target ‘K’, else return false.

A binary search tree (BST) is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.

• The right subtree of a node contains only nodes with data greater than the node’s data.

• Both the left and right subtrees must also be binary search trees.

Note:

1. All the elements of the Binary Search Tree are unique.

2. You can’t use the same node value/element of BST twice.

For example:

tree: 8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
'K' = 13,

The nodes with values 8 and 5 as shown in the above figure gives sum equal to the given target 13. 

Therefore, the output will be “true” i.e it is possible to find a pair in the given BST having sum equal to ‘K’.

Problem approach

This problem can be solved using hashing. The idea is to traverse the tree in an inorder fashion and insert every node’s value into a set. Also check if, for any node, the difference between the given sum and node’s value is found in the set, then the pair with the given sum exists in the tree.
Time Complexity :O(n).

Try solving now

3. Statistics From A Large Sample

Moderate

25m average time

75% success

0/80

Asked in companies

You have been given a sample of integers in the range [0, 255]. Since the sample is quite large, you are provided with an array/list “count” whose i-th element denotes the number of times ‘i’ appears in the sample.

You are supposed to calculate the following statistics :

1. minimum: The minimum element in the sample.

2. maximum: The maximum element in the sample.

3. mean: The average of the sample, calculated as the total sum of all elements divided by the total number of elements.

4. median:
If the sample has an odd number of elements, then the median is the middle element once the sample is sorted.
If the sample has an even number of elements, then the median is the average of the two middle elements once the sample is sorted.

5. mode: The number that appears the most in the sample. It is guaranteed to be unique.

Problem approach

The basic idea of this approach is to iterate through the sample twice. In the first iteration, we will get the minimum, maximum, mean and mode. In the second iteration, we’ll find the median of the sample

Try solving now

Round

Medium

Face to Face

Duration60 minutes

Interview date24 Apr 2015

Coding problem3

Technical Interview round with questions on DSA. A puzzle was also asked.

1. LRU Cache Implementation

Moderate

25m average time

65% success

0/80

Asked in companies

Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:

1. get(key) - Return the value of the key if the key exists in the cache, otherwise return -1.

2. put(key, value), Insert the value in the cache if the key is not already present or update the value of the given key if the key is already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting the new item.

You will be given ‘Q’ queries. Each query will belong to one of these two types:

Type 0: for get(key) operation.
Type 1: for put(key, value) operation.

Note :

1. The cache is initialized with a capacity (the maximum number of unique keys it can hold at a time).

2. Access to an item or key is defined as a get or a put operation on the key. The least recently used key is the one with the oldest access time.

Problem approach

Structure of an LRU Cache :

1) In practice, LRU cache is a kind of Queue — if an element is reaccessed, it goes to the end of the eviction order
2) This queue will have a specific capacity as the cache has a limited size. Whenever a new element is brought in, it is added at the head of the queue. When eviction happens, it happens from the tail of the queue.
3) Hitting data in the cache must be done in constant time, which isn't possible in Queue! But, it is possible with HashMap data structure
4) Removal of the least recently used element must be done in constant time, which means for the implementation of Queue, we'll use DoublyLinkedList instead of SingleLinkedList or an array.

LRU Algorithm :

The LRU algorithm is pretty easy! If the key is present in HashMap, it's a cache hit; else, it's a cache miss.

We'll follow two steps after a cache miss occurs:

1) Add a new element in front of the list.
2) Add a new entry in HashMap and refer to the head of the list.

And, we'll do two steps after a cache hit:

1) Remove the hit element and add it in front of the list.
2) Update HashMap with a new reference to the front of the list.

Tip : This is a very frequently asked question in interview and its implementation also gets quite cumbersome if you are doing it for the first time so better knock this question off before your SDE-interviews.

Try solving now

2. Sorting Of A Rotated Sorted Array

Easy

10m average time

90% success

0/40

Asked in companies

Given a rotated sorted array of size ‘N’ and let the elements of the given array be a1,a2,......,an . You need to sort the given array in increasing order.

For Example - Consider ‘N’ = 4 and the given array is [2,3,4,1] then the output should be [1,2,3,4].

A rotated sorted array is a sorted array in which each element is shifted ‘x’ (‘x’ >= 0 and ‘x’ <= ’N’) times to its right and the rightmost element is shifted to the beginning of the array.

For Example - [3,4,1,2] is a rotated sorted array in which each element is shifted two times to its right.

Problem approach

A simple solution would be to first find the point of rotation and then rotate the array.
1. Find the split point where the sorting breaks.
2. Then call the reverse function in three steps.
- From zero index to split index.
- From split index to end index.
- From zero index to end index.

This solution can be optimised by using binary search instead of linear search to find the rotation point.
Steps :
1. First find the index of minimum element (split index) in the array using binary search
2. Then call the reverse function in three steps.
From zero index to split index.
From split index to end index.
From zero index to end index.

Try solving now

3. Puzzle

5 Pirates and 100 Gold Coins

Problem approach

The answer is 98.
A uses the facts below to get 98.

Consider the situation when A, B, and C die, only D and E are left. E knows that he will not get anything (D is senior and will make a distribution of (100, 0). So E would be fine with anything greater than 0.
Consider the situation when A and B die, C, D, and E are left. D knows that he will not get anything (C will make a distribution of (99, 0, 1)and E will vote in favor of C).
Consider the situation when A dies. B, C, D, and E are left. To survive, B only needs to give 1 coin to D. So distribution is (99, 0, 1, 0)
Similarly, A knows about point 3, so he just needs to give 1 coin to C and 1 coin to E to get them in favor. So distribution is (98, 0, 1, 0, 1).

Round

Easy

HR Round

Duration30 minutes

Interview date24 Apr 2015

Coding problem1

HR round with typical behavioral problems.

1. Basic HR Questions

Q1. Do you have a good work ethic?
Q2. Why Hike?

Problem approach

Tip 1 : The cross questioning can go intense some time, think before you speak.
Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.
Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round, like what are the projects currently the company is investing, which team you are mentoring. How all is the work environment etc.

SDE - 1

Interview preparation journey

Interview rounds

1. Running Median

You are given a stream of 'N' integers. For every 'i-th' integer added to the running list of integers, print the resulting median.

Print only the integer part of the median.

2. Pair Sum in BST.

You are given a Binary Search Tree (BST) and a target value ‘K’. Your task is to return true if there exist two nodes in the given BST such that the sum of their values is equal to the given target ‘K’, else return false.

A binary search tree (BST) is a binary tree data structure which has the following properties.

Note:

For example:

3. Statistics From A Large Sample

You have been given a sample of integers in the range [0, 255]. Since the sample is quite large, you are provided with an array/list “count” whose i-th element denotes the number of times ‘i’ appears in the sample.

You are supposed to calculate the following statistics :

1. LRU Cache Implementation

Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:

You will be given ‘Q’ queries. Each query will belong to one of these two types:

Note :

2. Sorting Of A Rotated Sorted Array

Given a rotated sorted array of size ‘N’ and let the elements of the given array be a1,a2,......,an . You need to sort the given array in increasing order.

For Example - Consider ‘N’ = 4 and the given array is [2,3,4,1] then the output should be [1,2,3,4].

A rotated sorted array is a sorted array in which each element is shifted ‘x’ (‘x’ >= 0 and ‘x’ <= ’N’) times to its right and the rightmost element is shifted to the beginning of the array.

For Example - [3,4,1,2] is a rotated sorted array in which each element is shifted two times to its right.

3. Puzzle

1. Basic HR Questions