Algorithm Interview Questions
- 2of 2 votes
AnswersGiven a set of entries, each containing a time index and a int count value,
- FrickenHamster September 26, 2014 in United States
ie
class Entry
{
time:int
count:int
}
write a function that will give the time interval with the highest count together,
ie,
if we had entries
100, 2
100, 1
110, 10
200, 4
1000, 3
1200, 8
and we ran something like
int highestInterval(int interval_range)
highestInterval( 50 )
it would return 100, because in 100-150, you have counts 2, 1, and 10.
I managed to get a O(n^2) solution for it, but I think theres a better solution. I think it might have to do with some preprocessing of the interval buckets, but I can't figure out the solution.| Report Duplicate | Flag | PURGE
N/A Software Engineer / Developer Algorithm - 2of 2 votes
AnswersProblem Statement
- suresh August 02, 2014 in India
You have two strings A and B. Each one contains some letters and exactly one asterisk.
You have to replace the asterisk in each string with a letter sequence (possibly of zero length) so that the resulting two
strings are equal. This equal string is what you have to return. Attempt to return the shortest possible string.
The letter sequences may be same or different.
If it is not possible to make the given strings equal, return the string "not-possible".
Additional Constraints
- A and B will contain only uppercase letters and asterisks.
- A and B will contain one asterisk each.
Examples
0)
"SOCIA*TWIST"
"SOCIALTWI*T"
Returns: "SOCIALTWIST"
1)
"HELLO*"
"HI*"
Returns: "not-possible"
2)
"PROFESS*"
"*PROFESS"
Returns: "PROFESS"
3)
"*EXAMPLETEST"
"THIRDEXAMPLE*"
Returns: "THIRDEXAMPLETEST"
4)
"*TELL"
"*AFRIEND"
Returns: "not-possible"
5)
"*"
"B*"
Returns: "B"
6)
"*C"
"D*"
Returns: "DC"
program should be written in java| Report Duplicate | Flag | PURGE
A9 Applications Developer Algorithm - 2of 2 votes
AnswersA graph contains one start node with no out-edges and a ending node with no in-edges. Such graph contains, say 10 million nodes. Question is how to find out effectively if two nodes are connected. The graph is a directed, unweighted and acyclic graph.
- ur2cdanger January 15, 2014 in United States
Additional Information : the graph will be queried for such connectivity queries at least a million times.
I was able to come up with building a transitive closure. But the space requirements ( O(10million * 10 million ) is huge.
2) I suggested BFS but it would be O( million * 10 million ), so that also was rejected.
Is there any other effective way ?. Practically I couldn't think of any other way.| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 2of 2 votes
AnswersWhat could be performance hits for searching on Local computer i.e. if you are searching computer for content what are the parameters you will consider for performance
- Anon June 27, 2013 in United States| Report Duplicate | Flag | PURGE
Apple Senior Software Development Engineer Algorithm - 2of 2 votes
Answers• Including the initial parent process, how many processes are created
- Linux :) February 23, 2013 in United States
#include <stdio.h>
#include <unistd.h>
Int main()
{
Fork(); // Fork a child Process
Fork(); // Fork another child process
Fork(); // and fork another
Return 0;
}| Report Duplicate | Flag | PURGE
Algorithm - 2of 2 votes
AnswersDropbox
- aonecoding March 21, 2018 in United States
Grid Illumination: Given an NxN grid with an array of lamp coordinates.
Each lamp provides illumination to every square on their x axis,
every square on their y axis, and every square that lies in their diagonal
(think of a Queen in chess).
Given an array of query coordinates,
determine whether that point is illuminated or not. The catch is when checking a query all lamps adjacent to, or on,…| Report Duplicate | Flag | PURGE
Dropbox Software Engineer Algorithm - 2of 2 votes
AnswersMaximum Sum of Building Speed
- uppubhai December 04, 2017 in India
You are the king of Pensville where you have 2N workers.
All workers will be grouped in association of size 2,so a total of N associations have to be formed.
The building speed of the ith worker is Ai.
To make an association, you pick up 2N workers. Let the minimum building speed between both workers be x, then the association has the resultant building speed x.
You have to print the maximum value possible of the sum of building speeds of N associations if you make the associations optimally.
Constraints
1≤N≤5∗10 ^4
1≤Ai≤10^4
Input
First line contains an integer N, representing the number of associations to be made.
Next line contains 2N space separated integers, denoting the building speeds of 2N workers.
Output
Print the maximum value possible of the sum of building speeds of all the associations.
Sample Input
2
1 3 1 2
Sample Output
3| Report Duplicate | Flag | PURGE
Practo SDE1 Algorithm - 2of 2 votes
AnswersI was given a questions during an interview which I was not able to solve, please help me in finding the solution.
Ques : - Divide the set in two partition such that both the partition has minimum difference of their sum. If we add an element to the left subset during partitioning than the value of that number will automatically increases by 1, but it will not increase by 1 if I add it to the right side. Find the minimum difference between both the subsets : -ex :- {1,2,3,4,5} leftSubset = {3,4} , rightSubset = {1,2,5} effective sum of leftSubset = 3+4+2(number of elements) effective sum of rightSubset = 1+2+5 = 8 difference of left and right = (9-8)=1 =, min difference
solution : (1,2,3} {4,5}
- himanshu.tomar05 August 21, 2017 in India| Report Duplicate | Flag | PURGE
Goldman Sachs Applications Developer Algorithm - 2of 2 votes
Answers4/5 Round at Uber
- aonecoding July 20, 2017 in United States
Coding: Given a 2D array of either '\' or '/', find out how many pieces this rectangle is divided into graphically.
For a 2X2 matrix with
/\
\/
The matrix split into 5 pieces - the diamond in middle and the four corners. Return 5 as the answer.
5/5 Round at Uber
Design Excel.| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 2of 2 votes
AnswersYou are given a class name Person that looks like this
interface Person { boolean moveUp(); boolean moveDown(); boolean moveRight(); boolean moveLeft(); boolean found(); }
This person is standing somewhere in a cell (like a array index) inside a grid (a 2D array) of unknown size and unknown boundaries. Only given info to you is the Person object and in this unknown size grid you have a apple in some unknown cell, you have to reach to this apple in efficient way.
The methods available in the Person object will actually move the person to that cell if method returns true.
You have to implement a method
- tazo March 11, 2015 in United Statesvoid findApple(Person person);
| Report Duplicate | Flag | PURGE
Algorithm - 2of 2 votes
AnswersCrypt Analysis problem :
- akii March 03, 2015 in United States
The Interviewer told me to implement the following interface
interface Expression {
Set<Char> getChars();
boolean eval(Map<Char, Int> m);
}
Map will contain values like
{ 'O' => 2, 'N' => 3, 'E' => 1, ... 'T' => 4 , } :
And eval function evaluates if the answer is correct or not , input will have 3 strings operand1 , operand2 and answer .
Overall the question was not complete , so I asked him again and again that I just have to verify the answer and not calculate it .
Verifying was really easy just get the values from map and convert to int . Add them and verify if the answer is correct.
Cam someone tell if my assumption is correct about the problem .
Example:
ONE
+ONE
----
TWO
231
+231
----
462
FOUR
+FOUR
-----
EIGHT
5239
+5239
-----
10478| Report Duplicate | Flag | PURGE
Palantir Technology Software Engineer Algorithm - 2of 2 votes
AnswersYou have a set of N objects. Each of these objects have certain properties associated with them. A property is represented by a (key, value) pair. For example, assume you have the following two objects.
- Rahul Sharma November 23, 2014 in India
Tower:
{
(height, 100), (weight, 50),
(xposition, 25), (yposition, 36)
}
Tree:
{
(area, 100), (noofleaves, 500),
(height, 25), (yposition, 36)
}
Each object you have, will have at most 4 properties. An object will have at least 1 property. Note, from the two objects above, that it is not necessary for key in the properties to be same for all the objects. Also, it is not necessary for the key to be different.
Now, given N such objects, you wish to answer M queries. Each query is represented by a set of properties (again, at most 4 properties, and at least 1 property). The answer for the query is the number of objects in the set, that have all the given properties. Two properties are considered equal iff both the key and the value match.
For example, if you have the above two objects, then the answer for the following queries is
Query:
{ (height, 100), (yposition, 36) }
Answer:
1 // matches Tower, but not Tree
Query:
{ (yposition, 36) }
Answer:
2 // matches both Tower and Tree
Query:
{ (height, 100), (noofleaves, 500) }
Answer:
0 // neither Tower, not Tree satisfy both properties
Input
The first line of input contains N and M. This is followed by the description of the N objects. The description of the i-th object will start by a number k, which is the number of properties associated with the object. The next k lines contain two space separated strings - the property key and the property value. Note that the property value is not necessarily an integer (although this is so for the example above).
This is followed by the description of M queries. The format of a query will be exactly same to that of the objects. Check the Sample Input for clarification.
One test file will contain only one test case. A single test case may contain several queries.
Output
Print M lines. Each line must be the answer of the respective query.
Constraints
1 ≤ N ≤ 10000
1 ≤ M ≤ 100000
1 ≤ k ≤ 4
Sample Input
2 3
4
height 100a
weight 50b
xposition 25a
yposition 36b
4
area 100a
noofleaves 500
height 25
yposition 36b
3
weight 80
xposition 25a
yposition 36b
1
yposition 36b
2
xposition 25a
yposition 36b
Sample Output
0
2
1| Report Duplicate | Flag | PURGE
Directi Intern Algorithm - 2of 2 votes
AnswersDesign Elevator system. And then write an algorithm for that Design such that, the user request should be completed in logN time in a N story building with M elevators,
- fbrubacher June 16, 2013 in United States for Search| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersI was asked to explain memento pattern.I explained with this example.
class Originator:ICloneable { public string a; public int b; public object Clone() { Originator o = new Originator(); o.a = this.a; o.b = this.b; return o; } } class CareTaker { List<Originator> l = new List<Originator>(); public void SaveMemento(Originator o) { l.Add((Originator)o.Clone()); } public Originator RetrieveMemento(int i) { return l[i]; } } class Program { static void Main(string[] args) { CareTaker c = new CareTaker(); Originator o = new Originator(); c.SaveMemento(o); } }
The interviewer said this is is different from memto pattern ... can anyone explain where the difference is!!!
- Jack March 21, 2013 in India| Report Duplicate | Flag | PURGE
Bank of America Software Engineer / Developer Algorithm - 2of 2 votes
AnswersWe have to paint n boards of length {A1, A2…An}. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get
- neer.1304 July 03, 2019 in United States
this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.
Input : k = 2, A = {10, 10, 10, 10}
Output : 20.
Here we can divide the boards into 2
equal sized partitions, so each painter
gets 20 units of board and the total
time taken is 20.
Input : k = 2, A = {10, 20, 30, 40}
Output : 60.
Here we can divide first 3 boards for
one painter and the last board for
second painter.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersYahoo Sunnyvale onsite
- aonecoding May 28, 2018 in United States
A string s3 consists of multiple repetitions of s1.
Given s1 and another string s2, find if s2 is a substring of s3.
s3 = s1 + s1 + … + s1 = n * s1, where n is a positive integer 0.
For example
s1 = “aabc”, s2 = “caa” => true
s1 = “aabc”, s2 = “cab” => false
s1 = “aabc”, s2 = “caabcaa” => true| Report Duplicate | Flag | PURGE
Yahoo Software Engineer Algorithm - 2of 2 votes
AnswersAirbnb: Design webbrowser back button
- aonecoding May 23, 2018 in United States
Your web browser supports will support three actions: back, forward and open. The init webpage is “about:blank”.
Given a sequence of commands. Return the result page.| Report Duplicate | Flag | PURGE
Airbnb Software Engineer Algorithm - 2of 2 votes
AnswersAWS phone interview
- aonecoding May 13, 2018 in United States
Find the left view of binary tree
1
/ \
2 3
/\ \
4 5 6
/ /
7 8
/
9
return [1, 2, 4, 7, 9]| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 2of 2 votes
AnswersApril Google Interview 1/4
- aonecoding May 06, 2018 in Korea
A = a+b-c-a-b-c-a-b (Tree)
B = b+a+c+a+b-c+b (Tree)
is A equal to B| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersApril Google Interview 3/4
- aonecoding May 06, 2018 in Korea
Maze
N,M array
Level 1 0,0 to N-1,M-1 => Path exsits?
Level 2 if path exists then print path
Level 3 if path exists then print min cost path
Level 4 O(nm log mn) using Priority Queue.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven the list of the numbers. In this list, there are the numbers from the Fibonacci sequence.
- denis.zayats February 13, 2018 in Switzerland
Write the algorithm that retrieves all the numbers which belong to the Fibonacci sequence of numbers.| Report Duplicate | Flag | PURGE
MobiCastle Software Engineer Algorithm - 2of 2 votes
AnswersPhone Interview Amazon, Seattle
- aonecoding July 28, 2017 in United States
I. Get the sum of all prime numbers up to N. primeSum(N).
Follow-up: If primeSum(N) is frequently called, how to optimize it.
II. OODesign Parking Lot| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 2of 2 votes
AnswersOpen Ended: Design an email system
- techpanja October 02, 2013 in United States| Report Duplicate | Flag | PURGE
Apple Software Engineer / Developer Algorithm - 2of 2 votes
AnswerWas asked at GHCI Bangalore at their booth for a prize and perhaps hiring interns or experienced software developers.
- jaryya@hawk.iit.edu November 10, 2019 in India
Find the return value for N=100
int returnAns(int N){
int ans=0;
for(int i=0; i<N; i++){
for(int j=i+1; j<N; j++){
ans +=((i & -i) == (j & -j)?1:0); //the question missed the condition and was returning a boolean, so I added it myself
}
}
return ans;
}
My answer: 0 ; their answer: 1610, hence got it wrong.
My explanation: I assumed negative of i in binary to be
simply represented by setting the MSB to 1 e.g. for 8 bit representation of 3: +3 is 0000 0011 and -3 is 1000 0011. In the inner loop the value of ans will always evaluate to 0 since Bitwise & of these i and -i or j and -j will always result into i and j respectively. (undergrad computer organization concept.)
Negative numbers can also be represented as 1s and 2's complement and in all modern machines by architecture its 2s complement.
Now if we assume 1's complement, +3: 0000 0011 and -3: 1111 1100. so bitwise & of these two is 0 and so the value of ans will always be incremented by 1. By two loops 100+99+98+97+...+1 = 100*101/2 (i.e. n*(n+1)/2)
Then 2's complement, which is the most relevant representation of signed binary numbers.
Odd numbers:
+3: 0000 0011 -3: 1111 1101 Binary & is 0000 0001.
For all even numbers:
+4: 0000 0100 and -4: 1111 1011+0000 0001 = 1111 1100 and Bitwise & of 4 and -4 is 0000 0100 which is 4.
So, in the innermost loop ans is incremented by 1 when i is odd and j is also odd. ie. when i is 1, 3, 5, 7... 97 and j is 3, 5, 7, 9,...,99 ans is added 1(return value of true ==) when calculated it comes to 1610.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswerGoogle
- aonecoding January 20, 2018 in United States
1st round
Given a box with N balls in it, each ball having a weight, randomly choose pick one out base on the weight.
Input ball1-> 5kg, ball2 -> 10kg and ball3 -> 35kg,
then Prob(ball1 chosen) = 10%, Prob(ball2) = 20%,
Prob(ball3) = 70% ;
Follow-up:
Select a ball randomly based on weights. Once a ball is chosen, remove it. Next time select from the remaining balls. Go on until there is nothing left in the box.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswerTwitter
- aonecoding January 04, 2018 in United States
Create a simple stack which takes a list of elements.
Each element contains a stack operator (push, pop, inc) and a value to either push/pop or two values, n and m,
which increment the bottom n values by m.
Then print the topmost value of the stack after every operation. If the stack is empty, print "empty"| Report Duplicate | Flag | PURGE
Twitter Software Engineer Algorithm - 2of 2 votes
AnswerFacebook
- aonecoding November 03, 2017 in United States
-Phone: LC304 & longest arithmetic sequence. Return the sequence.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
AnswerAirbnb Online Assessment Paginate List
- aonecoding October 13, 2017 in United States
5
13
1,28,310.6,SF
4,5,204.1,SF
20,7,203.2,Oakland
6,8,202.2,SF
6,10,199.1,SF
1,16,190.4,SF
6,29,185.2,SF
7,20,180.1,SF
6,21,162.1,SF
2,18,161.2,SF
2,30,149.1,SF
3,76,146.2,SF
2,14,141.1,San Jose
Here is a sample input. It’s a list generated by user search.
(1,28,100.3,Paris) corresponds to (Host ID, List ID, Points, City).
5 in the first row tells each page at most keeps 5 records.
13 in the second row is the number of records in the list.
Please paginate the list for Airbnb by requirement:
1. When possible, two records with same host ID shouldn’t be in a page.
2. But if no more records with non-repetitive host ID can be found, fill up the page with the given input order (ordered by Points).
Expected output:
1,28,310.6,SF
4,5,204.1,SF
20,7,203.2,Oakland
6,8,202.2,SF
7,20,180.1,SF
6,10,199.1,SF
1,16,190.4,SF
2,18,161.2,SF
3,76,146.2,SF
6,29,185.2,SF -- 6 repeats in page bec no more unique host ID available
6,21,162.1,SF
2,30,149.1,SF
2,14,141.1,San Jose| Report Duplicate | Flag | PURGE
Airbnb Software Engineer Algorithm - 2of 2 votes
AnswerUber
- aonecoding July 17, 2017 in United States
1. Mirror Binary Tree
2. String pattern matching
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(String str, String pattern)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa","a{1,3}") → true
isMatch("aaa","a{1,3}") → false
isMatch("ab","a{1,3}b{1,3}") → true
isMatch("abc","a{1,3}b{1,3}c") → true
isMatch("abbc","a{1,3}b{1,2}c") → false
isMatch("acbac","a{1,3}b{1,3}c") → false
isMatch("abcc","a{1,3}b{1,3}cc{1,3}") → true
In pattern string, a char followed by {lower, upper} means that the char occur lower to upper(exclusive) times. e.g. a{1, 3} -> a occurs 1 or 2 times.| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 2of 2 votes
AnswerVMWare Standard Online Screen
- aonecoding April 18, 2017 in United States
The Online Assessment was called something like Life Cycle Challenge-qpan.
There are 4 questions in total given 60 minutes. The problem description was unexpectedly long that it takes 5 minutes just to read a question.
1st Question Design a function to create BST. Given an integer array, insert the integers into the binary search tree and print all the steps taken.
2nd Question Given an integer, print the index of all the positions in which the binary bit is 1 in order.| Report Duplicate | Flag | PURGE
VMWare Inc Software Engineer Algorithm