Interview Questions 15

1. Input Data : {[1,3],[2,4],[10,11],[4,6]}
Output: {[1,6],[10,11]}
We have to merge all the ranges that are overlapping. You can consider Input data as any Data structure.

2. Given a char array with words in it, find all ‘a’ characters and replace with xyz. Modify the input array, do not create a copy of the array.

3. How do you output the nodes from a binary search tree given a range

4. Implement a function
public long[] GetMultiplesOfTwoLessThan(int num)
eg if num is given as 30, output array should contain {1,2,4,8,16}. It shouldn’t contain 32 since 32 is more than the given number.

Another exp: if num is 300 then output will be {1,2,4,8,16,32,64,128,256}
Super optimized solution desired

5. Write a program to arrange numbers from 1 to 16 such that the sum of two consecutive numbers is a perfect square.

6. Print all edge nodes of a complete binary tree anti-clockwise.
That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.
In other words, print the boundary of the tree.

Variant: Print the same for a tree that is not complete.

7. Given 3 product categories and a respective file of a huge size containing only the list of order numbers in sorted manner. Write an algorithm (best possible time complexity to be achieved) which can find common order numbers in all 3 files.

8. Implement boolean ValidateIP(string inpIP)

9. Given a file in which the data is stored in the form

ABC
_DEF
_GEH
XYZ
_PQR
__STY

Construct an nary tree out of it in O(n) time such that DEF and GEH are the children of ABC and XYZ is the sibling of ABC, PQR is child of XYZ and STY is child of PQR. The spaces after the beginning of a line specify the relation of a node to its predecessors.

10. Why auto variables are not stored in heap?

11. Each cell of an N x N grid is either a 0 or a 1. You are given two such N x N grids, the initial grid and the final grid. There is a button against each row and each column of the initial N x N grid. Pressing a row-button toggles the values of all the cells in that row, and pressing a column-button toggles the values of all the cells in that column. You are required to find the minimum number of button presses required to transform the grid from the initial configuration to the final configuration, and the buttons that must be pressed in order to make this transformation.

Interview Question 14

1. Given a line segment of length n. You need to cut it into m pieces specified by position[n] array. The price of cutting a segment of length len in two parts is always len (irrespective of cut position). Give a dynamic programming solution to minimize the cost of cutting.

2. Given a BST, print all the values >=vmin and <=vmax. Time complexity should be better than O(n). O(logn + (vmax-vmin)) in worst case.
No parent pointers are available.

3. You have a huge graph of cities and cost of flight between them. Find the cheapest path from A to B. The graph doesn’t fit in memory.

4. Write a function

int count_div(int a,int b,int k);

That given three integer numbers a, b and k return number of integers from range [a..b] divisible by k, i.e.:
For example, for a=6, b=11, and k=2, your function should return 3, because there are 3 numbers divisible by 2 in the range [6..11], namely 6, 8 and 10.
You can assume that , and k>0.

5. Given is an array of integers. Element is called an extreme if no other element’s value is more distant from the average. Write a function

int extreme(int[] A);

That given an array of integers returns the index of an extreme (any one of them if there are many).

If no extreme exists, the function should return -1.
A[0]=9, A[1]=4, A[2]=-3, A[3]=-10
the index of an extreme is 3, because the average of the array is
(9 + 4 + (-3) + (-10)) / 4 = 0
and in this array no value is further from 0 than -10

6. Say you need to design a web application which needs to support friends of friends function(like in linked in, when you search a person, it will show you if this person is linked with you, your connection or your connections’ conection…), we expect to have millions of users and each user may have thousands of friends, how would you design/implement this function to make it scalable.

7. Given two n digit prime numbers, change the first number to the second by changing one digit at a time. The resulting intermediate numbers should also be prime.

8. Given an input array of integers of size n, and a query array of integers of size k, find the smallest window of input array that contains all the elements of query array and also in the same order.

9. There is an array
A[N][M] =
1 2 3
4 5 6
The array is rotated so that
A'[M][N] =
3 6
2 5
1 4
is obtained.
Establish the relation between A and A’ by using i, j, M, N

A[i][j] = A'[_][_]

10. Given a list of strings say N, how would you write a perfect hash function and ensure 0 collissions?

Interview Questions 13

1. Give a string, print total count of substrings (length>=2) which are palindromes. He was expecting better than O(n2) time complexity.

2. How do you implement a linked list without using dynamic memory allocation? So basically you need to use an array as a linked list.

3. Give an algorithm to compress a memory. To be more clear if you are given a memory of some stored data here and there and some empty and null memory in between, how will you fragment and compress your memory?

4. Given a 3d plane, and infinite points find kth closest point from a given point.

5. Given a statement which took an integer, incremented it by 1 and then branched to another location which you provide, implement addition of two numbers multiplication, etc using just that statement

6. You dont know the required size of the array.how will you allocate space for the array.for eg. if you allocate 100 blocks then user can have just 10 elements or 1000 elements.

7. What happens after entering URL address at the browser(details of how we get to see the web page)?

8. Sorted Array is rotated n times. You have to find the current index of the some element X. If element is not present then return the maximum element of the array in O(log n).

9. There is an array consisting of postive and negative integers. find the subarray whose sum is 0.

10. Given a dictionary of words and a string with all spaces removed, return whether the string is composed of valid words
e.g
helloworld-> hello world (valid)
isitniceinhere-> is it nice in here (valid)
zxyy-> invalid

Interview Questions 13

1. You are in a maze(like a labyrinth), and you open your eyes so you don’t know your position. The maze has walls and you can move only in up, right, left and down directions. You can escape the maze when you find a ladder.
The following API is given:
bool TryMove(direction) – returns true when you don’t hit a wall;
bool HasLadder() – return true if you found the ladder.
Write a method bool Explore() that returns true if you can escape the maze, false otherwise. Also, provide test cases.

2. Given a MxN matrix, in how many ways can you go from top-left to bottom-right?

3. You have given a node of a tree. that node is defined as below:
struct Node {
int value,
struct Node *left;
struct Node *right;
struct Node *grandparent;
} node;

At the starting the grand parent node is null in the tree. you have to assign the grandparent node for all the nodes in the tree.

4. Write pattern matching algorithm.
i.e isMatch(String,Pattern)
Pattern can have ?(one character) and *(many characters).
ex. abbdef and a?b*f are a match
aaabab and a*ba are not a match

5. Pretend there is a robot that has to navigate a maze (N x M). The robot can only move down or right and the maze can contain walls. Write an algorithm to determine the number of paths the robot can take. [Tricky :)]

6. Write a function to find the nearest link on a webpage given the mouse x,y coordinates.
If your algorithm just iterates through all the links, give an idea of how to make it faster.

7. In C++, write functions for:

string serialize(vector v);
vector deserialize(string s);

such that a string returned from ‘serialize’ can be passed into deserialize to get the original set of strings back.

8. There is a byte array which contains the character of one byte and two bytes. One byte character has range 0 to 127 and first character of 2 byte character is 128 to 255 and second byte character has range 0 to 255. Now, two pointers are given, one points to the start of the and another points to somewhere else.
Tell which character 2nd pointers points to?

9. You have a graph with and start point A and end point B. All edges have positive weights. Now the shortest path from A to B can be found using Djikstra.
a) Find the kth shortest path
b) Find the longest path

10. Many overlapping rectangles – want to return which (doesn’t matter which one, if it’s over several) rectangle the mouse is over.

%d bloggers like this: