## Math & Computation Interview Questions

- 0of 0 votes
We have a quote file with millions of entries. Design a system to read from the system and return a random quote always with O(1) time. We can read the file once and can keep in memory but should not re read the same. Also when you restart your system, it should preserve and work with O(1) complexity.

- 0of 0 votes
Given a 3x3 tic-tac-toe board with players 1 and 2. Find all the possible ways player 1 can lose given a particular configuration of the board.

For example (0 denotes empty spot):

input:

0, 1, 0

2, 2, 1

1, 1, 2

Output: 1 (because the only move for player 2 to win would be to play board[0,0])

The input board can have any configuration (player 1 and 2 can be in all possible spots with any number).

- 0of 0 votes
Write a program to generate the all possible combinations of a number?

Example: If input is 123, output is 123,132,213,231,312,321.

- 0of 0 votes
Given a Matrix A,

The rules for movement are as follows :

1. Can only move Right or Down from any element

2. Can only move within the row and column of element we start from intially.

3. You can only visit or cross an element if its value is lesser than the value of element you start from.

Find total number of elements one can visit, If one starts from an element A(i,j) where i-> row and j-> column.

Note : You have to print this output for each matrix element.

Input : Matrix

1 2 3

2 3 1

3 1 2

Output:

1 1 3

1 3 1

3 1 1

- 1of 3 votes
Given array of length n, having element 0 to n-1.

you are allowed to swap adjacent element only if Absolute difference of two element is equal to 1.

Is it possible to sort array.

If yes print sorted output.

- 0of 0 votes
Given a number n that represents n lockers and n students. All lockers start closed. First student goes and opens all the lockers. Second goes and toggles 2nd, 4th, 6th.. lockers. Third student toggles 3rd, 6th, 9th.. lockers. Print the lockers that remain open after all students pass.

`public void lockers(int n) { // Implementation here }`

- 0of 0 votes
1. If I say quick sort takes O(e^n ) on the average, would I be wrong?

2. Do you think O( f ) is a good idea for real engineering?

3.Given a choice, what other 'order of' measure would you propose to use ?

4. Do you see a real problem with the modified *order of* ?

5. If you were to sort 10 elements, what sorting method would you have used?

6. If you were to sort 1 trillion unicode characters, what sorting method you would have used?

- 0of 0 votes
We tend to use computer to solve practical problems that actually earns or save dollars. Here is something that happens across the stock exchanges : people buy and sell stocks.

We generally use automated intelligent systems to buy and sell stocks. That part is too much mathematics, and beyond scope of this interview. There is another part. Suppose the system issues a buy order : buy 1000 Microsoft stock. Now, there are more than 1 ( in fact 10 ) active exchanges from where we can buy MSFT. There is a slight price delta, which keeps changing over time. There is another problem. In each stock exchange, prices are stacked, that is :

1. For first 100 stocks prices are 55$.

2. Next 200 stocks, prices are 55.2$.

... etc, and you got the idea. Even this stacks are changing over time.

Thus, here is the problem to solve. Design and implement a system such that one can buy n stocks with minimal price.

Also, in the same spirit, the same system should be able to sell n stocks with maximum payoff possible.

This is a non trivial problem, for Quant systems.

There are always k no of exchanges to hit.

- 0of 0 votes
As you know, Computers were invented to solve practical business problems, we tend to ask practical applied questions. One of the key areas where we want to apply computers is simulation. As most of the people working in software are Engineers, here is the problem. It is called 3 body problem.

3 Bodies with masses [ m1, m2, m3 ] are initially positioned in the 3 points in the space, thus, having positions [ P1, P2, P3 ].

Observe that each Pi is nothing but [ xi, yi, zi ].

Once the initial condition is set, definitely gravity would work and they would start falling against each other. Write code to simulate this problem. Imagine G, the constant of gravity as 1.

How do you go about simulating it?

Hint : feynmanlectures.caltech.edu/I_09.html see 9.5

Face to face. Pen and Paper. Panel Interview, 2 person Panel. 60 Minutes. For Engineers only, was specifically told about it.

- 0of 0 votes
Given an arithmetic expression, write a program to find the value of the expression. Only binary operations that are allowed are +,-,*,/. Also assume that all parentheses are well matched.

Note that the use of eval() is forbidden

Input format :There is a single positive integer T on the first line of input . It stands for the number of expressions to follow.

Next T lines followed by expression

Output format : For each expression print the value of expression

3

19 + 12 / 4 - ((4 - 7) * 3 / 1)

1 + (2 - 3) * 4 + 5 - 6 * 8 - (18 * 12 * 13) - (11 / (5 + 2 + 4))

((2 + 4) / 3 - 2 + 1)

Output:

31

-2855

1

- 0of 0 votes
(x-1)! % x = -1 in efficient way.

- 1of 1 vote
Write function to determine if given unsigned 32-bit number is a power of 3

`int is_power_of_3(uint32_t n)`

return 1 if yes, 0 otherwise.

e.g.`is_power_of_3(27) = 1 is_power_of_3(9) = 1 is_power_of_3(42) = 0 is_power_of_3(0) = 0`

Expected the answer not to be straightforward loop, but something faster.

- 1of 1 vote
Given 2 large number A and B, create a new number C using the digits from A which needs to be grater than B.

e.g. A = 5281, B = 7443

