Recent Interview Questions
- 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
AnswersArrayList list = new ArrayList();
- glebstepanov1992 October 03, 2013 in Russia for Yandex
what would you improve in this code?| Report Duplicate | Flag | PURGE
Developer Program Engineer - 9of 9 votes
Answersprint hockey stick number in pascal triangle where row of triangle can be upto 30000 and length of stick can be upto 100.
- Randhir September 09, 2018 in India| Report Duplicate | Flag | PURGE
Wissen Technology Software Developer Coding Data Structures Dynamic Programming Java - 9of 9 votes
AnswersDeveloping Java game
- stallapp November 03, 2017 in United States
creating a RESTful service using which players can play a simple game described
below.
The game should have the following rules:
• The player has an infinite amount of coins.
• The player bets 10 coins to play a normal game round.
• In any round (free or normal), the player has a 30% chance of winning back 20 coins.
• In any round (free or normal), the player also has a 10% chance of triggering a free round where
the player does not have to pay for bet. The free round works in the same way as a normal round except
it costs 0 coins. The free round should follow immediately after the normal round.
• The player can both win coins and free round at the same time.| Report Duplicate | Flag | PURGE
Amazon Backend Developer Java - 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
AnswersGiven the array of digits (0 is also allowed), what is the minimal sum of two integers that are made of the digits contained in the array.
- azil November 28, 2013 in United States
For example, array: 1 2 7 8 9. The min sum (129 + 78) should be 207| Report Duplicate | Flag | PURGE
Google Algorithm - 8of 8 votes
AnswersYou are given a list of n float numbers x_1, x_2, x_3, ... x_n, where x_i > 0.
- emb September 04, 2015 in United States
A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes counter-clockwise)
Write an single-pass algorithm that uses O(1) memory to determine, if the travelers path crosses itself, or not (i.e. if it's self-intersecting)
e.g.
2 1 1 2 -> crosses
1 2 3 4 -> doesn't cross| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 8of 8 votes
AnswersGiven an array int32 arr[] of size n, return the number of non-empty contigious subarrays whose sum lies in range [a, b]
That is, implement the following naive algorithm faster than O(n^2)def naive_algorithm(lst, a, b): result = 0 for i in xrange(len(lst)): for j in xrange(i, len(lst)): if a <= sum(lst[i:j + 1]) <= b: result += 1 return result
Examples:
count([1,2,3], 0, 3) = 3 # [1], [2], [3], [1, 2], [3] count([-2,5,-1], -2, 2) = 3 # [-2], [-1], [-2, 5, -1]
You may assume that there are no overflows, that is sum(|x_i|) <= MAX_INT - 1
- emb September 26, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 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
AnswersWrite a function which returns kth element from the tail in a linked list.
- hasan.tanpinar April 04, 2013 in United States| Report Duplicate | Flag | PURGE
Google Intern Linked Lists - 8of 8 votes
AnswersWrite code to find the next least node in a binary search tree given a node?
- mav February 20, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Algorithm - 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 - 8of 8 votes
AnswersFind the missing letters from a string if it doesn't create a pangram.
- lord.claxton March 08, 2018 in United States| Report Duplicate | Flag | PURGE
JP Morgan Associate Java - 8of 8 votes
AnswersYou are given a graph, some edges are black, some are red. Find a spanning tree with one restriction: if we take some node as root, every path from it to some leaf node must consist of alternating red-black-red-black edges. That is, no path from root to leaf must contain sequential black-black edges or red-red edges.
- emb April 12, 2016 in United States
You are guaranteed that such spanning tree exists.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 8of 8 votes
AnswersSuppose you have ten million data in a array where each data should be 15 in length. Some of the data length changed somehow. How do you find out which data are distorted.
- pcbabu January 05, 2016 in United States| Report Duplicate | Flag | PURGE
Software Developer - 8of 8 votes
Answerswrite a program that take l and r as input and display the number of prime numbers that lie between l and r(l and r inclusive) and can be represented as sum of two consecutive prime numbers +1
- angomarjundas1994 October 08, 2017 in India| Report Duplicate | Flag | PURGE
Juspay Jr. Software Engineer C - 8of 8 votes
AnswersYou stand in one corner of a large room, and your assistant is in its opposite corner. In front of the assistant is a 4-corner table, with a coin in each of the 4 corners. Your objective is to get the coins to be all heads or all tails. When that happens, the coins start jumping up and down; so, you'll know for sure when it happens. What you can do is to tell your assistant: (a) flip one coin; (b) flip two coins on a side of the table; (c) flip two coins on a diagonal of the table. You can't tell the assistant which coin, which side, or which diagonal to use. You can either think of your assistant as being extremely dumb, or that the table is being constantly rotated by external forces. What is the sequence of commands that you should give to your assistant to make sure the coins start jumping up and down?
- YKeselman September 09, 2014 in United States| Report Duplicate | Flag | PURGE
Brain Teasers - 8of 8 votes
AnswersConsider 10 years down the line we have a mobile device which have 10 TB hard disk.Consider the device a file of 5TB and RAM on the device is 1GB. How will you sort the file of 5TB. You can use extra space but RAM is 1GB which is used by other application on the device also.
- Utsav April 18, 2017 in India| Report Duplicate | Flag | PURGE
Morgan Stanley Senior Software Development Engineer - 8of 8 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 8 votes
AnswersI have been given 2 strings namely A and B and I have to find the no. of strings lying between A and B where the inbetween lying strings must be formed only from the characters of A.
- urname September 20, 2018
Another restriction is that each letter has to be used exactly once.
For example :
A->abc
B->ddd
Ans=5
From string abc, the strings obtained are acb, bac, bca, cab, cba, all of them are larger than abc, but smaller than ddd. So the answer is 5.
Also, it may be the case that a given character in the string may repeat any number of times.ie- the below case is also included in the problem statement.
A->abacaba
B->ubuduba
Ans=64
How do I find the no. of such strings ?
link : https://codeforces.com/contest/895/problem/D| Report Duplicate | Flag | PURGE
- 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 11 votes
AnswersThe "surpasser" of an element in an array is defined as the number of elements that are to the "right" and bigger than itself.
- carchen2015 July 10, 2015 in United States
Example:
Array:
[2, 7, 5, 5, 2, 7, 0, 8, 1]
The "surpassers" are
[5, 1, 2, 2, 2, 1, 2, 0, 0]
Question: Find the maximum surpasser of the array.
In this example, maximum surpasser = 5| Report Duplicate | Flag | PURGE
Google Software Engineer 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