Algorithm Interview Questions
- 0of 0 votes
AnswerWrite a function that compares Spanish strings, how would you handle special cases like 'ch' ?
- Gear November 17, 2016 in United States
c < ch < d, ch will be represented as 2 ASCII characters| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven a function getRandom that returns a random double in [0,1). Write a function getRandomPermutation(int n) that takes a positive integer n as argument and returns a random permutation of first n natural numbers.
- AlgoBaba November 15, 2016 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a nxn matrix, with partially filled cells of numbers from 1..n and the rest with 0's. Fill the cells such each row and column has numbers 1 to n without any repetition.
- faizvf November 14, 2016 in United States
Eg:
[
[1, 2, 0],
[0, 1, 0],
[0, 0, 1]
]
[
[1, 2, 3],
[3, 1, 2],
[2, 3, 1]
]| Report Duplicate | Flag | PURGE
Yahoo SDE1 Algorithm - 3of 3 votes
AnswersDefine amazing number as: its value is less than or equal to its index. Given a circular array, find the starting position, such that the total number of amazing numbers in the array is maximized.
- wtcupup2017 November 13, 2016 in United States
Example 1: 0, 1, 2, 3
Ouptut: 0. When starting point at position 0, all the elements in the array are equal to its index. So all the numbers are amazing number.
Example 2: 1, 0 , 0
Output: 1. When starting point at position 1, the array becomes 0, 0, 1. All the elements are amazing number.
If there are multiple positions, return the smallest one.
should get a solution with time complexity less than O(N^2)| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersGiven 'n' circles (each defined by center and radius)
- sheva November 12, 2016 in United States
Write an algorithm to detect if circles intersect with any other circle in the same plane
Better than O(n^2) complexity| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a sorted array, and given a number n, find number of times n occurs in the array.
- bharos92 November 11, 2016 in United States for NSBU| Report Duplicate | Flag | PURGE
VMWare Inc Software Engineer Intern Algorithm - 1of 1 vote
AnswersGiven the village of a map represented as a 2D grid containing houses,bushes and open-spaces, write a program to find a point for conducting a meeting in the map. Such point should be minimum from all the houses in the village.
Eg.# # # # # # # A # # B # # # # # # # C # # # # # #
# -> represents the bushes
- angry_scorpion November 10, 2016 in United States
A, B, C -> position of houses
I provided a O(n*a*b) approach, where n-> no. of houses , a,b->dimensions of the grid.
The interviewer asked me for some special cases. Can it be done more efficiently?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersUsing that data structure, devise an algorithm to compute the dot product between two sparse matrices.
- Brookekelseyryan November 05, 2016 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersWe are given a book with N number of pages and two words. Find the distance(in pages) between the first occurrence of first word and first occurrence of second word. For Example, you are given the book "Thinking in C++" and two words 1. "Inheritance" whose first occurrence is in page 220 and 2. "Polymorphism" whose first occurrence is in page 350, the result would be 130. You can take your decision to choose how the data structure of the book would be.
- iamaniceboy16 November 05, 2016 in United States| Report Duplicate | Flag | PURGE
Bank of America Dev Lead Algorithm - 1of 1 vote
AnswersMagical binary strings are non-empty binary strings if the following two conditions are true:
- zandu November 01, 2016 in India
The number of 0's is equal to the number of 1's.
For every prefix of the binary string, the number of 1's should not be less than the number of 0's.
A magical string can contain multiple magical substrings. If two consecutive substrings are magical, then we can swap the substrings as long as the resulting string is still a magical string. Given a magical binary string, str, perform zero or more swap operations on its consecutive magical substrings such that the resulting string is aslexicographically large as possible. Two substrings are considered to be consecutive if the last character of the first substring occurs exactly one index before the first character of the second substring.
-----
Input Format
a single binary string, str.
Constraints
It is guaranteed that str is a binary string of 1's and 0's only.
1 ≤ length(str) ≤ 50
It is guaranteed that str is a magical string.
Output Format
Find a string denoting the lexicographically largest magical string that can be formed from str.
Sample Input 0
11011000
Sample output
11100100
Explanation of sample
Given the magical string str = 11011000, we can choose two consecutive magical substrings, 1100 and 10, to swap such that the resultant string, str' = 11100100, is the lexicographically largest possible magical string possible. Thus, we return the value of str', which is 11100100, as our answer.
.| Report Duplicate | Flag | PURGE
N/A Software Engineer Algorithm - 3of 3 votes
AnswersGiven the root of a Binary Tree along with two integer values. Assume that both integers are present in the tree.
- teli.vaibhav October 30, 2016 in United States
Find the LCA (Least Common Ancestor) of the two nodes with values of the given integers.
2 pass solution is easy. You must solve this in a single pass.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersYou are given 2 lists -
List 1: List<Demand> is a list of Demand objects.
List 2: List<Supply> is a list of Supply objects.
Return a result fulfillment List<Demand,List<Supply>>.
This means each demand could be satisfied by more than one supplies.class Demand { Date startDate; Date expirationDate; int quantity; } class Supply { Date startDate; Date expirationDate; int quantity; }
The Demand and Supply refers to that of groceries. You must map supplies to a demand only if the supply still has at least 3 days remaining to its expiration before the demand can be fulfilled.
- teli.vaibhav October 30, 2016 in United States
A demand is said to be fulfilled 24 hours after all demands have been mapped to correspondingly available supplies.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersGiven a string with only parenthesis. Check if the string is balanced.
- teli.vaibhav October 30, 2016 in United States
ex -
1) "<({()})[]> is balanced
2) "<({([)})[]> is not balanced| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -1of 1 vote
AnswerWrite code for the partition subroutine in Quicksort.
- teli.vaibhav October 30, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersFor this problem, we would like you to think of a single line of text, and justify that text into a buffer,where the first character of the line of text is in the first spot in the buffer and the last character of textis in the specified slot in the buffer.
In ruby, you might define this function as follows:def justify(line, length)
It might be called like this:
puts justify("The quick brown fox jumps over the lazy dog.", 52)
It produces a string that looks like this:
- teli.vaibhav October 30, 2016 in United StatesThe quick brown fox jumps over the lazy dog. 1234567890123456789012345678901234567890123456789012 (You have 7 characters remaining in the buffer)
| Report Duplicate | Flag | PURGE
RealSelf Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWhat is indexing in a database?
- teli.vaibhav October 30, 2016 in United States
What are the underlying data structures you think are involved in indexing of a database?
What are some upsides and downsides of using indexing?| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an array of integers. Find the surpasser count of each element of the array.
- teli.vaibhav October 30, 2016 in United States
"A surpasser of an element of an array is a greater element to its right"
ex -
Input: [2, 7, 5, 3, 0, 8, 1]
Output: [4, 1, 1, 1, 2, 0, 0]| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array of integers and a sum 'S'. Find 2 integers in the array that add up to S.
- teli.vaibhav October 30, 2016 in United States| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFind the first unrepeated character in a given string. Solve this in a single pass.
- teli.vaibhav October 30, 2016 in United States| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a binary tree & the following TreeNode definition, return all root-to-leaf paths.
Definition of TreeNode:public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int val) { this.val = val; this.left = this.right = null; } }
EXAMPLE
Given the following binary tree: 1 / \ 2 3 \ 5 All root-to-leaf paths are: [ "1->2->5", "1->3" ]
From Lint Code - http://www.lintcode.com/en/problem/binary-tree-paths/
- johndifini October 29, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersEach test file starts with an integer ‘t’ - the number of testcases.
- scylla October 29, 2016 in India
In each of the next ‘t’ lines, you are given a string of ‘n’ characters [ either ‘(‘ or ’)’ or ‘*’ ].
Your task is to find the number of distinct balanced parentheses expressions you can make by replacing the ‘*’ with either ‘(‘ or ‘)’ or removing the ‘*’
Note : You have to replace each ‘*’ with one of ‘(‘ or ‘)’ or remove it. If removed, assume the string has reduced by 1 character.
Duplicate strings are not allowed. The final expressions to be counted have to be distinct
As the answer may be large, please output it modulo 1000000007 (10^9+7)
Output one integer per line corresponding to each testcase.
Constraints :
1 <= t <= 20
1 <= n <= 100
0 <= Number of ‘*’ in the input string <= min(n,10)
Sample Input:
2
(*(*)*)
*(*(**)*
Sample Output
5
9
Explanation
The five possible valid solutions are for the first input are :
((()))
()(())
()()()
(())()
(())
The nine possible valid solutions are for the second input are :
(((())))
(()(()))
(()()())
(()())
((()))
()(())
()()()
()()
(())| Report Duplicate | Flag | PURGE
Uber Software Developer Algorithm - 0of 0 votes
AnswersGiven a string, parse it and return a string array. It's like a tokenizer, but the rules are too...
- OctA October 29, 2016 in United States
For exmple, string="abc(edf)hij{klmn}opq[rst]uvw"
The delimiter are (), {}, []. They are in pair. So output array:
["abc", "edf", "hij", "klmn", "opq", "rst", "uvw"]
That's the rule 1. The rule 2 is, if any two consecutive "(" means escaping, that is "((" is actually output char "(". It's not part of the delimitor. Similar to ")", "{", "}", "[", "]".
abc(e))df) => ["abc", "e)df"], since the "))" outpus ")".
Rule 3: if "{" is inside a delimiter pair (), then "{" isn't part of the delimitor. Output it as is.
abc(e{df}}g) => ["abc", "e{df}}g"]| Report Duplicate | Flag | PURGE
HULU Software Engineer Algorithm - 1of 1 vote
Answers/*
- cheeyim October 28, 2016 in Singapore
# There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room.
# For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words:
# Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
# For example:
# input = [(1,4), (2,3)]
# > 3
# input = [(4,6), (1,2)]
# > 3
# input = [(1,4), (6,8), (2,4), (7,9), (10, 15)]
# > 11
*/| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
Answersfind first not-repeating character by iterating through the length of the string only once and by using constant space.
- Raj October 28, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon SDET Algorithm - 0of 0 votes
AnswersThe original question can be found from here :
- NoOne October 25, 2016 in India
franklinchen.com/blog/2011/12/08/revisiting-knuth-and-mcilroys-word-count-programs/
Read a file of text, determine the *n* most frequently used words, and print out a sorted list of those words along with their frequencies.
In the same spirit of the history:
1. Do it using pure shell scripting
2. Do it in the favourite language of your choice
Try to minimise code and complexity.| Report Duplicate | Flag | PURGE
Deshaw Inc Software Developer Algorithm - 0of 0 votes
Answer1. If I say quick sort takes O(e^n ) on the average, would I be wrong?
- NoOne October 21, 2016 in India
2. Do you think O( f ) is a good idea for real engineering?
3.Given a choice, what other 'order of' measure would you propose to use ?
4. Do you see a real problem with the modified *order of* ?
5. If you were to sort 10 elements, what sorting method would you have used?
6. If you were to sort 1 trillion unicode characters, what sorting method you would have used?| Report Duplicate | Flag | PURGE
Microsoft SDET Algorithm Math & Computation - 2of 2 votes
AnswersGiven a string "2-4a0r7-4k", there are two dashes which we can split into 3 groups of length 1, 5, 2.
- J@sper October 20, 2016 in United States
If we want each group to be length 4, then we get "24A0-R74k"
Given a String A and an int K, return a correctly formatted string.
IF A is "2-4A0r7-4k" and B is 4, string is "24A0-R74K"
IF K is 3, string is "24-A0R-74K" as the first grp could be shorter.| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersThe actual problem from question?id=6289136497459200
Implement pow, with :// Assume C/C++, as of now double pow ( double x, double power )
No library functions allowed.
Should return : x^power
=== Edit ===
People took it a bit trivially, thus examples should help :
- NoOne October 20, 2016 in United Statesx = pow ( 4, 0.5 ) // x = 2.0 x = pow ( 8, 0.333333333 ) // 1.99999999986137069 x = pow ( 10.1 , 2.13 ) // 137.78582031242644
| Report Duplicate | Flag | PURGE
Microsoft SDET Algorithm - 0of 0 votes
AnswersFrom here : question?id=5660692209205248
- NoOne October 19, 2016 in United States
In-order traversal:
A->B->C->D->E->F->H->L->M-P->R->S->T
Write a function (pseudo-code is fine) that given a starting node, advances to the next in-order node in a binary tree.
Please also provide a data-structure definition of a node.| Report Duplicate | Flag | PURGE
Arista Networks Software Developer Algorithm Trees and Graphs - 1of 1 vote
Answersdetermine whether a word is in a stored list;
- kanukadze October 18, 2016 in United States
the list doesn't fit into memory;
no disk access allowed, for lookups, memory access only;
no false positives allowed, false negatives ok| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Algorithm