Recent Interview Questions
- 1of 3 votes
AnswersFirst greater number in an array. Given a large array of positive
- nim January 24, 2012 in United States
integers, for an arbitrary integer A, we want to know the first integer in
the array which is greater than or equal A . O(logn) solution required
ex [2, 10,5,6,80]
input : 6 output : 10
input :20 output : 80| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
Answersgiven an integer find the next(smallest number greater than given number) integer which is palendrom
- getjar.com/todotasklist my android app November 17, 2011 in India
for ex 111 next palendrom 121
301 next palendrom 313| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersDifference is Minimum
- manu January 31, 2011
Algorithm to find the two numbers whose difference is minimum among the set of numbers.
For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19
The algorithm should return min diff = 20-19 = 1.
Constraint - Time Complexity O(N) & Space is not a constraint [upto O(3N)]
Assumption - Sorting O(nlogn) & comparison of adjacent numbers is already known & is not an option. Try to keep it linear| Report Duplicate | Flag | PURGE
Microsoft Amazon Software Engineer / Developer Software Engineer in Test Algorithm - 1of 1 vote
Answersyou are given 2 arrays sorted in decreasing order of size m and n respectively.
- SA August 29, 2010
Input: a number k <= n*n and >= 1
Output: the kth largest sum(a+b) possible. where
a (any element from array 1)
b (any element from array 2)
The Brute force approach will take O(n*n). can anyone find a better logic. thnkx in advance.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -2of 2 votes
AnswersWrite an algorithm to find out how many different summations you can compute using numbers range from 1 to 1000. 2 constrains
- tagle November 22, 2009
1) Each valid sum must be less than 10000
2) A number can only be used once for a sum
example:
1+2+300 < 10000 is valid
1+2+300+400 < 10000 is valid
1+2+2 is not valid (2 appear twice)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a binary tree with the following node structure
- Idea July 20, 2009
struct node
{
//data
//pointer to left subtree
//pointer to right subtree
//pointer to sibling
};
The sibling pointers are NULL for all the nodes.Make the sibling pointers point to their respective nodes in O(n)time complexity| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Trees and Graphs Algorithm - 0of 0 votes
AnswersGiven two log files, each with a billion usernames (each username appended to the log file), find the usernames existing in both documents in the most efficient manner? Use pseudo-code or code. If your code calls pre-existing library functions, create each library function from scratch.
- dotNet February 20, 2006| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Coding Algorithm Object Oriented Design - 2of 2 votes
AnswersFind whether string S is periodic.
- acoding167 June 07, 2019 in United States
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"
follow up:
Given string S, find out the P (repetitive pattern) of S.| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 0of 0 votes
AnswersGiven two sorted arrays A and B that may have repeated elements. Form a new sorted array C that contains the elements of A and B [Condition : You are not allowed to merge the two arrays and then sort. ]
- nidhi.prakash.410 January 23, 2017 in India| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer - 0of 0 votes
AnswersGiven a stream of characters (e.g. acacabcatghhellomvnsdb) and a list of words (e.g. ["aca","cat","hello","world"] ) find and display count of each and every word once the stream ends.(Like : "aca" : 2 , "cat" : 1 , "hello" : 1 , "world" : 0 ).
- badebhaiyya April 16, 2016 in United States| Report Duplicate | Flag | PURGE
Booking.com Software Developer Algorithm - 0of 0 votes
Answersgiven a string, calculate the frequency of characters, output the array with the letter and frequency. (such as: for “abbcdc”, the output should be (a,1),(b,2),(c,2),(d,1))
- eminsqa January 26, 2016 in United States for AmazonMusic| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer Quality Assurance Algorithm Java - 5of 5 votes
AnswersGiven a prime set, we call "prime expressible" if a number can be factorized only using given prime numbers. Find n-th big expressible number.
- pandacoder October 30, 2015 in United States
E.g., prime set = {2, 3}
expressible number = {1,2,3,4,6,8, 9, 12...}
non-expressible number = {5, 10... }
The primes in the prime set are ordered in an increasing order, and can include a prime < 10^4 (don't remember the exact range), and n can also be as large as 1-10^6.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven an array of integers. Modify the array by moving all the zeros to the end (right side). The order of the other elements doesn't matter.
- m.mirzamo October 28, 2015 in United States| Report Duplicate | Flag | PURGE
Facebook Intern Algorithm Data Structures - 1of 1 vote
AnswersCounting the islands.
- byPaco September 15, 2015 in United States
Given a map N x N, 2-D array
0 - sea
X - land
Land is connected by 4-Neighbor connections, i.e.: above, down, left and right.
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
0000000000000000000X000000000000000
000000000000000000XXX00000000000000
000XX000000000000000000000000000000
000XXXX0000000000000000000000000000
0000000X000000000000000000000000000
00000000000000000000000000000000000
000000000000000000000X0000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
Output of this map: 4 (totally 4 islands on the map)| Report Duplicate | Flag | PURGE
Google iOS Developer - 6of 8 votes
AnswersGiven an unsorted array of natural numbers. Where numbers repeat in array. Out put numbers in the order of frequency. Where number of out put is passed as parameter.
- dreamchaser1984 March 25, 2015 in United States
For Ex:
Array -> [0, 0, 100, 3, 5, 4, 6, 4, 2, 100, 2, 100]
n -> 2
Out put -> [100, 0] or [100, 2]
Since 100 is repeated 3 times and 0, 2 is repeated 2 times, out put up to 2 most frequent elements, program should out put either 100, 0 or 100, 2| Report Duplicate | Flag | PURGE
Google Principal Software Engineer Algorithm - 2of 2 votes
AnswersConsider the 52 cards of a deck. You generated a random sequence for these cards and want to send that sequence to a receiver. You want to minimize the communication between you and the receiver, i.e., minimize the number of bits required to send the sequence.
- eng.ahmed.moustafa February 23, 2015 in United States
What is the minimum number of bits required to send the sequence?
Hint: It is not 6 x 52| Report Duplicate | Flag | PURGE
Google Software Engineer Arrays - 13of 13 votes
AnswersA book contains with pages numbered from 1 - N. Imagine now that you concatenate all page numbers in the book such that you obtain a sequence of numbers which can be represented as a string. You can compute number of occurences 'k' of certain digit 'd' in this string.
- autoboli January 16, 2015 in United States
For example, let N=12, d=1, hence
s = '123456789101112' => k=5
since digit '1' occure five times in that string.
Problem: Write a method that, given a digit 'd' and number of its occurences 'k', returns a number of pages N. More precisely, return a lower and upper bound of this number N.
Example:
input: d=4, k=1;
output {4, 13} - the book has 4-14 pages
input d=4 k=0;
output {1, 3} - the book has 1-3 pages| Report Duplicate | Flag | PURGE
Google - 5of 5 votes
AnswersGiven an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number target.
- rjrush December 06, 2014 in United States
If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|
You can assume each number in the array is a positive integer and not greater than 100
Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 0of 0 votes
AnswersHow to find non- common elements between two string arrays. Eg: String a[]={"a","b","c","d"};
- ananth.gorthi August 24, 2014 in India
String b[]={"b","c"};
O/p should be a,d| Report Duplicate | Flag | PURGE
Amazon SDE-2 Java - 2of 2 votes
AnswersYou are given an array of both negative and positive integers. You need to rearrange the array such that positive and negative numbers alternate. Also, the order should be same as previous array and only O(1) auxiliary space can be used and time complexity boundation O(n).
- peechus July 29, 2014 in United States
eg. -2 3 4 5 -1 -6 7 9 1
result – 3 -2 4 -1 5 -6 7 9 1.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 8of 10 votes
AnswersFind next higher number with same digits.
- codechamp April 02, 2014 in United States for Knowledge Graph
Example 1 : if num = 25468, o/p = 25486
Example 2 : if num = 21765, o/p = 25167
Example 3 : If num = 54321, o/p = 54321 (cause it's not possible to gen a higher num than tiz with given digits ).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Ideas - 14of 14 votes
AnswersGiven a 2-D matrix represents the room, obstacle and guard like the following (0 is room, B->obstacle, G-> Guard):
- Obiwana March 10, 2014 in United States
0 0 0
B G G
B 0 0
calculate the steps from a room to nearest Guard and set the matrix, like this
2 1 1
B G G
B 1 1
Write the algorithm, with optimal solution.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersGiven two String, s1 and s2.
- niraj.nijju October 15, 2013 in India
to find the longest substring which is prefix of s1, as well as suffix of s2.| Report Duplicate | Flag | PURGE
Amazon Algorithm - 5of 5 votes
AnswersThere are n bombs in a big circle,and each bomb has a value and a 'effect range'.If you detonated a bomb,you will get this bomb's value,but a bomb can have effect on the neighbors which the distance(difference between index) between them is smaller than the 'effect range'.It's say that the neighbor bomb will be destoryed and you could not get their values.
- lxfuhuo September 13, 2013 in CHINA
You will given each bomb's value and the 'effect range',and you need calculate the max value you can get.
eg. n=3 index 0's bomb' v is 2,range is 0(will not effect others).and v[1]=1,r[1]=1,v[2]=3,r[2]=1;
this case's max value is 5.(detonate the 0's and than the 2's).
HELP ME.
ps: It's a interval DP.| Report Duplicate | Flag | PURGE
Google Intern Algorithm - -1of 1 vote
AnswersDelete the repeated elements in a singly linked list in O(n) time complexity without using extra space. Linked list contains elements in unsorted order
- Saurabh Singhal August 22, 2013 in India
P.S. - Sorting is not allowed| Report Duplicate | Flag | PURGE
VMWare Inc Intern Coding Data Structures Linked Lists - 3of 3 votes
AnswersGiven a string pattern of 0s, 1s, and ?s (wildcards), generate all 0-1 strings that match this pattern.
- lsecrease June 25, 2013 in United States
e.g. 1?00?101 -> [10000101, 10001101, 11000101, 11001101].
You can generate the strings in any order that suits you.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersYou have two sorted list A and B.
- xankar April 07, 2013 in United States
A = [1, 3, 4, 6,8,10, 17, 34]
B = [2, 8, 17, 33, 44, 66, 89, 100, 123]
Write a program to print those numbers which are
1) in A and not in B
2) in B and not in A
Eg: After print: 1 , 3 , 4 , 6 , 10, 33, 34, 44,, 66, 89, 100, 123
I was asked to write this in JAVA.| Report Duplicate | Flag | PURGE
Morgan Stanley Senior Software Development Engineer Algorithm Java