Recent Interview Questions
- -8of 8 votes
Answerssort the array so that the odd number in front of the even number and their relative order doesn't change in Time O(n) and Space O(1). I believe quickselect can do this, but it will change the relative order of the input.
- Guy February 01, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 7of 7 votes
AnswersGiven a regular expression with characters a-z, ' * ', ' . '
- kevin October 13, 2013 in United States
the task was to find if that string could match another string with characters from: a-z
where ' * ' can delete the character before it, and ' . ' could match whatever character. ' * ' always appear after a a-z character.
Example:
isMatch("a*", "") = true;
isMatch(".", "") = false;
isMatch("ab*", "a") = true;
isMatch("a.", "ab") = true;
isMatch("a", "a") = true;| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 1of 3 votes
AnswersReverse a string without using any temporary variable.
- rasmiranjanbabu August 31, 2013 in India
Suppose {{char str[] = "Hello"; then str[] = "olleH";}}}.
I told him we can "shift H to o then o to H", similarly so on. But could able to write the code.| Report Duplicate | Flag | PURGE
HCL Software Engineer / Developer C - 3of 5 votes
AnswersA string is called sstring if it consists of lowercase english letters and no two of its consecutive characters are the same.
- priteshpathak15 July 29, 2013 in India
You are given string s of length n. Calculate the number of sstrings of length that are not lexicographically greater than s.
Input format
The only line of input contains the string s. It's length is not greater than 100.
All characters of input are lowercase english letters.
Output format:
Print the answer of test modulo 1009 to the only line of output.
Sample input:
bcd
Sample output:
653| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Front-end Software Engineer Algorithm - 0of 0 votes
AnswersGiven a sorted integer array and a number, find the start and end indexes of the number in the array.
- bvinay84 July 11, 2013 in United States
Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6}
Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}
Complexity should be less than O(n)| Report Duplicate | Flag | PURGE
Linkedin Software Engineer in Test Algorithm - 12of 12 votes
AnswersGiven 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree.
- bharat June 03, 2013 in India
Ex:
2 3 1
2 1 3
will construct the same tree
A1[]={2,1,3}
2
1 3
A2[]={2,3,1}
2
1 3| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersA string contains only 0's and 1's, like 001010, swapping is permitted only with adjacent elements. Find an efficient way so that all the zero's are in the begining and the one's in the end. So the resultant string becomes 000011.
- singh May 22, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersPrint the numbers of form 2^i.5^j in increasing order. For eg:
- controlc September 18, 2011 in India
1, 2, 4, 5, 8, 10, 16, 20| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Brain Teasers - 1of 1 vote
AnswersGiven an array of 2n elements of which n elements are same and the remaining n elements are all different. Write a C program to find out the value which is present n times in the array
- Jamob May 22, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersThere is an Array with positive and negative integers randomly distributed. find the maximum sum of a subset of this array. (subset could contain any number of elements but not the adjacent elements). Follow up, what is the complexity of your algo.
- HighLander May 06, 2011
You can use additional Datastructures if you want.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow do you shift a String given a String
- Anonymous Access July 19, 2009 in United States
For instance the following string abcdef and given an index 3, how would you make this in to defabc. So basically the index at a given point must be moved to the front and the rest of the string shifted to the right.
Another example:
Given an index 2 the result is cdefab| Report Duplicate | Flag | PURGE
Intel Software Engineer / Developer Algorithm - 0of 0 votes
Answers#1 There is a linked list. The last node could point back to any node in the list (including the head). Find the node in the list to which the last node points. Or in other words at which node does the circular linked list start.
- Programmer August 20, 2006| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Coding 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 - 3of 3 votes
AnswersGiven two binary numbers each represented as a string write a method that sums up the binary numbers and returns a result in the form of binary number represented as a string. You may assume that input fits in the memory and the input strings are, in general, of different length. Optimize your solution, do not use unnecessary 'if' branching.
example:sumBinary('0111101', '1101')
returns
- autoboli April 21, 2015 in United States
'1001010'| Report Duplicate | Flag | PURGE
Amazon - 9of 9 votes
AnswersQuestion was "Given a pattern and a string input - find if the string follows the same pattern and return 0 or 1.
- David_Maxwell November 24, 2014 in United States
Examples:
1) Pattern : "abba", input: "redbluebluered" should return 1.
2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.
I can think of a brute-force solution for this question where we add the character in the pattern and n length of the string to a hashmap and recurse over the pattern array and string. But is there anything more efficient? This was a pretty difficult question in my opinion.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 10 votes
AnswersSuppose we are given a set L of n line segments in the plane, where the endpoints of each
- polo November 01, 2014 in United States
segment lie on the unit circle x^2 + y^2 = 1, and all 2n endpoints are distinct. Describe
and analyze an algorithm to compute the largest subset of L in which no pair of segments
intersects.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 2of 2 votes
Answersgiven n > 0 fair dice with m > 0 "sides", write an function that returns a histogram of the frequency of the result of dice rolls. For example, for two dice, each with three sides, the results are:
- Aurelius October 29, 2014 in United States for BVal
(1, 1) -> 2
(1, 2) -> 3
(1, 3) -> 4
(2, 1) -> 3
(2, 2) -> 4
(2, 3) -> 5
(3, 1) -> 4
(3, 2) -> 5
(3, 3) -> 6
And the function should return:
2: 1
3: 2
4: 3
5: 2
6: 1| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Coding - 11of 11 votes
AnswersGive a N*N matrix, print it out diagonally.
- Mem February 28, 2014 in United States
Follow up, if it is a M*N matrix, how to print it out.
Example:
1 2 3
4 5 6
7 8 9
print:
1
2 4
3 5 7
6 8
9
This is the question in the phone interview.
Please share more questions.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersGiven a number N, find the smallest 3 digits number such that product of its digits is equal to N.For example for N=100 , 3 digits number is 455.
- sam February 14, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 8of 10 votes
AnswersRearrange an array using swap with 0.
- cm29xm August 14, 2013 in Australia
You have two arrays src, tgt, containing two permutations of the numbers 0..n-1. You would like to rearrange src so that it equals tgt. The only allowed operations is “swap a number with 0”, e.g. {1,0,2,3} -> {1,3,2,0} (“swap 3 with 0”). Write a program that prints to stdout the list of required operations.
Practical application:
Imagine you have a parking place with n slots and n-1 cars numbered from 1..n-1. The free slot is represented by 0 in the problem. If you want to rearrange the cars, you can only move one car at a time into the empty slot, which is equivalent to “swap a number with 0”.
Example:
src={1,0,2,3}; tgt={0,2,3,1};| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 5 votes
AnswersThere are N(0 to N-1) players each having at Max 'M' (0 to M-1) number of followers. You have to select minimum number of players so that the total followers must be equal to a given number 'K'.
I/P would be like,
first line contain N, M, K followed by N lines containing string of 0 or 1 s.t. for i'th line if j'th char is 1 it means j'th person follows player 'i'
For. eg.
- P3A July 18, 2013 in India3 6 5 111100 000100 000010 ans=2 ( select 0th and 2nd )
| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - -1of 1 vote
AnswersIs this even possible? Move the spaces to the starting of the string in a c style string. In place within one iteration.
- madzig June 14, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer C++ - 1of 1 vote
AnswersGiven a string.Find the longest substring in it such that the substring contains only 2 unique characters.Ex- aabbcbbbadef Ans-bbcbbb
- ANONU April 14, 2013 in India| Report Duplicate | Flag | PURGE
Google SDE1 - 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 - 1of 1 vote
AnswersSuppose that we have a sorted singly linked list with integer values. For example:
- snass005@ucr.edu February 05, 2013 in United States
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
We want to change the pointers of this linked list so that it becomes:
7->1->6->2->5->3->4
I did not have enough time left to finish my code and I could not think of a good solution.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 2of 2 votes
AnswersWrite the code to find lexicographic minimum in a circular array, e.g. for the array
- ALgeek September 25, 2012 in India
BCABDADAB, the lexicographic mininum is ABBCABDAD| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersVerify if the given password is valid/invalid;
- S.A.M March 10, 2012 in United States
1. must be 5-12 characters long
2. must contain atleast one number and one lowercase character
3. a sequence must not be followed by the same sequence (like 123123qs is invalid, 123qs123 is valid)| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Java - 0of 0 votes
AnswersPrint continuous alphabets from a sequence of arbitrary alphabets
- Anony February 02, 2012 in United States
For example:
Input: abcdefljdflsjflmnopflsjflasjftuvwxyz
Output: abcdef; mnop; tuvwxyz
Input: AbcDefljdflsjflmnopflsjflasjftuvWxYz
Output: abcdef; mnop; tuvwxyz| Report Duplicate | Flag | PURGE
Epic Systems