Software Engineer / Developer Interview Questions
- 0of 2 votes
AnswersGiven pattern P (say aba) search for the pattern if the input is a stream of characters.
- Goooogle2014 May 02, 2014 in United States for Bing
1. You cant store the stream of chars. not even till Length(P)
2. You have access to only one char of stream at a time.
I gave KMP algo which was okay for him, but he mentioned you could have used some better DS..
I am wondering which DS can be used to store pattern..
Trie ???
You need to consider cases for stream like aababa
there are 2 occurences| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
Answers
- sh88990 May 02, 2014 in United States/* This class will be given a list of words (such as might be tokenized * from a paragraph of text), and will provide a method that takes two * words and returns the shortest distance (in words) between those two * words in the provided text. * Example: * WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick")); * assert(finder.distance("fox","the") == 3); * assert(finder.distance("quick", "fox") == 1); * /
| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer - 0of 4 votes
AnswersGiven a balanced BST, how would you return the nth smallest element in logn time .
- !@# May 01, 2014 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
Answerspublic interface FirstCommonAncestor {
- gul2u April 30, 2014 in United States
/**
* Given two nodes of a tree,
* method should return the deepest common ancestor of those nodes.
*
* A
* / \
* B C
* / \ \
* D E M
* / \
* G F
*
* commonAncestor(D, F) = B
* commonAncestor(C, G) = A
*/
public Node commonAncestor(Node nodeOne, Node nodeTwo)
{
}
}
class Node {
final Node parent;
final Node left;
final Node right;
public Node(Node parent, Node left, Node right, data) {
this.parent = parent;
this.left = left;
this.right = right;
this.data = data
}
boolean isRoot() {
return parent == null;
}
}| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersThe question was:
- puneet.sohi April 28, 2014 in United States for AWS
What are general guidelines you follow while creating new classes in C++
My answer:
1. Keep variables pvt (use setter and getter methods)
2. Use reference counting to do mem management, he asked me to use shared_ptr within the class| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Object Oriented Design - 2of 2 votes
AnswersI have two arrays A and B(each containing 8 bit integers). Find the common elements between them.
- puneet.sohi April 28, 2014 in United States for AWS
The questions started out as a general discussion with the most inefficient method. Then the interviewer asked me to improve the solution (to give a NlogN and finally a linear time solution)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswerWhat approach you will take in migrating your production databases from MySql to Postgre SQL with zero downtime.
- hulk April 26, 2014 in India| Report Duplicate | Flag | PURGE
Collective Software Engineer / Developer Database - 0of 0 votes
Answeri) Difference between HashMap & HashTable
- hulk April 26, 2014 in India
ii) How will you implement your own sorting algorithm in java?| Report Duplicate | Flag | PURGE
Collective Software Engineer / Developer Java - 0of 0 votes
AnswersCoin Change Problem
- hulk April 26, 2014 in India
-----------------------------
Given an unlimited supply of coins of denominations C1, C2, ..., CN we wish to make change for a value V. Give an algorithm for producing change with minimum number of coins.
You have to print the denominations selected.| Report Duplicate | Flag | PURGE
Collective Software Engineer / Developer Dynamic Programming - 0of 0 votes
Answers1 2 3
- hulk April 26, 2014 in India
4 5 6
7 8 9
* 0 #
Given a starting number, find all 6-digit numbers possible, numbers can only be dialed horizontally or vertically.
Repetitions not allowed. Number can't start from zero and doesn't include * and #. For example, if last dialed number
is 3, the next one could be 1, 2, 6 or 9.| Report Duplicate | Flag | PURGE
Collective Software Engineer / Developer Algorithm - 10of 10 votes
AnswersYou want to create a staff to use in your martial arts training, and it has to meet some specific requirements.
- krvangala98 April 25, 2014 in United States
1. You want it to be composed of two smaller staves of equal length so that you can either use it as a single staff or as two smaller ones.
2. You want the full sized staff's center of gravity to be exactly in the middle of the staff.
You have a very, very long branch from which you can cut the pieces for your staff. The mass of the branch varies significantly throughout it, so you use just any two pieces of the same length. Given a description of the mass throughout the branch, determine the longest staff you can make, then return three integers on a single line, the first two indicating the first index of each half-staff, and the third indicating the length of each half-staff.
The input will be given on a single line as a string of digits [1-9], each digit representing the mass of a section of the branch. All sections are the same size and the maximum length of the string is 500. Here is an example:
41111921111119
11119 11119
If the indicated sections are cut from the branch they will satisfy your requirements. They are both the same length, and they can be put together as either 9111111119 or 1111991111, both of which have a center of gravity exactly in the center of the staff.
Center of gravity can be determined by taking a weighted average of the mass of each section of the staff. Given the following distances and masses:
Distance: 12345678
Mass: 22241211
Sum of the mass of each section: 2 + 2 + 2 + 4 + 1 + 2 + 1 + 1 = 15
Weighted sum of the masses:
2*1 + 2*2 + 2*3 + 4*4 + 1*5 + 2*6 + 1*7 + 1*8 = 60
Weighted sum / regular sum = 60 / 15 = 4
This means that the center of mass is in section 4 of the staff. If we wanted to use this staff the center of gravity would need to be (8+1)/2 = 4.5.
Here is an example problem:
131251141231
---- ----
If we take the sections indicated we get 1312 and 1231. By reversing the first one and putting them together we get 21311231
Sum of the mass of each section: 2 + 1 + 3 + 1 + 1 + 2 + 3 + 1 = 14
Weight sum of the masses:
2*1 + 1*2 + 3*3 + 1*4 + 1*5 + 2*6 + 3*7 + 1*8 = 63
Weighted sum / regular sum = 63 / 14 = 4.5
This puts the center of mass exactly in the center of the staff, for a perfectly balanced staff. There isn't a longer staff that can be made from this, so the answer to this problem is
0 8 4
Because the half-staves begin at indices 0 and 8 (in that order) and each is of length 4.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 3of 3 votes
AnswersCode for computing a^b and optimize it.
- AlgoAlgae April 25, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 2of 2 votes
AnswersThe buildings of an office are numbered sequentially. Person A is in building 1 and person B is in building 106. If A crosses 5 offices in a minute and B crosses 10 offices in a minute, at which office number will they both meet?
- pkala April 25, 2014 in United States| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer - 0of 0 votes
AnswersFind the next number in the series.
- pkala April 25, 2014 in United States
-3, 6, -18, 72, - 360| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer - 0of 0 votes
AnswersFind the missing number in the series.
- pkala April 25, 2014 in United States
3, 8 , 18 , _ , 78| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer - 0of 0 votes
AnswersA string 'aBlY' is said to be well ordered because the letters of the string occur one after the other in the alphabet. Write a function where the number of letters in the string are passes as parameter and all such well ordered strings are found.
- pkala April 25, 2014 in United States| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer - 1of 1 vote
AnswersLet the user enter a decimal number. The range allowed is 0.0001 to 0.9999. Only four decimal places are allowed. The output should be an irreducible fraction.
- pkala April 25, 2014 in United States
Eg: If the user enters 0.35, the irreducible fraction will be 7/20.| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer - 0of 0 votes
AnswersThere are two roommates. Each one prepares a list for grocery store. Make a combined list without any duplicates.
- pkala April 25, 2014 in United States| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer - 0of 0 votes
AnswersWrite a program for a word search. If there is an NxN grid with one letter in each cell. Let the user enter a word and the letters of the word are said to be found in the grid either the letters match vertically, horizontally or diagonally in the grid. If the word is found, print the coordinates of the letters as output.
- pkala April 25, 2014 in United States| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer - 0of 0 votes
AnswersFind the maximum sum subset in an array with negative integers
- intervyou April 23, 2014 in United States| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer - 0of 0 votes
Answersfind the Maximum product subset with negative and positive integer
- intervyou April 23, 2014 in United States| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer - 0of 0 votes
AnswersHow would you speed up dynamically generated web content?
- pecan April 23, 2014 in United States| Report Duplicate | Flag | PURGE
Laserfiche Software Engineer / Developer Front End Web Development - 0of 0 votes
AnswerGiven a spreadsheet program, determine a method to prevent recursive formula calculation
- pecan April 23, 2014 in United States| Report Duplicate | Flag | PURGE
Laserfiche Software Engineer / Developer Algorithm - 2of 2 votes
Answersimplement division without using division operator in log(n) time.
- !@# April 22, 2014 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 2 votes
Answers8 coins are given where all the coins have equal weight, except one. The odd one may be less weight than the other or it may be heavier than the rest 7 coins. In worst case, how many iterations are needed to find the odd one out?
- Gaile April 22, 2014 in United States| Report Duplicate | Flag | PURGE
VMWare Inc Software Engineer / Developer - 1of 1 vote
AnswersAn array which is a Post order traversal of a Binary Tree. Write a function to check if the Binary Tree formed from the array is a Binary Search Tree.
- Gaile April 22, 2014 in United States
Eg:
2
1 3
The array given as input would be 1 3 2.
Write a function to say if the tree formed is a Binary Search Tree.
Example 2: 4 is root. 0 is left child of 1 , 1 is left child of 2 and 2 is left child of 4. 5 is right child of 4 and 6 is right child of 5.
4
2 5
1 6
0
0 1 2 6 5 4 is the input array.| Report Duplicate | Flag | PURGE
VMWare Inc Software Engineer / Developer - 9of 9 votes
AnswersGiven an array of integers, sort the array into a wave like array, namely
- Zen April 22, 2014 in United States
a1 >= a2 <= a3 >= a4 <= a5.....| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 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 - 1of 1 vote
AnswersYou are given a matrix where some pixels are white and some are black. Basically there are different disjoint images in the matrix.
- hulk April 20, 2014 in India
a) Expand/Shrink the images
b) Count the no of images
c) Color the images
d) Rotate the images| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays