Recent Interview Questions
- 3of 3 votes
AnswersA standard chess knight (it moves in its standard way i.e. L shaped OR 2.5 moves) is sitting at the position a1 on an N x N chess board. What is the minimum number of moves it will take to reach the diagonally opposite corner?
- Saurabh Singhal August 17, 2013 in India
P.S. - If it were a 8 x 8 chess board, the final destination for the knight would be h8| Report Duplicate | Flag | PURGE
Goldman Sachs Intern Algorithm Coding Data Structures Trees and Graphs - 3of 3 votes
AnswersFind out if the given string forms a valid lottery number.
- AnonD June 09, 2017 in United States
- A valid lottery number contains 7 unique digits between 1 and 59.
e.g.
4938532894754 (yes) -> 49 38 53 28 9 47 54
1634616512 (yes) -> 1 6 34 6 16 51 2
1122334 (no)| Report Duplicate | Flag | PURGE
Facebook Software Developer - 3of 3 votes
AnswersGiven the following set of strings, write a function that stores this information.
- JSDUDE April 19, 2017 in United States
// /Electronics/Computers/Graphics Cards
// /Electronics/Computers/Graphics Cards
// /Electronics/Computers/SSDs
// /Electronics/Computers/Graphics Cards
// /Electronics/Computers/SSDs
// /Electronics/TVs
// /Electronics/Computers/Graphics Cards
// /Electronics/TVs
// /Electronics/TVs
// /Garden
// /Automotive/Parts
Your datastructure should be able to provide information as such:
// / = 11
// /Electronics = 9
// /Electronics/Computers = 6
// /Electronics/Computers/Graphics Cards = 4
// /Electronics/TVs = 3
// etc
// ["/Electronics/Computers/Graphics Cards", "/Garden"]| Report Duplicate | Flag | PURGE
NVIDIA Senior Software Development Engineer Data Structures Trees and Graphs - 3of 3 votes
AnswersTask schedule: given a sequence of task like A B C(means 3 different tasks), and a coldtime, which means you need to wait for that much time to start next [same] task. Now----
- songty11 January 27, 2016 in United States
Input: string, n
Output: the best task-finishing sequence.
eg. input: AAABBB, 2
Output: AB_AB_AB
( "_" represents do nothing and wait)| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 3of 3 votes
AnswersGiven a matrix containing 0 and 1. Consider 1 as 'Land' and 0 as 'Water'. Find out the number of 'Islands' in the matrix. That is, set of all adjacent 1 will make up for an island.
- prajakta mahamuni July 17, 2015 in India
For example:
[ 0 1 1 0 1 ]
[ 1 1 1 0 0 ]
[ 0 0 0 1 1 ]
[ 1 0 0 1 0 ]
This problem has 4 islands. ( consider set of 1s, vertically, horizontally and diagonally ).| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 3of 3 votes
AnswersWrite an algorithm to find the ‘next’ node (e.g., post-order successor) of a given node in a binary tree and binary search tree
- Jeff May 18, 2014 in United States
a.) where each node has a link to its parent.
b.) without parent pointer
implement 2 versions of the algorithm: 1.) binary tree 2.) BST| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 3 votes
AnswersHere is a good puzzle:
- Anonymous October 15, 2013 in United States
How do you write a program which produces its own source code as output?| Report Duplicate | Flag | PURGE
Microsoft Front-end Software Engineer - 3of 3 votes
AnswersReturn a shortest prefix of <code>word</code> that is <em>not</em> a prefix of any word in the <code>list</code>
- pk March 07, 2013 in United States
e.g.
word: cat, it has 4 prefixes: “”, “c”, “ca”, “cat”
list: alpha, beta, cotton, delta, camera
Result is “cat”| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 3 votes
AnswersI was asked this during my onsite google interview but was unable to come up with an optimization for it. Here is the question:
- Jaysun October 26, 2019 in United States
There's a list of (x,y) points and a method getCircle with the following signature:
/**
* Given three points returns a circle (Radius, and center) such that all three points lie in its circumference
* or it returns null if no such circle is possible.
*/
Circle getCircle(point1, point2, point3);
getCircle method is already implemented and given to you as a black box. The problems asks you to find the Circle with most points in its perimeter.
The obvious answer is to get all possible triplets of points and find all possible circles and keep track of which one appears most often O(n^3) . Any ideas on how to further optimize this?| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 3of 3 votes
AnswersFind max size of contiguous shape below, where X represents a shape and . is empty:
- steez September 21, 2017 in United States
.XXXXXX....
...X..XX..X
...XXXX....
..X.....X..
..XXX..XX..
.....XX....
/*method stub*/
public int GetMaxShape(char[][] array) {
}
i was able to come up with a recursive solution but i'd love tips on a dp solution| Report Duplicate | Flag | PURGE
Google Software Engineer - 3of 3 votes
AnswersGiven:
- alvaroneirareyes March 12, 2017 in United States
a encoded to 1
b encoded to 2
....
z encoded to 26
You can translate a number to a string:
'123' can be translated to 'abc'
but also can be translated to 'aw','lc' which gives 3 total translations
'12' can be translated to 'ab' and 'l' -> 2 translations
Write a function to get the number of valid combinations from a number like '123123123'| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 3of 3 votes
AnswersGiven a linked list consisting of String in each Node . Given just a pointer to the head Node find whether the resultant String formed by combining all the Nodes of the linked list is a palindrome or not in O(1) space and O(n) time.
- neer.1304 November 29, 2015 in United States
eg – Consider this linked List structure
“aba” -> “cd” -> “efe” -> “d” -> “caba”
Hence this structure is palindrome .| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 3of 3 votes
AnswersThis question was asked in the chat, just adding here with the solution. I don't know for which company it is.
Replace wild cards with all possible combinations of zeros and ones using recursion.Input String: 0?1? Output: 0010, 0011, 0110, 0111
This is my solution using recursion:
- gigi84 December 20, 2014import java.util.*; public class ReplaceWildcardsRec { public static List<String> expandString(String s, int i) { List<String> l = new ArrayList<String>(); if(i>s.length()-1) { l.add(""); return l; } for(String expanded: expandString(s,i+1)) { if(s.charAt(i)=='?') { l.add('0'+expanded); l.add('1'+expanded); } else { l.add(s.charAt(i)+expanded); } } return l; } public static void main(String[] args) { List<String> l = new ArrayList<String>(); String s = "1111?"; l = expandString(s,0); System.out.println(l); } }
| Report Duplicate | Flag | PURGE
String Manipulation - 3of 3 votes
AnswersIn a given array a = {1, 7, 3, 4, 5, 6, 2} Print the indices of all the combinations which lead to a given sum called target. For e.g. if the method is
- Jeanclaude July 09, 2013 in United States
Void PrintAllSumCombos(int[] arr, int target) - and the array shown above is passed with sum target = 7, then the output should be:
0, 3, 6
0, 5
1
2, 3
4, 6
Note: For simplicity, You may assume the array does not contain any negative numbers and also consider same set of indices with a different order as identical - for e.g. if 2, 3 is already printed, ignore 3, 2 as they are one and the same.| Report Duplicate | Flag | PURGE
Accenture Software Engineer in Test Arrays - 3of 3 votes
AnswersAs kernel can access user space memory, why should copy_from_user is needed?
- bvgr December 24, 2012 in United States| Report Duplicate | Flag | PURGE
Qualcomm Software Engineer / Developer Linux Kernel - 3of 3 votes
AnswersRound4
- aonecoding August 09, 2017 in United States
Starting from num = 0, add 2^i (where i can be any non-negative integer) to num until num == N. Print all paths of how num turns from 0 to N.
For example if N = 4,
Paths printed are [0,1,2,3,4], [0,1,2,4], [0,1,3,4], [0,2,4], [0,2,3,4], [0,4].
[0,2,4] is made from 0 + 2^1 + 2^1. [0,1,3,4] from 0 + 2^0 + 2^1 + 2^0| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven a list of manager and employee information represented in hashMap entries {AAA->BBB,CCC,EEE},{CCC->DDD}.
Print company structure tree with proper indentations. BBB, CCC and EEE directly reports to AAA, so they have one white space before "-", DDD reports to CCC, it has two whitespace before "-". The input is map<String,List<String>>
- wtcupup2017 December 08, 2016 in United States-AAA -BBB -CCC -DDD -EEE
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersAssume there are 10000 stars in sky, how would you find which star is closest to the earth? in C
- The Puzzler 2.0 January 05, 2016 in India| Report Duplicate | Flag | PURGE
Software Engineer / Developer C - 3of 3 votes
AnswersGiven 4 teams and 3 gamedays, create an algorithm such that each team plays another team every gameday and by the end of the 3 game days each team should have played one game with every other team.
- popeye123 January 03, 2016 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm Problem Solving - 3of 3 votes
Answerspublic class LogEntry {
- Invhelper May 05, 2014 in United States
public final long startTime; // start time of a job in millisec granularity
public final long endTime; // end time of a job in millisec granularity.
public final long ram; // the amount of ram the job occupies.
public final long jobId;
... constructor ...
}
running total of RAM
|
| 3GB
| -----
| 2GB
| ------
| 1GB -----------
|----- -----------
|
|____________________________________________________time
Find the peakRAM when the input is a collection of LogEntry objects| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 3of 3 votes
AnswersThe interviewer asked the following question.
char *s = "Hello"; printf("%s",s); printf(s)
The second print statement crashes sometimes. Why
- chid1989 January 07, 2014 in United States| Report Duplicate | Flag | PURGE
NVIDIA Intern C - 3of 3 votes
AnswersThere is a fictional company called fooBar in fooLand. The CEO of fooBar, fooMan, directs all managers to minimize the total hike that they give to employees, while ensuring that the hike is fair to them. Usually, this is done by giving more hike to employees who are rated better. So, for example, if an employee is rated 2 and is given hike 3x, an employee rated 3 should be given a hike greater than 3x. Hikes are always in multiples of x only and the minimum hike to be given to any employee is x.
- poojabasia August 24, 2013 in United States
This year, however, a wicked manager, barMan comes up with a brilliant strategy. He assumes that each employee would get to know the hike of only the two employees who sit next to him (one on the left, one on the right). And therefore, he reasons(using whole of his analytical left brain), that as long as he could make hikes fair for each employee with respect to the two employees that sit next to him, he would fulfill the dual objective of being "fair" as well as minimizing the total hike given. Just for clarification, the employees of each team sit in one big line.
barMan hires you to calculate the hike to be given to each employee. Over to you. You are supposed to come up with the total hike number that will excite barMan and make him roll on the floor laughing. You are given that no two employee sitting next to each other would have a common rating.
Input:
The order of rating of each employee should be in the order in which they sit. First line will be the value of x. The second line will be the number of employees 'n'. The next 'n' lines specify the rating of each employee. Rating can be integers from 1 to 105. (weird, right?)
1 <= n <= 105.
1 <= x <= 104.
Sample input 1:
10
4
1
4
6
2
Output:
70
Why?
If we have the hikes as first employee gets 10, second gets 20, third gets 30 and fourth gets 10, we satisfy all our constraints.| Report Duplicate | Flag | PURGE
Brain Teasers - 3of 3 votes
AnswersGiven a string and a dictionary. Break the string into meaningful words.
- RXH February 21, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
Answersvery large bytestream (PB)
- Yashwanth January 08, 2013 in United States for Youtube
synchronization algorithm
given:
unsigned char read_byte(); ← side effect that it advances a byte pointer in the stream
write:
unsigned char read_sync_byte(); ← may result in >1 calls to read_byte()
remove byte '03' from the stream if the stream is in pattern 00 00 03
Example:
read_byte():
00 0f 42 17 00 00 03 74 00 00 00 00 14 ...
read_sync_byte():
00 0f 42 17 00 00 74 00 00 00 00 14 ...| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersSuppose you have a incoming stream of numbers and a method like T* readNextNumber() to read them, and each time there is only limited amont of them coming in and readNextNumber would return null if no more available. implement a method to calculate the median of all numbers you have read.
- lucifer1986 August 28, 2015 in United States
The key point to the question is figure out the data structure to store those numbers you have read and I stopped at a balance tree, the interviewer told me it should be 2 heaps, one ascending and one descending, plus a median value between them. The final algorithm I figure out based on it is each time compare the new number with median, if bigger than it insert to the descending heap at the right side of the median else to the left, recalculate the median by checking heap sizes, the new median would be either current median, max of the left heap or min of the right heap.| Report Duplicate | Flag | PURGE
Google Data Structures - 3of 3 votes
AnswersGiven a staircase that has 'n' step, and you climb the staircase by jumping over the steps. You can cover at max of 'k' steps in a single jump. List all the possible sequence of jumps you could take to climb the staircase.
- NEO December 16, 2014 in India
input:
n=4, k=2
output:
1,1,1,1
1,1,2
1,2,1
2,1,1
2,2| Report Duplicate | Flag | PURGE
Adobe Member Technical Staff Algorithm - 3of 3 votes
AnswersGiven a board made of 2 x n squares, and boards made of 2 x 1 squares, write a function that will calculate the number of possible ways to arrange the 2 x 1 boards on the 2 x n board, in a way that will fill it completely.
- GeorgyBoy December 30, 2013 in Israel
(Asked to refine the solution to be more efficient)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Coding Problem Solving - 3of 3 votes
AnswersA lot of transistors contains 0.6 percent defectives. Each transistor is subjected to a test that correctly identifies a defective but also misidentifies as defective about two in every 100 good transistors. Given that a randomly chosen transistor is declared defective by the tester, compute the probability that it is actually defective.
- sarora9876 July 29, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Analyst Brain Teasers