## Algorithm Interview Questions

- 0of 0 votes
On google search, how to enable key word auto completion after a few letters typed.

Follow-up: How to rank the words if they are weighted by frequency?

- 1of 1 vote
Find largest sub-array?

- 1of 1 vote
You have two servers. Both of these servers have an identical file with billion characters except for one single character. These servers are connected over a very slow connection.

How do you find the different character?

My ans: split those files in to batches of characters of 10,000 (say), now calculate checksum and compare the checksums for the chunks of 10,000 character lines. So now you are just comparing 'ints' and not the files per say. (remember the connection is very slow)

His question: How do you optimize this?

- 0of 0 votes
Find the longest cycle in a graph ?

- 0of 0 votes
Cross the River

Saatwik, an elite programmer love the woods. Once he was in one of his trips to the mighty Himalayas , he encountered a strange problem. As we all know that, Himalayas has abundant river streams and forests. While travelling in one of the forest, he was trapped by the river stream flowing. As the stream flow was fast, he couldn't cross by swimming across water, he must find some other way to cross it.

River is present throughout the X axis and its boundary is marked by y coordinates (i.e. from y=A to y=B) .

--------------------------------------------------------------------------------- (y=A)

..................................................................................................

..................................................................................................

..................................................................................................

---------------------------------------------------------------------------------- (y=B)

Now, You are provided with some rocks along with their centres and radius respectively. Currently Saatwik is present on the shore having y=B . We can't jump between the rocks but we can move from one rock to other if both overlap at some points. You need to tell whether Saatwik will be able to cross the river by using any number of rocks or not . If he can, then output the minimum number of rocks taken to achieve it otherwise output −1

Input :

First line of input will contain T denoting number of test cases. For each of the test cases, First line will contain N denoting number of rocks. From second line onward, there will be N lines containing 3 integers X,Y,R where (X,Y) denotes the coordinates of the centre of that rocks and R stands for its radius. Last line will contain two integers A and B denoting the upper and lower boundary of the river respectively.

Output:

Output the required answer in a separate line for each of the test case.

Constraints :

1≤T≤10

1≤N≤5000

−109≤X,Y,A,B≤109

1≤R≤109

B<A

Sample Input

1

3

1 1 2

1 2 1

3 4 1

3 0

Sample Output

1

Explanation

At first we can step onto the first rock from the river shore. Then we can cross river directly or can move to second rock and then cross it. Note that we can't use third rock as it is beyond the reach from the other rocks.

Time Limit: 2.0 sec(s) for each input file

Memory Limit: 256 MB

Source Limit: 1024 KB

- 0of 0 votes
Given an array A of size N, where the ith integer of the array is A[i] and has a value ranging between 1 and 1000 inclusive, you need to help Monk with the following task :

Given 3 additional numbers K, X and Y, you need to report the number of un-ordered pairs of elements (i,j) from this array, such that (1≤i<j≤N), (A[i]+A[j])%K=X, and (A[i]×A[j])%K=Y.

Input Format :

The first line contains 4 space separated integers N, K and X and Y. The next line contains N space separated integers where the ith integer denotes A[i].

Output Format :

Print the required number of ordered pairs of array elements on a single line. As the answer could be rather large, beware of integer overflows.

Constraints :

2 ≤ N ≤ 10 raised to power 5

1 ≤ K ≤ 10 raised to power 6

0 ≤ X, Y < K

1≤A[i]≤1000

Sample Input

5 2 1 0

1 2 3 2 1

Sample Output

6

- 1of 1 vote
Given a set of possibly overlapping rectangles in different levels (All of which are "not rotated", can be uniformly represented as (left-bottom,right-top) tuplets), return a minimal set of (non-rotated) non-overlapping rectangles, that occupy the same area.

The rectangle at lower level has more priority than at higher levels.

- 0of 0 votes
There is dedicated Samsung software for coding test the question is given below:

There is one spaceship. X and Y co-odinate of source of spaceship and destination spaceship is given. There are N number of warmholes each warmhole has 5 values.

First 2 values are starting co-ordinate of warmhole and after that value no. 3 and 4 represents ending co-ordinate of warmhole and last 5th value is represents cost to pass through this warmhole. Now these warmholes are bi-direction.

Now the to go from (x1,y1) to (x2,y2) is abs(x1-x2)+abs(y1-y2).

The main problem here is to find minimum distance to reach spaceship from source to destination co-ordinate using any number of warm-hole. It is ok if you wont use any warmhole.

- 0of 0 votes
list1 -->aaa,bbb,ddd,xyxz,...

list2-->bbb,ccc,ccc,hkp,..

list3> ddd,eee,,ffff,lmn,..

Inside a list the words are sorted

I want to remove words which are repeated across the list and print in sorted order

If the words are repeated in same list its valid.

