Algorithm Interview Questions
- 6of 6 votes
AnswersComponents of computer systems often have dependencies -- other components that must be installed before they will function properly. These dependencies are frequently shared by multiple components. For example, both the TELNET client program and the FTP client program require that the TCP/IP networking software be installed before they can operate. If you install TCP/IP and the TELNET client program, and later decide to add the FTP client program, you do not need to reinstall TCP/IP.
- Byll September 26, 2014 in United States
For some components it would not be a problem if the components on which they depended were reinstalled; it would just waste some resources. But for others, like TCP/IP, some component configuration may be destroyed if the component was reinstalled.
It is useful to be able to remove components that are no longer needed. When this is done, components that only support the removed component may also be removed, freeing up disk space, memory, and other resources. But a supporting component, not explicitly installed, may be removed only if all components which depend on it are also removed. For example, removing the FTP client program and TCP/IP would mean the TELNET client program, which was not removed, would no longer operate. Likewise, removing TCP/IP by itself would cause the failure of both the TELNET and the FTP client programs. Also if we installed TCP/IP to support our own development, then installed the TELNET client (which depends on TCP/IP) and then still later removed the TELNET client, we would not want TCP/IP to be removed.
Write a program to automate the process of adding and removing components. To do this we will maintain a record of installed components and component dependencies. A component can be installed explicitly in response to a command (unless it is already installed), or implicitly if it is needed for some other component being installed. Likewise, a component, not explicitly installed, can be explicitly removed in response to a command (if it is not needed to support other components) or implicitly removed if it is no longer needed to support another component.
I found a reference to this problem online.. Check this for i/o details. This is the exact same problem
http://www.cs.cornell.edu/Info/Courses/Spring-98/CS211/assgts/assgt3/assgt3.pdf| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm - 6of 0 votes
AnswersImagine there is a square matrix with n x n cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels;
- Edde May 12, 2007| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 5of 15 votes
AnswersGiven a function
- mabid.mahmood July 15, 2014 in United States
getRandomTripplet()
which returns a random triplet of letters from a string. You don't know the string using calls to this function you have to correctly guess the string. the length of the string is also given.
Lets say the string is helloworld the function getRandomTriplet will return things like
hlo
hew
wld
owo
the function maintains the relative order of the letters. so it will never return
ohl since h is before o in the string.
owe since w is after e
The string is not known you are only given length of the string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 13 votes
AnswersGiven n, output the numbers from 0 to 2^n-1 (inclusive) in n-bit binary form, in such an order that adjacent numbers in the list differ by exactly 1 bit.
- xxyyzz February 23, 2013 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 9 votes
AnswersQ: Given a sorted 2D N x N array (where array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]), can you write a function that converts this to a sorted 1D array?
- pdoggeth October 18, 2013 in United States
The obvious and naive way that I thought of was to convert the entire array into a 1D and do a mergesort on it, but there must be a better way than that. I'm wondering what the better and more efficient way is.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 7 votes
AnswersImplement below function.
int getRandom(int N, int K[])
Constraints:
->K is sorted and contains elements in range [0,N)
->Output should be a random number between [0,N) excuding elements from K
->probability of generated number should be 1/(N-K.length) and not 1/N
-->int uniform(int N) is given which returns random number [0,N) with 1/N probability for each number.
->No more than O(1) memory
->No more than O(N) time
Below is my solution but it uses O(N) space.
- G10 November 01, 2013 in United Statespublic int randomNumber(int N, int[] K) { // K is sorted //assumed size of K is less than N int remains[] = new int[N-K.length]; //i is index [0,N-1], j is an index of K, k is an index of remainings //Fill remaining array for (int i=0,j=0,k=0;i<N;i++){ if (i!=K[j]){ remainings[k++]=i; }else{ j++; } } int index = uniform(remainings.length); return remainings[index]; } Time complexity: O(N) Space Complexity: O(N)
| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 5of 7 votes
AnswersGiven the English alphabet, 'a' through 'z' (lowercase), and an imaginary onscreen keyboard with the letters laid out in 6 rows and 5 columns:
a b c d e f g h i j k l m n o p q r s t u v w x y z
Using a remote control - (up - 'u', down 'd', left 'l', right 'r' and enter '!'), write a function that given a word will produce the sequence of key presses required to type out the word on the onscreen keyboard. The function should return the sequence string.
- superduper March 01, 2013 in United States
NOTE: This was an actual question. I didn't pull this from TopCoder.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 7 votes
AnswersGiven N strings, find the smallest string in lexicographic order which contains all the given strings as subsequences
- geekofthegeeks November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven a N*N Matrix.
- 646 November 23, 2010
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven two sorted array in ascending order with same length N, calculate the first K min a[i]+b[j]. time complexty O(N).
- mario87 December 18, 2013 in United States
some misunderstood first K, to put it straight, to find the Kth min, not the first min| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven an integer N, print numbers from 1 to N in lexicographic order.
Details: To be implemented without using character conversion (or Strings).
Example:
N = 25
Print:
1
10
11
..
19
2
20
21
..
25
3
4
5
6
7
8
9
A simple solution using Strings (may not be acceptable):
- Abhi October 04, 2013 in United StatesSystem.out.print("\n\tLexicographic Order\n\nEnter an integer: "); Scanner input = new Scanner(System.in); Integer n = input.nextInt(); List<String> list = new ArrayList<String>(); for (int i = 1;i<n;i++){ list.add(""+i); } Collections.sort(list); for (String j: list){ System.out.println(j); }
| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Algorithm - 5of 5 votes
AnswersGiven a array of integers , find 3 indexes i,j,k such that, i<j<k and a[i] < a[j] < a[k]. Best possible is a O(n) algorithm.
- kingKode October 26, 2012 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven "n", generate all valid parenthesis strings of length "2n".
- anusha136 December 02, 2013 in United States
Example:
Given n=2
Output:
(())
()()| Report Duplicate | Flag | PURGE
Facebook Intern Algorithm - 5of 5 votes
AnswersGiven a set of numbers, find the longest subset with consecutive numbers be it any order.
- anonymous June 14, 2013 in India
Input:
S = { 5, 1, 9, 3, 8, 20, 4, 10, 2, 11, 3}
we have 2 consecutive sets
s1 = {1, 2, 3, 4, 5}
s2 = { 8, 9, 10, 11}
Ans.
s1 = {1, 2, 3, 4, 5}| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 5of 5 votes
AnswersGiven two strings, return boolean True/False, if they are only one edit apart.Edit can be insert/delete/update of only one character in the string. Eg:
- abkr990 October 31, 2014 in United States
-True
xyz,xz
xyz, xyk
xy, xyz
-False
xyz, xyz
xyz,xzy
x, xyz| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 5 votes
AnswersLet's say you have 10,000 servers, each with a billion integers. How do you find the median?
- 352905 July 03, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven two strings .Print all the interleavings of the two strings.
- grave July 10, 2012 in India
Interleaving means that the if B comes after A .It should also come after A in the interleaved string.
ex-
AB and CD
ABCD
ACBD
ACDB
CABD
CADB
CDAB| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm String Manipulation - 5of 5 votes
AnswersI recently, appeared for second phone interview with CloudEra, the interviewer asked me to
- gravityrahul June 28, 2014 in United States
write a function which takes in an array of integers and returns the highest positive product
possible by multiplying 3 distinct numbers. NO SORTING is ALLOWED
PS: Please write a solution in JAVA or Python. (Not interviewer request)
example:
[1, 3, 5, 2, 8, 0, -1, 3]
=> 8 * 5 * 3 = 120
[0, -1, 3, 100, -70, -5]
=> -70*-50*100=350000| Report Duplicate | Flag | PURGE
Cloudera Software Engineer in Test Algorithm - 5of 5 votes
AnswersGiven three arrays A,B,C containing unsorted numbers. Find three numbers a, b, c from each of array A, B, C such that |a-b|, |b-c| and |c-a| are minimum
- Greg September 04, 2014 in United States
Please provide as efficient code as you can.
Can you better than this ???| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays C++ Coding - 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 - 5of 5 votes
AnswersGiven a prime set, we call "prime expressible" if a number can be factorized only using given prime numbers. Find n-th big expressible number.
- pandacoder October 30, 2015 in United States
E.g., prime set = {2, 3}
expressible number = {1,2,3,4,6,8, 9, 12...}
non-expressible number = {5, 10... }
The primes in the prime set are ordered in an increasing order, and can include a prime < 10^4 (don't remember the exact range), and n can also be as large as 1-10^6.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersGiven an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number target.
- rjrush December 06, 2014 in United States
If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|
You can assume each number in the array is a positive integer and not greater than 100
Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 5of 5 votes
AnswersThere are n bombs in a big circle,and each bomb has a value and a 'effect range'.If you detonated a bomb,you will get this bomb's value,but a bomb can have effect on the neighbors which the distance(difference between index) between them is smaller than the 'effect range'.It's say that the neighbor bomb will be destoryed and you could not get their values.
- lxfuhuo September 13, 2013 in CHINA
You will given each bomb's value and the 'effect range',and you need calculate the max value you can get.
eg. n=3 index 0's bomb' v is 2,range is 0(will not effect others).and v[1]=1,r[1]=1,v[2]=3,r[2]=1;
this case's max value is 5.(detonate the 0's and than the 2's).
HELP ME.
ps: It's a interval DP.| Report Duplicate | Flag | PURGE
Google Intern 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 - 5of 5 votes
Answers
- Alex March 04, 2015 in United StatesQuestion: Given two strings, find number of discontinuous matches. Example: “cat”, “catapult” Output: 3 => “CATapult”, “CatApulT”, “CAtapulT”
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersSay you have a keypad that has keys for the numbers 0 through 9 and the correct code is some sequence of 5 digits. This keypad does *not* reset after entering an incorrect sequence of 5 digits. ie. If the correct sequence is 12345, entering 7512345 will succeed in opening it because it ends in the correct sequence. If the keypad actually resets after every 5 digits pressed, then it would not succeed b/c it would interpret the above sequence as "75123" then "45".
- Jason May 30, 2015 in United States
1. Write an algorithm that will try to find the correct code for this keypad. Assume you have an API similar to KeyPad.pressKey(int n) where you pass in a number (0...9) and it returns true if the keypad unlocks and false if it's still locked.
Note that you could easily enter all digits of all numbers 00000 through 99999 resulting in 5*100000 key presses, but remember that the panel does not reset after every sequence of 5 digits, so find a way to do this more efficiently. Notice for example that entering the stream 3791283780 will test the length 5 sequences 37912, 79128, 91283, 12837, 28378, 83780; not only the two disjoint sequences 37912 and 83780.
Think of this keypad as remembering the last 4 keys pressed (and the order pressed); when the next key is pressed, if the last 4 keys + the current key equal the correct code, the keypad will unlock. Assume the keypad does all this internally, so you can just keep feeding it keypresses and it will eventually unlock if the last 5 keypresses entered is the correct code.
2. Generalize your algorithm to work for a keypad where you don't know the length of the correct sequence in advance.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 5of 5 votes
AnswersI came across this problem online.
- xiaoc10 August 07, 2015 in United States
> Given an integer:N and an array int arr[], you have to add some
> elements to the array so that you can generate from 1 to N by using
> (add) the elements in the array.
Please keep in mind that you can only use each element in the array once when generating a certain x (1<=x<=N). Return the count of the least adding numbers.
For example:
N=6, arr = [1, 3]
1 is already in arr.
add 2 to the arr.
3 is already in arr
4 = 1 + 3
5 = 2 + 3
6 = 1 + 2 + 3
So we return 1 since we only need to add one element which is 2.
Can anyone give some hints?| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 5of 5 votes
AnswersWrite a program to replace each element of an array with a number present on the right side of the element such that the number is least greater than the element. If there is no greater number replace it with -1
- 3139a1m July 02, 2014 in India
e.g : 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28
ans : 18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1
I gave the obvious o(n^2) solution. He asked to optimize it.| Report Duplicate | Flag | PURGE
Adobe SDE1 Algorithm