Recent Interview Questions
- 77of 79 votes
AnswersYou have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.
- ericaturner0 April 01, 2013 in United States
For example,
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]
The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 44of 48 votes
AnswersPots of gold game: Two players A & B. There are pots of gold arranged in a line, each containing some gold coins (the players can see how many coins are there in each gold pot - perfect information). They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has a higher number of coins at the end. The objective is to "maximize" the number of coins collected by A, assuming B also plays optimally. A starts the game.
- 352905 February 12, 2013 in United States
The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?
At the end I was asked to code this strategy!| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 35of 35 votes
AnswersWrite a code to reverse the words in a sentence.
- Rajesh Burla March 11, 2016 in India| Report Duplicate | Flag | PURGE
Capgemini Senior Software Development Engineer - 33of 39 votes
AnswersGiven an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.
- LAP June 10, 2013 in United States
* The sub-arrays should not overlap.
eg- [2 -1 -2 1 -4 2 8] ans - (-1 -2 1 -4) (2 8), diff = 16
I gave him o(n^2) algorithm but he was not satisfied.| Report Duplicate | Flag | PURGE
Google Algorithm - 33of 35 votes
AnswersA k-palindrome is a string which transforms into a palindrome on removing at most k characters.
- sc.shobhit August 28, 2013 in India
Given a string S, and an interger K, print "YES" if S is a k-palindrome; otherwise print "NO".
Constraints:
S has at most 20,000 characters.
0<=k<=30
Sample Test Case#1:
Input - abxa 1
Output - YES
Sample Test Case#2:
Input - abdxa 1
Output - No| Report Duplicate | Flag | PURGE
Facebook Intern Algorithm - 29of 29 votes
AnswersYou are given a binary tree with the following node structure:
struct Node { int data; // some data struct Node *left, *right; // References to left and right children struct Node *previous, *next; // References to previous and next nodes };
The tree is initialized with previous = next = NULL for all the nodes.
- codebuddy November 21, 2010
Using the previous and next pointers construct a doubly linked list such that each node's next is the node to its right at the same level and the last node's next is the first node at the next level.(similarly previous). The algorithm should have space complexity O(1). i.e., should be done without using extra data structures.You are given a binary tree with the following node structure| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 29of 29 votes
AnswersGiven string say ABCGRETCABCG and substring length let us take length as 3, find the count of possible substrings, for example in above string ABC => 2 and BCG => 2 , where CGR and other 3 word length substrings has a count of 1.
- softwaregeek December 08, 2015 in India for Not known| Report Duplicate | Flag | PURGE
Linkedin Software Developer Algorithm - 27of 27 votes
AnswersWrite a program to check if the given string is repeated substring or not.
- Lakshman July 27, 2016 in India
ex 1: abcabcabc - yes - abc is repeated.
2: abcdabababababab - no.| Report Duplicate | Flag | PURGE
Ivycomptech Algorithm - 26of 26 votes
AnswersIf a canoe can hold 2 kids and a max weight of 150 lbs, write a function that returns the minimum number of canoes needed, given a list of kids and their weights.
- Rando May 17, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 26of 26 votes
AnswerSome users can put some files to a shared network drive. A Cron Job* is programmed to delete files from the shared network drive. The shared location has limited access and only people with Admin Rights can add a file to the drive. The Cron Job picks up only those files which fulfill the following conditions:
- abhiatniit April 08, 2016 in India
i. File Type = .txt
ii. 5kb<=file size=<20kb
iii. Filename = <4 digit unique id>_<username>_mmddyyyyhhmmss.txt
The time is in 24 Hour format
The cron job can delete only 10 files at a time.
The cron job is executed at the interval of ten minutes. Its running sequence is 10:00AM, 10:10AM, 10:20AM……………
Any error is reported in an xml file with the causes behind delete failure. The XML file is placed In the same drive, the name of the file is errorlog.xml.
Write test cases for testing the system. Just write test case description, avoid using standardized format.| Report Duplicate | Flag | PURGE
Testing - 25of 27 votes
AnswersGiven a large network of computers, each keeping log files of visited urls, find the top ten of the most visited urls.
- chandeepsingh85 September 26, 2013 in United States
(i.e. have many large <string (url) -> int (visits)> maps, calculate implicitly <string (url) -> int (sum of visits among all distributed maps), and get the top ten in the combined map)
The result list must be exact, and the maps are too large to transmit over the network (especially sending all of them to a central server or using MapReduce directly, is not allowed)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design - 25of 25 votes
AnswersThere is an island which is represented by square matrix NxN.
- amnesiac March 01, 2013 in India
A person on the island is standing at any given co-ordinates (x,y). He can move in any direction one step right, left, up, down on the island. If he steps outside the island, he dies.
Let island is represented as (0,0) to (N-1,N-1) (i.e NxN matrix) & person is standing at given co-ordinates (x,y). He is allowed to move n steps on the island (along the matrix). What is the probability that he is alive after he walks n steps on the island?
Write a psuedocode & then full code for function
" float probabilityofalive(int x,int y, int n) ".| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 23of 23 votes
AnswersYou are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number .
- Kavish Dwivedi July 15, 2013 in India for Bangalore
NOTE: The array isn't necessarily sorted.| Report Duplicate | Flag | PURGE
Amazon SDE1 Arrays - 23of 23 votes
AnswersYou have a complete graph with N vertices. You know that all edges have a cost of A and you are given a set of K edges whose cost is B. Find the shortest (cheapest) path from node 0 to node N - 1.
- f.v.anton April 12, 2014
0 < N, K < 500k
1 < A, B < 500k| Report Duplicate | Flag | PURGE
Java Developer Algorithm - 23of 23 votes
AnswersWrite test conditions and test data to test a app which has login and signup screen on a mobile app and once you click on signup or login it takes you to a website to fill the remaining details(for sign up) or to perform any activities post login. The screens were provided with all the fields.
- kreetanshu December 26, 2016 in India| Report Duplicate | Flag | PURGE
Amazon Testing / Quality Assurance Testing - 22of 38 votes
AnswersGive you an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed.
- lxfuhuo August 23, 2013 in CHINA
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.
o(n)time complexity and o(1) space complexity is perfect.| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 22of 22 votes
AnswersImplement binary addition of two strings.
- fruktoed August 14, 2020 in UK, London
For example "101101" and "111101" equal "1101010"
You cannot use any type conversion, operate only with strings.| Report Duplicate | Flag | PURGE
Facebook Android Engineer Algorithm - 22of 22 votes
Answerswrite a function :
- SDguy April 20, 2013 in United States
char * CreateEmptyString(int len);
function should return an pointer to an empty string of length len| Report Duplicate | Flag | PURGE
Apple Quality Assurance Engineer String Manipulation - 21of 27 votes
AnswersYou are given two array, first array contain integer which represent heights of persons and second array contain how many persons in front of him are standing who are greater than him in term of height and forming a queue. Ex
- grave August 04, 2013 in India
A: 3 2 1
B: 0 1 1
It means in front of person of height 3 there is no person standing, person of height 2 there is one person in front of him who has greater height then he, similar to person of height 1. Your task to arrange them
Ouput should be.
3 1 2
Here - 3 is at front, 1 has 3 in front ,2 has 1 and 3 in front.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 21of 23 votes
AnswersGiven a undirected graph with corresponding edges. Find the number of possible triangles?
- redsanket March 25, 2014 in United States
Example:
0 1
2 1
0 2
4 1
Answer:
1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 19of 19 votes
AnswersGiven two strings a and b, find whether any anagram of string a is a sub-string of string b. For eg:
- Masterchief117 March 23, 2014 in United States
if a = xyz and b = afdgzyxksldfm then the program should return true.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer String Manipulation - 19of 19 votes
AnswersHow do you parse a phone number from a huge database of a 'n' billion webpages in 30 minutes ?
- Yashwanth January 30, 2013 in United States| Report Duplicate | Flag | PURGE
Apple Software Engineer in Test Algorithm - 19of 19 votes
AnswersYou have a grid of size N x M. Rows of the grid are numbered from 1 to N from top to bottom and columns of the grid are numbered from 1 to M from left to right. So, top-left corner is indexed as (1,1) and bottom-right corner is indexed as (N,M).
- RohitKadam244 December 09, 2016 in India
Cost of visiting a cell at index (i,j) is denoted by C[i][j]. Cost of changing the direction of your facing at index (i,j) is denoted by P[i][j].
You have to start from cell (1,1) and reach to cell (N,M) with minimum cost. At cell (1,1), you can either face towards 'Right' or face towards 'Down'. At any point of time, you can either face 'Right' or face 'Down'.
There are 2-types of moves allowed:
1. Move one cell towards the facing direction i.e. if you are facing 'Right', you can move one cell 'Right' or if you are facing 'Down', you can move one cell 'Down'. The cost of visiting cell (i,j) will be C[i][j].
2. Change the direction of facing i.e. if you are facing 'Right', you can now face 'Down' or if you are facing 'Down', you can now face 'Right'. The cost of changing the facing direction at cell (i,j) will be P[i][j].
Find the minimum cost to reach (N,M) after starting from (1,1).
Constraints:
1 <= T <= 3
1 <= N,M <= 1000
1 <= C[i][j], P[i][j] <= 1000
Input Format:
First line of each testfile contains T, the number of test cases.
In each testcase, First line contains two inetgers N and M denoting the dimensions of the grid.
Next N lines contains M integers each denoting the cost matrix C.
Next N lines contains M integers each denoting the cost matrix P.| Report Duplicate | Flag | PURGE
- 18of 22 votes
AnswersGiven a BST and a value x. Find two nodes in the tree whose sum is equal x. Additional space: O(height of the tree). It is not allowed to modify the tree
- pavel.em January 26, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 18of 18 votes
AnswersIf a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.
- diffuser78 June 07, 2013 in United States
For example:
Input: "1123". You need to general all valid alphabet codes from this string.
Output List
aabc //a = 1, a = 1, b = 2, c = 3
kbc // since k is 11, b = 2, c= 3
alc // a = 1, l = 12, c = 3
aaw // a= 1, a =1, w= 23
kw // k = 11, w = 23| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm Coding - 18of 18 votes
AnswersDesign an Email sender, need to send 100,000000 emails and you have 5 machines how could you do it efficiently.
- shaileshagarwal1 June 15, 2015 in India for Transportation Team| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - 17of 21 votes
AnswersYou have the file with word at a single line.
- madeinindia March 24, 2014 in neitherland for perl backend
#input sample file
abactor
abaculus
abacus
Abadite
.
.
Zyrenian
#Output
******************************************************************a
*************b
**********************************c
**********************d
*******************************************************************************e
a) you have to count the character and create a histogram in alphabetical order.
b) now you have to produce a histogram with max 80 character in line in reference to max count
c) now same out based histrogram based on the character count| Report Duplicate | Flag | PURGE
Booking.com Software Engineer / Developer Perl - 17of 17 votes
AnswersFind the intersection of two linked list given their head pointer.
- Punit Jain March 29, 2012 in India
Constraint: You can only traverse a linked list only once.| Report Duplicate | Flag | PURGE
Algorithm - 16of 20 votes
AnswersGiven two object arrays of "id,weight" (sorted by weight), merge them together and create a one single array. If the "id"s are same values should be merged. Final resulting array should be sorted by weight. Result should be O(nlogn) in time complexity.
- dee707 July 28, 2016 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm