Algorithm Interview Questions
- 0of 0 votes
AnswersA monotonically increasing function F(X) exists. For a given no N , find the value of X when F(X) = N.
- knocks July 24, 2016 in India| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 0of 0 votes
AnswersSort an unsorted array containing o's and 1's. For eg: [0,1,1,1,1,0,0,1]. Do it in-place as well as in O(n) time. While sorting you are not allowed to change the original ordering of same element.
- acinom July 23, 2016 in United States| Report Duplicate | Flag | PURGE
Accolite software Algorithm - 9of 9 votes
AnswersGiven a random function with equal probability of getting 1 or 0 ie 50% each. write a custom function which uses the above random function such that your function should return 1 with 75% probability and 0 with 25% probability
- coolcoder3 July 22, 2016 in India| Report Duplicate | Flag | PURGE
Oracle Software Developer Algorithm Problem Solving - 0of 2 votes
AnswersGiven a list of numbers of odd length, design an algorithm to decide whether it's possible to remove any number from the list and split the remaining numbers into two sets of equal length with the same sum.
- jakeb July 22, 2016 in United States
Example:
Input: [1, 1, 1, 1, 1]
Output: Yes
Input: [1, 2, 2]
Output: No| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 4of 4 votes
AnswersGiven a string return the longest palindrome that can be constructed by removing or shuffling characters.
- enkadi13 July 22, 2016 in United States
Example:
'aha' -> 'aha'
'ttaatta' -> ' ttaaatt'
'abc' -> 'a' or 'b' or 'c'
'gggaaa' -> 'gaaag' or 'aggga'
Note if there are multiple correct answers you only need to return 1 palindrome.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersA matrix is "Toepliz" if each descending diagonal from left to right is constant. Given an M x N matrix write the method isToepliz to determine if a matrix is Toepliz.
- enkadi13 July 22, 2016 in United States
Example:
Input:
67892
46789
14678
01467
Output:
True| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm Arrays - 0of 0 votes
AnswersHow to calculate sum of all numbers in a string. Example 11aa22bb33dd44 =110
- rageshpayyan July 21, 2016 in United States for Seattle
Note: Should not use Regex and replace| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 0of 0 votes
AnswersFind the index when slow and fast pointer meet in terms of n (length of list before cycle) and p ( length of loop in linked list).
- Deepak Agrawal July 16, 2016 in India
Let me meeting index is q then we should be able to find value of q when we pass n& p , there shouldn't be any extra variable.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersI was asked in an interview: You are given a dump file of IPv4 addresses. You are to find 4 most common occurring subnets. Lets say an IP address if of type a.b.c.d you have to find most common occurring four subnets of the form,
a.*.*.*
a.b.*.*
a.b.c.*
a.b.c.d
Here * matches anything.
My first solution was build an in memory hashtable. Given an IP address a.b.c.d split it as ["a","b","c","d"] and add "a", "a.b", "a.b.c", "a.b.c.d" to the hash table and count it. [There are optimizations possible like considering the entire IP address as a 32 bit unsigned integer and count it with masks and shifts]
Then the question got extended: "assume you can never hold everything in memory, how would you solve it?" Now, the very first solution that I could say was to do an external sort and then count it.
The next solution I gave was to split the IP addresses into buckets. The algorithm was,while there is an IP IP <- an IP address a <- first quadruple push IP to bucket[a]
The bucket which has maximum elements would give me the a.*.*.* solution. Now take each bucket and do the same. Even though this might give the correct result, in worst case I might end up having 255^4 buckets.
- miscanon July 15, 2016 in United States
This is indeed an open ended question with more than one correct answer. What would be the best way to solve this?| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 0of 0 votes
AnswersGiven Nodes such as
M-> N-> T-> D-> E | | | | C X Y L | | A Z
-> right pointer
- Raj July 14, 2016 in United States
| down pointer
Output should be
M->C->A->N->X->Z->T->Y->D-L>E
Write this to flatten
flatten(Node head) {
}
Node {
Node right;
Node down;
char a;
}| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 2 votes
AnswersGIven a list of words, and the number of rows and columns, return the number of words that can be fit into the rows and columns by stringing together each consecutive word. If the next word doesn't fit in the same line, it should move to the next line. Find an efficient solution for this. For eg.
- rucknrull July 14, 2016 in United States
List of words: { "Do", "Run" }
Number of columns: 9
Number of rows: 2
First row: "Do Run Do" (7 letters + 2 spaces fit into 9 columns)
Second row: "Run Do" (Only 2 words fit into 9 columns)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswerWrite a program for skyyscrapper?
- CareerCupUser1 July 09, 2016 in United States
http://www.conceptispuzzles.com/index.aspx?uri=puzzle/skyscrapers/techniques| Report Duplicate | Flag | PURGE
Google SDE-3 Algorithm - 0of 0 votes
AnswersYou have rating (0-10) of the hotels per user in this format:
- theconqueror July 06, 2016 in United States
scores = [
{'hotel_id': 1001, 'user_id': 501, 'score': 7},
{'hotel_id': 1001, 'user_id': 502, 'score': 7},
{'hotel_id': 1001, 'user_id': 503, 'score': 7},
{'hotel_id': 2001, 'user_id': 504, 'score': 10},
{'hotel_id': 3001, 'user_id': 505, 'score': 5},
{'hotel_id': 2001, 'user_id': 506, 'score': 5}
]
Any given hotel might have more than one score.
Implement a function, get_hotels(scores, min_avg_score) that returns a list of hotel ids that have average score equal to or higher than min_avg_score.
get_hotels(scores, 5) -> [1001, 2001, 3001]
get_hotels(scores, 7) -> [1001, 2001]
*/
How to solve this in C++ and Python?| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 0of 0 votes
AnswersFind out the longest repeated common sub-string(overlapped) in a string.
- rasmiranjanbabu July 05, 2016 in United States
For example:- mystr = banana # The "ana" is the common overlapped sub-string is been used 2 times.| Report Duplicate | Flag | PURGE
Amazon Software Analyst Algorithm - 2of 2 votes
AnswersYou want to design a Cab system which will show you nearest 5 taxis.
- Shanky.Q3 July 04, 2016 in United States
Each taxi will continuously emit (x,y) coordinates.
You need to print the nearest 5 taxis from (p,q).| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 1 vote
AnswersYou have an array of unique integer numbers and only one operation: MoveToFront(x) that moves given number to the beginning of the array.
- emb July 02, 2016 in United States
Write a program to sort the array using the minimum possible number of MoveToFront() calls.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswerIn a 2D(m*n) int array few cells are marked as 0(zero). Distance between each cell is 1(one). Hence diagonal from one cell to next cell in the diagonal is 2(two). For each cell find the distance from the closest 0(zero) value cell.
- priyam.saha87 July 02, 2016 in United States
Input would be: length of array. width of array. count of zero in the array. followed by list of x coordinates and list of y coordinates
Example:
3
5
1
0
0
Output:
0 1 2
1 2 3
2 3 4
3 4 5
4 5 6| Report Duplicate | Flag | PURGE
Algorithm Data Structures - 0of 0 votes
AnswersImplement a web crawler. Follow up - parrarelize it.
- Lively July 01, 2016 in United States| Report Duplicate | Flag | PURGE
Zillow Software Engineer Algorithm - 0of 0 votes
AnswersGiven points on the Cartesian plane. Return the K points closest to the origin (0,0).
- Lively July 01, 2016 in United States| Report Duplicate | Flag | PURGE
Zillow Software Engineer Algorithm - 0of 0 votes
AnswersGiven an N X M matrix where some position are free and some have trees in them. You can build a house on any group of free positions that form a square (including a single position). Return the largest house you can build given these requirements.
- Lively July 01, 2016 in United States| Report Duplicate | Flag | PURGE
Zillow Software Engineer Algorithm - 0of 0 votes
AnswersImplement a TwoSum interface that has 2 methods: Store and Test. Store adds an integer to an internal data store and Test checks if an integer passed to Test is the sum of any two integers in the internal data store. Once you provide an answer interviewer will ask the O complexity of the solution and ask you to optimize it.
I provided 2 solutions, one with O(n-square) and another O(n). However the O(n) solution used 2 internal data stores. I was asked to preserve O(n) but not use the second internal store
- palak.chokshi July 01, 2016 in United Statespublic interface TwoSum { /* * Stores input in an internal data structure. */ public void Store(int input); /* * Returns true if there is any pair of numbers in the internal data structure which * have sum val, and false otherwise. * For example, if the numbers 1, -2, 3, and 6 had been stored, * the method should return true for 4, -1, and 9, but false for 10, 5, and 0 */ public bool Test(int val); } public class TwoSumImpl : TwoSum { private List<int> _store = new List<int>(); private List<int> _sums = new List<int>(); public void TwoSumImp() { } //-3,-2,3,5,7 //-5,0,1,-2,-3,8, public void Store(int input) { if(!_store.Contains(input)) { _store.Add(input); } } public bool Test(int val) { for(int i=0; i<_store.Count;i++) { if(_store[i] < 0) //store[i] is negative { diff = val + Math.Abs(_store[i]); if(_store.Contains(diff)) { return true; } } else //store[i] is positive { diff = val - _store[i]; if(_store.Contains(diff)) { return true; } return false; } } }
| Report Duplicate | Flag | PURGE
Linkedin Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersYou are given an old touch smartphone numbers having dial pad and calculator app.
- tambimitesh22 July 01, 2016 in United States
The goal is to type a number on dialpad.
Calculator have 1-9 and +,-,*,/,= as operations. But as phone is old, some of the numbers and some operations can't be touched.
But you can always make a number using other numbers and operations. There could be multiple ways of making a number. You have to find minimum operation for making a number.
For ex: lets say 1,4,6,7,8,9 works and +,-,* works.
2,3,5 and / doesn't work.
If you have to type 18-> 2 operations. (Each touch is considered an operation)
If you have to type 5 -> '1+4=' that requires 4 operations. There could be other ways to make '5'.
The goal is to find minimum operations.| Report Duplicate | Flag | PURGE
Samsung SDE-2 Algorithm - 1of 1 vote
AnswersChess Knight Problem: - It deals with a knight piece on a chess board. You are given two inputs: starting location and ending location. The goal is to then calculate and print the shortest path that the knight can take to get to the target location.
- SS June 30, 2016 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersWrite a method given a string with unbalanced parenthesis, the output should return a string with balanced parenthesis.
- AndroidFan June 26, 2016 in United States
Ex: (a(b(c)de should change to (a(b(c)d)e)| Report Duplicate | Flag | PURGE
Android Engineer Algorithm - 6of 6 votes
AnswersYou are given a matrix with N rows and N columns. Elements in matrix can be either 1 or 0. Each row and column of matrix is sorted in ascending order.
Find number of 0-s in the given matrix.
Example:0 0 1 0 1 1 1 1 1 Answer: 3 0 0 0 0 Answer: 4
Update: Expected complexity is O(log(N)). The best I've seen in comments is still O(N).
- emb June 26, 2016 in United States
Update2: Alright, guys, sorry for a bit of trolling. Obviously this is not possible to do faster than O(N). Here is why: take a diagonal (N, 1), (N-1, 2), ... (1, N). Suppose input matrix has all 0's above this diagonal and all 1's under this diagonal. So only diagonal elements vary. Clearly, diagonal elements do not depend on each other. So we have to analyze each diagonal element which is O(N).
Nice job, @gen-y-s :)| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
AnswerWrite a program to detect cycle in loop.
- punapuna86 June 24, 2016 in United States| Report Duplicate | Flag | PURGE
A9 abc Algorithm - 0of 0 votes
AnswersWrite a program to sort an array in nlog(n) complexity
- punapuna86 June 24, 2016 in United States| Report Duplicate | Flag | PURGE
A9 abc Algorithm