Algorithm Interview Questions
- 2of 2 votes
AnswersGiven an array of positive integers(>0) , you have to insert '+','*','(',')' signs basically plus multiply and brackets such that value of resultant expression becomes maximum.
- smarthbehl August 25, 2015 in United States
Hint: Consider case of continuous ones
You have to print the resulting expression| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Algorithm - 1of 1 vote
AnswersWrite all solutions for a^3+b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5] in at least O(n^2) complexity
- dev123 August 24, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersCompany will start a new marketing campaign targeting the users according
- JavaBuddy August 22, 2015 in United States
to their purchasing profiles.
This campaign has 3 kinds of messages each one targeting one group of customers:
Message 1 - targets the 25% of customers that spend most at the site
Message 2 - targets the 25% of customers that spend least at the site
Message 3 - targets the rest of the customers.
Given the list of purchases made during the week, write a program that lists
what kind of message each customer will receive.
Each purchase in this list features the customer id, the purchase amount among other information.| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm Java - 0of 0 votes
AnswerWrite a program to get out of the Maze. Maze can be represented in the form of Matrix where x can be represented as wall. and _ can be represented as a path.
- hm August 21, 2015 in United States| Report Duplicate | Flag | PURGE
EMC Software Engineer Algorithm - 7of 7 votes
AnswersGiven a binary N X N matrix, return the size of the largest '+' of ones.
- zaxven August 19, 2015 in United States
input:
0 0 0 0
1 1 0 1
1 1 1 1
1 1 1 0
output:
5
(binary search is not allowed)| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersList of 2D points: (x1, y1), (x2, y2) … (xN, yN) - N 2D points.
- zaxven August 19, 2015 in United States
Each two points define a 2D line.
create an algorithm which returns a list of all unique 2D lines, which you can build using pairs of points from the list.| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersDesign a system java same as relational database.
For example,
You Have employee table as bellow:ID | Name | Manager | Salary
Now you can execute queries like :
select * from Employee where ID= ' something' select * from Employee where Name= ' something' select * from Employee where salary = ' something'
In same way you have a class Emplyee as bellow:
class Employee { String ID; String Name; String Salary; String Manager; }
Now I want to query on this class as same as the sql queries above,
- Ghosh August 17, 2015 in India
How can I do it efficiently?
The code should be optimized on time complexity and space complexity.| Report Duplicate | Flag | PURGE
Oracle Software Architect Algorithm Data Structures Java Object Oriented Design - 2of 2 votes
AnswersThe King's Land Sale - 2
- sunilkanaujia.manit August 14, 2015 in India
You might have seen shopkeepers offering sale on their trade items to promote their business - like sale on electronic gadgets or sale on clothing and accessories etc. But have you ever come across something like sale of land ?
Yes, the king of Byteland has grown old and wants to sell away his territory as soon as possible. So he announced a sale on his plot. This drew attention of many land lords and everybody hurried to buy land at the cheapest prices. The king had declared that he would accept bids of only rectangular plots and one needs to mention the diagonally opposite corners(a, b) and (c, d) of the land he wishes to buy. They would write these 4 numbers (a, b, c, d) on a piece of paper, seal it in an airtight envelope and give it to the king.
The king received N such envelopes. As the process was hidden there were many envelopes containing plot descriptions that shared some (or even all) common area. The king now wants to know the union of the areas of all plots that have come under the bidding.
Note that the rectangles made by the plots are always aligned to the rectangular axes, their areas is always positive and c >= a and d >= b.
Note that the rectangles made by the plots are always aligned to the rectangular axes, their areas is always positive and c >= a and d >= b.
Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 20
-10000 ≤ a, b, c, d ≤ 10000
Input
The first line of the input contains the number of test cases T. The description of T test cases follow. Each test case starts with a line containing an integer N, the number of rectangular plots. Then N lines follow, each with 4 space separated integers, a b c d,(a, b) and (c, d) representing the diagonally opposite corners of the plots.
Output
For each test case print one line, the union of the areas of all the plots.
Explanation
1) The individual areas of both plots are 4 each. But they share a common area of 1 between them (between (1, 1) and (2, 2)). Therefore the total area is 4 + 4 - 1 = 7
2)Both the plots of no area in common. So we simply add their individual areas (6 + 9 = 15).| Report Duplicate | Flag | PURGE
Adobe Developer Program Engineer Algorithm - 2of 4 votes
AnswersA string contains a-z, A-Z and spaces. Sort the string so that all lower cases are at the beginning, spaces in the middle and upper cases at the end. Original order among lower and upper cases needs to remain the same. For example: a cBd LkmY becomes ackm BLY. Is there a way in O(n) without extra space?
- chad August 13, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm Arrays - 4of 4 votes
AnswersThis is one of the interview questions during the Amazon SDE interview. Request your help in providing the solution.
- satish1987 August 12, 2015 in United States
Question - We are interested in building a special type of sequence. for a given number N, we want to arrange the numbers {1,1,2,2,3,3,... N,N} such that they have the following property.
For each number / in (1,N) there should be exactly / numbers between the first appearance of the number and the second appearance. Below example would clarify further.
Input:
A Single number N for which we want to produce the sequence.
Output:
A space separated list of sequence or NA if there is no possible sequence.
Example Input:
3
Example Output:
2 3 1 2 1 3
Explanation : There is 1 number between 1s(2). There are 2 numbers between the 2's(3 1 ). There are 3 numbers between the 3's(1 2 1 ).| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswerThis is one of the interview questions during the Amazon SDE interview. Request your help in providing the solution.
- satish1987 August 12, 2015 in United States
Question - We are interested in building a special type of sequence. for a given number N, we want to arrange the numbers {1,1,2,2,3,3,... N,N} such that they have the following property.
For each number / in (1,N) there should be exactly / numbers between the first appearance of the number and the second appearance. Below example would clarify further.
Input:
A Single number N for which we want to produce the sequence.
Output:
A space separated list of sequence or NA if there is no possible sequence.
Example Input:
3
Example Output:
2 3 1 2 1 3
Explanation : There is 1 number between 1s(2). There are 2 numbers between the 2's(3 1 ). There are 3 numbers between the 3's(1 2 1 ).| Report Duplicate | Flag | PURGE
Mathworks SDE1 Algorithm - 0of 0 votes
AnswerPrint out the order of dependencies and it they are cycles. Print array contains cycles.
- Bush2015 August 09, 2015 in United States
The method should take an array of strings with the fellow format: PackageName: dependencyName, dependencyName| Report Duplicate | Flag | PURGE
Algorithm - 5of 5 votes
AnswersI came across this problem online.
- xiaoc10 August 07, 2015 in United States
> Given an integer:N and an array int arr[], you have to add some
> elements to the array so that you can generate from 1 to N by using
> (add) the elements in the array.
Please keep in mind that you can only use each element in the array once when generating a certain x (1<=x<=N). Return the count of the least adding numbers.
For example:
N=6, arr = [1, 3]
1 is already in arr.
add 2 to the arr.
3 is already in arr
4 = 1 + 3
5 = 2 + 3
6 = 1 + 2 + 3
So we return 1 since we only need to add one element which is 2.
Can anyone give some hints?| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
AnswersMinimum number of jumps required to climb stairs
- utsav0goyal August 06, 2015 in India
Its basically like, you have 2 parallel staircases and both the staircases have n steps. You start from the bottom and you may move upwards on either of the staircases. Each step on the staircase has a penalty attached to it. You can also move across both the staircases with some other penalty.
I had to find the minimum penalty that will be imposed for reaching the top.
I tried writing a recurrence relation but I couldn't write anything because of so many variables.
I recently read about dynamic programming and I think this question is related to that.
With some googling, I found that this question is the same as
https://www.hackerrank.com/contests/frost-byte-final/challenges/stairway
Can you please give a solution or an approach for this problem ?| Report Duplicate | Flag | PURGE
Microsoft Intern Algorithm - 0of 0 votes
AnswersYou have an app that uses a 3rd party video player. The VP has the functionalities - play, pause, seek and close. On close, the VP makes a callback to your app. To the callback it sends the below parameters
- coolcoder3 August 04, 2015 in India
* videoLengthInSecs
* VideoPart[]. VideoPart {startTime, endTime}. Denotes a continuous part of the video that was watched without any disturbance caused by pause, seek.
Your app should be able to determine whether the user has watched the entire video or not.
60, [{0, 30}, {30, 60}]
return boolean| Report Duplicate | Flag | PURGE
StartUp SDE1 Algorithm - 0of 0 votes
AnswerGiven an array of integers, find a triplet of numbers adding up to a given number.
- dalas August 04, 2015 in United States| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersProblem Statement
- learning August 02, 2015 in United States
Given a stream of numbers, write code to calculate the rolling average and rolling maximum over two different window sizes. We provide an illustrative example below. It illustrates the expected output for window sizes of 3 and 5. For your solution please implement a solution that uses window sizes of 3 and 20.
For example, given a stream containing the following values:
[1, 2, 3, 4, 5, 6]
the following tuples would be expected, where ‘None’ indicates that a value is not available, and would be ‘NaN’ in some languages:
(None, None, None, None) (None, None, None, None) (2, 3, None, None) (3, 4, None, None) (4, 5, 3, 5) (5, 6, 4, 6)
You should write a class which accepts an iterator and acts as a generator which yields tuples as shown above.
C++ guidance
This is a sample interface for C++; you may use any functionally equivalent interface that you wish. Your implementation would accept an InputStream reference and implement StatisticsGenerator.
struct Statistics {
bool valid; // true only if mean and max fields are valid
double mean;
double max;
};
class StatisticsGenerator {
public:
// Returns true if more elements are available
bool HasNext();
// Get the current statistics.
std::pair<Statistics, Statistics> GetNext();
};
class InputStream {
public:
// Returns true if more elements are available
bool HasNext();
// Get the next element in the stream
double GetNext();
};| Report Duplicate | Flag | PURGE
Algorithm - 1of 3 votes
AnswersOn a given array with N numbers, find subset of size M (exactly M elements) that equal to SUM.
- coredo August 02, 2015 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven an array A with n integers.
- smarthbehl August 01, 2015 in United States
Rearrange array such that
A[0]<=A[1]>=A[2]<=A[3]>=A[4]<=A[5] and so on
Edit: Array is not sorted
You have to do it in linear time O(N)| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Algorithm - 0of 0 votes
Answersgiven an integer array, find the minimum triangle perimeter.
for example,{1, 2, 3, 4, 5}
,
- interviewee August 01, 2015 in United States
the minimum perimeter is 2 + 3 + 4 = 9.
The array is not necessarily sorted.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersYou should transform an structure of multiple tree from machine A to machine B. It is a serialization and deserialization problem, but i failed to solve it well.
You could assume the struct is like this:struct Node{ string val; vector<Node*> sons; }
and in machine A, you will given the point to root Node, and in machine B,you should return a pointer to root Node.
- lxfuhuo July 30, 2015 in China| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 5 votes
AnswersGenerate all possible sorted arrays from alternate elements of two given sorted arrays.
- vishgupta92 July 28, 2015 in United States
Given two sorted arrays A and B, generate all possible arrays such that once first element is taken from A then from B then from A and so on in increasing order till the arrays exhausted. Then first element is taken from B then From A, and do same as above.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 0of 0 votes
AnswersThere are n persons and k different type of dishes. Each person has some preference for each dish. Either he likes it or not. We need to feed all people. Every person should get atleast one dish of his chioce. What is the minimum number of different type of dishes we can order?
- prashant2006ster July 28, 2015 in India
Input is n x k matrix boolean matrix.For each person a row represent his likes or not likes each row.
n = 6 k = 7
1 0 0 0 1 0 0
1 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 0 0 1 0 0
0 0 1 0 0 1 0
0 0 0 1 0 0 1
Output
3
Explanation
Take dish number 5,6,7.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 1 vote
AnswersFind an algorithm to find a word ladder between 2 words by changing just one letter at a time. All the words formed should be valid dictionary words.
- soumi July 27, 2015 in United States for Echo
Eg.
FOOL ->POOL->POLL->POLE->PALE->SALE->SAGE
COLD → CORD → CARD → WARD → WARM| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersMaga gives a hard problem to Alex. And Alex couldn't solve yet. Could you help him?
- ALgorocks July 27, 2015 in India
The grid is n by m. Each cell contains a unique number on it. Maga is at the left-top and wants to go to right-bottom. But there is a condition. Maga can go through only two way - right and down. And the path of your move is called the nodes you have passed through over them. The path is called the most beautiful if the following condition is satisfied: The sorted of the path has to be lexicographic smallest as possible as. Output the most beautiful path for given grid.
Input:
In the first line you are given two numbers: the dimensions of grid - n and m. The next n lines contains m numbers. Each number is unique.
Output:
Output the most beautiful path.
Contraints:
1 <= n,m <= 1000
1 <= A[i][j] <= n*m, All of the numbers in the grid are unique.
Sample Input
2 2
4 2
3 1
Sample Output
1 2 4
Explanation
There are 2 ways to reach at (2,2) cell. The pathes are 4, 3, 1 or 4, 2, 1 respectively. So The most beautiful of them is 4, 2, 1 because if looking the sorted of them it looks like these : 1, 3, 4 and 1, 2, 4 respectively. So 1, 2, 4 is lexicographic smaller than the other. So the ans is 1 2 4.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersLittle Chandan is a friend everyone feels lucky to have. He is a happy-go-lucky-fellow and makes sure that everyone around him is happy. But recently, he came to know that his friend little Arjit is in serious trouble, and needs help. Like the great friend little Chandan is, he took the challenge upon himself without any serious thought, to make sure that little Arjit feels fine.
- ALgorocks July 27, 2015 in India
Now, little Arjit explains the story of his problems (His life, in general!) to let little Chandan figure out his troubles. After all, everyone needs help. All little Arjit needs is to get an internship somewhere, and complete his dual degree course, somehow, anyhow.
Little Chandan being the great genius man with psychic power decides to enter the brain of his friend to help him out.
Here are the contents of little Arjit's brain:
- His goals. (Internship, dual degree, remember?) - what Chandan needs to free. - Predictable empty spaces in his brain - plain empty spaces. - Ex-girlfriends and their memories - which CANNOT be penetrated, while traversing. - Windows which lead to the goal - which need to be open for little Chandan to pass.
Little Chandan knows the location of the two goals in his brain, the problem is while traveling through the path of his brain he'll have to break down the windows - once he has opened a window to cross that path, it remains open forever. So, he wants to minimize the number of windows he opens inside his friend's mind.
Help him plan his path accordingly, so he ends up breaking the minimum number of windows!
Input Format:
- First line contains a number t, denoting the number of test cases.
- Every test case will have the following:
- One line with two integers hm, wm - determining the width of the brain and the height of the brain.
The following characters define the state:
- X is the space which cannot be penetrated filled by the memories of ex-girlfriends. - W is the windows which little Chandan need to cross to reach the goal. - . is an empty space in the brain. - G are the two goals to be rescued.
Output Format:
1. Minimum number of windows Chandan needs to open to get to both the goals in Arjit's mind.
Constraints:
1 <= t <= 100
2 <= hm, wm <= 100
There are EXACTLY two goals in his mind.
For each goal, a path from the outside to that goal is surely going to exist.
Chandan can move around freely outside the mind.
Sample Input
1
5 9
XXXXWXXXX
X..W.W..X
XXXX.XXXX
XGW.W.WGX
XXXXXXXXX
Sample Output
4| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersWrite an algorithm to create tables of a given set of players (i.e divide the players into groups) for a game in the following manner. Each table will have 6 players. Total number of players will be a multiple of 6. There are some conditions that must be fulfilled to decide which player takes which table. These conditions are defined later and requires some definitions that we will look into first.
- pankajb64 July 27, 2015 in United States
'Distance' between the players:
Since these players have been playing with each other in the past, we have history (available in a data set) about who played with whom in the past. Using this player game history we can plot a graph of players where each player is a node in the graph. A player is connected to another player if they have played on the same table in the past. In such a case distance between them is 1.
For example: If Pi and Pj have played on the same table in the past then they are connected with each other and 'Distance' between Pi and Pj is 1. Distance between any 2 players is defined as length of the shortest path between 2 players. If 2 players are not connected then distance between them is same as maximum of distance between any 2 players + 1
Degree of separation of a table
Degree of separation of a table is defined as sum of (Distances of all players taken 2 at a time)
Example: For a table of 6 players: Degree of separation = Sum of all 15 distances (6 choose 2)
The condition on table formation is:
We have to create tables (i.e divide the players into groups) such that Sum of (degree of separation of all the tables) is minimum.
The constraints on data size:
Number of history records is upto 100M records
Number of unique players in history upto 200K
Number of tables possible in the solution is upto 1K| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
Answers2. There is a maze of size n*n. Tom is sitting at (0,0). Jerry is sitting in another cell (the position of Jerry is input). Then there are k pieces of cheese placed in k different cells (k <= 10). Some cells are blocked while some are not. Tom can move to 4 cells at any point of time (left, right, up, down one position). Tom has to collect all the pieces of cheese and then reach to Jerry’s cell. You need to print the minimum no. of steps required to do so.
- lucklypriyansh July 24, 2015 in India
I know it is possible throgh dp but please provide me solution with approoch i am unable to solve it please| Report Duplicate | Flag | PURGE
Flipkart Software Engineer Algorithm - 1of 1 vote
AnswersWrite a program in that determines the members and parents of nested groups without using recursion.
These are the requirements.
1. A group can have 0 or more members.
2. A group can be member of one or more groups
3. A group can be member of itself.
4. If there is a path from a group either directly or through multiple hops, then that user is considered as member of the group.
5. A group can have users or groups as members
EX: Input looks like thisvar groupMembers = new Dictionary<string, HashSet<string>> { { "G4", new HashSet<string> { "U1","G1"} }, { "G1", new HashSet<string> { "G2","G3","G6"} }, { "G3", new HashSet<string> { "G3","G5"} }, { "G2", new HashSet<string> { "G4","U2"} }, { "G5", new HashSet<string> { "U2","G6"} }, { "G6", new HashSet<string> { "U3"} }, };
Signature of function is:
private List<MyGroup> FindMembers(Dictionary<string, HashSet<string>> groupMembers)
You need to make sure that you take care of cycles in the graph and not go into infinite recursion.
Output should look like a list of groups where a group is as follows.private class MyGroup { public string Identity { get; set; } public Dictionary<string, MyGroup> MemberOf { get; set; } public Dictionary<string, MyGroup> Members { get; set; } public HashSet<string> Users { get; set; } public MyGroup(string name) { this.Identity = name; this.MemberOf = new Dictionary<string, MyGroup>(); this.Members = new Dictionary<string, MyGroup>(); this.Users = new HashSet<string>(); } }
Each group object should contain all the groups it's a memberOf (directly or indirectly), all the groups that are it's members (directly or indirectly) and all users that are it's members.
- enok July 23, 2015 in United States| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer Algorithm