Software Engineer / Developer Interview Questions
- 9of 9 votes
AnswersMicrosoft Excel numbers cells as 1...26 and after that AA, AB.... AAA, AAB...ZZZ and so on.
- Interviewee February 27, 2014 in United States
Given a number, convert it to that format and vice versa.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 9of 9 votes
AnswersA circus is designing an act consisting of a tower of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below her. Given the heights and weights of each person in the circus, what is the largest possible number of people in such a tower?
- algooz May 03, 2008
Input(ht wt) : (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56,90) (60,95) (65,100) (68,110) (70,150) (75,190)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 9of 9 votes
AnswersGiven a timer time() with nanosecond accuracy and given the interface
interface RealTimeCounter: void increment() int getCountInLastSecond() int getCountInLastMinute() int getCountInLastHour() int getCountInLastDay()
implement the interface. The getCountInLastX functions should return the number of times increment was called in the last X.
- peachandpotato January 29, 2014 in United States
(My note: an ideal solution will have space usage which does *not* grow unbounded with the number of calls to increment(). It seems to me that a solution involving a round-robin database could be good, but it sacrifices accuracy.)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 9of 9 votes
AnswersGiven a huge N*N matrix, we need to query the GCD of numbers in any given submatrix range(x1,y1,x2,y2). Design a way to preprocess the matrix to accelerate the query speed. extra space should be less than O(N^2) and the preprocess time complexity should be as litte as possible.
- mario87 December 18, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 9of 9 votes
AnswersIf u have a website in English with all its code now u have to convert the same website to any other language how will u proceed with it ? Suggest all possible methods.
- pulkit.2810 February 25, 2013 in India| Report Duplicate | Flag | PURGE
Software Engineer / Developer Application / UI Design - 8of 10 votes
AnswersEliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.
- jeso May 18, 2013 in Switzerland
Examples:
abc -> ac
ac->''
react->rt| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Arrays - 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 - 8of 10 votes
AnswersFind next higher number with same digits.
- codechamp April 02, 2014 in United States for Knowledge Graph
Example 1 : if num = 25468, o/p = 25486
Example 2 : if num = 21765, o/p = 25167
Example 3 : If num = 54321, o/p = 54321 (cause it's not possible to gen a higher num than tiz with given digits ).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Ideas - 8of 10 votes
AnswersComplete the below function which takes an arraylist and displays the list in the expected output
- AP October 07, 2013 in United States
public class TreePrinter {
public static void printTree(Iterable<Relation> rs) {
// your code
}
}
public static class Relation {
String parent;
String child;
public Relation(String parent, String child) { ... }
}
}
Example input:
List<Relation> input = newArrayList();
input.add(new Relation(“animal”, “mammal”));
input.add(new Relation(“animal”, “bird”));
input.add(new Relation(“lifeform”, “animal”));
input.add(new Relation(“cat”, “lion”));
input.add(new Relation(“mammal”, “cat”));
input.add(new Relation(“animal”, “fish”));
TreePrinter.printTree(input);
Expected output:
line 1: lifeform
line 2: animal
line 3: mammal
line 4: cat
line 5: lion
line 6: bird
line 7: fish| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 8of 8 votes
Answers1. qaz is a value for a number where this number is less than the other next values which have indexes larger than the index of this number.
- Pointer January 27, 2015 in United States for Autocomplete
for example: 33 , 25 , 26 , 58 , 41 , 59 -> qaz of (33) = 3 where 33 less than 3 numbers (58 , 41 , 59), qaz of (25) = 4 and not 5 because the index of 33 is less than the index of 25, qaz of (26) = 3 , qaz of (58) = 1 , qaz of (41) = 1 , qaz of (59) = 0.
the question is to find the max qaz.
it can be solved simply using 2 loops which takes time of O(n^2).
that's ok but how can we solve this problem in O(nlogn).
I have an approach and know the algorithm I got during the interview but it take a 40 of me to find it and write the code, but it was hard to think about it during the interview in that way.
I want to know if somebody can think and write the code in less than 20 minutes !!!| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 8of 8 votes
AnswersYou are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.
- King@Work March 05, 2011
Fastest way to find that single integer
-- using memory.
-- not using any external memory.
eg: [2,1,4,5,1,4,2,2,4,1]| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 8of 8 votes
AnswersQ: Design a component that will implement web browser history. the user goes to different site and once he press on history button you should display the last 5 (no duplicates allowed, and 5 can be any N later) if duplicates occur display the most recent one. so if user visit : G,A,B,C,A,Y and than press "history" we will display Y,A,C,B,G. and of course he can go later to two other websites and than press "history" we will show them than the previous 3.
- Dany November 21, 2013 in United States
A: I solved it with stack, list and hash table in O(n) but it was too complicated and I didn't like my solution. please suggest something simpler.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 8of 8 votes
AnswersPrint all valid phone numbers of length n subject to following constraints:
- cee.el.dg January 17, 2013 in India
1.If a number contains a 4, it should start with 4
2.No two consecutive digits can be same
3.Three digits (e.g. 7,2,9) will be entirely disallowed, take as input| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Coding - 8of 8 votes
AnswersYou are given N unique numbers a1<a2<a3<...an. Find out the count of all possible binary search tress that can be constructed using these numbers.
- ashok.singh.sairam September 13, 2012 in India
for example with 3 elements 1,2,3 there are 5 possible BST and for 1,2,3,4 there are 14 bst| Report Duplicate | Flag | PURGE
Samsung Software Engineer / Developer Algorithm - 7of 15 votes
AnswersWAP to modify the array such that arr[I] = arr[arr[I]].
- praveen February 28, 2014 in United States
Do this in place i.e. with out using additional memory.
example : if a = {2,3,1,0}
o/p = a = {1,0,3,2}
Note : The array contains 0 to n-1 integers.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 7of 9 votes
AnswersImagine an alphabet of words. Example:
- hani.amr June 30, 2013 in United States
a ==> 1
b ==> 2
c ==> 3
.
z ==> 26
ab ==> 27
ac ==> 28
.
az ==> 51
bc ==> 52
and so on.
Such that the sequence of characters need to be in ascending order only (ab is valid but ba is not). Given any word print its index if valid and 0 if not.
Input Output
ab 27
ba 0
aez 441
Note: Brute-force is not allowed.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 7of 7 votes
AnswersGiven a very long list of URLs, find the first URL which is unique ( occurred exactly once ).
- AK December 06, 2011 in India
I gave a O(n) extra space and O(2n) time solution, but he was expecting O(n) time, one traversal.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Large Scale Computing - 7of 7 votes
AnswersDetermine minimum sequence of adjacent values in the input parameter array that is greater than input parameter sum.
- bootcat April 20, 2014 in United States
Eg
Array 2,1,1,4,3,6. and Sum is 8
Answer is 2, because 3,6 is minimum sequence greater than 8.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 7of 7 votes
AnswersWrite a function that gets a billion integers. How can you find the midian in most efficient way (time)?
- adam2008 February 16, 2013 in United States
same question, but the input is an endless stream of integers, and we want to find the current median.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 7of 7 votes
AnswersPattern Matching
- mamidi.laxman.lnu June 11, 2013 in United States
----------------
Characters: a to z
Operators: * +
* -> matches zero or more (of the character that occurs previous to this operator)
+ -> matches one or more (of the character that occurs previous to this operator)
Output if a given pattern matches a string.
Example:
pattern:a*b
string:aaab b, ab, aab, aaab, ab
output:1
pattern:a+aabc
string:ab aabc, aaabc, aaaabc ..
output:0
pattern:aa*b*ab+
string:aab aab, aabab, aaaabbab
output:1
pattern: a+a*b*
string: a ab, aab, aaabb
output: 1
Valid Assumptions: Please assume that both the pattern and string input are valid| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 7of 7 votes
AnswersYou are given a graph with no cycles, each node representing different cities and there are stadiums for baseball games in all cities.
Each node contains a value representing the population of the city, and a list of neighbors. (feel free to extend data structure)
Every time there is a baseball game at a city, everyone from all the different cities will go to the city with the baseball game.
Return the maximum traffic between a city and its neighbours when there is a game at that city, for all cities. (Does not have to be sorted)
The total run-time after returning everything should be O(n).
Examples:
- djway August 10, 2016 in United StatesInput: 1 2 \ / 5 / \ 4 3 Output: 1 14 2 13 3 12 4 11 5 4 Input: 38 / 8 / 7 / 1 2 \ / \ 5 15 / \ 4 3 Output: 1 82 2 53 3 80 4 79 5 70 7 46 15 68 8 38 38 45
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 7of 7 votes
AnswersYou need to develop the game Snake. What data structures will you use? Code your solution.
- GeorgyBoy December 30, 2013 in Israel| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Coding Java Problem Solving - 6of 8 votes
AnswersGiven a NxN matrix which contains all distinct 1 to n^2 numbers, write code to print sequence of increasing adjacent sequential numbers.
- talktomenow July 14, 2014 in United States
ex:
1 5 9
2 3 8
4 6 7
should print
6 7 8 9| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 6of 8 votes
AnswersGiven a linked list where apart from the next pointer, every node also has a pointer named random which can point to any other node in the linked list. Make a copy of the linked list.
- Interviewee February 27, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 6of 6 votes
AnswersThe input is a sequence x1,x2,...,xn of integers in an arbitrary order, and another sequence
- Coder April 17, 2014 in United States
a1,a2,..,an of distinct integers from 1 to n (namely a1,a2,...,an is a permutation of
1, 2,..., n). Both sequences are given as arrays. Design an 0(n logn) algorithm to order
the first sequence according to the order imposed by the permutation. In other words, for
each i, Xi should appear in the position given in ai. For example, if x = 17, 5, 1,9, and a =
3, 2, 4, 1, then the outcome should be x = 9, 5, 17, 1. The algorithm should be in-place, so
you cannot use an additional array.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Arrays - 6of 6 votes
AnswersCode a function that receives a string composed by words separated by spaces and returns a string where words appear in the same order but than the original string, but every word is inverted.
Example, for this input string@"the boy ran"
the output would be
@"eht yob nar"
Tell the complexity of the solution.
- diegum June 06, 2014 in United States for iOS| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer String Manipulation - 6of 6 votes
AnswersGiven an array of ages (integers) sorted lowest to highest, output the number of occurrences for each age.
- streamer December 31, 2014 in United States
For instance:
[8,8,8,9,9,11,15,16,16,16]
should output something like:
8: 3
9: 2
11: 1
15: 1
16: 3
This should be done in less than O(n).| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 6of 6 votes
AnswersWrite a function for retrieving the total number of substring palindromes.
- Andrew November 04, 2013 in United States
For example the input is 'abba' then the possible palindromes= a, b, b, a, bb, abba
So the result is 6.
Updated at 11/11/2013:
After the interview I got know that the O(n^3) solution is not enough to go to the next round. It would have been better to know before starting implementing the solution unnecessarily ...| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 6of 6 votes
AnswersIn a certain language which has same alphabets as in english language (ie. a-z), but the order of the alphabets is different (for eg 's' is the first character, 'g' is second, and likewise). Given a dictionary of this new language (which has words arranged according to new alphabetical order), FInd out the order of alphabets in this language.
- sgarg June 09, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Google SDE1 Software Engineer / Developer SDE-2 Algorithm - 6of 6 votes
AnswersYou visited a list of places recently, but you do not remember the
- UserOne November 05, 2013 in United States
order in which you visited them. You have with you the airplane
tickets that you used for travelling. Each ticket contains just the
start location and the end location. Can you reconstruct your journey?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm