Status: Pre-final year, B Tech CS Top 10 CS schools in India
Position: SDE Intern at Visa
Location: Bangalore, IN
Date: Feb 19, 2020

Online Assessment
4 questions. 90 mins

Question 1 - Median Array
Given an array of n elements and m queries, you have to find the median for each query.
i.) For each given query, an integer 0<=x<=n-1 is given to you
ii.) Select the prefix of length x from the array
iii.) Find all possible integers u i such that for all i, 0<=i<=x, a[i] = a[i%u]
where 1<=u<=x+1
iv.) Make a sorted array of all the possibilities
v.) Print the median of this array

Constraints :
1 <= n <= 1000
1 <= m <= 1000
0 <= x <= n-1

Sample Input :
n = 3
Sample Output:
[]

Question 2 - Minimum Distance
Given a n*m matrix, we have to travel to a point (x_f, y_f) from a point (x_i, y_i). The cost of travelling from ith to i+1th row is given in rows array and the cost of travelling from jth to j+1th column is given in cols array. Find the minimum cost of travelling from (x_i, y_i) to (x_f, y_f) if we can move only in up, down, left, right directions.

Sample Input:
x_i = 0, y_i = 0, x_f = 1, y_f = 2
rows = [2, 5], cols = [6, 1]
Sample Output:
9

Explaination:
We can move down and right to the destination.
Follow the path as (0, 0) -> (1, 0) -> (1, 1) -> (1, 2)
Cost for the above path is 9.

Question 3 - Merge Palindrome

Given two strings as str1 and str2, find out a longest and lexicographically smaller palindrome that will be formed using the palindromes as obtained by str1 and str2.

Sample Input:
str1 = aaaabbbccc
str2 = ddeeccc
Sample Output:
aabcccdeedcccbaa

Explaination:
aacbcbcaa is a palindrome formed using str1
deccced is a palindrome formed using str2
aabcccdeedcccbaa is a palindrome made using aacbcbcaa and deccced.

Question 4

In-person Interview

Technical Round

1. What data structure to use when we are given millions of data ?
   Ans - Array or Linked List

2. What is the difference between lists, arrays, linked lists. Compare the time complexity for all the operations on all of these.
   Ans - Basic theory of DSA

3. How to traverse a tree?
   Ans - DFS and BFS (level order traversal)

4. Perform DFS on a tree
   Ans -
   Method 1 : Used recursion
   Method 2 : Used stack

5. What are the different types of learning (as I had mentioned Machine learning and deep learning) Explain all of them.
   Ans - Supervised, unsupervised, reinforcement learning

6. Give some real world applications of unsupervised learning.
   Ans - Image segmentation can be done based on colors and objects. Algorithms - K means clustering, etc. (I had done 1 project on this topic. So i was able to explain him sufficiently enough)

Some more basic theory questions from DSA.

HR
Tell me about yourself.
What are your hobbies
What do you do in free time
How will Trump's visit be beneficial for India.

Some more basic personality testing questions. :)

Hints and Solutions
Q1 - Use dp and solve the question. Time complexity will be O(n^2)

Q2 - We doesn't need to care the optimum path as all the paths will have the same cost

[[0, 6, 7],
[2, 8, 9],
[7, 13,14]]

This matrix shows the cost to go to any point from (0, 0)

Q3 - Generate all possible palindromes and check for the longest lexicographically smaller one.