## Recent Interview Questions

- 68of 68 votes
You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.

For example,

List 1: [4, 10, 15, 24, 26]

List 2: [0, 9, 12, 20]

List 3: [5, 18, 22, 30]

The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.

- 42of 46 votes
Pots of gold game: Two players A & B. There are pots of gold arranged in a line, each containing some gold coins (the players can see how many coins are there in each gold pot - perfect information). They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has a higher number of coins at the end. The objective is to "maximize" the number of coins collected by A, assuming B also plays optimally. A starts the game.

The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?

At the end I was asked to code this strategy!

- 30of 36 votes
Given an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.

* The sub-arrays should not overlap.

eg- [2 -1 -2 1 -4 2 8] ans - (-1 -2 1 -4) (2 8), diff = 16

I gave him o(n^2) algorithm but he was not satisfied.

- 29of 31 votes
A k-palindrome is a string which transforms into a palindrome on removing at most k characters.

Given a string S, and an interger K, print "YES" if S is a k-palindrome; otherwise print "NO".

Constraints:

S has at most 20,000 characters.

0<=k<=30

Sample Test Case#1:

Input - abxa 1

Output - YES

Sample Test Case#2:

Input - abdxa 1

Output - No

- 28of 30 votes
You are given an integer array, where all numbers except for TWO numbers appear even number of times.

Q: Find out the two numbers which appear odd number of times.

- 24of 24 votes
There is an island which is represented by square matrix NxN.

A person on the island is standing at any given co-ordinates (x,y). He can move in any direction one step right, left, up, down on the island. If he steps outside the island, he dies.

Let island is represented as (0,0) to (N-1,N-1) (i.e NxN matrix) & person is standing at given co-ordinates (x,y). He is allowed to move n steps on the island (along the matrix). What is the probability that he is alive after he walks n steps on the island?

Write a psuedocode & then full code for function

" float probabilityofalive(int x,int y, int n) ".

- 22of 24 votes
Given a large network of computers, each keeping log files of visited urls, find the top ten of the most visited urls.

(i.e. have many large <string (url) -> int (visits)> maps, calculate implicitly <string (url) -> int (sum of visits among all distributed maps), and get the top ten in the combined map)

The result list must be exact, and the maps are too large to transmit over the network (especially sending all of them to a central server or using MapReduce directly, is not allowed)

- 21of 21 votes
You are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number .

NOTE: The array isn't necessarily sorted.

- 20of 32 votes
Give you an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed.

eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.

o(n)time complexity and o(1) space complexity is perfect.

- 20of 22 votes
Given a undirected graph with corresponding edges. Find the number of possible triangles?

Example:

0 1

2 1

0 2

4 1

Answer:

1

- 19of 23 votes
You are given two array, first array contain integer which represent heights of persons and second array contain how many persons in front of him are standing who are greater than him in term of height and forming a queue. Ex

A: 3 2 1

B: 0 1 1

It means in front of person of height 3 there is no person standing, person of height 2 there is one person in front of him who has greater height then he, similar to person of height 1. Your task to arrange them

Ouput should be.

3 1 2

Here - 3 is at front, 1 has 3 in front ,2 has 1 and 3 in front.

- 19of 19 votes
Given two strings a and b, find whether any anagram of string a is a sub-string of string b. For eg:

if a = xyz and b = afdgzyxksldfm then the program should return true.

- 17of 21 votes
Given a BST and a value x. Find two nodes in the tree whose sum is equal x. Additional space: O(height of the tree). It is not allowed to modify the tree

- 16of 18 votes
Output top N positive integer in string comparison order. For example, let's say N=1000, then you need to output in string comparison order as below:

1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...

- 16of 16 votes
If a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.

For example:

Input: "1123". You need to general all valid alphabet codes from this string.

Output List

aabc //a = 1, a = 1, b = 2, c = 3

kbc // since k is 11, b = 2, c= 3

alc // a = 1, l = 12, c = 3

aaw // a= 1, a =1, w= 23

kw // k = 11, w = 23

- 14of 14 votes
Given a 2-D matrix represents the room, obstacle and guard like the following (0 is room, B->obstacle, G-> Guard):

0 0 0

B G G

B 0 0

calculate the steps from a room to nearest Guard and set the matrix, like this

2 1 1

B G G

B 1 1

Write the algorithm, with optimal solution.

- 14of 14 votes
Given an array having 16000 unique integers, each lying within the range 1<x<20000, how do u sort it. U can load only 1000 numbers at a time in memory.

