Recent Interview Questions
- 0of 0 votes
AnswersQ1) Given that there are n players and each one of them has played exactly one game with every
- words&lyrics July 12, 2012 in India
other player. Also given is an API that tells whether player ‘a’ won or lost to player ‘b’, where ‘a’ and
‘b’ could be any of the players. Arrange the n players in a length n array such that player at position
‘i’ has won from player at ‘i+1’ and lost to player at ‘i-1’
Interested in linear time solution
PS: Its not a sorting problem. Please notice that problem is not asking for ranking in decreasing order..| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm - 0of 0 votes
AnswersGiven a paragraph of text, write a program to find the first shortest sub-segment that contains each of the given k words at least once. A segment is said to be shorter than other if it contains less number of words.
- manishs747 June 24, 2012 in India
Ignore characters other than [a-z][A-Z] in the text. Comparison between the strings should be case-insensitive.
If no sub-segment is found then the program should output “NO SUBSEGMENT FOUND”.
Input format :
First line of the input contains the text.
Next line contains k , the number of words given to be searched.
Each of the next k lines contains a word.
Output format :
Print first shortest sub-segment that contains given k words , ignore special characters, numbers.If no sub-segment is found it should return “NO SUBSEGMENT FOUND”
Sample Input :
This is a test. This is a programming test. This is a programming test in any language.
4
this
a
test
programming
Sample Output :
a programming test This
Explanation :
In this test case segment "a programming test. This" contains given four words. You have to print without special characters, numbers so output is "a programming test This". Another segment "This is a programming test." also contains given four words but have more number of words.
Constraint :
Total number of character in a paragraph will not be more than 200,000.
0 < k <= no. of words in paragraph.
0 < Each word length < 15| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersA log of wood has n marks on it. Cost of cutting wood at a particular mark is proportional to the length of the log. The log of wood can be cut at all the marks. Find the optimal order of the marks where the log should be cut in order to minimize the total cost of cutting.
- brahmasani99 May 02, 2012 in India| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersThere are two integer arrays ,each in very large files (size of each is larger than RAM). How would you find the common elements in the arrays in linear time.
- doomguy January 20, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersYou have coins with different denominations and you have limited number of each denominations (some maybe zero), how will you determine if you can supply the given change. DP , are you sure? think again.
- __coder November 13, 2011 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a positive integer N, arrange the integers 1 to N such the position of the average of two numbers (if present) falls outside the two numbers. For example, for a[i] and a[j], if b = (a[i] + a[j])/2, then if a[k] = b, k < i or k > j.
- lyra_vega November 09, 2011 in -
Hint :- If the average of two numbers is not an integer then we can assume that they do not have an average.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWrite an 0(n) algorithm for detecting conflicts in appointments.
- jp January 06, 2011public class Appointment { long startTime; long endTime; boolean hasConflict; } public static ArrayList<Appointment> markCOnficts(ArrayList<Appointment> apntmnts) //your code here..for each appointment if it //has a conflict you need to set hasConflict //parm = true
| Report Duplicate | Flag | PURGE
Google Developer Program Engineer - 0of 0 votes
AnswersWrite a program to remove duplicate elements from array.(Array contains elements in range 1...N). Algorithm must be O(N) in time and O(1) in space. Come up with as many test cases as you can.
- omkar November 02, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - 0of 0 votes
AnswersFind the largest 1 million numbers in 1 billion numbers. Supposed the memory can hold all the one billion numbers.
- liandage June 13, 2007
The interviewer said there exist a O(n) solution, anyone has any hint?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow will you determine if a loop exists in a link list?
- Philip July 24, 2006| Report Duplicate | Flag | PURGE
Expedia Amazon NVIDIA Knoa Software Apple Software Engineer / Developer Intern Algorithm Linked Lists - 2of 2 votes
AnswersGiven some resources in the form of linked list you have to canceled out all the resources whose sum up to 0(Zero) and return the remaining list.
- ganesh.eng2015 July 24, 2016 in India
E.g-->> 6 -6 8 4 -12 9 8 -8
the above example lists which gets canceled :
6 -6
8 4 -12
8 -8
o/p : 9
case 3 : 4 6 -10 8 9 10 -19 10 -18 20 25
O/P : 20 25| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersList of string that represent class names in CamelCaseNotation.
- lavankumarmuvalla July 07, 2016 in United States
Write a function that given a List and a pattern returns the matching elements.
['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo']
H -> [HelloMars, HelloWorld, HelloWorldMars, HiHo]
HW -> [HelloWorld, HelloWorldMars]
Ho -> []
HeWorM -> [HelloWorldMars]| Report Duplicate | Flag | PURGE
Google String Manipulation - 0of 2 votes
AnswersWrite all jumbled number which is >0 && <N, where N is provided by the user.
- Harsh123 June 12, 2016 in India
A jumbled number is a number whose neighbour digit (either left or right) max differ by 1 value.
e.g.:
8987 is a jumbled number.
13 is not a jumbled number.
123456 is a jumbled number.
287 is not jumbled number.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Problem Solving - 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 - 0of 2 votes
AnswersGiven a sorted array, find a way to find the # of occurrence of a number
- aj June 09, 2015 in United States
for eg: [1, 1, 2, 3, 3, 3, 4, 5]
find # of occurrence of 3 in time better than O(n)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
Answers/*Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die. Given a flowerbed (represented as an array containing booleans), return if a given number of new flowers can be planted in it without violating the no-adjacent-flowers rule
- aj June 02, 2015 in United States
Sample inputs
Input: 1,0,0,0,0,0,1,0,0
3 => true
4 => false
Input: 1,0,0,1,0,0,1,0,0
1 => true
2 => false
input: 0
1 => true
2 => false */
public boolean canPlaceFlowers(List<Boolean> flowerbed, int numberToPlace) {
// Implementation here
}| Report Duplicate | Flag | PURGE
Linkedin Applications Developer Coding - 2of 2 votes
AnswersYou have a function rand5(). This function returns numbers between 1 and 5 randomly with equal probability. Implement a function rand7() which makes use of rand5 to return a number between 1 and 7 randomly with equal probability.
- reddygokul.i7 February 27, 2015 in India| Report Duplicate | Flag | PURGE
Intern Algorithm Arrays Java Python - 0of 0 votes
AnswersWrite a function that takes an array of numbers and returns the maximum and minimum values.
- trophygeek February 21, 2015 in United States
Give BigO for runtime.
(This is a basic coding question. There are no real tricks or shortcuts.)| Report Duplicate | Flag | PURGE
Google Software Engineer Coding - 0of 0 votes
AnswersGiven an array of positive and negative numbers(no zeroes),i have to arrange them in such a way that the positive and negative numbers should be arranged consecutively.The number of positive and negative numbers may not be equal i.e. if there is no positive number(or negative) left,then all the remaining negative numbers(or positive) are appended to the end of the array.The order is important i.e.if input array is { 2,-1,-3,-7,-8,9,5,-5,-7},then the output array should be {2,-1,9,-3,5,-7,-8,-5,-7}.The code is done in O(n) without using another array.I came up with a solution in which i chose 0 as pivot element and separate the numbers (using quicksort) but in this case the order is not preserved.
- sudeep.chauhan24 September 01, 2014 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - -4of 8 votes
AnswersGiven an array of positive and negative numbers, arrange them in an alternate fashion such that every positive number is followed by negative and vice-versa maintaining the order of appearance.
Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.*
Example:Input: arr[] = {1, 2, 3, -4, -1, 4} Output: arr[] = {-4, 1, -1, 2, 3, 4} Input: arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8} output: arr[] = {-5, 5, -2, 2, -8, 4, 7, 1, 8, 0}
Limitations:
- gdg August 27, 2014 in United States
a) Use O(1) extra space
b) Time Complexity should be O(N)
c) Maintain the order of appearance of elements as in original array.| Report Duplicate | Flag | PURGE
Google - 4of 4 votes
Answersgive an algorithm for finding duplicate parenthesis in a expression.
example :
- rahul May 02, 2014 in United States(( a + b ) + (( c + d )))
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Stacks - 2of 4 votes
AnswersGiven a dictionary, and a list of letters ( or consider as a string), find the longest word that only uses letters from the string. [I didn't meet this question, what's the best solution?]
- Obiwana March 11, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersGiven an array of +ve as well as -ve numbers, find out whether it is possible or not to convert it to 0 by adding/subtracting operations on all the elements.
- prateeksinghal January 17, 2014 in India
e.g arr[]={1,2,3}
YES (1+2-3)
arr[]={3,6,2}
3+6-2 != 0
3-6-2 !=0
-3-6-2 !=0
-3-6+2 !=0
-3+6-2 !=0
-3+6+2 !=0
3-6+2 !=0
3+6+2 !=0
Hence ans= NO| Report Duplicate | Flag | PURGE
Amazon Intern Algorithm - 6of 6 votes
AnswersYou visited a list of places recently, but you do not remember the
- UserOne November 05, 2013 in United States
order in which you visited them. You have with you the airplane
tickets that you used for travelling. Each ticket contains just the
start location and the end location. Can you reconstruct your journey?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersReplace element of an Array with nearest bigger number at right side of the Array in O(n)
- SachinG2 October 23, 2013 in India
For example if the input Array is
7, 5, 6, 3, 4, 1, 2, 9, 11
output array should be
9, 6, 9, 4, 9, 2, 9, 11, 11| Report Duplicate | Flag | PURGE
PayPal Member Technical Staff Algorithm - 1of 1 vote
AnswersIt was a pretty interesting question.
- b2010 September 25, 2013 in United States
Assume that you are given a fixed set of floating point numbers. Now given a new floating point number 'x', the goal is to efficiently find the number that is closest to 'x' from the fixed set. Question is: what data structure will you actually use for storing the fixed set of floating point numbers to achieve this?
Edit:
I missed to add. The interviewer further mentioned that I can not sort and that I can use any amount of time for creating the data structure (meaning this need not be efficient).
Since, I am not allowed to 'sort', I assumed that I can not use BST as I will have to compare numbers while populating the tree. But I didn't clarify it with him; I should have in hindsight.| Report Duplicate | Flag | PURGE
Amazon Research Scientist Data Structures - 1of 7 votes
AnswersGiven an array of numbers, arrange it such that all the numbers less than a given key should come before the key and all the numbers greater than the key should come after it.
- Vasily_Zaytsev June 30, 2013 in United States
For example: arr = { 0, -1, -2, 2, 0, 3, 5}, given key = 0
answer should be {-1, -2, 0, 0, 2, 3, 5}
Order of elements that are smaller or greater than key does not matter i.e. sorting is not expected. So, {-1,-2, 0, 0, 5, 2, 3} is also a correct answer.
Time complexity should not be more than O(n).| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - 1of 1 vote
AnswersGiven an array of positive integers, find the max no that can be formed by any permutation of the arrangement.
- Vin June 26, 2013 in India
input {21,9,23}, output = 92321| Report Duplicate | Flag | PURGE
Amazon SDE1