Algorithm Interview Questions
- 4of 4 votes
AnswersLets say someone accidentally deleted all the whitespaces from a sentence. Write a program to reconstruct the sentence from that stripped out string. Assume you have access to a dictionary function that returns if a given string is a valid word or not.
- NS August 23, 2016 in United States
Example input: thisisavalidsentence
Output: this is a valid sentence
If multiple solutions are possible, any one valid solution should be given. Assume there is always a valid solution. No invalid input will be given.| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
AnswersIdeal goal:
- stella.rafailov August 23, 2016 in India
Given data set of strings divide them into equivalence classes such that the equivalence relation is fuzzyMatchingOfString
Problem: as far as I know there isn’t a relation function fuzzyMatchingOfString such that it is transitive, i.e. given A,B,C and fuzzyMatchingOfString(A,B), fuzzyMatchingOfString(B,C) does not imply fuzzyMatchingOfString(A,C)
e.g. foo ~ goo and goo~gol but not foo~gol
given that I think we have to compromise about our goal and create a set to each string In our data set – that is n^2 for each run when the basic action is fuzzyMatchingOfString| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
AnswersMickey got an assignment from his school that he has to collect money from each house for next day's event. The city is built just like a 2-D array and each house owner kept certain amount for Mickey (for ex: The house owner at (i,j) coordinate kept A[i,j] for Mickey). Mickey is in a hurry and he wants to reach home as soon as possible otherwise he will miss the match between India and Bangladesh. Also he can only move to any adjacent house from his location, and he cannot move diagonally. So please find a way so that he will collect maximum amount from everyone if he will reach home earliest.
*Input Specification*
input1 = first input will tell you size of the array
input2 = String as shown in the example and you have to parse it to build your 2-D array
*Output Specification*
output1 = You need to set maximum amount collected to this global variable (type int)
*Example*
Consider input1 = 4 and it means school is at (0,0) and his house is at (4,4). In between the houses are like input2 = '(1,7,5,2),(5,12,3,6),(100,9,23,16),(16,4,5,9)'.
To collect maximum amount, Mickey should take his path {1,5,100,9,23,16,9} so that the total amount collected,output1 = 1 + 5 + 100 + 9 + 23 + 16 + 9 = 163
**CLARIFICATION **
The programming test was like this, you store the input into the variablesinput1
and
input2
and store the output to the variable
- invincible1000 August 22, 2016 in United Statesoutput1
| Report Duplicate | Flag | PURGE
Sap Labs Algorithm - 0of 0 votes
AnswersGiven a multi-dimensional array as input which consists of 0's and 1's. Traverse from starting {0,0} to end {n,n} in a shortest path with any direction. You have to move to next item only when next item is 1, if it is 0, you can't move.
- XXX August 18, 2016 in India| Report Duplicate | Flag | PURGE
Algorithm - 5of 5 votes
Answers* Given an unsorted integer array, place all zeros to the end of the array without changing the sequence of non-zero
- haldokan August 12, 2016 in United States
* elements. (i.e. [1,3,0,8,12, 0, 4, 0,7] --> [1,3,8,12,4,7,0,0,0])| Report Duplicate | Flag | PURGE
Bloomberg LP Developer Program Engineer Algorithm - 0of 0 votes
Answers* Implement a tick server the has multiple clients interested in different tickers. Clients have Plotters that are updated
- haldokan August 12, 2016 in United States
* in real-time with the top 10 tickers that have the most price updates on the top. What data structure would you choose
* for the server and client plotters?| Report Duplicate | Flag | PURGE
Bloomberg LP Developer Program Engineer Algorithm - 0of 0 votes
Answers* Royal titles consist of name followed by space and a Roman numeral. Example: Richard IV. The Roman numeral in the title
- haldokan August 12, 2016 in United States
* can go to L (50). You are given the roman numerals from 1 to 10:
* I II III IV V VI VII VIII IX X. And you are given the 10 multiples up to 50: XX XXX IL L. Numbers between 10 and 50 that
* are not given can be formed from 10 multiples and a numeral b/w 1 and 9. Example: 48 is XLVIII wichi is XL (40) plus
* VIII (8).
* <p>
* You are given an array of Roman titles sort it as follows: sort it on the name unless the names are equal, in which
* case you have to sort it on the ordinal of the numerals.
* Examples:
* Henry II, Edward VIII => Eward VII, Henry II
* Richard V, Richard II, Richard X => Richard II, Richard V, Richard X| Report Duplicate | Flag | PURGE
Bloomberg LP Developer Program Engineer 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 - 2of 2 votes
AnswersConvert a number to English representation.
- coder145 August 09, 2016 in United States
Ex: Input : 100
Output : One Hundred.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 4 votes
AnswersYou have a bunch of light bulbs. Store them as you wish. Implement a function that tells you if the light is on or off given its index and another one that toggles the state of the light bulbs given a start and end index.
- ad09 August 09, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersThere are n+1 loading docks. a permutation of boxes 1->n is placed on the first n. there is a fork that can move one box to an empty location at a time. Give an algorithm to sort then boxes with minimum number of moves.
- ad09 August 05, 2016 in United States
Follow up: minimum distance| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
AnswersGiven the following inputs, return a list of rooms that are available and large enough:
- MM August 04, 2016 in United States
# of people
Start Time
End Time
You should return
total list of rooms
capacity of each rooms
availability| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersGiven a Pattern and a dictionary, print out all the strings that match the pattern.
- ad09 August 02, 2016 in United States
where a character in the pattern is mapped uniquely to a character in the dictionary ( this is what i was given first).
e.g 1. ("abc" , <"cdf", "too", "hgfdt" ,"paa">) -> output = "cdf"
2. ("acc" , <"cdf", "too", "hgfdt" ,"paa">) -> output = "too", "paa"| Report Duplicate | Flag | PURGE
Google Algorithm - -3of 3 votes
Answersdsjfvbhfgvbfhv
- New Grad August 01, 2016 in United States| Report Duplicate | Flag | PURGE
Accenture Data Scientist Algorithm - 0of 0 votes
AnswersThe stepping number:
- abhishek.agar2 July 31, 2016 in India
A number is called as a stepping number if the adjacent digits are having a difference of 1. For eg. 123,121,9878 are all stepping numbers. While 890, 098,012 are not i.e. a number should not start with 0.
Also all 1-digit numbers are stepping numbers.
Find out how many stepping numbers exist with number of digits =N (input given)| Report Duplicate | Flag | PURGE
Toppr SDE1 Algorithm - 0of 4 votes
AnswersYou are currently in practice mode. This is a demo only.
- New Grad July 30, 2016 in United States
A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.
A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].
Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.
For example, consider the following array A consisting of N = 8 elements:
A[0] = -1
A[1] = 3
A[2] = -4
A[3] = 5
A[4] = 1
A[5] = -6
A[6] = 2
A[7] = 1
P = 1 is an equilibrium index of this array, because:
A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
P = 3 is an equilibrium index of this array, because:
A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
P = 7 is also an equilibrium index, because:
A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0
and there are no elements with indices greater than 7.
P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.
Write a function:
int solution(int A[], int N);
that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.
For example, given array A shown above, the function may return 1, 3 or 7, as explained above.
Assume that:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 16of 20 votes
AnswersGiven two object arrays of "id,weight" (sorted by weight), merge them together and create a one single array. If the "id"s are same values should be merged. Final resulting array should be sorted by weight. Result should be O(nlogn) in time complexity.
- dee707 July 28, 2016 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersJacob and Peter have their favorite number X and Y. We have given an array with positive interger number and we need to find the longest prefix index which contain equal number of X and Y. return -1 if there is no prefix with equal number of X and Y.
Suppose we have an array A = [7,42,5,6,42,8,7,5,3,6,7]
X = 7
Y =42
Output should be 9 as prefix will be index from 0 to 9 with equal number of X and Y.
I wrote below code but this has some bug which I could not find.
- sandeepmnit35 July 28, 2016 in Indiapublic int findIndex(int A[],int N,int X,int Y) { int nx =0; int ny=0; int result = -1; for( int i=0;i<N;i++) { if(A[i] == X) nx+=1; else if(A[i] == Y) ny+=1; if(nx== ny&& nx!=0&&ny!=0) result = i; } return result; }
| Report Duplicate | Flag | PURGE
Groupon Applications Developer Algorithm - 0of 0 votes
AnswersGiven a dictionary and a string, find all the substrings that are valid words in dictionary.
- Pedro July 28, 2016 in United States
I was thinking of a Trie solution but I'm not sure a Trie will work easily to match sub words that begin in the middle of the string.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
AnswersGiven a String input and a tree, write a code to return the same node for same input string. Also each node will should be given equal amount of weight between nodes at the same level while choosing a path.
- shrinks July 27, 2016 in United States| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersGiven an array: 1,2,3 ,5,8,7,6,9,5,7,3,0,5
- sindhu1690 July 27, 2016 in United States
subarry:5,7
Find the subarray in the large array and return the minimum length and index where you can find the subarray. Note: that the subarray may be present in the large array non-contiguous.
In the above case : the answer is length = 2 and
index = 8| Report Duplicate | Flag | PURGE
Microsoft Software Developer Algorithm - 2of 2 votes
AnswersSwap the elements in Kth position from the start and end of a link list.
- Aussie July 27, 2016 in United States
ex:
input: list: 1,2,4,5,7,8 & K=2
output: 1,7,4,5,2,8| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm - 27of 27 votes
AnswersWrite a program to check if the given string is repeated substring or not.
- Lakshman July 27, 2016 in India
ex 1: abcabcabc - yes - abc is repeated.
2: abcdabababababab - no.| Report Duplicate | Flag | PURGE
Ivycomptech Algorithm - 0of 0 votes
AnswersThe following is the design question I was asked.
- gopi.komanduri July 26, 2016 in India
Design a dash board.
Should be very realistic.
Should be scalabe .
Should have very less latency .
Can expect millions of updates per second.
Dash board should show :
for each day :
1. city name ,
2.total trips in that city for that day ,
3.total fare it could collect in that city on that day,
4. fare collected from old clients
5. fare collected from new clients (new client is the client who is having his first ride in Uber after registration)
Input : we get two strings s1 , s2.
the format of s1 : trip_id , client_id , city , datetime
the format of s2 : trip_id , fare.
Could you please suggest how to proceed for this kind of question?| Report Duplicate | Flag | PURGE
StartUp Analyst Algorithm Business Question Cache Computer Architecture & Low Level Data Structures Distributed Computing Hash Table Ideas System Design - 2of 2 votes
AnswersGiven an array of numbers, find the maximum and minimum sum of sub sequences at a distance > m
- nitinsharma021 July 25, 2016 in India
Example –
arr = {3, 4, -2, 1, -2, 4, 6, -3, 5} & m = 2
Solution – max = 13 {4 + 4 + 5}, min = -5 {-2-3}| Report Duplicate | Flag | PURGE
Deshaw Inc Algorithm - 2of 2 votes
AnswersGiven some resources in the form of linked list you have to canceled out all the resources whose sum up to 0(Zero) and return the remaining list.
- ganesh.eng2015 July 24, 2016 in India
E.g-->> 6 -6 8 4 -12 9 8 -8
the above example lists which gets canceled :
6 -6
8 4 -12
8 -8
o/p : 9
case 3 : 4 6 -10 8 9 10 -19 10 -18 20 25
O/P : 20 25| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersIn an incoming stream of +ve integers, return true if 2 numbers with sum equal to 10 has occurred till now.
- ganesh.eng2015 July 24, 2016 in India
How to handle stream of numbers| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersGiven an array,find all valid ip-address form this array.
- ganesh.eng2015 July 24, 2016 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersAn unsorted array is given . Find the no of greater elements on right side on current element in array. Find this for every element of array Expected time complexity is lesser then O(n^2)
- knocks July 24, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 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