Algorithm Interview Questions
- 0of 0 votes
AnswersYou have a stream of numbers coming in (lets say more than a million). The numbers are between [0-999). Implement a class which can
- ranganath.mr February 16, 2016 in United States
insert(int i);
getMean();
getMedian();
in constant time O(1).| Report Duplicate | Flag | PURGE
Thumbtack SDE-3 Algorithm Data Structures - 1of 1 vote
AnswersGiven an array of 0s and 1s, and k, Find the longest continuous streak of 1s after flipping k 0s to 1s.
- neer.1304 February 14, 2016 in United States
E.x array is {1,1,0,0,1,1,1,0,1,1}
k = 1 (which means we can flip ‘k’ one 0 to 1)
Answer: 6 (if we flip 0 at index 7, we get the longest continuous streak of 1s having length 6)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersGiven two arrays/Lists (choose whatever you want to) with sorted and non intersecting intervals. Merge them to get a new sorted non intersecting array/list.
- HumbleLearner February 12, 2016 in United States
Eg:
Given:
Arr1 = [3-11, 17-25, 58-73];
Arr2 = [6-18, 40-47];
Wanted:
Arr3 = [3-25, 40-47, 58-73];| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 2of 2 votes
AnswersDefine a function that can detect whether the characters of a string can be shuffled without repeating same characters as one other's neighbors. E.g. :
- fahmida.hamid February 11, 2016 in United States
apple >> alpep, so valid
a >> a, valid
aa >> aa, invalid/impossible
aab >> aba, valid
aaaabbcc >> acabacab, valid
etc.
You do not have to find one representation, just have to detect if it is possible or not!| Report Duplicate | Flag | PURGE
Google Software Developer 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 - 1of 1 vote
AnswersSecond Least common element from an Integer array.
- PS February 08, 2016 in United States
Example:
[5,5,4,5,4,6,6,6,1,3,3,4,4,5,4]
Answer: 3
Reason: {1=1, 3=2, 4=5, 5=4, 6=3}| Report Duplicate | Flag | PURGE
Bank of America Software Engineer Algorithm - 0of 0 votes
AnswersGiven a binary tree, we are supposed to find nth smallest element.
- nick.dom1519 February 06, 2016 in India| Report Duplicate | Flag | PURGE
xyz abc Algorithm - 0of 0 votes
AnswersGive java code that takes an instance of the stable marriage problem as input and decides if there is { exactly one} stable matching for this instance (that is, the program outputs either ``unique stable matching'', or ``more than one stable matching'').
- ritikashah017 February 06, 2016 in United States
input:
3
0 1 2
1 0 2
0 1 2
1 0 2
0 1 2
0 1 2
Output:
more than one stable matching| Report Duplicate | Flag | PURGE
Intuit Software Engineer Intern Algorithm - 0of 0 votes
AnswersFind a 1st non-repeated char in the string for e.g. if string is "Salesforce is the best company to work for” returns 'l'
- eminsqa January 27, 2016 in United States| Report Duplicate | Flag | PURGE
Salesforce Quality Assurance Engineer Algorithm Java - 0of 0 votes
AnswersFind the length of a maximum palindrome subset in an array. For example: in 1, 2, 4, 1 the maximum palindrome subset is 1, 2, 1 and the answer is 3
- dlyakolesa January 27, 2016 in United States| Report Duplicate | Flag | PURGE
Linkedin Software Engineer Algorithm - 0of 0 votes
AnswersImplement a function which modifies a binary tree so that the output is the tree that is a mirror of an input tree
- dlyakolesa January 27, 2016 in United States| Report Duplicate | Flag | PURGE
Linkedin Software Engineer Algorithm - 3of 3 votes
AnswersTask schedule: given a sequence of task like A B C(means 3 different tasks), and a coldtime, which means you need to wait for that much time to start next [same] task. Now----
- songty11 January 27, 2016 in United States
Input: string, n
Output: the best task-finishing sequence.
eg. input: AAABBB, 2
Output: AB_AB_AB
( "_" represents do nothing and wait)| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern 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 - 0of 0 votes
AnswersGeneric Question: You have a list of items that's nearly sorted. What algorithm would you use to completely sort it? Even though it's already sorted, the least element could be at the other end ...eg: 4,5,6,7,8,9,10,11,1
- Engineer1111 January 24, 2016 in United States
She then said that what would be the approach if the data was not like that, as in , not so extreme.| Report Duplicate | Flag | PURGE
Microsoft Dev Lead Algorithm - 5of 5 votes
AnswersYou are given a function bool rand_bit_p() that returns true with some unknown probability p and false with probability 1 - p.
- emb January 24, 2016 in United States
Write function rand_bit() using rand_bit_p that will return true and false with equal probability (that is, implement a fair coin, given unfair coin)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersYou have table defining meta data for all tables in your system
- abc006 January 22, 2016 in United States for NA
col name | table name | primary key| foreign key|
design a algorithm to generate sql dynamically based on column selection.| Report Duplicate | Flag | PURGE
xyz Backend Developer Algorithm - 0of 0 votes
AnswerWe have board represented using matrix (i.e Board[N][N],
- anshkun January 22, 2016 in India for 1
We have right angle triangle with same height, base and area of four types.
Types can be distinguish using points
i.e {1,0,1,1}, {1,1,0,1} etc which makes a right angle triangle in one block. We have to identify total count each triangle type. There are multiple cases
1. Include every possible triangle shape one can overlap with other triangle cell
2. Include every possible triangle shape without overlap with other triangle cell
3. Include adjacent triangles only (exclude triangle which is adjacent to two triangles )
4.Include adjacent triangles only
i.e : Input pattern
110011
100101
110110
000001
We see one triangle is getting formed a[0][0],a[0][1] and a[1],[0]
Triangles are adjacent if vertical and horizontal values are one.| Report Duplicate | Flag | PURGE
HCL Intern Algorithm - 3of 3 votes
AnswersGiven an array and an integer k, find the maximum for each and every contiguous subarray of size k.(Using DP)
- HimanshuP January 21, 2016 in United States| Report Duplicate | Flag | PURGE
SDE1 Algorithm - 0of 0 votes
AnswersImplement a finite state machine.
- neer.1304 January 18, 2016 in United States
– The machine should have one start state and can have multiple end states
– It should be extensible (I should be able to add any number of states or transitions at any time)
– I should be able to set notifications on or off for any state or for the whole state machine| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswersYou are given some equations which may contain > or = on different-different operand. For example there are valid input and invalid (a=5, b<a=50)
- neer.1304 January 18, 2016 in United States
String e1 = "a>b=1";
String e2 = "a>b=2";
String e3 = "a>c>e=3";
String e4 = "a>c>f=4";
String e5 = "b>a=5";
String e6 = "a>b>c=5";
String e7 = "b=7";
String e8 = "a>b>c>d=99";
String e9 = "a>b=99";
You need to create JSON string from it.
{
‘a’: {
‘b’: [1,2,99],
‘c’: {
‘e’:3,
‘f’:4
}
},
‘b’: {
‘a’ : 5
}
}
Input: You are given those string in string array
Output:
Construct JSON
Print it| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 6of 6 votes
AnswersGiven a non-directed, strongly connected graph where the node values are letters of the alphabet, write an algorithm that prints out all possible permutations of strings. What is this called?
- william.brandon.lee83 January 18, 2016 in United States
For example:
V = A,B,C
Printout
ABC
ACB
BAC
BCA
CAB
CBA
BAC etc.| Report Duplicate | Flag | PURGE
IBM Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a sorted integer array, write a method that builds a balanced binary search tree. What is the runtime complexity?
- william.brandon.lee83 January 18, 2016 in United States
Hint: Recursion.
Follow-up: Non-recursive solution| Report Duplicate | Flag | PURGE
IBM Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a list of tuples {x, y, x' } that describe histograms on the X/Y axis, such that X is the X coordinate, Y is the Y coordinate, and X' is the distance from X, write a function that draws the skyline of these tuples.
- william.brandon.lee83 January 18, 2016 in United States
For example:
{3, 2, 4} , {4,5,3} will give the following points:
{3,0} - trivial
{3,2} - trivial
{4,5} -calculated
{7,0} -if list is done.
You cannot assume that the tuples are sorted. Provide runtime analysis.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a list of integers of size n, write a method to write all permutations the list; do this in O(1) space
- william.brandon.lee83 January 18, 2016 in United States
Hint: No recursion.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a string that represents an integer with no upper bound (billions, trillions, etc..), write a function "convert" that returns the integer value of the string. For example: "1000322" returns 1000322.Try to do this in O(1) space, and O(n) time. Better if possible.
- william.brandon.lee83 January 18, 2016 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-3 Algorithm - 0of 0 votes
AnswersGiven a list of IP address correspondences, such as
- william.brandon.lee83 January 18, 2016 in United States
IP1 = IP2
IP3 = IP4
IP3 = IP2
IP5 = IP6
IP7 = IP8
etc.
Return a list of unique IP addresses. In this case
IP1, IP5, IP7
Consider IPs as Strings or any other data type.| Report Duplicate | Flag | PURGE
Microsoft SDE-3 Algorithm - 0of 0 votes
AnswersGiven a list of integers (array or list), write a function that returns true if the list can be split into two lists that have an equal sum.
- william.brandon.lee83 January 18, 2016 in United States
Example: {4,2,2,0,-1, 1} returns true
{4}, {2,2,0,-1,1}
and {3,3,1} returns false.
Hints by interviewer:
- Complexity is 2^n| Report Duplicate | Flag | PURGE
Microsoft SDE-3 Algorithm - 0of 0 votes
AnswersThere is down-turn in the ship-building industry. Ace Shipping Corp (ASC) wants to be prepared by having a system that will help evaluate the total cost saving they will achieve if they were to ‘let go’ some employees.
- neer.1304 January 18, 2016 in United States
Following are the rules for drawing up this Firing List:
Each manager at every level in the organization will have to contribute ‘heads’ from his team to the firing list
The input to the system would be a small integer k (=1,2, etc) which would be the number of employees chosen per manager. The output would be the total cost saved for this k. Different values of k would give an idea of the total cost saving achieved.
The primary selection criteria is Performance Rating. k employees with the minimum rating under a given manager are to be selected.
If two employees have the same rating, the one with the higher salary gets selected (to maximize cost saved)
The activity might be requested for the sub-org under any manager. The default is to consider the entire org.
Although total number of reportees for a manager is usually of the order of 10, it could possibly be a much larger number in some org too. An optimal way of choosing the k reportees would be preferred.
The following information needs to get stored per Employee:
Employee ID (unique)
Name
Performance Rating (1-5, 1 is lowest, 5 is highest)
Salary (Rs)| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswersHow can we find the missing numbers if they are more than 1 in array ??
- HimanshuP January 17, 2016 in United States
Also can we generalize it for 'k' elements?
Example: {1,2,3,5,7}
output: 4,6| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersA is [4,3,2,0,1]
- chill_bill January 17, 2016 in United States
B is [E,D,C,A,B]
Constant space and O(n) Sorting such that
A is [0,1,2,3,4,]
B is [A,B,C,D,E]| Report Duplicate | Flag | PURGE
JP Morgan freshers Algorithm