In the above case

it should print aaa-->ccc-->ccc-->eee--->fff-->glk-->hkp-->lmn-->xyxz

- 2of 2 votes
Write a function that receives a position in 2 dimensional (x,y) array, which was initially initialized with 'o' (signals "water"), the function changes the value/state of that position to 'x' (signals "land") and returns the number of isles in the board.

For example, for 3x3 board, it will initially look like the following:

o o o

o o o

o o o

After calling the function with the position (1,2), the board will look like the following:

o o x

o o o

o o o

and the functions returns 1

An isle is defined as 'x' surrounded horizontally and vertically with 'o'

In the following board there is only one isle

o o o

o x x

o x o

- 0of 0 votes
Find top n cities which got most orders. For example, amazon got a list of orders, and these orders will be shipped to different cities.

- 1of 1 vote
I got my interview yesterday and the problem they asked me was: Giving a method intToEnglish that receives an int as a parameter, how do you return its representation in english words. The number can be of any size but no more than around 2 billion since the parameter is an int 2ˆ32

- 2of 2 votes
# There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room.

# For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words:

# Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.

# For example:

# input = [(1,4), (2,3)]

# > 3

# input = [(4,6), (1,2)]

# > 3

# input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}

# > 11

- 0of 0 votes
I recently had a take home assignment for a optimization engineer position at FB. I got 24 hours to finish it however it was suggested to finish under 90 minutes. The problem was to calculate the dot product of sparse matrix (optimize for speed). I wrote following code but got dinged. Not sure what's wrong to not clear even first stage!

`#include <iostream> #include <string> #include <map> #include <sstream> using namespace std; class SparseVector{ private: map<int, double> m_map; int m_size; public: SparseVector(int size){ this->m_size = size; this->m_map = *new map<int, double>(); } void setValue(int i, double value){ if( i < 0 || i > m_size) return; if(value == 0.0){ map<int, double>::iterator it = m_map.find(i); if(it != m_map.end()) m_map.erase(it); } else m_map[i] = value; } double getValue(int i){ if( i < 0 || i > m_size) return 0.0; else { map<int, double>::iterator it = m_map.find(i); if(it != m_map.end()) return it->second; else return 0.0; } } int getSize(){ return m_size; } static double s_dotProduct(SparseVector a, SparseVector b){ if (a.m_size != b.m_size) return 0.0; double sum = 0.0; if (a.m_map.size() <= b.m_map.size()) { for (map<int, double>::iterator it = a.m_map.begin() ; it != a.m_map.end(); it++) if ((b.m_map.find(it->first)) != b.m_map.end()) sum += a.getValue(it->first) * b.getValue(it->first); } else { for (map<int, double>::iterator it = b.m_map.begin() ; it != b.m_map.end(); it++) if ((a.m_map.find(it->first)) != a.m_map.end()) sum += a.getValue(it->first) * b.getValue(it->first); } return sum; } template <typename T> static string s_ToString(T val) { stringstream stream; stream << val; return stream.str(); } static string s_printSparseVector(SparseVector a) { string s = ""; for (map<int, double>::iterator it = a.m_map.begin(); it!= a.m_map.end(); it++) s += "(" + s_ToString(it->first) + ", " + s_ToString(it->second) + ") "; return s; } }; int main(int argc, char *argv[]){ int lenA = 0, lenB = 0, setValA = 0, setValB = 0; cout << "Enter length for Sparse vector A : " << endl; cin>> lenA; cout << "Enter length for Sparse vector B : " << endl; cin>> lenB; SparseVector v1 = SparseVector(lenA); SparseVector v2 = SparseVector(lenB); double y; int x; cout << "Enter number of set values for Sparse vector A : " << endl; cin >> setValA; cout << "Enter the set Index, Value pair in separate lines" << endl; for(int i = 0; i < setValA; i++){ cin >> x; cin >> y; v1.setValue(x, y); } cout << "Enter number of set values for Sparse vector B : " << endl; cin >> setValB; cout << "Enter the set Index, Value pair in separate lines" << endl; for(int j = 0; j < setValB; j++){ cin >> x; cin >> y; v2.setValue(x, y); } cout <<"Sparse Vector1 = " << SparseVector::s_printSparseVector(vectorA) << endl ; cout <<"Sparse Vector2 = " << SparseVector::s_printSparseVector(vectorB) << endl; cout <<"Dot product of two sparse vectors is = " << SparseVector::s_dotProduct(vectorA, vectorB) << endl; return 0; }`

- 0of 0 votes
Array consist of -1 and 1, Find count of all sub-arrays where sum = 0.

Ex. [-1,1,-1,1]

Ans : 4

[-1,1] [1,-1],[-1,1],[-1,1,-1,1]

Ex. [-1,-1,1,1]

Ans : 2 [-1,1][-1,-1,1,1]

- 0of 0 votes
Write a iterator wrapper to remove duplicates from collections without using temporary storage.

For Example:

ArrayList A = {RAT,CAT,BAT}

ArrayList B = {RAT,CAT,MAT}

ResultIterator itr = new ResultIterator();

itr.next() should display {RAT,CAT,BAT,MAT}

Program skeleton:

class ResultIterator {

ResultIterator(iterator itr1, iterator itr2) {

}

bool hasnext {

// implement this method

}

E next() {

// implement this method

}

}

- 1of 1 vote
Find the median of an unsorted array.

Have to do better than O(nlogn) time.

e.g.

Given [2, 6, 1] return 2

Given [2, 6, 1, 4] return 3 which is sum of the two elements in middle over 2

- -1of 1 vote
You are given a series of moves as a string, such as ">^V<^". You need to output a list with all the series of moves that represent a loop if they were made by a robot for example.

A loop is defined as a series of moves that lead to the same position, for example "><" or "^V".

In the case of "^>V<^" the output should be ["^>V<", "^>V<"], essentially the last move generates a new loop because it leads to a position that was visited before and that naturally can be followed up to the same position and describe a loop.

- -1of 1 vote
Consider a hotel where the guest is checked in and check out. Find a day when the maximum number of guests stay in a hotel.

example:

Input :

[

{check-in : 1, check-out 4},

{check-in : 2, check-out 5},

{check-in : 10, check-out 12},

{check-in : 5, check-out 9},

{check-in : 5, check-out 12}

]

Output : 5

- 0of 0 votes
Given number N, Find the least number of perfect square number sum needed to get N.

Example :

n=5 (4+1) i.e. 2

n=7 (4+1+1+1) i.e. 4

n=12 (4+4+4) i.e 3

n=20 (16+4) i.e. 2

- 0of 0 votes
You are given an array A[] with n elements. You are given S[], E[] and H[] array with each M elements.

Apply an operation such that all the elements from A[ S[i] ] and A[ E[i] ] will be less than H[i].

Example :

given array A[] = [2,4,8,6,7]

S[0] = 1

E[0] = 4

H[0] = 5

So, after doing an operation, the resulting array is A[] = [ 2,4,5,5,5]

Thus, u need to do the same thing for all i.

After doing this, find out the maximum element in the array.

- 0of 0 votes
Giving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.

eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple"

I was thinking of the following approach,

Build a Trie for all words in the Dict - O( n * k) where k is the longest string in the dict

For each character c, in S check if there is a word in Trie that starts with it and has the letters that appear in S after c. We can short circuit based on remaining characters and the length of longest string found so far.

This should take O( N * k) where N is length of S.

- 1of 1 vote
/**

Given many coins of 3 different face values, print the combination sums of the coins up to 1000. Must be printed in order.

eg: coins(10, 15, 55)

print:

10

15

20

25

30

.

.

.

1000

*/

- 1of 1 vote
Find all comments in the Java (it could be Python or any other language of your choice) codes that’s parsed in as a string.

You may assume the codes given is valid.

Input is a single string, e.g.

String codes =

“/* file created by aonecode.com\\n” +

“ welcome to the tech blog*/ \\n” +

“//main method\\n” +

“public static void main(String[] args) { \\n“ +

“ System.out.println(“//welcome”); //output\\n” +

“}”

Output is a list of strings

List<String> ret =

[

“ file created by anecode.com\n welcome to the tech blog”,

“main method”,

“output”

]

- 2of 2 votes
Q: If you were given a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C]

and then another series [A != C, D != H, ..., F != A ]

Check whether the equations combined is valid.

For the example given, your program should return 'invalid', because the first series implies that A = C, which contradicts the statement A != C in the second series.

- 0of 0 votes
Considering a server that should ignore requests older than 1 second, create a structure to handle this behavior and give its complexity.

Use any language you want.

- 0of 0 votes
Implement, recursively, fast exponentiation and give its complexity.

Use any language you want.

- 0of 0 votes
Design the movement algorithm of a snake from snake game and give its complexity. You can base your idea of algorithm in whatever design for the game. eg. a matrix to represent the grid, use a linked list to represent the snake...

Use any language you want.

- 0of 0 votes
Create a structure to store the median of people ages and give its complexity. If keeping ordered ages, also give the insertion complexity.

Use any language you want.

- -1of 1 vote
I was asked the following: Given integers N and A. Find how many integer sequences with elements between 1 and A have sum of all elements equals to N.

N, A <= 1000.

Sample input: 4 3 , sample output is 7.

In this moment, I realized I do not understand the question. If I have a sequence of 1,2,3, the only sub-sequence that sums 4 is 1,3. So the answer should be 1. What am I missing?

Thank you