Algorithm Interview Questions
- 2of 2 votes
AnswerHow do we achieve (google news) personalization.
- sati November 05, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswerLet's say I gave you a long String and I wanted you to tell me the most common word in that String. How would you do that?
- utopia August 12, 2014 in United States
follow-up: OK, how would you estimate the size and time complexity of this solution? How would you estimate the ACTUAL size usage? (Hint: how many words are in the English language? Would having a dictionary in front of you help?)
follow-up #2: OK, how about if I gave you the entire works of Alexandre Dumas, one of the most prolific authors in history. How would your solution work? How could you change it to solve this more specific problem?
follow-up #3: Now, what if we wanted to find the most common PHRASE in his writings. (Upon clarification, the interviewer wouldn't give a specific length, so I clarified to finding as long as a common 10 word phrase, because anything longer is unlikely.)| Report Duplicate | Flag | PURGE
Goldman Sachs Software Engineer / Developer Algorithm Hash Table - 2of 2 votes
Answerplease help me out!!..Its not striking me.
- guptaabhinav206 January 22, 2014 in India
Ramesh and Suresh get a box full of five stars on lottery each. Since both the boxes need not have the same number of chocolates, they decide to play a game. The winner gets to have both the boxes of chocolates. They play alternatively and Suresh starts the game. Given the number of chocolates in both the boxes, let them be c1 and c2, the player takes either c1 or c2 number of chocolates and divide the remaining box of chocolates to two boxes (these two boxes need not have the same number of chocolates). The player who cannot make such a move loses. Input
First line of input contains a number T(1<=T<=1000), the number of test cases. Then follows T lines each containing two space separated integers c1 and c2
(1<=c1<=c2<=10000).
Output For each test case print "Ramesh" or "Suresh" depending on who is the winner.
Input: 2 3 1 4 5
Output: Ramesh Suresh| Report Duplicate | Flag | PURGE
Capgemini Intern Algorithm - 2of 2 votes
AnswersA list of relation is given. We need to express the relation in a single line with the largest unit leftmost.
- accessdenied December 09, 2019 in United States
eg.
a = 10b
b=5c
c = 20a
e=20d
a=10b=25e=50c=500d| Report Duplicate | Flag | PURGE
Algorithm - 2of 2 votes
Answersthere are N cities (numbered from 1 to N) in the game and connect them by N-1 highways. It is guaranteed that each pair of cities are connected by the highways directly or indirectly.The game has a very important value called Total Highway Distance (THD) which is the total distances of all pairs of cities. Suppose there are 3 cities and 2 highways. The highway between City 1 and City 2 is 200 miles and the highway between City 2 and City 3 is 300 miles. So the THD is 1000(200 + 500 + 300) miles because the distances between City 1 and City 2, City 1 and City 3, City 2 and City 3 are 200 miles, 500 miles and 300 miles respectively.
- hulei660066 October 06, 2015 in United States for bing
During the game the length of some highways may change. you want to know the latest THD.
sample input
3 5
1 2 2
2 3 3
QUERY
EDIT 1 2 4
QUERY
EDIT 2 3 2
QUERY
sample output
10
14
12| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 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 0 votes
AnswersSimulate a seven-sided die using only five-sided
- vodangkhoa March 23, 2008| Report Duplicate | Flag | PURGE
Amazon Microsoft Software Engineer / Developer Algorithm - 2of 0 votes
AnswersIn MS Excel, the column numbers are named as A, B, C, ......, Z. If you go beyond this 'Z' column you will encounter AA-->AZ, BA-->BZ, .... ZA-->ZZ then AAA-->AAZ, ABA-->ABZ, ........ and you can imagine how long this sequence can go! The question was to write a function which takes in a positive integer and
- Aniruddha Gore November 02, 2008
returns the character set at that column. For example: if column number is 26 my function must return 'AA' (0-based index). I basically started looking for any specific pattern if I can find for how many columns names are 1 letter, 2 letter, etc. fortunately there's a pattern involved. I couldn't solve the question completely as we ran out of time but interviewer seemed satisfied as I started by looking for a pattern and not sat down to code without giving a thought.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 2of 0 votes
AnswersGiven an n*n matrix A. Each row of the matrix and each column of the matrix is sorted.
- Kevin October 14, 2008
Given a number S, you are required to find S in the matrix( report k, l such that A[k,l] = S) or conclude S is not in A.
How can you solve it in O(n)?| Report Duplicate | Flag | PURGE
Amazon Development Support Engineer Software Engineer / Developer Algorithm - 2of 0 votes
AnswersYou are given a lot of cuboid boxes with different length, breadth and height. You need to find the maximum subset which can fit into each other.
- Me January 21, 2009
For example:
If Box A has LBH as 7 8 9
If Box B has LBH as 5 6 8
If Box C has LBH as 5 8 7
If Box D has LBH as 4 4 4
then answer is A,B,D
A box can fit into another only and only if all dimensions of that is less than the bigger box. Also Rotation of boxes is not possible.| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Algorithm - 2of 0 votes
Answerscode a function that returns the nth fibnocci number... coded it the most efficient way by using 3 variable... Then the interviewer wrote the recursive form and asked me what are the pros and cons of your(iterative) approach and recursive approach.
- offerFromMS October 14, 2008| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 2of 0 votes
AnswersIf there are two structs, TreeNode and Tree. TreeNode contains 3 elements, data, lChild and rChile. Tree contains 2 elements, int size and TreeNode *root. The tree is a complete tree. So how to find a O(logN) approach to insert a new node.
- Little Bread June 08, 2006| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs Algorithm - 2of 0 votes
AnswersGiven a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 using only one call to strstr routine?
- vodangkhoa January 31, 2007
(eg given s1 = ABCD and s2 = CDAB, return true)
(given s1 = ABCD, and s2 = ACBD , return false)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Coding Algorithm - 2of 0 votes
AnswersMinimum Common ancestor of given two values in the Binary tree
- Adobe October 03, 2008| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Trees and Graphs Algorithm - 2of 0 votes
Answers1. Carefully see the following transition from one word to other-
- Aks December 07, 2008
PAN -> PEN -> MEN -> MET
Here each word is achieved by changing any one character in previous word. Now you are given with a Source word (PAN here) and a Destination word (MET here) and need to find out shortest transition chain following above rule using only meaningful words. Dictionary containing thousands of meaningful words is provided to you. WAP for this.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 2of 0 votes
AnswersIn an unending stream of numbers, pick a number with equal probability.
- SDE Interview November 04, 2008| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Algorithm - 2of 0 votes
Answerslink list
- jack July 11, 2008
struct node
{
int d;
struct node *next;
struct node *random;
}
random is a pointer which can point to any link in the link list.One link list is given, you have to create the copy of that link list| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 0 votes
AnswersList as many data structures as you can think of. How do you detect a loop in a linked list?
- Bloomberg london July 31, 2008| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Data Structures Algorithm Linked Lists - 2of 0 votes
AnswersBased upon what points we should choose proper search/sort algorithm for problem solution from all available algos (Quick, heap, selection, shell, insertion, Binary Tree, bubble sort etc.) ? To be specific, when should we use above algos ? examples will be appreciated.
- Sadhana July 21, 2008
Regards| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 1of 9 votes
AnswersQ: Weighted meeting room
Given a series of meetings, how to schedule them. Cannot attend more than a meeting at the same time. Goal is to find maximum weight subset of mutually non-overlap meetings.class Meeting: def __init__(self): self.startTime self.endTime self.weight
@concernedCoder
- aonecoding February 27, 2017 in United States
When you claim the questions as fake, provide evidence. These are no doubt questions asked in the coding interviews of the best companies and they definitely help interviewees to prepare for the interview.
Why do you have a problem with this?| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 7 votes
AnswersGiven an excel column number convert it to excel column alphabet and reverse.
- codechamp March 30, 2014 in India for AWS
Example : If column number(starts from 0) = 26 : Column alpha = AA.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Brain Teasers Data Structures - 1of 5 votes
AnswersDivide a list of numbers into group of consecutive numbers but their original order should be preserved?
- rhine November 23, 2008
e.g.
8,2,4,7,1,0,3,6
2,4,1,0,3 and 8,7,6
obviously in shortest time and space.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 5 votes
AnswersWrite a function that takes an integer as input and produces an output string.
- tbag March 11, 2015 in United States
Some sample Input/outputs are as follows
i/p o/p
1 - A
2 - B
3 - AA
4 - AB
5 - BA
6 - BB
7 - AAA
8 - AAB
9 - ABA
10 - ABB
11 - BAA
12 - BAB
13 - BBA
14 - BBB
15 - AAAA| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 5 votes
AnswersBelow question was asked in online coding exam for Palantir Technology, Palo Alto, CA. Time given was 100 min. I could not complete it by the time.
- Nitin Gupta February 02, 2013 in United States
-----------------------------
A group of farmers has some elevation data, and we’re going to help them understand how rainfall flows over their farmland.
We’ll represent the land as a two-dimensional array of altitudes and use the following model, based on the idea that water flows downhill:
If a cell’s four neighboring cells all have higher altitudes, we call this cell a sink; water collects in sinks.
Otherwise, water will flow to the neighboring cell with the lowest altitude. If a cell is not a sink, you may assume it has a unique lowest neighbor and that this neighbor will be lower than the cell.
Cells that drain into the same sink – directly or indirectly – are said to be part of the same basin.
Your challenge is to partition the map into basins. In particular, given a map of elevations, your code should partition the map into basins and output the sizes of the basins, in descending order.
Assume the elevation maps are square. Input will begin with a line with one integer, S, the height (and width) of the map. The next S lines will each contain a row of the map, each with S integers – the elevations of the S cells in the row. Some farmers have small land plots such as the examples below, while some have larger plots. However, in no case will a farmer have a plot of land larger than S = 5000.
Your code should output a space-separated list of the basin sizes, in descending order. (Trailing spaces are ignored.)
While correctness and performance are the most important parts of this problem, a human will be reading your solution, so please make an effort to submit clean, readable code. In particular, do not write code as if you were solving a problem for a competition.
A few examples are below.
Input:
3
1 5 2
2 4 7
3 6 9
Output:
7 2
The basins, labeled with A’s and B’s, are:
A A B
A A B
A A A
Input:
1
10
Output:
1
There is only one basin in this case.
Input:
5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4 2
3 3 5 2 1
Output:
11 7 7
The basins, labeled with A’s, B’s, and C’s, are:
A A A A A
A A A A A
B B A C C
B B B C C
B B C C C
Input:
4
0 2 1 3
2 1 0 4
3 3 3 3
5 5 2 1
Output:
7 5 4
The basins, labeled with A’s, B’s, and C’s, are:
A A B B
A B B B
A B B C
A C C C| Report Duplicate | Flag | PURGE
Palantir Technology Front-end Software Engineer Algorithm - 1of 5 votes
AnswersGiven an array of positive integers that represents possible points a team could score in an individual play. Now there are two teams play against each other. Their final scores are S and S'. How would you compute the maximum number of times the team that leads could have changed?
- maomaofixer August 17, 2014 in United States
For example, if S=10 and S'=6. The lead could have changed 4 times:
Team 1 scores 2, then Team 2 scores 3 (lead change);
Team 1 scores 2 (lead change), Team 2 score 0 (no lead change);
Team 1 scores 0, Team 2 scores 3 (lead change);
Team 1 scores 3, Team 2 scores 0 (lead change);
Team 1 scores 3, Team 2 scores 0 (no lead change).| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 5 votes
AnswersIn school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
- aonecoding March 22, 2017 in United States
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),
check whether the student qualifies for the reward.
e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.
@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True
Follow-up:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm