Algorithm Interview Questions
- 0of 0 votes
AnswersA is [4,3,2,0,1]
- chill_bill January 17, 2016 in United States
B is [E,D,C,A,B]
Constant space and O(n) Sorting such that
A is [0,1,2,3,4,]
B is [A,B,C,D,E]| Report Duplicate | Flag | PURGE
JP Morgan freshers Algorithm - -3of 3 votes
Answersdsgfd
- Niki92 January 16, 2016 in United States| Report Duplicate | Flag | PURGE
X Jr. Software Engineer Algorithm - 0of 0 votes
Answersconvert a number m to n with minimum operations. The operations allowed were -1 and *2.
- Rahul Sharma January 13, 2016 in United States
For Eg : 4 and 6. Answer is 2.
1st operation : -1 -> 4-1 = 3.
2nd operation : * -> 3 * 2 =6.| Report Duplicate | Flag | PURGE
Software Developer Algorithm - 0of 0 votes
AnswersThere is a car company and customers ask the car company for 'n' cars for start - end time intervals.
- rishab99999 January 13, 2016 in India
A company can get multiples request for the cars, find the minimum numbers of cars that the car company should have, to satisfy all the requirement for the given list of time intervals:
Eg :
for interval 1-3 cars needed are 2
for interval 2 -3 cars needed are 3
for intervals 3-4 cars needed are 4
for intervals 5-6 cars needed are 2
Answer is 5 for above, as we there is overlap between interval 1-3 & 2-3| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 2 votes
AnswersHow many Fibonacci numbers exists less than a given number n.Can you find a function in terms of n , to get the number of fibonacci number less than n.
- Rahul Sharma January 13, 2016 in United States
Example : n = 6
Answer: 6 as (0, 1, 1, 2, 3, 5)| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 3of 3 votes
AnswersATM has x currency notes of 100 rupee,y currency notes of 500 rupee,and z currency notes of 1000 rupee notes.
- rajat sadh January 10, 2016 in India
Customer wants to withdraw n amount at any given time. as per bank rules,Customer can not withdraw more than INR.40000/-per transaction.
If ATM is running out of cash it should throw a message that insufficient Balance, Kindly enter multiple of m value of currency note.where m>=4000 and m<=total number of cash available in ATM.
An intelligent banker has found in customer survey that customer prefers to receive more than 5 currency notes 100 rupee,more than 2 currency noes of 500 rupee and rest of the currency notes is of 1000 rupee where ever possible.
If amount is less than 500,customer will receive 100 rupee currency notes. Bankers goal is to tender the minimum number of currency notes to save customer waiting time and increase customer satisfaction by following customer survey.Banker has hired you to program ATM dissaptch function.
FOR Example: Lets ATM has 200 currency notes of 100 rupees,90 currency notes of 500 rupee and 50 currency notes of 1000 rupee.Customer has placed a withdrawal request of Rs 22,200.00. Dispatch function has given him 7 currency notes of 100,3 currency notes of 500 and 20 currency notes of 1000 rupee| Report Duplicate | Flag | PURGE
Adobe SDE1 Algorithm - 1of 1 vote
AnswersGiven a decimal number, write a function that returns its negabinary (i.e. negative 2-base) representation as a string.
- JP Ventura January 09, 2016 in United States#!/usr/bin/env python3 assert solution(-15) == '110001' assert solution(2) == '110' assert solution(13) == '11101'
| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow can I count frequencies of all elements of an array?
- HimanshuP January 05, 2016 in United States| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersYou have a function f1() that generates 0 or 1 with the equal probability. Write a function f200() that generates a number between 1 and 200 with equal probability.
- holdnet January 04, 2016 in United States| Report Duplicate | Flag | PURGE
Big Fish SDE-2 Algorithm - 3of 3 votes
AnswersGiven 4 teams and 3 gamedays, create an algorithm such that each team plays another team every gameday and by the end of the 3 game days each team should have played one game with every other team.
- popeye123 January 03, 2016 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm Problem Solving - 0of 0 votes
AnswersGiven an array of ints (positive numbers) find out the index that balances the array. If no such index exists, return the index that minimizes the difference.
- tamashionuth January 02, 2016 in United States
How can you do it by touching each element only once.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 0of 0 votes
AnswerInsert an int into a circular single linked list.
- tamashionuth January 02, 2016 in United States
Discuss corner cases: what if the element to be inserted is the smallest, how can we speed things up (e.g. if the method is called multiple times you can keep track of the "last"/greatest element).
Thorough testing discussions.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 2of 2 votes
AnswersGiven a number (integer) as a string turn in into a number:
- tamashionuth January 02, 2016 in United States
E.g. "One million two hundreds thousands fifty seven" => shoud return 1200057.
How to model it and how to test it? What data structures would you use. Deep testing (corner cases)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 1of 1 vote
AnswersGiven a number N, write all possible sums of consecutive numbers that add up to N.
- tamashionuth January 02, 2016 in United States
That is:
return all pairs (a, k) such that a+(a+1)+...+(a+k)=n
After that:
1. what if N is negative or a is negative;
2. what if N is real and the possible implications of this| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 0of 0 votes
AnswersCreate a program to compute nth Fibonacci number in O(1) space and faster than O(n) time.
- zr.roman January 02, 2016 in Russia
(Target complexity is O(logn)).| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 0of 0 votes
AnswersDesign a datastructure which stores employee details Name,PhoneNumber,Addres and the employee details are(all the 3 given above) fetched when the user searches the data structure by Name or phone number
- Rajarathinam Antony December 29, 2015 in India| Report Duplicate | Flag | PURGE
ThoughtWorks SDE1 Algorithm - 2of 2 votes
AnswersGiven an undirected graph and a node, modify the graph into a directed graph such that, any path leads to one particular node.
- neer.1304 December 25, 2015 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersFind if a given binary tree has duplicate sub trees or not.
- neer.1304 December 25, 2015 in United States
(Two leaf nodes of a parent do not count as subtree)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersImage an airport with the control tower having a constantly rotating radar scanning for airplanes. The radar's coordinates in the 2-d plane are (0,0). The radar has an API: void scan(const Plane &P) that is called periodically whenever the radar detects a plane. You can imagine that the Plane structure has x,y coordinates for that plane. You should fill in the function Scan, such that at any given time you are able to return the 100 closest planes to the tower (0,0).
- Johnybegood December 24, 2015 in United States for Derivatives| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Algorithm - 7of 7 votes
AnswersFind missing element in the A.P.
- poojaarora014 December 22, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDET Algorithm - 0of 0 votes
AnswersImplement the power function with o(logN) time complexity and O(1) space
- poojaarora014 December 22, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDET Algorithm - 0of 0 votes
Answers
- Desi Joe December 22, 2015 in United Statesinterface RangeContainerFactory { /** * builds an immutable container optimized for range queries. * Data is expected to be 32k items or less. * The position in the “data” array represents the “id” for that instance * in question. For the “PayrollResult” example before, the “id” might be * the worker’s employee number, the data value is the corresponding * net pay. E.g, data[5]=2000 means that employee #6 has net pay of 2000. */ RangeContainer createContainer(long[] data) } /** * a specialized container of records optimized for efficient range queries * on an attribute of the data. */ interface RangeContainer { /** * @return the Ids of all instances found in the container that * have data value between fromValue and toValue with optional * inclusivity. The ids should be returned in ascending order when retrieved * using nextId(). */ Ids findIdsInRange(longfromValue, long toValue, boolean fromInclusive, boolean toInclusive) } /** * an iterator of Ids */ interface Ids { /** * return the next id in sequence, -1 if at end of data. * The ids should be in sorted order (from lower to higher) to facilitate * the query distribution into multiple containers. */ static final shortEND_OF_IDS = -1 short nextId() } Validation: Your implementation should pass the following simple JUnit test before you start tuning for performance with volume data: public class RangeQueryBasicTest { private RangeContainer rc @Before public void setUp(){ RangeContainerFactory rf = new YourRangeContainerFactory() rc = rf.createContainer(new long[]{10,12,17,21,2,15,16}) } @Test public void runARangeQuery(){ Ids ids = rc.findIdsInRange(14, 17, true, true) assertEquals(2, ids.nextId()) assertEquals(5, ids.nextId()) assertEquals(6, ids.nextId()) assertEquals(Ids.END_OF_IDS, ids.nextId()) ids = rc.findIdsInRange(14, 17, true, false) assertEquals(5, ids.nextId()) assertEquals(6, ids.nextId()) assertEquals(Ids.END_OF_IDS, ids.nextId()) ids = rc.findIdsInRange(20, Long.MAX_VALUE, false, true) assertEquals(3, ids.nextId()) assertEquals(Ids.END_OF_IDS, ids.nextId()) } } FAQ Can't we just use a B-Tree/ NavigableMap/HashTable/BinarySearch/Lucene... Sure, if you want. But there are a number of things we'd like to achieve: ● The container will be in memory and will need to hold lots of data, so we'd like it to be as space efficient as possible, but not to the extent where speed is significantly compromised. Speed is king, memory/disk can be purchased. ● Since we hate collecting garbage, we need to be careful about memory allocation during a query, as my grandmother told me, "allocate not, gc not". ● Code should be clear and understandable. ● The rough order of trade off to consider for this case is: search performance, efficient usage of memory, simplicity and maintainability of the code These objectives are often at odds - we'd like to explore what's possible.
| Report Duplicate | Flag | PURGE
unknown Software Developer Algorithm - 0of 0 votes
AnswersGiven an array of five integers that represents a poker hand e.g. [2,2,2,3,3] return the value of the hand, valid values are only "pair","two pairs","three of a kind","full house","four of a kind" we don't have to worry about straight, flush or straight flush.
- DanOG99 December 15, 2015 in United States
My approach was to have a fixed array of 13 elements (each element represents one possible value of the hand) this array will keep the occurrence of each value of our hand and after we have all the values we just iterate this array and multiply all the values by itself and adding them to get a unique result.
For example if we have [2,2,3,4,5] our fixed array will have a "2" and three "1" so our result will be "2*2+1*1+1*1+1*1",the result will be 7, so all the possible hands will have unique values, if we find a 7 as a result we will know it is a pair, a 9 will be two pairs, a 11 will be three of a kind, 13 will be a full house and 17 will be a four of a kind.
This algorithm is O(1) both in complexity and space but the interviewer didn't like it too much.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 0of 0 votes
AnswersAssume that garbage collector is not there in place or you are implementing a garbage collector for C++. Write the design and sample code for garbage collector implementation
- johnsvakel December 15, 2015 in India for Endpoint Computing
We have 3 classed and Class A, B, C. object of A uses object B and Object of B uses Object of C. How can we track the object existence and clear memory ?
Answer which I suggested : Write a tree (or Graph?)data structure (Garbage collector is a container class holds this data structure) where each node has multiple paths to reach. If any of the node is not having a path to reach then we can clean that memory. This way the garbage collection will work. Please suggest your design as well.| Report Duplicate | Flag | PURGE
VMWare Inc Member Technical Staff Algorithm - 0of 0 votes
AnswersWhat is the maximum leads that can be generated from ad budget of 30k. Below is the table provided:
- Prasad90 December 14, 2015 in Singapore
Budget 10000 20000 30000 40000 50000
Display Leads 500 1000 1200 1500 1700
SEO Leads 1000 1500 1700 1900 2500| Report Duplicate | Flag | PURGE
Komli Media xyz Algorithm - 1of 1 vote
AnswersGiven integer k and a subset S of set {0, 1, 2, ..., 2^k - 1}
- emb December 13, 2015 in United States
Return the count of pairs (a, b) where a and b are from S and (a < b) and (a & b == a)
& here is bit-wise and.
Do it faster than O((2^k)^2), assume k <= 16
Example:
0b111
0b101
0b010
Answer: 2
0b110
0b011
0b101
Answer: 0| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 4 votes
AnswersFind the n-th smallest multiple given a set of numbers. For example, set = {4, 6}, n = 6:
- supatroopa December 12, 2015 in United States
The sequence is:
4, 6, 8, 12, 16, 18, etc...
Answer is 18| Report Duplicate | Flag | PURGE
Google Algorithm - 2of 4 votes
AnswersWe have a long string. We label some substrings with tags.
- Bill December 10, 2015 in United States
- A tag entry is [startIndex, endIndex, tag].
- Query: 1 or more tags
- Output: all blocks/ranges with all queried tags.
Example tag entries:
[23, 72, 0] // label [23, 72) with tag 0
[34, 53, 1] // label [34, 53) with tag 1
[100, 128, 0]
Query and Output:
0 => [23, 72], [100, 128]
0,1 => [34,53] // [34, 53) matches both tag 0 and 1
Give an efficient algorithm. Please describe your algorithm before posting code.
**Edit**: To add some difficulties, partial overlap is treated the same as full overlap, ONLY the overlapped part matches both tags. E.g. if we have entries:
[23, 72, 0] // label [23, 72) with tag 0
[10, 53, 1] // label [34, 53) with tag 1
Query and Output:
0,1 => [23,53] // [23, 53) matches both tag 0 and 1
Minor detials: Note in the comments we used open range on the right, i.e. if the string named "str", [23, 72, 0] includes str[23] but NOT str[72]; and there's no overlap between the following entries:
[23, 72, 0]
[10, 23, 0]| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersDesign Interprocess Singleton class in C++
- Rajarathinam Antony December 10, 2015 in India
When multiple instance of singleton.exe is running, same memory(singleton instance) should be shared among all the process| Report Duplicate | Flag | PURGE
Texas Instruments Tech Lead Algorithm - 2of 2 votes
AnswersGiven a binary tree print it in inward spiral order i.e first print level 1, then level n, then level 2, then n-1 and so on.
- neer.1304 December 10, 2015 in United States
For Ex -
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
Print- 1 15 14 13 12 11 10 9 8 2 3 7 6 5 4
Follow up question - Extend the algorithm to n-ary tree.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm