Algorithm Interview Questions
- 0of 0 votes
AnswersGiven a rectangle with width 'W' and height 'H', you have to fit a string 'S' in it with maximum possible font size
- neer.1304 April 21, 2019 in United States
The font size ranges from 1 to 30
You are given two APIs getCharacterWidth(char c , int font_size) and getCharacterHeight(int font_size)
getCharacterWidth(char c , int font_size): returns the width of a character for a particular font size
getCharacterHeight(int font_size): returns the height of characters for a particular font size| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
AnswerHow will you implement organizational chart? Implement two methods - isPeer - Should return true if two employees have same managers. isManager - should return true if manager is management chain of given employee.
- neer.1304 April 21, 2019 in United States| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 0 votes
AnswersRelation between 2 animals is given. A is child of B C is child of B A is child of D
- neer.1304 April 21, 2019 in United States
An animal can be child of 0 to 2 parents. With this given data, find out if two animals are related to each other. Follow up question was - Maternal side animals, should not be related to patrernal side family.| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 2of 2 votes
AnswersYou have a 3x3 grid. In each cell you can have two colors, white or black. At the beginning, the matrix has some cells painted white and others black.
- neer.1304 April 21, 2019 in United States
If you change a color cell, that is, grid [i] [j] the cells grid [i-1] [j], grid [i + 1] [j], grid [i] [j-1] and grid [ i] [j + 1] also change (if these positions do not leave the 3x3 grid), that is, if they were white, they change to black.
Return, the minimum number of cells you have to flip for the 3x3 grid to be totally white. If you cannot do this, return -1!
Sample input/output - ibb.co/3Y0WVNR| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 1of 1 vote
AnswersGiven array of integer, count number of distinct sub array such that it has at most k odd elements and two sub array differ if only when they have at least one member differ.
Example:
{3, 2, 3, 4}, k = 1;
output; 7
[ [3], [2], [4], [3,2], [2,3], [2,3,4],[3,4] ]; Note we did not count [3,2,3] since it has more than k odd elements.
Example 2:
{6, 3, 5, 8}, k = 1;
[ [6], [3], [5], [8] , [6,3], [5,8] ] = 6
We did not count [3,5] as it has > k odd elements
Example 2:
{2, 2, 5, 6, 9, 2, 11, 9, 2, 11, 12}
There are these many arrays ;
[2], [2] , [5], [6], [9] , [2], [11], [9], [2], [11], [12]
[2, 2] , [2, 5] , [5, 6] , [6, 9] , [9, 2] , [2, 11] , [11, 9] , [11, 12] , [2, 2, 5] , [2, 5, 6] , [5, 6, 9] , [6, 9, 2] , [9, 2, 11] , [2, 11, 9] , [11, 9, 2] , [2, 11, 12] , [2, 2, 5, 6] , [2, 5, 6, 9] , [5, 6, 9, 2] , [6, 9, 2, 11] , [9, 2, 11, 9] , [2, 11, 9, 2] , [11, 9, 2, 11] , [9, 2, 11, 12] , [2, 2, 5, 6, 9] , [2, 5, 6, 9, 2] , [5, 6, 9, 2, 11] , [6, 9, 2, 11, 9] , [9, 2, 11, 9, 2] , [2, 11, 9, 2, 11] , [11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2] , [2, 5, 6, 9, 2, 11] , [5, 6, 9, 2, 11, 9] , [6, 9, 2, 11, 9, 2] , [9, 2, 11, 9, 2, 11] , [2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11] , [2, 5, 6, 9, 2, 11, 9] , [5, 6, 9, 2, 11, 9, 2] , [6, 9, 2, 11, 9, 2, 11] , [9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9] , [2, 5, 6, 9, 2, 11, 9, 2] , [5, 6, 9, 2, 11, 9, 2, 11] , [6, 9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9, 2] , [2, 5, 6, 9, 2, 11, 9, 2, 11] , [5, 6, 9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9, 2, 11] , [2, 5, 6, 9, 2, 11, 9, 2, 11, 12]
But only 18 get qualified as there are duplicates like [9, 2, 11] etc.
Qualified arrays are
[2] , [5], [6], [9] , [11], [12] , [2, 2] , [2, 5] , [5, 6] , [6, 9] , [9, 2] , [2, 11] , [11, 12] , [2, 2, 5] , [2, 5, 6] , [6, 9, 2] , [2, 11, 12] , [2, 2, 5, 6]
MY finding so far;
we can use sliding window technique, such that we start counting all sub array of len = 1 to n such that each sub array are different and have at most k odd elements
Here is the code, that i've written for this approach O(n^2)static int subArraysBrute(int arr[], int k) { int count = 0; Set<Integer> set = new HashSet<>(); //Count single length for (int i = 0; i < arr.length; i++) { count += set.contains(arr[i]) ? 0 : 1; set.add(arr[i]); } int len = 2; int odd; Set<List<Integer>> setArray = new HashSet<>(); while (len < arr.length) { setArray.clear(); for (int i = 0; i < arr.length - len + 1; i++) { int j = i + len - 1; odd = 0; List<Integer> ar = new ArrayList<>(); for (int x = i; x <= j; x++) { if (arr[x] % 2 != 0) odd++; ar.add(arr[x]); } if (!setArray.contains(ar)) { if (odd <= k) { count++; System.out.print(ar + " , "); } } setArray.add(ar); } len++; } return count; }
Other findings;
- nitinguptaiit April 20, 2019 in United States
1. We can't sort the array, as they will ruin the subarray property
2. We can't use simple sliding technique as they will mis so many sub arrays ( moving from left to right window) - I've tried this, this fails like any thing;
Probably, in second idea (sliding window), can be improve further such that once we counted sub arrays, we can run one more time and count those sub array which are left out.| Report Duplicate | Flag | PURGE
Uber SDE-2 Algorithm - 0of 0 votes
AnswersCount number of possible rhythm in a poem.
- nitinguptaiit April 18, 2019 in India
Explanation:
Twinkle, twinkle, little star, [ A ]
How I wonder what you are! [A]
Up above the world so high, [B]
Like a diamond in the sky. [B]
In the above poem, we see the first two line ( ending with "star" and "are" ) is in the rhythm that's why they are given as character "A" and similarly last two lines (ending with "high" and "sky" ] s in the rhythm that's why they are given as character "B".
Questions: Given "n" number of lines in a poem, Count number of possible rhythm in a poem.
P.S. output should be in lexicographical order only
Example:
n=1
only one possible "A"
Answer: A, count =1
n=2 [ possible chars are A,B]
AA
AB
BA <- This is not possible as it collide with AB. How? Look at the pattern
AB says first line has different rhythm and second line has different rhythm then first line.
Similarly BA is also shows the same ; first line has different rhythm and second line has different rhythm then first line.
Hence discard
n=2
AA
AB , count=2
n=3 [ possible chars are A,B, C]
AAA
AAB
ABA
ABB
ABC, count=5
Look we can't have AAC as it collide with AAB (first two are same and last is different in both)
Similarly other BCA/ BAC etc we'll discard them because of collide and lexicographical ordering.
n=4, there will be 15 [ we need to print all of them too ]
My Finding;
1. I found out that, this is just a bell number ( see the pattern 1,2,5,15.... )
2. I found, this is Dynamic programming question, we can generate the next n+1 from n; How
n=2 has
AA
AB
n=3
Take AA; there are three possiblilties to append a character is A,B,C
But since the last character is A; so lexicographically A and B can be appended at the most, since appending C could conflict with B.
AA(A)
AA(B)
Take AB; there are three possibilities to append a character is A,B,C
But since the last character is B; which is lexicographically smaller than A, so lexicographically A, B,C can be appended easily,
AB(A)
AB(B)
AB(C) <- this is possible since its not colliding with any thing
So ans; 5
AA(A)
AA(B)
AB(A)
AB(B)
AB(C)
Now lets try n=4 [ now its become complicated ;A,B,C,D]
Take AAA; possibilty A,B, not possible C/D conflict with B
AAA(A)
AAA(B)
Take AAB, Possibility is A, B C but what about D; is it possible ? Yes/No
AAB(A)
AAB(B)
AAB(C)
AAB(D) <- it collide with last C so discard ;
Hence with AAB
AAB(A)
AAB(B)
AAB(C)
Take ;
ABA(A)
ABA(B)
ABA(C)
ABA(D) Not possible ; collide with C
If you observe there is a pattern with last character to first character from right to left;
Solution: Brute force is obvious solution; and generating number is also fine since you can use Bell number [ i was not able to come up with this solution though, found later]
Any one can help me over here?| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 0 votes
AnswersWrite a program to sort a string without using java API?
- vijaydhanakodi April 10, 2019 in India
I/P : "a390testai"
O/P: 039aaiest| Report Duplicate | Flag | PURGE
Google Backend Developer Algorithm - 7of 7 votes
AnswersCount number of strings of length N with following properties:
- oaashifo April 08, 2019 in India for India
A. Consists of char 'A' and 'B' only.
B. There is atleast one occurrence of 3 consecutive Bs.
Input: Only line having integer N.
Output: Number of string with given properties. As then number can be very large print it with modulo 10^9+7.
Sample Input 1:
3
Sample Input 2:
1
Explanation: Only possible string "BBB"| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 0of 0 votes
AnswersIts farewell day, there are total N students, every student has bought a gift to give. He/She will give this gift to some other student. After gifting process is over, you are given an array, representing number of gift student receive i.e. ith number denoting number of gift he/she got. Your task is to find, whether given gift count array is valid or not. If it is valid print any of possible way of gifting that lead given array.
- oaashifo April 08, 2019 in India for India
PS: Student can't gift to himself. Student has exactly one gift with himself.
Input: First line will have one integer M, denoting number of students. Next line wil have N spaced integers denoting number of gift student gets.
Ouput: -1, if given gift received array is not valid else print N spaced integers denoting ith gifted to jth.
Sample Input 1:
3
1 1 1
Sample Output 1:
2 3 1| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 1of 1 vote
AnswersYou have a bit pattern and an infinite stream of bits coming in. You need to raise an alarm whenever the given pattern comes. Storing the stream is not allowed.
- neer.1304 April 07, 2019 in United States| Report Duplicate | Flag | PURGE
Uber SDE-3 Algorithm - 1of 1 vote
AnswersThere is a notepad which accepts only four operations:
- neer.1304 April 07, 2019 in United States
1. Character X
2. select all
3. copy
4. paste
Given n number of operations, provide the sequence of choices that gives maximum characters in the notepad.| Report Duplicate | Flag | PURGE
Uber SDE-3 Algorithm - 1of 1 vote
AnswersGiven an array find if array gets sorted by reversing any subarray of this array. Ex: In {1, 2, 3, 4, 8, 7, 6, 9} we can reverse subarray from index 4 to 6.
- neer.1304 April 06, 2019 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersFind the sum of n elements after a kth smallest element in BST. Tree is very large, you are not allowed to traverse the tree.
- neer.1304 April 06, 2019 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersConsider an infinite stream of numbers. At any point print smallest k elements.
- neer.1304 April 06, 2019 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersGiven an array of integers(duplicates allowed) return if it is a set of contiguous integers or not?
- neer.1304 April 06, 2019 in United States
Input: 5,2,3,6,4,4,6,6 Output: Yes (as it is from set of [2,3,4,5,6])| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 1of 1 vote
AnswersGiven an array of integers with the property that arr[j] – arr[j-1] is either 1,0,-1 and a search value, provide an efficient search mechanism.
- neer.1304 April 06, 2019 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersGiven coin denomination of 3, 6 and 17, find the number of ways in which you can form a sum 'n'. How will do it for large numbers?
- neer.1304 April 06, 2019 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersThere is a huge road. Given are the following
- neer.1304 April 06, 2019 in United States
- Array D that stores the distance from a starting point where billboard can be installed.
- Array C that stores the profit. C[i] -> profit if the billboard is installed at distance D[i].
- dist -> minimum distance to maintain between the billboards.
Assume you can install any number of billboards while maintaining a given minimum distance 'dist' between each of them. Find the maximum profit you can achieve.| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersGiven two strings, A and B, of equal length, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.
- nemishsangani96 March 23, 2019 in India
Extension1. How would you change your solution if the strings could be cut at any point (not just a common point)?
Extension2. Multiple cuts in the strings (substrings to form a palindrome)? Form a palindrome using a substring from both strings. What is its time complexity?| Report Duplicate | Flag | PURGE
Algorithm Coding Computer Science Data Structures Dynamic Programming String Manipulation - 3of 3 votes
AnswersGiven a dictionary of words & a miss-spelled input, write a function which will find 3 words from the dictionary which are closest (by difference of 1-character) to the given input.
- vinzee93 February 28, 2019 in United States
eg - dict = {vil, sit, flick, pat, pluck, sat, vat}, input = vit, ans = {sit, vil, vat}| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersI am given an array of Transactions in a ledger. A Transaction object has three things.
- goyalshub February 16, 2019 in United States
1. Sender (which means who started this transaction)
2. Receiver (means who is the destination of transaction)
3. Timestamp (at what time this transaction was executed)
Now I need to write a method findIfTransactionIsValid() which will have the array of all transactions, one sender, one receiver. A transaction is valid is following cases:
1. if sender and receiver are same
2. The timestamp should be increasing (what I mean here is if A -> B happens at Time 2 and B-> C happens at Time 1, then A->C is not a valid transaction, however if B -> C happens at Time 3 then A--> C is a valid transaction)
Example:
Transaction
{
Sender;
Receiver;
Timestamp;
}
Example: [T is timestamp here]
A -> B (T=0)
B -> C (T=1)
C -> F (T=0)
findIfTransactionIsValid(A, C) -> this should return true
findIfTransactionIsValid(B,F) -> false (time is backwards)
If the question is still not clear, please see the solution I wrote. I have written a recursive solution and is working but I am seeing help to improve the solution.| Report Duplicate | Flag | PURGE
unknown Software Engineer Algorithm - 2of 2 votes
AnswersThere are N countries, each country has Ai players. You need to form teams of size K such that each player in the team is from a different country.
- crowdx February 12, 2019 in India
Given N and number of players from each country and size K. Find the maximum number of teams you can form.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 0of 0 votes
AnswersGiven 2 trees T1 & T2 (both can have > 2 childs), write an algorithm to find if T2 is a subtree of T1.
- sanjos February 09, 2019 in United States
Follow up question, for any branch in T1
a->b->c->d
the following is a valid branch in tree T2(i.e. the isSubTree() algorithm mush evaluate to true in below circumstances)
a->d
a->c->d
c->d| Report Duplicate | Flag | PURGE
Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersYou are given a 2d grid where each grid item has a value of 1 or 0, you can only move horizontally or vertically and if both blocks have value of 1. You are also given a starting index, the output should have the "connected" grid items property to true.
For example:input = [ [{value: 0}, {value: 1}, {value: 1}], [{value: 0}, {value: 0}, {value: 1}], [{value: 1}, {value: 1}, {value: 1}] ]; startRowIndex = 2; startColumnIndex = 0; output = [ [{value: 0}, {value: 1, connected: true}, {value: 1, connected: true}], [{value: 0}, {value: 0}, {value: 1, connected: true}], [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}] ];
This is the first part of the question, this can be easily solved using either DFS or BFS.
The second part is you are given the output of the first function and the same start indices. Along with these two input arguments, you are also given a flipIndex. The grid item at the given flip index will have the value flipped. Now give the updated matrix with the updated "connected" path.
- noobtiger February 09, 2019 in United Statesinput = [ [{value: 0}, {value: 1, connected: true}, {value: 1, connected: true}], [{value: 0}, {value: 0}, {value: 1, connected: true}], [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}] ]; startRowIndex = 2; startColumnIndex = 0; flipRowIndex = 1; flipColumnIndex = 2; output = [ [{value: 0}, {value: 1}, {value: 1}], [{value: 0}, {value: 0}, {value: 0}], [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}] ];
| Report Duplicate | Flag | PURGE
Software Engineer Algorithm - 0of 0 votes
AnswersGiven a list of sorted lists each of size maximum size M, implement an iterator (maintain the order of items as in the original list of lists).
- sanjos February 04, 2019 in United States
I had a solution requiring extra space using minHeap; However, the interviewer was looking for a constant space solution.| Report Duplicate | Flag | PURGE
Microsoft Software Developer Algorithm - 0of 0 votes
AnswersGiven an array of edges between any two points in 2 dimensional space. A single edge is represented by the co-ordinates of two points it is connecting for example (2,3),(4,5) represents and edge connecting points (2,3) and (4,5).Find out the total number of squares possible if all edges are parallel to X or Y axis.
- jadonv January 26, 2019 in United States
NOTE : Include overlapping squares, squares having one side in common and squares contained within another square. Co-ordinates can have float values.
Example below -
I have considered a very simple input and output combination to keep it short.
Input
{
(0,0),(0,3)
(0,0),(3,0)
(0,3),(3,3)
(3,0),(3,3)
}
Output : 1
Possible Approach : Create a map as below -
Key(Slope of Edge in Degrees) - Value(Array of Edges)
0 - {(0,0),(3,0)},{(0,3),(3,3)}
90 - {(0,0),(0,3)},{(3,0),(3,3)}
While inserting edges in the map, make sure the edges are sorted by max(x1,x2) first and then max(y1,y2).
Pick 2 edges from one slope let's say slope 0, then pick 2 edges from slope 90 and see if square is formed or not. If square not formed, then look at next 2 edges of slope 90 and so on.
Sorting here is an expensive operation.
Please share any better solutions.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersYou have a bunch of shops. Each shops sells a bundle of chocolates at a fixed cost. You are given an amount and the price sheet of shops. Find the maximum number of chocolates that you can buy with the amount.
Int Calculate(Int Amount, []Int Quantities, []Int Cost) { // Implement }
Other points: (1) You cannot use 'sort' (2) The costliest shop need not sell the maximum number of chocolates. (3) Tricky cases exist. For example: Shop 1 sells 10 chocolates in a 10 $ bundle. Shop 2 sells 9 chocolates in a 1$ bundle. If you have 10$ in your hand, Here the maximum number of chocolates that you can buy is not 10 but 90.
- git January 24, 2019 in United States| Report Duplicate | Flag | PURGE
Numeric Backend Developer Algorithm - 0of 0 votes
AnswersGiven a graph in which there is an edge between (u,v) if gcd(u,v)>g . Given queries of u,v find if a path from u,v exists
- manaranjanfav January 17, 2019 in United States| Report Duplicate | Flag | PURGE
Algorithm - 1of 1 vote
AnswersGiven an integer S, you have to count the total number of integral solutions of the equation a+b^2+c^3+d^4<=S, such that 0<=a,b,c,d<=10000 and 0<S<10^15
- Ankita January 13, 2019 in United States
Edit: Here value can be less than or equal to S, so if input S= 2 ,then output=12
i.e we can consider 0,0,0,1 and 0,0,0,0 etc also as sum will be less than S(i.e 2)| Report Duplicate | Flag | PURGE
SDE1 Algorithm