Algorithm Interview Questions
- 0of 0 votes
AnswersApparently DESCO asked it. It was faulty, and I am fixing it. The physics was wrong. A mono pole is an abstract magnet with either the north or the south pole of the magnet.
[ en.wikipedia.org/wiki/Magnetic_monopole ]
Imagine you are given such *n* monopoles, all of the same type, say North type. Thus, all of these repel one another. The force of repulsion follows inverse square law :
[ en.wikipedia.org/wiki/Inverse-square_law ]
That is, given two such monopoles with a distance *r* between them, the force of repulsion between them is given by :F = ( 1.0 ) / ( r ** 2 )
Now, suppose you are also given an array of *n* number of positions over X axis, like : [ 0, 1, 4, 10 , 21 , .. ] where you need to place the monopoles ( imagine they are hold tight there, and do not move away ).
- NoOne October 18, 2016 in United States
After placement, you are given another monopole, of different type S, say. Find positions to place the monopole so that it is stable.
Fixes from the original question :
[geeksforgeeks.org/d-e-shaw-interview-experience-set-19-on-campus/ ]
1. Monopoles exhibit inverse square law, not inverse law.
2. It is impossible to have stable configuration using same type monopole, so one must use another type, repulsion is not stable, attraction is.
( Terrible physics mistakes )
PS. Do not try to do binary search here. Binary search assumption is underlying linearity of the structure, thus, effectively there are proportionate elements in left and right. In the classic cases of sorted array, the expectation is 50/50. But here due to non linearity (inverse square) , it won't work.| Report Duplicate | Flag | PURGE
Deshaw Inc Software Developer Algorithm - 0of 0 votes
AnswersWrite a code to convert from long type time to date using java?
- sambasivareddy.s October 15, 2016 in United States
Eg: 324561092314 to 02/20/2015| Report Duplicate | Flag | PURGE
Intuit Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersWrite a code to find index of integer item in an integer array using java? Note : Complexity should be less than O(n) or with out using any for loop.
- sambasivareddy.s October 15, 2016 in United States| Report Duplicate | Flag | PURGE
Intuit Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersFind the shortest path between a start node and end node in a undirected +ve weighted graph.
You are allowed to add at max one edge between any two nodes which are not directly connected to each other.
ex:
From | To | Weight
1 2 2
1 4 4
2 3 1
3 4 3
4 5 1
start node = 1, end node = 5.
extra edge weight = 2.
- JerryGoyal October 15, 2016 in United States1----(2)----2 | | | | (4) (1) | | | | 5-(1)-4----(3)----3 In this case answer would be 3 (from 1 - > 5 - > 4) Solution: 1----(2)----2 /| | / | | (2)/ (4) (1) / | | / | | 5-(1)-4----(3)----3
| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
AnswersGiven a set of numbers, find out all subsets of the set such that
the sum of all the numbers in the subset is equal to a target number.s = [ 1, 2, 3, 4, 5 ] target = 5 op = [ [ 1,4 ] , [2,3] , [5] ]
Application: Given a fixed budget, and work items we are doing back filling to check what all we can attain with the budget.
Continuation. Imagine the set is actually a set of work items, with cost and utility involved :def work_item : { name : 'foo bar' , cost : 10 , utility : 14 }
Now, solve this to maximise utility.
Continuation. Imagine that the work items are related, so that, if work item w1 is already in the
subset of the work items selected, w2 's utility increases further!.
( Can you imagine how it can happen? Effectiveness of Mesi increases when he plays for Barca)
So, you are given a list like this :w1 -> normal utility 14, with w2 20, ....
Now maximize payoff.
NOTE: Payoff is a matrix. This comes from game theory.
Hence, a payoff matrix looks like :w1 w2 w3 w4 .... w1 w1 w2 w2 w3 w3 w4 w4
A cell ( i,j) is filled up with if a list contains both wi and wj, then how much the payoff would be. It is a symmetric matrix.
- NoOne October 15, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersWe 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.
- NoOne October 15, 2016 in India
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.| Report Duplicate | Flag | PURGE
Goldman Sachs Software Engineer / Developer Algorithm Cache Computer Architecture & Low Level Computer Science Distributed Computing Large Scale Computing Math & Computation Software Design - 0of 0 votes
AnswersAs 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.
- NoOne October 15, 2016 in India
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.| Report Duplicate | Flag | PURGE
Software Developer Algorithm Computer Science Graphics Math & Computation Programming Skills - 0of 0 votes
AnswersGiven a convex polygon ( is planer as opposed to a polytope) and a point one had to tell if the point lies inside the polygon or outside the polygon.
- NoOne October 14, 2016 in India
To understand convexity : mathopenref.com/polygonconvex.html
Thus the question comprise of 3 sub problems :
1. How to store a polygon.
2. How to define inside and outside of a polygon.
3. How to solve the actual one, given 1,2 ?| Report Duplicate | Flag | PURGE
Deshaw Inc Software Developer Algorithm - 0of 0 votes
AnswersLinux has this nice command called *tree*.
- NoOne October 14, 2016 in India
If you did not use it, please take a look around.
You do not have to write one. BUT, you have to do something similar. Given a file name ( not a path ), and an initial directory, you have to list all the file paths, which matches the file name, case should not be considered.
Also allow regex match.
Again, the problem is non trivial.
It was expected to ask the right questions.| Report Duplicate | Flag | PURGE
SDET Algorithm Operating System - 0of 0 votes
AnswersThere is this nice tiny *nix utility called *wc*.
The idea here is :wc file_name
prints :
- NoOne October 14, 2016 in India
character count of the file.
Word count of the file.
Line count of the file.
You have to implement your own *wc* program.
NOTE: The problem is non trivial for 3 reasons.
It was expected to ask about the non triviality.| Report Duplicate | Flag | PURGE
SDET Algorithm Operating System - 0of 0 votes
AnswersNone actually understands how garbage collection works, albeit people ask this in the interviews. Nonetheless, we are going to ask you something very similar. Here is the problem.
Take an array of bytes, perhaps 1MB in size.
Implement these two operations:ptr_structure = alloc ( amount_of_storage ) freeed = free ( ptr_structure )
Now, here is your problem. alloc must allocate contiguous storage. If it is not possible, you need to compact ( defragment ) memory. So, you need to implicitly write a :
defragment() // defragments memory
Worse is coming. Even imagining you have written a stop the world defragmenter, after you reallocate, how the ptr_structures would actually work?
- NoOne October 14, 2016 in India
Solve this whole problem.
Time allocated was 1 hour. Face to face, panel with 2 interviewers.| Report Duplicate | Flag | PURGE
SDET Algorithm Assembly Computer Architecture & Low Level Computer Science Data Structures - 0of 0 votes
AnswersImagine there are brick boulders, all of integer size.
Their sizes are stored in an array.
The figure looks something like this :
peltiertech.com/Excel/pix2/Histogram2.gif
Now, suppose someone is pouring water into it till water starts spilling.
You have to answer how much water the boulders are holding up.
- NoOne October 14, 2016 in Indiadef water_holding( arr ) { /* answer this */ }
| Report Duplicate | Flag | PURGE
Deshaw Inc SDET Algorithm - 0of 0 votes
AnswersXPATH implementation problem.
- NoOne October 14, 2016 in India
Here is the problem.
Implement XPATH expressions, given there is a DOM tree :
1. $x('//*[text() = "abc"])
How do you think it is implemented? Write code, imagine you have a general purpose tree.
2. $x('//span[text() = "abc"])
How do you think it is implemented? Write code, imagine you have a general purpose tree.
Now, explain which one would be faster, and why?
Explain from the design and the code you have written.| Report Duplicate | Flag | PURGE
SDET Algorithm Application / UI Design - 0of 0 votes
AnswerAs you know, every OS comes up with this tiny application called the calculator. It is good. Now, here is our problem. If we try to implement the function
def calculate( operand, operator, operand ) { /* Do Interviewers bidding here */ }
I have to write if upon if upon if upon if to do for all operators. Moreover, some operators are not even binary! Take example the abs() or say the negate()!
- NoOne October 14, 2016 in India
Bigger problem persists. With the if mode, we can not even add operators as we wish to without changing code!
But that is a sin. So, what do we do? That is question 1.
In question 2, as a software tester, how do you propose to test and automate the above? Writing more if than the developer is not allowed.| Report Duplicate | Flag | PURGE
SDET Algorithm Data Structures Object Oriented Design Programming Skills Software Design - 0of 0 votes
AnswersWe all know databases are very very slow. In fact they are so slow that very serious people who wants to do volumes of read operation and search operations write their own implementation. In this question, you would be asked to do the same, for a very limited operation - select.
Every item stored has this field called timestamp.
Now, here is the problem you need to solve :select items where time < some_time select items where time < some_time and time < another_time select items where time > some_time
Imagine you have millions of data rows. How to store it in HDD, and how to load, entirely your problem. None is going to insert anything on existing data - only read.
- NoOne October 14, 2016 in India
Write an algorithm that solves this problem, and a data structure that works as storage for the data.| Report Duplicate | Flag | PURGE
SDET Algorithm Database - 0of 0 votes
AnswersYou are given 20 questions to solve in 20 minutes.
- NoOne October 14, 2016 in India
If you successfully solve the question, you would receive 2 marks.
If you failed to solve the question, and you do not try it ( let it untouched ) , you would receive 0 marks. If you solve it wrong ( i.e. not the correct answer ) - you would receive -1 ( negative) .
With the story, here are the problems:
1. Write an algorithm, which, given an input array ( set ) of questions, and varying probability ( 0 <= p <= 1 ) of can do and can not do per question, generates a strategy for solving the paper to generate maximum expected pay off.
2. Given the question paper is multiple choice, between 4 choices ( a,b,c,d ) do a bias analysis ( e.g. if more a's are coming than 'c's ), and decide if you would like to probabilistically take risk and mark some to increase pay off.
Obviously, you can get a maximum 40, and a minimum -20.
3. Now, put yourself in the position of the examiner, and try to ensure it is almost impossible to increase payoff by random selection over the questions. Try to negate the bias. That is question 3.
In all 3 cases write an algorithm. Face to face interview, time allocated was 60 minutes. Panel Interview.| Report Duplicate | Flag | PURGE
unknown SDET Algorithm - 0of 2 votes
AnswersGiven a list of shops each of which have a list of toys with their prices and max number of children who can play with it at a time. Output the a list of best possible toy option from each shop given the number of children who are shopping.
- mesmerizing.memories123 October 14, 2016 in India
ToyShopping
{
getListOfBestToysFromEachShop(List<Shop> shops);
}
Shop
{
int id,
List<Toy> listOfToys;
}
Toy
{
int toyId;
int shopId;
int price;
int maxChildren; //max number of children who can play with this toy
}| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -1of 1 vote
AnswersGiven an un-directed weighted graph G(V,E), find the minimum weight between two given nodes X & Y
- gsharma34065 October 14, 2016 in India
(i.e. sum of weights of edges between X & Y).
You can add an extra egde with weight W between any two nodes in the graph exactly one time (if required).| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersFind the n'th Ugly no. An ugly no. is defined as a no. which are of the form :
n = ( 2 ** p ) * ( 3 ** q ) * ( 5 ** r )
with p,q,r >= 0 and are integers not all equal to zero.
- NoOne October 12, 2016 in United States
You must not memorise the whole sequence, as n can be really large.
Hint : use number theory to figure out the pattern of the increasing sequence.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersYou are a string conscious guy. You categorise strings into 3 types: good, bad, mixed. If a string has 3 consecutive vowels or 5 consecutive consonants or both, it is bad. Else it is good. If a string has ‘?’, that can be replaced with any character. Thus, string ‘?aa’ can be bad if ‘?’ is vowel or good if consonant. Thus, it is mixed. Implement function which takes string s as input and returns good, bad or mixed
- novicedhunnu October 11, 2016 in India| Report Duplicate | Flag | PURGE
Adobe SDE1 Algorithm - 0of 0 votes
AnswersYou are a musician who plays different songs at different volumes. You have a particular difference that needs to be present for new song, but you don't care if it is more or less. You are given initial volume l, array of volume changes where arr[i] is volume change required after i-th song, max_vol h (min vol always 0), array size n. You need to find the max possible volume for the last song. But if at any point change is not possible, return -1. Format: n, arr[n], l, h. Ex: 3, 1 1 1, 0, 5. Ans: 3. Ex: 4, 9 1 5 4, 8, 15. Ans: -1. Ex: 3, 5 3 7, 5, 10. Ans: 10.
- novicedhunnu October 11, 2016 in India
Input explanation :
First number = size of array,
then next ‘n’ numbers of array.
Then ‘l’ means initial volume
Then ‘h’ means max volume.
Eg. 3, 1 1 1, 0, 5 means n = 3, arr = {1,1,1}, l = 0, h = 5,
Output explanation: initially you play music at vol 0, then for first arr element. Arr[0] inc. by 1,
Arr[1] inc. by 1, arr[2] inc by 1 total = 3| Report Duplicate | Flag | PURGE
Adobe SDE1 Algorithm - 0of 2 votes
AnswersHey guys, I was asked this question on Bloomberg's pre-interview screening exam and I was wondering how to go about it.
- it_tech_guy October 11, 2016 in United States
Find the tightest asymptotic bound for:
T(n) = n(T(n/2)^2)
so far I was able to get it to look like this (not sure if correct):
T(n) = 1 / (1 + T(n/2)^2)
From then I made a recursion tree which led me to think that T(n) might be exponential in this case. Do you have any idea where could I go from here? Do you think this has no tight asymptotic bound?| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Algorithm - 0of 0 votes
AnswersProgram to Print below number sequence
- yogesh.malhotra85 October 10, 2016 in India
If(n=3)
then
1*2*3
7*8*9
4*5*6
if n=5
1*2*3*4*5
11*12*13*14*15
21*22*23*24*25
16*17*18*19*20
6*7*8*9*10
Can anyone also tell me what kind of pattern it is?
Correct me If something is wrong.| Report Duplicate | Flag | PURGE
Algorithm - 2of 2 votes
AnswersGiven infinite supply of coins of denominations 25, 10, 5 and 1, find the distinct number of ways to use the coins to sum up to the given value
- rajansthapit October 10, 2016 in United States| Report Duplicate | Flag | PURGE
Adobe Software Engineer Algorithm - 3of 3 votes
AnswersGiven an array of 1 billion numbers with just a few 100 missing, find all the missing numbers. you have only enough memory to store only 10k elements
- PS October 07, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersGiven a string s, return all the palindromic permutations ( without duplicates), of it. Return an empty array if no palindromic combinations can be formed.
- NS October 04, 2016 in United States| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 0of 0 votes
AnswersGiven a string, determine if a permutation of a string can form a palindrome.
- NS October 04, 2016 in United States| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 0of 0 votes
AnswersString Rotation. Given two string check if String1 is rotating match for String2
- Saurabh October 03, 2016 in United States for Software Developement - Tools# Given two strings. Write a function that will return true if one string is a rotation of the other string. # e.g. 'bca' and 'cab' are rotations of 'abc' and the function should return true # 'barbazfoo', 'oobarbazf' and 'rbazfooba' are rotations of 'foobarbaz' def is_rotation(string1, string2):
| Report Duplicate | Flag | PURGE
Linkedin Software Developer Algorithm - 14of 14 votes
AnswersWrite a program to check whether it is a valid binary tree or not. Check all test cases (e.g. No left Node case).
- Neelavan October 02, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersYou are given a matrix of size n*m and need to count the number of submatrices which which have atleast k occurances of x and atleast two corner elements equal. Submatrices should have minimum two rows and two columns.
- sukhmeet032795 October 01, 2016 in United States
Example:
1 2 3
1 3 6
22 1 33
output: 4
i.e
a)
1 2
1 3
b)
1 2 3
1 3 6
c)
1 2
1 3
22 1
d)
1 3
22 1| Report Duplicate | Flag | PURGE
Sabre Holdings Software Developer Algorithm