C = 8125.

- 0of 0 votes
given 2 inputs. first one represents sum of two numbers and second one represents there product. print those 2 numbers

ex: i/p 6,8 o/p 2,4

- -2of 2 votes
Round 4

Question 5 : Question 5 : Do you know A/B testing ?, when we tell you some result of an experiment, how do you know the results are accurate ?, actually this question was about the statistics, he asked me many questions to check my statistics knowledge ?

- -1of 1 vote
Dave's Father wants to make chocolates for his birthday. The volume of every chocolate will be 2 cm3. Every chocolate will be cuboid in shape. He has a box of a*b*c dimensions (again a cuboid). Given an input a,b,c write a function to find out if x number of chocolates of 2cm3 volume can fill the box completely. If so, find the number of chocolates too (x).

- 2of 2 votes
You are given a bag with N balls (where the value of N is unknown). Each ball in the bag is uniquely numbered with a value between 1 to N (inclusive) i.e. for each number between 1 and N, there is only one ball with that number. Now you pick a ball from the bag and see its number. You repeat this experiment K times. What is the best possible estimate of the value of N (the number of balls in the bag) you can make from the above experiment (of taking out a ball from the bag K times) in the following cases

a) With replacement

b) Without replacement.

- 0of 2 votes
The text of question below is exactly given by Google interviewer. So they are owner of the text and I am just quoting them. I am not the author of the text below:

"

Imagine a museum floor that looks like this:

.#.G.

..#..

G....

..#..

G == Museum Guard

# == obstruction/impassable obstacle

. == empty space

Write a piece of code that will find the nearest guard for each open floor space. Diagonal moves are not allowed. The output should convey this information:

2#1G1

12#12

G1223

12#34

You may choose how you want to receive the input and output. For example, you may use a 2-d array, as depicted here, or you may use a list of points with features, if you deem that easier to work with, as long as the same information is conveyed.

"

- 0of 0 votes
Write a utility function that takes the starting position (P0) and length (L0) of one line segment plus the start position (P1) and length (L1) of a second line segment and returns the configurations where both segments end at the same point. Both starting points can be anywhere in three dimensional space.

- 1of 1 vote
You toss a fair coin 400 times. What’s the probability that you get at least 220 heads? Round your answer to the nearest per cent.

- 0of 0 votes
//Given a method that takes in a positive non-zero number N, return from that method the total number of factors of N. //Start with O(n) solution and make it faster if we have time

- 0of 0 votes
Implement the divide of two integers without using the divide operator.

After implementing the O(n) algorithm to subtract the divisor from the divider, he asked me to implement a better algorithm.

I started working towards bit manipulation, but ran out of time.

He also hinted that I could have used binary search. Not sure how though.

- 0of 2 votes
There are two coins that make 55 cents. If one of them is not nickle then what are the two coins?

- 2of 2 votes
A bear have to climb a 60.5 feet long hill. It climbs 3 feet in every minute before it fall down for 2 feet. How long it will take to climb the hill?

- 1of 1 vote
Two dices are tossed. Once die is regular and the other is biased with probabilities P(1) = P(6) = 1/6, P(2) = P(4) = 0, P(3)= P(5) = 1/3.

Determine the probabilities of obtaining the sum 4.

- 1of 1 vote
Write a method that takes an int as input and outputs an int with the digits of the input in reverse, i.e. 12345 -> 54321.

- 0of 2 votes
Design a system like friend's functionality in facebook. should have all features of facebook's friends functionality. like for each person , he can have any number of friends , he will get suggestions for new firends , showing common friends if we visits any other profile . algo should be scalable , robust .

- -2of 2 votes
Given an integer Q and an array A of size N, can we figure out the answer to each of the Q queries?

Each query contains two integers x and y, and we need to find whether the value find(x,y) is odd or even:

find(int x,int y)

{

if(x>y) return 1;

ans = pow(A[x],find(x+1,y));

return ans;

}

Here pow(a,b)=ab.

Example: Let N=3, the array be [3,2,7], and the query be x=1 and y=2. Now do find(1,2)=9, which is odd so answer is odd.

I know the basic approach, but what if queries can be as large as 105 and same is with N?

Its given that 1≤x, y≤N, and x≤y

- 0of 0 votes
Unable to get what exactly the Question Is?

so What is the whole logic behind this question .It seems to be complete Math problem to me.

There is a Grasshopper in a tropical forest. The grasshopper can jump only vertically and horizontally, and the length of jump is always equal to x centimeter. A GRasshopper has found herself at the center of some cell of the chess board of the size pxq centimeters(each cell is 1x1 centimeters). She can jump as she wishes for an arbitrary number of times, she can even visit a cell more than once. the only restriction is that she cannot jump out of the board.

The grasshopper can count the number of cells that she can reach from the starting position(x,y). Let's denote this amount by dx,y. your task is to find the number of such starting position(x,y), which have the maximum possible value of dx,y

Input

The integer array contains three integers p,q,x

p= length of the board

q= width of the board

x=length of the grasshoppers jump.

Output

Output the only integer - the number of the required starting position of the Grasshopper

Example

input 2 3 1000000

output 6

input 3 3 2

output 4

Regards,

JSD

- 2of 4 votes
How many squares are present in an NxN grid?

In an MxN grid, how many squares are present and how many rectangles?