Algorithm Interview Questions
- 4of 4 votes
AnswersGiven infinite array in which the first n cells contain integers in sorted order and rest filled with symbol $. Assume we don't know n value. Give algorithm that takes an integer k as input and finds a position in array in O(logn)
- pirate July 27, 2013 in India| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 4of 4 votes
AnswersYou are given set of strings, You have return anagrams subsets from it. An anagram set is that one where every string is an anagram of another string. If the subset contains only one string, don't include that in the result.
- sonesh May 11, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm String Manipulation - 4of 4 votes
AnswersGiven a linkedlist, write an algorithm to divide the linkedlist into two linkedlists, the first contains the Fibonacci numbers in the list and the second contains the non-Fibonacci numbers.
- a.ahmed.shalabey October 23, 2015 in United States for Software Development
Test the algorithm after developing the code| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm C Data Structures - 4of 4 votes
AnswersDesign and implement the constructor for the minesweeper game that takes in the dimension of the field and number of mines as input
- JSDUDE September 24, 2015 in United States| Report Duplicate | Flag | PURGE
Tableau Software Engineer / Developer Algorithm Object Oriented Design - 4of 4 votes
Answersgiven a matrix of size m * n, place k students in such a way so that cheating in an exam could be minimized
- dddd July 27, 2013 in United States| Report Duplicate | Flag | PURGE
Algorithm Brain Teasers Coding - 4of 4 votes
AnswersFeb On-site Google
- aonecoding March 10, 2018 in United States
DP Problem. Given the length and width of a matrix, get the number of paths from bottom-left to bottom right.
You may only walk into those 3 directions ➡ (right) ↗ (upper-right) ↘ (lower-right) at each point.
Follow-up: optimize 2d DP to 1d DP of linear extra space.
Follow-up: what if some cells are blocked
System Design
Availability test/debug on distributed system. Discussed and drafted about failover, replication, NoSQL etc.
Interviewer seemed to be expecting more but time ran out.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersGiven a list of queries and their counts, write a function that returns one of the queries at random such that over time it returns an equal distribution based on the counts provided in the input.
- Rando May 17, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersGive an 2d-characters Grid, char[][] A, and a dictionary, List<String> dict. Search all possible words in the 2d-Grid.
- wyu277 December 04, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 4of 4 votes
AnswersAmazon
- aonecoding January 06, 2018 in United States
Given an ArrayList of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder.| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 4of 4 votes
Answers1/4 round of FB on-site interview, Master Degree, Hired
- aonecoding July 15, 2017 in United States
1.1 diameter of tree
1.2 find the point which have the maximum overlap of intervals| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 4of 4 votes
AnswersWrite atof in Java, which converts a string representation of a float (like "342.18E-10") to an actual float without using any built-in parsing functions.
- dke.ade February 25, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 4of 4 votes
AnswerWish Interview
- aonecoding November 03, 2017 in United States
-Phone: Two sum, Three sum, N sum(recursion)
Onsite:
-Implement merge sort (recursion&iteration)
-Merge two sorted arrays: one of length m+n, the other n; store the result in the longer array
-Given a number print diamond:
Given 1
Pirnt 1
Given 3
Print
1
121
1
Given 5
Print
1
121
12321
121
1
- Rank N people in a game. There may be a tie among participants. How many possible ways of ranking there is.
- Design: Define a bot as an IP that hits the web app over M times in the past T seconds (not necessarily hits on the same page. Also take into account different API calls.) How to design a bot detector layer and where to place it in the system.| Report Duplicate | Flag | PURGE
Wish Solutions Engineer Algorithm - 4of 0 votes
AnswersThere is an array of 52 numbers ? How do you shuffle this array ? Whats the complexity of your algorithm ? What are the possible test cases ? How do you change the design and or code if this program is used by a house wife or casino?
- Nachiketha October 08, 2008| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 3of 13 votes
AnswersIn a language, there are only 4 characters ‘h’, ‘i’,’r’, ‘e’. and we have to write a function which takes a string as input and returns whether the given input string is a “valid word” or not.
- hugakkahuga October 23, 2013 in India
Definition of valid word :
1. A given word is a valid word if it is of the form h^n i^n r^n e^n where n >=1. (eg: hhiirree)
2. Valid words has concatenation property i.e. if w1 and w2 are valid words w1w2 is also a valid word.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 11 votes
AnswersGiven a binary representation of an integer say 15 as 1111, find the maximum longest continous sequence of 0s. The twist is it needs to be done in log N. I could think of O(N) solution. but couldn't go for log(N).
- TapeRecordia October 24, 2013 in United States
For example. 10000101
the answer should be 4, because there are 4 continouos zeroes.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 7 votes
Answersgiven an input array of integers where each integer represent the maximum amount of jump a frog can take.Frog has to reach the end of the array in minimum number of jumps.
- aka[1] August 05, 2013 in United States
Example:[1 5 4 6 9 3 0 0 1 3] answer is 3 for this.
[2 8 3 6 9 3 0 0 1 3] answer is 2 for this.
Any DP solution for this?| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm - 3of 7 votes
AnswersConsider a hotel where the guest is checked in and check out. Find a day when the maximum number of guests stay in a hotel.
- itsvks February 01, 2017 in Netherlands
example:
Input :
[
{check-in : 1, check-out 4},
{check-in : 2, check-out 5},
{check-in : 10, check-out 12},
{check-in : 5, check-out 9},
{check-in : 5, check-out 12}
]
Output : 5| Report Duplicate | Flag | PURGE
Booking.com Software Engineer / Developer Algorithm - 3of 5 votes
AnswersYou're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of values that satisfy A+B = C + D, where A,B,C & D are integers values in the array.
- omair.ahmed08 October 09, 2014 in United States
Eg: Given [3,4,7,1,2,9,8] array
The following
3+7 = 1+ 9 satisfies A+B=C+D
so print (0,2,3,5)| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm Arrays Data Structures - 3of 5 votes
AnswersPrint all palindromes of size greater than equal to 3 of a given string. (DP)
- amnesiac February 15, 2014 in United States| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm - 3of 5 votes
AnswersGiven a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
- Phoenix December 02, 2014 in United States
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 5 votes
AnswersA string is called sstring if it consists of lowercase english letters and no two of its consecutive characters are the same.
- priteshpathak15 July 29, 2013 in India
You are given string s of length n. Calculate the number of sstrings of length that are not lexicographically greater than s.
Input format
The only line of input contains the string s. It's length is not greater than 100.
All characters of input are lowercase english letters.
Output format:
Print the answer of test modulo 1009 to the only line of output.
Sample input:
bcd
Sample output:
653| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Front-end Software Engineer Algorithm - 3of 5 votes
AnswersThere are N(0 to N-1) players each having at Max 'M' (0 to M-1) number of followers. You have to select minimum number of players so that the total followers must be equal to a given number 'K'.
I/P would be like,
first line contain N, M, K followed by N lines containing string of 0 or 1 s.t. for i'th line if j'th char is 1 it means j'th person follows player 'i'
For. eg.
- P3A July 18, 2013 in India3 6 5 111100 000100 000010 ans=2 ( select 0th and 2nd )
| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 3of 5 votes
AnswersThere are many sorted arrays. Find a minimum range, so that in each array there's at least one integer within this range.
- edcent February 25, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer Intern Algorithm - 3of 5 votes
AnswersA robot has to move in a grid which is in the form of a matrix. It can go to
- thisandthat March 09, 2015 in United States
1.) A(i,j)--> A(i+j,j) (Down)
2.) A(i,j)--> A(i,i+j) (Right)
Given it starts at (1,1) and it has to go to A(m,n), find the minimum number of STEPS it has to take to get to (m,n) and write
public static int minSteps(int m,int n)
For instance to go from (1,1) to m=3 and n=2 it has to take (1, 1) -> (1, 2) -> (3, 2) i.e. 2 steps| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 5 votes
AnswersProblem Statement
- nirajkantsinha March 13, 2015 in United States
Diameter
The diameter of a graph is the maximum shortest path between any two nodes.
At the beginning, there is a simple grpah contains exactly 1 node. Then we add new nodes one by one to the graph. Each time when we add a new node to the graph, we also add exactly one edge to connect this node to another node which already exists.
We want to find the diameter of the graph each time we add a new node. Note that each edge cost 1.
Input Format:
First line of the input contains one integer N, indicating how many new nodes we will add.
Then following N lines. The ith line contains an integer X, which means we add the ith node and an edge connecting the Xth node and ith node.
The original node is the 0th node.
Output Format:
Output N lines. The ith line is an integer indicating the diameter of the graph after adding the ith node.
Constraints:
0 < N <= 100000
0 <= Xi < i
i is counting from 1
Sample Input:
5
0
0
1
1
1
Sample Output:
1
2
3
3
3
Explanation:
Firstly the graph contains only node 0. The first line of output is 1 because the diameter becomes 1 when node 1 is added and connected to node 0. Diameter becomes 2 after adding node 2 to node 0. Then adding node 3, 4, 5, all of them are connecting to node 1, caculate the shortest path of all pairs of nodes, the maximum shortest path is 3, so the last 3 lines of output are all 3.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 3of 5 votes
AnswersGiven an n X n matrix, find all elements which are zero, when found set all the elements in that row and column to zero.
- akula.maheshk September 24, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm - 3of 5 votes
AnswersThere are several people sitting in the cinema, some of them are couples, some are not, they decide to swap their seats so that the couples can seat together, please calculate the minimal swap numbers.
- xblwyc October 07, 2015 in United States
1. the swap can happen between any two position.
2. E.g. AABCCDB -> AADCCBB, ans is 1| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 5 votes
Answersgiven a dictionary of wrods,find the pair of word with following property:
- haozyname November 19, 2013 in china
1,the two word don't have same letter.
2,the multiple of the two word's length is maximum.
i give a simple O(n*n*k)(k is the average length of word) method.but i think there will be better one .| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 5 votes
AnswersGenerate all possible sorted arrays from alternate elements of two given sorted arrays.
- vishgupta92 July 28, 2015 in United States
Given two sorted arrays A and B, generate all possible arrays such that once first element is taken from A then from B then from A and so on in increasing order till the arrays exhausted. Then first element is taken from B then From A, and do same as above.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm