Recent Interview Questions
- 1of 1 vote
AnswersGiven the array of integers containing equal number of even and odd numbers. Rearrange
- zammer May 26, 2015 in India
the array such that even number is at even place and odd number is at odd place.
Example : [2,1,3,4,7,9,24,98]
Answer : 1,2,3,4,7,24,9,98| Report Duplicate | Flag | PURGE
VMWare Inc SDET Algorithm - 0of 0 votes
AnswersGiven set of job schedules with start and end time, write a function that returns indexes of overlapping sets.
- Tom Walker May 13, 2015 in United States
for ex :-
input -> [1,2][5,6][1,5][7,8][1,6]
return -> [0,1,2,4]| Report Duplicate | Flag | PURGE
Amazon SDE1 - 1of 1 vote
AnswersGiven two binary trees ( not BST) , return true if both of them have same inorder else return false.
Eg.B / \ A C
A \ B \ C
Both of the trees have same inorder ( A-B-C) hence function will return true
- Anonymous April 25, 2015 in United States
P.S.
Please note, we can write inorder method call it once for first tree and then second tree, and finally compare both inorder.
We want to parallely do inorder on both tree, if there is mismatch between inorder nodes of both trees, we can stop the traversal and return false| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 1of 1 vote
AnswersGiven a set of n people, find the celebrity.
- JSDUDE January 16, 2015 in United States
Celebrity is a person who:
1. Knows only himself and no one else
2. Every one else knows this person
You are given the following helper function:
bool knows(i, j);
Returns:
True: If i knows j
False: otherwise
I proposed the O(n2) algorithm at first but he wanted me to improve on it. He wanted an O(n) algorithm| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 0of 0 votes
AnswersGiven a array of positive integers, you have to find the smallest positive integer that can not be formed from the sum of numbers from array.
- hacker123 December 07, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Arrays - 16of 18 votes
AnswersOutput top N positive integer in string comparison order. For example, let's say N=1000, then you need to output in string comparison order as below:
- John July 15, 2014 in United States
1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 0of 4 votes
AnswersGiven a matrix of size N*N and a starting point "s" in the matrix which represents a color.
Find the area of the shape represented by the color of the starting point "s".
Note 1: A shape can be anything as long as it is connected, e.g. a square, a circle, a doughnut or a line.
Note 2: It is only a shape if they are connected from the starting point.
Note 3: Connected means, adjacent and the same color.
E.g.zero based index. Starting point = top left "R" [3][2], color = R, area = 10 000000000 000000000 000000000 00RRRR000 00R00R000 00RRRR000 000000000 000000000 000000000
Update: OK as requested further clarifications, a cell is only a single color, it is a matrix and contains
a single value stating the color of the cell. Think of each cell as a pixel and each pixel represents a length of 1.
The shape above has an area of 10, because that it is not a regular square but has two holes in the middle, if you do it mathematically:
(3*4) - (1*2) = 10 or simply by visually counting the R squares.
You are not trying to create shapes, you are using the starting point "s" to find the complete shape (traverse the matrix until you have found all connected pixels) and calculate the area.
If you need more clarification I can try but I think that should clarify.
State your Time and Space complexity of your algorithm.
Consider also this:0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 00RRRR0000000 00R00R000RR00 00RRRR000RR00 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 zero based index. Starting point s = top-left "R" [5][2], area = 10.
In the above case, the other shape, same color is not connected to the shape specified by the starting point, hence is not part of the area calculation.
- DotQ May 09, 2014 in United States
Apologies for the formatting.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven a list/array of names(String) sort them such that each name is followed by a name which starts with the last character of the previous name.
- anurag.11feb January 07, 2014 in Netherlands
# input
[
Luis
Hector
Selena
Emmanuel
Amish
]
# output:
[
Emmanuel
Luis
Selena
Amish
Hector
]| Report Duplicate | Flag | PURGE
Booking.com Developer Program Engineer Algorithm - 5of 5 votes
Answerswhy strings are immutable ?
- tare.rohan November 11, 2013 in India
how many objects will be created in
String temp = "A" + "B" + "C" ;
explain your answer in detail.| Report Duplicate | Flag | PURGE
Goldman Sachs Java Developer Java - 0of 4 votes
Answers2.Given an integer linked list of which both first half and second half are sorted independently. Write a function to merge the two parts to create one single sorted linked list in place [do not use any extra space].
- Harjit Singh September 27, 2013 in India for TCS
Sample test case:
Input: List 1:1->2->3->4->5->1->2; Output: 1->1->2->2->3->4->5
Input 2: 1->5->7->9->11->2->4->6; Output 2: 1->2->4->5->6->7->9->11
C/C++/Java/C#
struct node
{
int val;
node *next;
}
node* sortList(node* list1) {
}
Java
class Node
{
int val;
Node next;
}
Node sortList(Node list1) {
}| Report Duplicate | Flag | PURGE
Amazon SDE1 Linked Lists - 1of 1 vote
Answerscalculate (x^y)%z without pow();
- changran52m July 23, 2013 in United States for youtube| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersWrite a program to calculate Sum of two singly linked lists.
- shaktiman April 30, 2013 in -
e.g.
1-->2-->3
8->9->10
.
Result list should be 10-->2-->3
You are not allowed to make any change in input lists. Those are read only.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 0of 0 votes
AnswersWrite a program to reverse the sequence of words in a sentence.
- xankar April 11, 2013 in United States
For Eg:
String str = "Today is Wednesday";
Output:
String str2 = "Wednesday is Today"| Report Duplicate | Flag | PURGE
Goldman Sachs Senior Software Development Engineer Algorithm - 1of 5 votes
AnswersBelow question was asked in online coding exam for Palantir Technology, Palo Alto, CA. Time given was 100 min. I could not complete it by the time.
- Nitin Gupta February 02, 2013 in United States
-----------------------------
A group of farmers has some elevation data, and we’re going to help them understand how rainfall flows over their farmland.
We’ll represent the land as a two-dimensional array of altitudes and use the following model, based on the idea that water flows downhill:
If a cell’s four neighboring cells all have higher altitudes, we call this cell a sink; water collects in sinks.
Otherwise, water will flow to the neighboring cell with the lowest altitude. If a cell is not a sink, you may assume it has a unique lowest neighbor and that this neighbor will be lower than the cell.
Cells that drain into the same sink – directly or indirectly – are said to be part of the same basin.
Your challenge is to partition the map into basins. In particular, given a map of elevations, your code should partition the map into basins and output the sizes of the basins, in descending order.
Assume the elevation maps are square. Input will begin with a line with one integer, S, the height (and width) of the map. The next S lines will each contain a row of the map, each with S integers – the elevations of the S cells in the row. Some farmers have small land plots such as the examples below, while some have larger plots. However, in no case will a farmer have a plot of land larger than S = 5000.
Your code should output a space-separated list of the basin sizes, in descending order. (Trailing spaces are ignored.)
While correctness and performance are the most important parts of this problem, a human will be reading your solution, so please make an effort to submit clean, readable code. In particular, do not write code as if you were solving a problem for a competition.
A few examples are below.
Input:
3
1 5 2
2 4 7
3 6 9
Output:
7 2
The basins, labeled with A’s and B’s, are:
A A B
A A B
A A A
Input:
1
10
Output:
1
There is only one basin in this case.
Input:
5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4 2
3 3 5 2 1
Output:
11 7 7
The basins, labeled with A’s, B’s, and C’s, are:
A A A A A
A A A A A
B B A C C
B B B C C
B B C C C
Input:
4
0 2 1 3
2 1 0 4
3 3 3 3
5 5 2 1
Output:
7 5 4
The basins, labeled with A’s, B’s, and C’s, are:
A A B B
A B B B
A B B C
A C C C| Report Duplicate | Flag | PURGE
Palantir Technology Front-end Software Engineer Algorithm - 0of 0 votes
AnswersYou have a web server's log that records for each user the URL that he accessed.
Example format:Time-stamp User-id URL
How to find the maximum common (sub)sequence of visited URLs from all users? Write code in java
Log entries are ordered based on timestamp.
Example log (omitting timestamp for clarity):
John URL1
John URL2
Jim URL2
Mary URL1
John URL4
etc
Update:
Example:User-id URL 186 A 187 B 186 C 188 B 186 C 187 A 186 B 188 A 188 C 189 A 189 D 187 C 189 B 186 A 187 C 189 A 189 C
So the max common URL sequence is A,C,C (URL A followed by URL C, followed by URL C)
- Jim January 20, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Java - 1of 1 vote
AnswersYou are given a grid of numbers. A snake sequence is made up of adjacent numbers such that for each number, the number on the right or the number below it is +1 or -1 its value. For example,
- T December 07, 2012 in United States
1 3 2 6 8
-9 7 1 -1 2
1 5 0 1 9
In this grid, (3, 2, 1, 0, 1) is a snake sequence.
Given a grid, find the longest snake sequences and their lengths (so there can be multiple snake sequences with the maximum length).| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm - 0of 0 votes
Answersimplement Java's pow function, then list test cases, examine performance, see if you can optimize performance.
- rollingstar.15 October 30, 2012 in United States for NA
public double pow(double a, int b)| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Coding - 0of 0 votes
AnswersPrint a binary tree in vertical.
- kaushikdev9 October 11, 2012 in India
e.g.,
1
/ \
2 3
/ /
4 5
\
6
o/p: 4 2 1 5 3 6| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersA n*n matrix is given which is containing elements in which each row alone is sorted. column is not sorted. I have to convert it into a single dimensional array which will hold all the elements of the array in a sorted manner
- firefox October 01, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an N x M matrix having only positive values, we have to nullify the matrix i.e make all entries 0.
- anurag.gupta108 September 20, 2012 in United States
We are given two operations
1) multiply each element of any one column at a time by 2.
2) Subtract 1 from all elements of any one row at a time
Find the minimum number of operations required to nullify the matrix.
Note: no range of input was given| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFind lowest common ancestor of two nodes in a binary tree iteratively.
- Aashish August 05, 2012 in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 0of 0 votes
AnswersCount number of duplicated in a BST. Just print count at end or return count. Can't use HashMap or HashSet. Not supposed to any extra space
Example tree:5 / \ 3 10 / \ / \ 2 4 8 10 / / \ 3 5 8 \ 8
Answer for this is 5 (1 extra 3, 1 extra 5, 2 extra 8 and 1 extra 10)
- tazo August 02, 2012 in United States
EDIT: tree can't be modified. No extra space should be used. It should be O(n)| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersDelete the nth node in a linked list by passing only "n" as a parameter to the function. i.e the function does not have the address of the first node of the Linked list.
- jaiswal.amarnath July 29, 2012 in India| Report Duplicate | Flag | PURGE
HCL Software Engineer / Developer Data Structures - 0of 0 votes
AnswersAn array arr[] has coins of several denominations. Given the array and a required Sum find the minimum number of picks to get that sum. eg:
- Aryan July 09, 2012 in India
Input: {1,3,10} Sum required = 11
Output: 1+10 => 2 pickings| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array which contains the parent of the ith element in the n-ary tree.Parent[i] = -1 for root.
- grave July 07, 2012 in India
Find the height of the tree.
Gave O(n2) ,space O(1).
Expected Complexity- Linear
You can use extra space if you want.
Example-
{-1 0 1 6 6 0 0 2 7}
0 1 2 3 4 5 6 7 8
0 is the root here.
0 is the parent of 1 5 6
1 is parnt of 2
6 is parent of 3 4
2 is of 7 which is parent of 8.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures Hash Table Trees and Graphs - 0of 0 votes
AnswersFind the nth most frequent number in array
- mdfirozansari June 09, 2012 in India for MP3 mobile team| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer Arrays - 0of 0 votes
AnswersYou are getting a stream of characters and at any time you can be asked to find out if the string received yet is palindrome or not.
- Ajax May 21, 2012 in India
There can be multiple queries.He insisted to do it in better than O(n) and No extra space.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGive you an array of String,
- superffeng April 20, 2012 in United States
return number of distinct strings in that array.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a Binary tree where nodes may have positive or negative value, store the sum of the left and right subtree in the nodes.
Eg-10 -2 6 8 -4 7 5
Output:
- Puzzle November 19, 2011 in India20(-2+6+4+12) 4(8-4) 12(7+5) 0 0 0 0
| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Trees and Graphs Data Structures - 0of 0 votes
AnswersThree men on their way from San Jose to New jersey by walk, decides to rest under a tree, And all go deep sleep under it. A fourth person who was passing by the tree, wanted to have fun and draws a smiley face on the forehead of all three and leaves. After all three wake up and they start smiling at each other checking out smiley faces on each other. But only one smart one realizes it. How does he realize it??
- einstein.goli October 25, 2011 in United States| Report Duplicate | Flag | PURGE
Qualcomm Software Engineer / Developer Brain Teasers