Recent Interview Questions
- 3of 3 votes
Answersone unsorted array is given.Find out the index i and j ,j> i for which a[j] - a[i] is maximum.perform in linear time complexity
- rahul baid February 17, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Data Structures Arrays - 3of 3 votes
AnswersPrint a character 1000 times without using loop and recursion.
- arun September 07, 2012 in India| Report Duplicate | Flag | PURGE
ThoughtWorks Applications Developer - 3of 3 votes
AnswersQ1.- Written exam (Amazon, Bangalore)
- Nitin Gupta May 12, 2012 in India
Given a singly link list and a number 'K', swap the Kth node from the start with the Kth node from the last. Check all the edge cases.
Sample Input: 1->2->3->4->5->6->7->8 and K = 3
Sample Output : 1->2->6->4->5->3->7->8
Sample Input: 1->2->3->4->5->6->7->8 and K = 10
Sample Output: print error "LIST IS OF LESSER SIZE".| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm C C# C++ Coding Data Structures Java Linked Lists - 3of 3 votes
AnswersGiving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.
- IKnowThings January 28, 2017 in United States
eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple"
I was thinking of the following approach,
Build a Trie for all words in the Dict - O( n * k) where k is the longest string in the dict
For each character c, in S check if there is a word in Trie that starts with it and has the letters that appear in S after c. We can short circuit based on remaining characters and the length of longest string found so far.
This should take O( N * k) where N is length of S.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven a circular single linked list.Write a program that deletes every kth node until only one node is left.
- Aashish August 01, 2012 in India
After kth node is deleted, start the procedure from (k+1)th node.
e.g.list is 1->2->3->4->5->1
k=3
1. You are at 1, delete 3.
List is: 1->2->4->5->1
2. You are at 4, delete 1
List is: 2->4->5->2
3. You are at 2,delete 5
List is: 2->4->2
4. You are at 2, delete 2
List is: 4
Return 4.
How efficient you can do it?| Report Duplicate | Flag | PURGE
Amazon Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a binary search tree (BST), write a mehtod that will convert this BST into a doubly linked list that is sorted (ascending or descending order) and returns the first element in this list. You may assume you are given following Node class:
public class Node { public Node left, right; public String val; }
Example: The following BST
- autoboli January 06, 2015 in United States
G
/ \
A T
can be converted into a list
A = G = T
Do it in place! Hnce the memory complexity of your algorithm shoul be O(1).| Report Duplicate | Flag | PURGE
Google Algorithm - 3of 3 votes
AnswersCheck if an integer array is arithmetic sequence.
- PS February 08, 2016 in United States
Example: 1, 2, 3, 4, 5, 6, 7, 8 => true
1, 3, 5, 7, 9 => true
Array may not be sorted.| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 3of 3 votes
AnswersGiven a value and a binary search tree.
- vodangkhoa April 24, 2007
Print all the paths(if there exists more than one) which sum up to that value. It can be any path in the tree. It doesn't have to be from the root.| Report Duplicate | Flag | PURGE
Microsoft Yahoo Software Engineer / Developer Trees and Graphs Coding Algorithm - 3of 3 votes
AnswersQuestion: Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T
- ep February 27, 2015
Example
[23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20
[1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8
[1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersYou are given a string S. Each character of S is either ‘a’, or ‘b’. You wish to reverse exactly one sub-string of S such that the new string is lexicographically smaller than all the other strings that you can get by reversing exactly one sub-string.
- Rahul Sharma October 09, 2014 in India
For example, given ‘abab’, you may choose to reverse the substring ‘ab’ that starts from index 2 (0-based). This gives you the string ‘abba’. But, if you choose the reverse the substring ‘ba’ starting from index 1, you will get ‘aabb’. There is no way of getting a smaller string, hence reversing the substring in the range [1, 2] is optimal.
Input:
First line contains a number T, the number of test cases.
Each test case contains a single string S. The characters of the string will be from the set { a, b }.
Output:
For each test case, print two numbers separated by comma; for example “x,y” (without the quotes and without any additional whitespace). “x,y” describe the starting index (0-based) and ending index respectively of the substring that must be reversed in order to acheive the smallest lexicographical string. If there are multiple possible answers, print the one with the smallest ‘x’. If there are still multiple answers possible, print the one with the smallest ‘y’.
Constraints:
1 ? T ? 100
1 ? length of S ? 1000
Sample Input:
5
abab
abba
bbaa
aaaa
babaabba
Sample Output:
1,2
1,3
0,3
0,0
0,4| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 3of 3 votes
AnswersConsider an array of integers wherein each element is +1 or -1 its preceding element. Given a number, find the first occurence of this number (index) in this array without using linear search.
- nilukush June 04, 2013 in India for World Wide Operations
For example, consider the array :
4 5 6 5 6 7 8 9 10 9 10 (each element in this array is +1 or -1 its preceding element)
Input : 10 (find first occurence of 10 without using linear search)
Output : 8| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm Arrays - 3of 3 votes
AnswersYou are given a dictionary, in the form of a file that contains one word per line. E.g.,
- audi March 14, 2013 in United States
abacus
deltoid
gaff
giraffe
microphone
reef
qar
You are also given a collection of letters. E.g., {a, e, f, f, g, i, r, q}.
The task is to find the longest word in the dictionary that can be spelled with the collection of
letters. For example, the correct answer for the example values above is “giraffe”. (Note that
“reef” is not a possible answer, because the set of letters contains only one “e”.)| Report Duplicate | Flag | PURGE
Google Algorithm - 3of 3 votes
AnswersWrite a program to determine whether n/2 distintinctve pairs can be formed from given n integers where n is even and each pair's sum is divisible by given k. Numbers cannot be repeated in the pairs, that means only you can form total n/2 pairs.
- topjobsncr October 09, 2012 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a length n, return the number of strings of length n that can be made up of the letters 'a', 'b', and 'c', where there can only be a maximum of 1 'b's and can only have up to two consecutive 'c's
- djway August 10, 2016 in United States for None
Example:
findStrings(3) returns 19
since the possible combinations are: aaa,aab,aac,aba,abc,aca,acb,baa,bac,bca,caa,cab,cac,cba,cbc,acc,bcc,cca,ccb
and the invalid combinations are:
abb,bab,bba,bbb,bbc,bcb,cbb,ccc| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
Answerssuppose a string is consists of a, b, and c
- codingfunnyguy November 25, 2013 in United States
Now given a integer N, output the amount of all possible strings of length N that don't of have consecutive a,b,c.
e.g. given N=5, string bacca is invalid since the first 3 letters have consecutive a,b,c. and bbbbb is valid.| Report Duplicate | Flag | PURGE
Google Algorithm - 3of 3 votes
AnswersThere are N pots. Every pots have some water in it. They may be partially filled. So there is a Overflow Number 0 associated with every pot which tell how many minimum stone pieces are require for that pot to overflow. So if for a pot 0-value is 5 it means minimum 5 stone pieces should be put in that pot to make it overflow. Initially a crow watched those pots and by seeing the water level he anticipated 0-value correctly for every pot ( that is he knew 01 to On). But when he came back in evening he found that every pot is painted from outside and he is not able to know which pot has what 0-value. Crow wants some K pots to overflow so that he can serve his child appropriately. For overflow of pots he need to search for stone in forest( assume that every stone has same size). He wants to use minimum number of stones required to overflow K pots. But only he know the 0-value of pots he doesn't know now which pot has what 0-value. So the task is that in what minimum number of stones he can make K pots overflow in worst case.
- veeru April 29, 2015 in India for Development
Input/Output Specifications Input Specification: 1) A array 0 corresponding to 0-value of N pots {01, 02, On} 2) Number of pots 3) K -value ( number of pots which the crow wants to overflow}
Output Specification: Minimum number of stones required to make K pots overflow in worst case. Or -1 if input is invalid
Example: Let say there are two pots pot 1 has 0 value of 5 , 01= 5 pot 2 has 0 value of 58, 02= 58 Let say crow wants to make one of the pot to overflow. If he know which pot has what 0-value he would simple search for 5 stones and put then in pot 1 to make it overflow. But in real case he doesn't know which pot has what 0-value so just 5 stones may not always work. However he does know that one pot has 0-value S and other has 58. So even in worst case he can make one of the pot overflow just by using 10 stones. He would put 5 stones in one pot if it doesn't overflow he would try the remaining 5 in the other pot which would definitely overflow because one of the pot has 0-value of 5. So the answer for above question is minimum 10 stones even in worst case. Input : Input 1= {5,58} Input 2= 2 Input 3= 1 Output : 10| Report Duplicate | Flag | PURGE
Amazon Software Engineer - 3of 3 votes
AnswersGiven a dictionary that contains mapping of employee and his/her manager like this
- enok April 09, 2015 in United States
Dictionary<string, string> employees = new Dictionary<string, string>()
{
{ "A","C" },
{ "B","C" },
{ "C","F" },
{ "D","E" },
{ "E","F" },
{ "F","F" }
};
Write a function to get no of employees under each manager in the hierarchy not just their direct reports.
In the above dictionary the root node/ceo is listed as reporting to himself.
Output should be a Dictionary<string,int> that contains this
A - 0
B - 0
C - 2
D - 0
E - 1
F - 5| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm - 3of 3 votes
AnswersGiven: sorted array of integers
- 123georgedavid September 21, 2016 in United States
Return: sorted array of squares of those integers
Ex: [1,3,5] -> [1,9,25]
Integers can be negative.| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 3of 3 votes
AnswersGiven two binary numbers each represented as a string write a method that sums up the binary numbers and returns a result in the form of binary number represented as a string. You may assume that input fits in the memory and the input strings are, in general, of different length. Optimize your solution, do not use unnecessary 'if' branching.
example:sumBinary('0111101', '1101')
returns
- autoboli April 21, 2015 in United States
'1001010'| Report Duplicate | Flag | PURGE
Amazon - 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 - 3of 3 votes
AnswersFind the k'th largest element in a binary search tree. Write code for
- jtr.hkcr March 03, 2013 in United Statesstruct Node { int val; struct Node *left; struct Node *right; } Node; Node * kth_largest(Node *root, unsigned int k);
| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Coding - 3of 3 votes
AnswersGiven an array A[], find (i, j) such that A[i] < A[j] and (j - i) is maximum.
- lyra_vega November 09, 2011 in -| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersYou are given an array of N elements.arrange array in such a way that sum of any cunsucative k numbers are divisible
- dilip kasana October 25, 2012 in India
by NUM.if not possible print -1.(it may possible that there are many solution possible then return any one)
For example:
N=6
k=3
NUM=63
array={80,17,90,82,27,19}
Answer:{19,17,27,82,80,90}
any 3 cunsucative no. like (27+82+80)%63=0
another solution={27,19,17,90,82,80}
may be a hint :try to group all no.'s in mod NUM map and use vector and map.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a bst and a group of numbers g, check whether all the elements of g occur in the same path.
- thebiker925 September 12, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 3of 3 votes
AnswersA binary search tree is given. Find the ceiling value present in the BST of a given key.
eg-8 3 12 2 6 10 15 4
key - 13 => 15
- LAP June 24, 2013 in United States
key - 4 =>6
key - 8 =>10| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 3of 3 votes
AnswersGiven a String find the first non repeating char in a single pass of the string.
- um01 April 18, 2015 in United States
Assume a big character set like utf-8 (eleminate use of char[256])
Avoid any subloop to have a very optimal solution| Report Duplicate | Flag | PURGE
Yahoo SDE1 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 - 3of 3 votes
AnswersFind the seed of a number.
- flash March 23, 2012 in United States
Eg : 1716 = 143*1*4*3 =1716 so 143 is the seed of 1716. find all possible seed for a given number.| Report Duplicate | Flag | PURGE
Epic Systems - 3of 3 votes
AnswersCount smaller elements on right side
- NaiveCoder February 27, 2012 in India
eg : [4,12,5,6,1,34,3,2]
o/p [3,5,3,3,0,2,1,0]| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 3 votes
AnswersGiven an input string and ordering string, need to return true if the ordering string is present in Input string.
- ranjith2jeeth August 04, 2016 in United States
input = "hello world!"
ordering = "hlo!"
result = FALSE (all Ls are not before all Os)
input = "hello world!"
ordering = "!od"
result = FALSE (the input has '!' coming after 'o' and after 'd', but the pattern needs it to come before 'o' and 'd')
input = "hello world!"
ordering = "he!"
result = TRUE
input = "aaaabbbcccc"
ordering = "ac"
result = TRUE| Report Duplicate | Flag | PURGE
Uber Software Engineer String Manipulation