Algorithm Interview Questions
- -1of 1 vote
AnswersI realized this algorithm for generating combinations. It works in the following way, if we have the input:
- pasquale.restaino1992 July 11, 2015 in United States
[A, B, C]
The combinations will be
[A], [B], [C]. [A, B], [A, C], [B, C], [A, B, C].
While if we have in input:
[1,1,2,3]
The combinations will be:
[1], [2], [3], [4], [1,2], [1,3], [2,3 ], [1,1,2,3].
However, this algorithm has a running time of good only when the input is a list of size 4, if the list is of size 5 or more (when there are 5 different elements ( for example 80 A, 150 B , 80 C , 30 D , 20 E)) the program stops and gives me java.lang.OutOfMemory (I increased the memory for in java). One problem could be the fact that I have used LinkedList, but I'm not sure.| Report Duplicate | Flag | PURGE
Developer Program Engineer Algorithm - 7of 11 votes
AnswersThe "surpasser" of an element in an array is defined as the number of elements that are to the "right" and bigger than itself.
- carchen2015 July 10, 2015 in United States
Example:
Array:
[2, 7, 5, 5, 2, 7, 0, 8, 1]
The "surpassers" are
[5, 1, 2, 2, 2, 1, 2, 0, 0]
Question: Find the maximum surpasser of the array.
In this example, maximum surpasser = 5| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersWrite an itoa
- JSDUDE July 09, 2015 in United States| Report Duplicate | Flag | PURGE
Booking.com Software Developer Algorithm String Manipulation - 0of 0 votes
AnswersThis is a sample program to find the maximum contiguous sum in an array.
int maxSubArraySum(int a[], int size) { int max_so_far = a[0], i; int curr_max = a[0]; for (i = 1; i < size; i++) { curr_max = max(a[i], curr_max+a[i]); max_so_far = max(max_so_far, curr_max); } return max_so_far; }
Now modify this to print the start and end indices.
- Anand Barnwal July 09, 2015 in India| Report Duplicate | Flag | PURGE
Adobe Developer Program Engineer Algorithm - 2of 2 votes
AnswersFind the longest common prefix in a list of phrases. For instance; "i love all dogs", "i love cats" should return "i love".
- tamaracmike July 08, 2015 in United States| Report Duplicate | Flag | PURGE
Google Algorithm - 2of 2 votes
AnswersHow will you serialize the binary tree ?
- algeek July 08, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 2of 2 votes
AnswersThere's a function that concatenates two strings and returns the length of the resultant string. When called upon a series of strings how do we minimize the cost of using this function. Let's say we have 3 strings, A= "abc", B="def", C = "gh".
- Spectral July 07, 2015 in United States
Now cost of merging AB = 6 and cost of merging the resultant string with C is 8. Thus the total cost is 6 + 8 = 14. However, if we merge A and C, then the cost is 5 and then merge B with this, the cost is 8, so the total cost is 13.
Find an algorithm that minimizes the cost of adding such a series of strings.| Report Duplicate | Flag | PURGE
Bloomberg LP SDET Algorithm - 2of 2 votes
AnswersGiven a binary tree, implement an iterator that will iterate through its elements.
- carlosgsouza July 07, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven access to live stream of purchases, design the algorithm to list the top 100 products in past X minutes/hours/days.
- emptycup July 06, 2015 in India| Report Duplicate | Flag | PURGE
Flipkart SDE-3 Algorithm - 1of 1 vote
AnswersGiven a binary tree (not search tree), find the path which adds up to given sum.
- emptycup July 06, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven a array of numbers, find all the numbers which add up to given sum.
- emptycup July 06, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersThere are buses taking various routes and each route has some stops. Given a matrix of stops and distances (distance between two stops for connected stops), find all cluster of stops of any size with all stops in a cluster fully connected and are at a distance not greater than D.
- emptycup July 06, 2015 in India
Assume that the routes are bi-directional.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm Dynamic Programming - 0of 0 votes
AnswersHello , I must write a program that given the elements in a list , generates all combinations of these elements .
- pasquale.restaino1992 July 06, 2015 in United States
For example, if I [A, B , C ] , the possible combinations are [ A] , [B ] , [ C ] , [A, B ] . [ A, C ] , [ B, C ] , [A, B , C ] . Another example , having [ A, A, B] the possible combinations are [ A] , [ A, A ] , [A, B ] , [ A, A, B, A ] .
How can I write it in java ?| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
Answersmy algorithm generates combinations of elements . For example having [A , B , C ] creates the following combinations [ A] , [ B ] , [ C ] , [ AB ] , [ AC ] , [ B , C ] , [ ABC ] . Unfortunately for items too large too long and too much memory space . So many times I java.lang.OutOfMemory launches . How can I fix ?
- pasquale.restaino1992 July 06, 2015 in United States
public void combine() {
this.findAllCombinations(combinazioneMassima);
}
private static class Node{
int lastIndex = 0;
List<Elemento> currentList;
public Node(int lastIndex, List<Elemento> list) {
this.lastIndex = lastIndex;
this.currentList = list;
}
public Node(Node n) {
this.lastIndex = n.lastIndex;
this.currentList = new ArrayList<Elemento>(n.currentList);
}
}
public List<List<Elemento> > findAllCombinations(List<Elemento> combinazioni) {
Date dataInizio = new Date();
List<List<Elemento>> resultList = new ArrayList<List<Elemento>>();
LinkedList<Node> queue = new LinkedList<Node>();
int n = combinazioni.size();
ArrayList<Elemento> temp = new ArrayList<Elemento>();
temp.add(combinazioni.get(0));
queue.add(new Node(0, temp));
// add all different integers to the queue once.
for(int i=1;i<n;++i) {
if(combinazioni.get(i-1) == combinazioni.get(i)) continue;
temp = new ArrayList<Elemento>();
temp.add(combinazioni.get(i));
queue.add(new Node(i, temp));
}
// do bfs until we have no elements
while(!queue.isEmpty()) {
Node node = queue.remove();
if(node.lastIndex+1 < n) {
Node newNode = new Node(node);
newNode.lastIndex = node.lastIndex+1;
newNode.currentList.add(combinazioni.get(node.lastIndex+1));
queue.add(newNode);
}
for(int i=node.lastIndex+2;i<n;++i) {
if(combinazioni.get(i-1) == combinazioni.get(i)) continue;
// create a copy and add extra integer
Node newNode = new Node(node);
newNode.lastIndex = i;
newNode.currentList.add(combinazioni.get(i));
queue.add(newNode);
}
GestoreRegole gestoreRegole = new GestoreRegole();
gestoreRegole.esegui(node.currentList);
}
Date dataF = new Date();
long tempo = dataF.getTime() - dataInizio.getTime();
logger.info ("durata genera combinazioni: " + tempo);
return resultList;| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersOn a screen, there are multiple rectangles drawn, when a user clicks on any point, find the smallest rectangle enclosing this point.
- ritwik_pandey July 05, 2015 in India
I could not come up with a solution. The end points of rectangles were given and also the the point where the mouse was kept was given.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersTech Screening
- sonesh July 02, 2015 in United States
Question 1 : You will be given a stream of integers, and a integer k for window size, you will only receive the streams integers one by one. whenever you receive an integer, you have to return the maximum number among last k integers inclusive of current entry.
Interviewer was expecting O(N) solution for N asks.
Edits: Interviewer was expecting O(N) Time + O(1) avg case space complexity solution for N asks.
and integers are not given in a array, every time only one integer will be passed as input to your method.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Arrays Data Structures - 0of 0 votes
AnswersRound 1
- sonesh July 02, 2015 in United States
Question 1.a
You are given a stock market feed of a single stock.
It contains the change over the previous value. you have to find out the max gain one can get out of it.
Example : -1, 2, 6, -5, -3 7, -3
Days 0 1 2 3 4 5 6
Answer is buy before day 1 and sell it after day two.
WAP for this.
Question 1.b : How do you make the changes in previous code to return the maximum loss. Please note that the changes should be minimum only.
Question 1.c: Lets undo the Question 1.b's additional changes, and now lets you are given a limit on how many days one can hold the money, lets say "k", which means, the investor will give you the money for k days only. you have to again make the additional change to figure out the optimal start date and end date.
Few Example
input : -1 -6 10 2 -5 20 5 -10 6
days 0 1 2 3 4 5 6 7 8
Max Gain : End of first day to end of 6th day, amount is 32.
Max Loss : End of 6th day to end of 7th day, amount is -10.
if K is 3 then the max gain is 25, which is end of 4th day to end of 6th day.
Edits : Interviewer was expecting O(N) solution here.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven a string such as "123", convert it to an integer. Basically, write Integer.parseInt(string).
- moriarty.rj June 30, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 0of 0 votes
AnswersGiven a CSV of names and ages, perhaps:
- moriarty.rj June 30, 2015 in United States
Alice, 30
Bob, 17
Clyde, 49
Sort the names by age.| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 0of 2 votes
AnswersGiven a List of Strings, return the number of sets of anagrams.
- SK June 30, 2015 in United States
For instance, given:
<abc,cab,dac,beed,deb,few,acd>
return 5| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersA paper consists of a series of consecutive numbers from 1 up to 2^n values. For example,
- vasanthvpsgece June 30, 2015 in India
For case 2^1, content of the paper is,
1 2
For case 2^2, content of the paper is,
1 2 3 4
For case 2^3, content of the paper is,
1 2 3 4 5 6 7 8
There will be n number of commands for 2^n case. Below are the commands,
L – Fold the paper from Left edge to Right edge
R – Fold the paper from Right edge to Left edge
After performing the n number of commands, there will be a single number in all layer of paper, you need to write down the numbers in all layers when you see the paper from upside of it.
Please provide an efficient algorithm.
Example:
Content of the paper (2^3):
1 2 3 4 5 6 7 8
Commands: LRL
Output:
5 4 1 8 7 2 3 6| Report Duplicate | Flag | PURGE
unknown Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersQ: Print out the number that is a duplicate in this unsorted array.
My follow up clarification questions:
Are the pairs always guaranteed to be sequential? Yes
Do we always know the size of the array? Yes
Will there always be just one number that does not have a pair? Yes
Original problem:int main() { int pairs[] = {1,1,7,7,3,3,19,19,4,10,10,11,11,15,15,2,2}; }
My solution:
void PrintDuplicate() { int pairs[] = { 1, 1, 7, 7, 3, 3, 19, 19, 4, 10, 10, 11, 11, 15, 15, 2, 2}; int size = 17; bool numberFound = false; for (int i = 0; i < size; i += 2) { if (i + 1 > size || pairs[i] != pairs[i + 1]) { std::cout << pairs[i] << std::endl; numberFound = true; break; } } if (!numberFound) { std::cout << "All pairs matched" << std::endl; } }
I believe this should give an O(n log n) solution with no extra space necessary.
- CareerCupDom June 29, 2015 in United States
After this solution they gave me a hint about using a binary search or a BST.
I do not see how that would have made this solution better than mine. Taking the array then moving the data to a BST would just be duplicating the process.
You could use a hashtable and every time you encounter a number see if it matches one you have already found, but that is only useful if this was an unsorted array.
What are the thoughts on my solution and why they would have gave me a hint at using a BST or a binary search on the array?| Report Duplicate | Flag | PURGE
Game Programmer Algorithm - 0of 0 votes
AnswersYou have a function f1() that generates 0 or 1 with the equal probability. Write a function f29() that generates a number between 0 and 29 with equal probability.
- azaad2004 June 29, 2015 in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer Algorithm - 0of 0 votes
AnswersFind the most frequent element in an array in logn time.
- ksahoo June 28, 2015 in United States| Report Duplicate | Flag | PURGE
ADP Java Developer Algorithm - 0of 0 votes
AnswersImplement an iterator in java. It should be thread-safe
- grwl June 26, 2015 in United States for Data Structures| Report Duplicate | Flag | PURGE
Ebay Quality Assurance Engineer Algorithm - 0of 0 votes
AnswersWrite a function to print Tree which can have any number of nodes, in level order each level in new line.
- snehit.gajjar June 25, 2015 in United States
1
2 3
4 5 6
if above is tree then answer should be,
1
2,3
4,5,6| Report Duplicate | Flag | PURGE
Groupon Software Engineer Algorithm - -1of 1 vote
AnswerWrite a function to print Tree which can have any number of nodes, in level order each level in new line.
- snehit.gajjar June 25, 2015 in United States
1
2 3
4 5 6
if above is tree then answer should be,
1
2,3
4,5,6| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersConvert a string to it's permutated string using only adjacent Swapping. e.g. CAT, TAC
- Ash June 25, 2015 in United States
Output: CAT, CTA, TCA, TAC| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersTech Screening round
- sonesh June 25, 2015 in United States
Q.1 : a non decreasing sorted array is rotated by some random amount, write a routine to figure out this random amount.you can consider the clockwise rotation.
Write the test cases for it.
Interviewer wanted to see prod ready code.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm Arrays Coding - 0of 0 votes
AnswerDesign an object oriented console application named universe that reads in a file containing the schema of a two
- AnonD June 24, 2015 in United States
dimensional (2D) universe and outputs certain information about the universe.
A 2D universe is a simplified universe that contains galaxies, stars, and planets, all of which are located on a flat plane
specified using 2-coordinates (x-axis and y-axis).
There is only one universe and it contains one or more galaxies.
A galaxy may contain one or more stars located in it.
A star may contain zero or more planets located near it in the same galaxy.
A planet may belong to one or two stars located near it in the same galaxy (Planet E465D in the sample file below is an example).
In order to allow the objects to support more descriptive attributes and functionality in future revisions of the
application, all the object types described above should be represented using separate classes. Parent-Child relationships should also be represented using links between the various object instances.
The program will run with three arguments specified: the input-file, and the name of two objects of any type, A and B.
Example command-line: universe text.txt Alpha_Dra E465D
Based on the command line arguments specified, the program will compute and display:
1. The parents location for both object A and B. (If needed, assume the coordinate of the universe is 0,0)
2. The minimum distance between object A (Alpha_Dra) and B (E465D). This is the distance between the two objects
given locations.
3. Any of the two closest stars in the entire universe.
4. The farthest object from A, that is of the same type as A; and the farthest object from B, that is of the same type as
B. (if one exists)
The input file contains new-line separated lines each describing one object using the format:
Type|Unique-Name|X-Coordinate|Y-Coordinate|Parent’s-Name|
Example test.txt input file:
Galaxy|Draco|75434.2|89151.4|Universe|
Star|Beta_And|23315.83|-2234.73|Andromeda|
Star|Alpha_Dra|75243.25|84123|Draco|
Galaxy|Andromeda|2967.78|-2357.2|Universe|
Planet|P165EU|75242.42|84121.2|Alpha_Dra|
Star|Alpha_And|26413.83|-2727.73|Andromeda|
Planet|E465D|26412.4|-2726.51|Alpha_And|
Planet|E465D|26412.4|-2726.51|Beta_And|
Notes:
The Universe object that serves as a parent to the galaxies is implicit, and will not be explicitly defined in the input
file.
The input lines may occur in any order
The file may contain millions of lines.
Example output of running: universe test.txt Alpha_Dra E465D
Parent of Alpha_Dra is located at: 75434.2,89151.4
Parent of E465D is located at: 26413.83,-2727.73
Distance between Alpha_Dra and E465D: 99635.8
Closest two stars in the universe are: Alpha_And and Beta_And| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm