Recent Interview Questions
- 1of 1 vote
AnswersYou are given an unsorted integer array of size N. This array contains integer from range 0 - N (not necessarily distinct and same integer can appear multiple time in an array).
- Rajat January 30, 2013 in India
You need to find pair of all the elements in array which sum up to N.
First i gave a solution using an extra array of size N to keep count of each integer in original array and was able to give solution in O(n) Time complexity and O(n) space complexity.
Then interviewer asked me to decrease space complexity, for which i gave solution as sorting the given array (in nlogn time) and then find the pairs in O(n) time, and hence total time complexity was O(nlogn) and space complexity as O(1).
But interviewer kept pressing for a better time complexity (than O(nlogn)) with O(1) space complexity.
How is it possible, i could not think of any way.| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm Arrays - 0of 0 votes
AnswersGiven an array of positive and distinct integers, output all pythogrean triplets of them i.e They have to satisfy: a.a + b.b = c.c
- nishanth2 November 22, 2012 in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array [a1b2c3d4] convert to [abcd1234] with 0(1) space and O(n) time
- kumarasvn October 02, 2012 in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 2of 2 votes
AnswersGiven an array contains positive and negative values, find the subarray, whose sum is most closed to zero. Require nlogn time complexity.
- wolfyink September 06, 2012 in United States| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 0of 0 votes
AnswersYou are given a positive integer A. The goal is to construct the shortest possible sequence of integers ending with A, using the following rules:
- Itcecsa May 02, 2012 in United States
the first element of the sequence is 1,
each of the successive elements is the sum of any two preceding elements (adding a single element to itself is also permissible),
each element is larger than all the preceding elements; that is, the sequence is increasing.
For example, for A = 42, a possible solutions is [1, 2, 3, 6, 12, 24, 30, 42]. Another possible solution is [1, 2, 4, 5, 8, 16, 21, 42].| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersSuppose an array is of the form [i1,i2,i3,i4,c1,c2,c3,c4] where i[1..n] are integer elements and c[1..n] are character elements. Write an in place algorithm so that the resulting array is of the form [i1,c1,i2,c2,i3,c3,i4,c4]. State optimised time and space complexities.
- user4321 January 11, 2012 in India
Example: array: [1,7,9,4,a,x,r,d] should become [1,a,7,x,9,r,4,d].| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersThe glasses are arranged in the following order
1 2 3 4 5 6 7 8 9 10 .................... ....................
When you pour liquid into the 1st glass if it's full, then the extra liquid would be flown into the glasses 2 and 3 in equal quantities. When glass 2 is full, the extra liquid would be flown into 4 and 5 and so on.
- manjunath426jc December 28, 2011 in India
Given an N liters of liquid and capacity of each glass is C and the number of levels of glasses is L. Give the amount of liquid present in each glass if you empty N liters of liquid by pouring into glass 1.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 1of 1 vote
AnswersSMS Problem
- gowtham.n.mail November 25, 2011 in United States
1 - NULL, 2 - ABC, 3 - DEF, 4 - GHI, 5 - JKL, 6 - MON, 7 - PQRS, 8 - TUV, 9 - WXYZ, * - <Space>, # - <Break>
We must convert the numbers to text.
Eg
I/P - O/P
22 - B
23 - AD
223 - BD
22#2 - BA (# breaks the cycle)
3#33 - DE
2222 - 2
2222#2 - 2A
22222 - A (cycle must wrap around)
222222 - B| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer - 0of 0 votes
AnswersGiven an array of integers for each elemnt in the array find the closest greatest elemnt to the right.
- Guest August 22, 2011
Closest means the distance beteen two elements array indices must be miminim . can it be done better 0(n2) ?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answershow to crash your system immediately?
- Domino February 26, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Brain Teasers - 1of 1 vote
Answersthere was a party.there was a log register in which entry and exit time of all the guests was logged.you have to tell the time at which there was maximum guest in the party.
- career.baghel September 11, 2010
input will be the entry and exit time of all the n guests [1,4] [2,5] [9,12] [5,9] [5,12]
the output will be t=5 as there was maximum 3 guest were there namly guest(starting from 1) 2,4 and 5.| Report Duplicate | Flag | PURGE
Google Developer Program Engineer - 0of 0 votes
AnswersHow to find the missing K elements out of the unsorted natural N elements in an integer array.
- Novice June 07, 2010
Time complexity has to be O(n), with 3 extra variables of Space.
One suggestion was to do it in-place in the array.
Is there exists an in place countsort kind of method?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array of n numbers in which all the members are less than or equal to k (k<n). device an algorithm of order O(k) to find the first repeating element.
- Ramesh January 14, 2010| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Arrays Brain Teasers Data Structures Ideas Math & Computation Sorting - -3of 3 votes
AnswersGive two parking locations P1 and P2, P1 and P2 both have n slots. n-1 cars with same IDs are parked in n-1 slots in both P1 and P2. Design an algorithm to let n-1 cars in P1 and P2 park in the same slots
- Anonymous December 30, 2009| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
Answersgiven a number round it off to next power of 2.
- Chop December 29, 2009
eg: if given 3 it should return 4,
if given 5 it should return 8.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersReverse a string , . don't use any temp variable to store the string .
- neal October 07, 2008| Report Duplicate | Flag | PURGE
Apple Microsoft Software Engineer / Developer Software Engineer in Test String Manipulation - 0of 0 votes
AnswersGiven an array having first n ints and next n chars.
- vodangkhoa December 16, 2007
A= i1 i2 i3 ... in c1 c2 c3 ... cn
Write an in-place algorithm to rearrange the elements of the array as:
A = i1 c1 i2 c2 ... in cn| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 6of 0 votes
AnswersImagine there is a square matrix with n x n cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels;
- Edde May 12, 2007| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou are given an array of integers and a sum. Find all pairs of integers that equal that sum. Assume you have some sort of data structures that will be able to store the pairs. Write an algorithm to find all these pairs.
- eww February 14, 2007
Try to think of the non-trivial solutions| Report Duplicate | Flag | PURGE
Zillow Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFind the first non repeating character in a string. For example if the input string "abcdeabc", non repeating character is "e"
- kag May 24, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersGiven a number (200), compare it to four variables (E.G A,B,C,D) and return true if they are all equal to the given number.
- J@sper January 09, 2016 in United States
Do this in the most efficient way, and if possible without if statements.| Report Duplicate | Flag | PURGE
Amazon Computer Scientist C - 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 - 3of 3 votes
AnswersFind longest substring with "m" unique characters in a given string.
- tazo March 12, 2015 in United States
input: aabacbeabbed
output:
4 (aaba) for 2 unique characters
6 (aabacb) for 3 unique characters| Report Duplicate | Flag | PURGE
Google Dynamic Programming Problem Solving - 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 1 vote
AnswersPrint all subset of a given set which sums up to ZERO
- apurohit.in January 09, 2015 in India
{8,3,5,1,-4,-8}
so ans will be : {8,-8}
{3,5,-8}
{3,1,-4}
size of set can be upto 50 but elemet of set can be as big as 18 digit number| Report Duplicate | Flag | PURGE
Amazon Dev Lead Dev Lead Algorithm - 0of 0 votes
AnswersGiven an array containing only stars '*' and hashes '#' . Find longest contiguous sub array that will contain equal no. of stars '*' and hashes '#'.
- Peter August 03, 2014 in India
Order (n) solution required| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 5of 5 votes
AnswersWrite a program to replace each element of an array with a number present on the right side of the element such that the number is least greater than the element. If there is no greater number replace it with -1
- 3139a1m July 02, 2014 in India
e.g : 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28
ans : 18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1
I gave the obvious o(n^2) solution. He asked to optimize it.| Report Duplicate | Flag | PURGE
Adobe SDE1 Algorithm - 2of 2 votes
Answers(Bar Raiser Round)
- gdg June 26, 2014 in United States
Divide the array(+ve and -ve numbers) into two parts such that the average of both the parts is equal.
Input:
[1 7 15 29 11 9]
Output:
[15 9 1 7 11 29]
Explanation:
The average of first two elements is (15+9)/2 = 12, average of remaining elements is (1+7 +11 +29)/4 = 12| Report Duplicate | Flag | PURGE
Amazon Arrays - 2of 2 votes
AnswersYou are given an array with numbers - [11, 3, 11, 11, 3, 2, 0, -2, 2]
- KevinK February 27, 2014 in United States
You are supposed to write a function that returns the number that appears "odd" number of times.
The solution is obviously using HashMap. But that takes O(n) to create the HashMap and O(n) to lookup. How can one eliminate the second O(n) yet keeping the HashMap?
Hint: Do you really need to count frequency of occurrence of each digit?| Report Duplicate | Flag | PURGE
Amazon Principal Software Engineer Arrays