- 13of 15 votes
Design an architecture for REST APIs where you have to upload big data like images/videos etc. Request should be async. Follow up: How will you tune the performance if you have millions of requests coming at same time? Clues: Queueing the request, Storing data in filesystems rather than traditional DB etc.

- 12of 18 votes
Write a program to find whether a given number is a perfect square or not. You can only use addition and subtraction operation to find a solution with min. complexity.

i/p : 25

o/p : True

i/p : 44

o/p: False

- 12of 14 votes
we will name a number "aggregated number" if this number has the following attribute:

just like the Fibonacci numbers

1,1,2,3,5,8,13.....

the digits in the number can divided into several parts, and the later part is the sum of the former parts.

like 112358, because 1+1=2, 1+2=3, 2+3=5, 3+5=8

122436, because 12+24=36

1299111210, because 12+99=111, 99+111=210

112112224, because 112+112=224

so can you provide a function to check whether this number is aggregated number or not?

- 12of 12 votes
Given 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree.

Ex:

2 3 1

2 1 3

will construct the same tree

A1[]={2,1,3}

2

1 3

A2[]={2,3,1}

2

1 3

- 12of 12 votes
A book contains with pages numbered from 1 - N. Imagine now that you concatenate all page numbers in the book such that you obtain a sequence of numbers which can be represented as a string. You can compute number of occurences 'k' of certain digit 'd' in this string.

For example, let N=12, d=1, hence

s = '123456789101112' => k=5

since digit '1' occure five times in that string.

Problem: Write a method that, given a digit 'd' and number of its occurences 'k', returns a number of pages N. More precisely, return a lower and upper bound of this number N.

Example:

input: d=4, k=1;

output {4, 13} - the book has 4-14 pages

input d=4 k=0;

output {1, 3} - the book has 1-3 pages

- 11of 13 votes
There are some glasses with equal volume 1 litre. The glasses kept as follows

`1 2 3 4 5 6 7 8 9 10`

You can put water to only top glass. If you put more than 1 litre water to 1st glass, water overflow and fill equally both 2nd and 3rd glass. Glass 5 will get water from both 2nd glass and 3rd glass and so on..

If you have X litre of water and you put that water in top glass, so tell me how much water contained by jth glass in ith row.

Example. If you will put 2 litre on top.

1st – 1 litre

2nd – 1/2 litre

3rd - 1/

- 11of 11 votes
Given a string which only contains lowercase. You need delete the repeated letters only leave one, and try to make the lexicographical order of new string is smallest.

i.e:

bcabc

You need delete 1 'b' and 1 'c', so you delete the first 'b' and first 'c', the new string will be abc which is smallest.

ps: If you try to use greedy algorithm to solve this problem, you must sure that you could pass this case:

cbacdcbc. answer is acdb not adcb

I can't solve this problem well and the interviewer said that you can scan the string twice. First scan is do some preprocess, and the second is to get the answer, but I really can't come up this idea.

- 11of 11 votes
There are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers?

Ex:

Servers capacity limits: 8, 16, 8, 32

Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8

For this example, the program should say 'true'.

Ex2:

Server capacity limits: 1, 3

Task capacity needs: 4

For this example, program should return false.

Got some idea that this needs to be solved using dynamic programming concept, but could not figure out exact solution.

- 11of 11 votes
Given a sequence of non-negative integers find a subsequence of length 3 having maximum product with the numbers of the subsequence being in ascending order.

Example:

Input: 6 7 8 1 2 3 9 10

Ouput: 8 9 10

- 11of 11 votes
Given an unsorted array of integers, you need to return maximum possible n such that the array consists at least n values greater than or equals to n. Array can contain duplicate values.

Sample input : [1, 2, 3, 4] -- output : 2

Sample input : [900, 2, 901, 3, 1000] -- output: 3

- 11of 11 votes
Given a string, find whether it has any permutation of another string. For example, given "abcdefg" and "ba", it shuold return true, because "abcdefg" has substring "ab", which is a permutation of "ba".

- 11of 11 votes
Give a N*N matrix, print it out diagonally.

Follow up, if it is a M*N matrix, how to print it out.

Example:

1 2 3

4 5 6

7 8 9

print:

1

2 4

3 5 7

6 8

9

This is the question in the phone interview.

Please share more questions.

- 10of 12 votes
Given s string, Find max size of a sub-string, in which no duplicate chars present.