Recent Interview Questions
- 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
AnswersInput - array of integers size N, integer Threshold. Output - the number of pairs (x, y) of distinct elements with condition x + y <= Threshold. Is that possible to implement it with O(n) ?
- anonymous October 04, 2013 in United States| Report Duplicate | Flag | PURGE
Google Java Developer - 5of 7 votes
AnswersWhat is the minimum representation in bits of two positions on an 8x8 chessboard?
- pretonesio August 28, 2013 in United States for Outlook| Report Duplicate | Flag | PURGE
Microsoft SDE1 Brain Teasers - 5of 7 votes
AnswersDelete last node from the linked list. First node pointer is not given.
- yolo July 11, 2013 in India
I told him its not possible in conventional linked list.
He asked me what if we can add some more data in node.
Data should not be a pointer to previous node i.e., it should still be singly linked list.| Report Duplicate | Flag | PURGE
Amazon SDE1 Linked Lists - 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 7 votes
AnswersIf you are behind the schedule on a project, what will you do?
- lngbrc October 24, 2013 in United States
I was asked by multiple interviewers.| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Behavioral - 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
AnswersThree strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.
- learn August 27, 2012 in United States
Ex: A="abcd" B="xyz" C="axybczd". answer is yes. o(n)| Report Duplicate | Flag | PURGE
Google - 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 source string and a destination string write a program to display sequence of strings to travel from source to destination. Rules for traversing:
- Dee November 06, 2012 in United States
1. You can only change one character at a time
2. Any resulting word has to be a valid word from dictionary
Example: Given source word CAT and destination word DOG , one of the valid sequence would be
CAT -> COT -> DOT -> DOG
Another valid sequence can be
CAT -> COT - > COG -> DOG
One character can change at one time and every resulting word has be a valid word from dictionary| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer - 5of 5 votes
AnswersGiven a number "n", find the least number of perfect square numbers sum needed to get "n"
- tazo March 12, 2015 in United States
Example:
n=12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1)
n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + 1^2)| Report Duplicate | Flag | PURGE
Google Dynamic Programming - 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
AnswersFind whether string S is periodic.
- aonecoding4 March 01, 2019 in United States
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"
Given string S, find out the P (repetitive pattern) of S.| Report Duplicate | Flag | PURGE
Google Software Engineer - 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