Software Engineer / Developer Interview Questions
- -1of 1 vote
Answerswhat is the best,worst and average case complexity for fibonacci no.s ..explain?
- rvndr December 22, 2013 in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersImplement the function accumulate below in the language of your choice. The code is in PHP but the syntax of this question should translate into any language. You should have enough information from the comments to define this function correctly. You do not need to implement the function calc.
/**
* This interface should be implemented to represent doing a binary operation on two integers
*/interface iBinaryOperator { /** * This will take int $x and int $y and return an integer value or throw an exception * * @param int $x * @param int $y * @return int the value of the binary operation of $x and $y * @throws MathException */ public function calc($x, $y); } /** * This function should go through the array of operands and run calc on each operand IN ORDER, then * return the accumulated value. * * For example the code below would echo the value 10: * * $op = new Addition(); //class Addition obviously implements iBinaryOperator * $operands = array(5,2,3); * echo accumulate($op, $operands); * * This function should work for ANY size array of operands, and ANY class that implements iBinaryOperator * * @param iBinaryOperator $op * @param array $operands array of integers of size N, can be empty * @return int|string returns an int on successful accumulation, or the string 'error' in error conditions */ function accumulate(iBinaryOperator $op, array $operands) {//Add code here in the language of your choice
}
- printfNum December 19, 2013 in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer PHP - 0of 0 votes
AnswersThere is a function that scans an array of characters for the character 'e' and prints out each index. What is the complexity? Please implement this function in C, C++, PHP or JavaScript.
- printfNum December 19, 2013 in United States
If I sort the array, what is the complexity of the sort? What type of sort?
After sorting, what is the complexity if I rescan the array for the character 'e'?| Report Duplicate | Flag | PURGE
Software Engineer / Developer PHP - 0of 0 votes
AnswersWrite a function that could evaluate the algebraic expressions.
- shivkalra1 December 19, 2013 in United Statesa = "2+5/2" print eval(a) // prints 4.5
| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWrite a program to return list of words (from the given list of words) that can be formed from the list of given characters. This is like Scribble game. Say for example the given characters are ('a' , 'c' , 't' } and list the words are {'cat', 'act', 'ac', 'stop' , 'cac'}. The program should return only the words that can be formed from given letters. Here the output should be {'cat', 'act', 'ac'}.
- vimal.varadachari December 19, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven two sorted array in ascending order with same length N, calculate the first K min a[i]+b[j]. time complexty O(N).
- mario87 December 18, 2013 in United States
some misunderstood first K, to put it straight, to find the Kth min, not the first min| 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 - 2of 2 votes
AnswersA soda water machine,press button A can generate 300-310ml, button B can generate 400-420ml and button C can generate 500-515ml, then given a number range [min, max], tell if all the numers of water in the range can be generated.
- mario87 December 18, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 1 vote
AnswersGiven an input file, find the line with the most vowels ( Easy)
- matanvr December 17, 2013 in United States
Followup:
Given an input file and any criteria write a function that will find the best score line and return it.
(He told me the best score can be anything, min/max/(anything that can be measured) of the criteria).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer General Questions and Comments - 2of 2 votes
AnswersYou have two numbers decomposed in binary representation, write a function that sums them and returns the result.
- getmax0 December 16, 2013 in United States
Input: 100011, 100100
Output: 1000111| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Bit Manipulation - 0of 0 votes
AnswersCalculate number of DISTINCT palindromic substrings in a string with help of suffix array or a trie.
- justhack4fun688 December 16, 2013 in India
Like if aba is string the their are 3 distinct palindromic subsrings:{a,aba,b}| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a amount and several denominations of coins, find all possible ways that amount can be formed? eg amount = 5, denominations = 1,2,3.
- Roxanne December 16, 2013 in United States
Ans- 5 ways
1) 1,1,1,1,1
2) 1,1,1,2 (combinations aren't counted eg 1,2,1,1 etc)
3) 1,1,3
4) 1,2,2
5) 2,3| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersReimplement this code so that its results will always be the same, but that it does not cause a stack overflow on large inputs. Your solution must still implement the Folder interface.
Coding
Your class must be named iteration.MyFolder
- techpanja December 11, 2013 in United Statespackage iteration; import java.util.Queue; public class MyFolder<T, U> implements Folder<T, U> { public U fold(U u, Queue<T> ts, Function2<T, U, U> function) { if(u == null || ts == null || function == null) throw new IllegalArgumentException(); if (ts.isEmpty()) { return u; } // The recursive implementation will overflow the stack for // any data set of real size, your job is to implement a // non-recursive solution // return fold(function.apply(ts.poll(), u), ts, function); return null; } } package iteration; import java.util.Queue; public interface Folder<T, U> { U fold(U u, Queue<T> list, Function2<T, U, U> function); } package iteration; public interface Function2<T, U, R> { R apply(T t, U u); }
| Report Duplicate | Flag | PURGE
Apple Software Engineer / Developer - -1of 1 vote
AnswersI want to calculate number of DISTINCT palindromic substrings in a string.How to do it?
- justhack4fun688 December 11, 2013 in India
Like if aba is string the their are 3 distinct palindromic subsrings:{a,aba,b}
length of string could be 10^5 range.So i dont think O(n^2) solution will work.So the interviewer required some better algorithm.But i know only O(n^2) one.| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Algorithm - 0of 0 votes
AnswersPrint an n-ary tree with level. For e.g.
- techpanja December 10, 2013 in United States0 foo 1 bar baz 2 foobar barfoo Desired output: Level 0: foo Level 1: bar baz Level 2: foobar barfoo class TreeNode { String name; List<TreeNode> getChildren(); } void printLevels(TreeNode root) { // -- CODE-- }
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - -1of 1 vote
AnswersSuppose you have N machines connected to a network.
- codingfunnyguy December 05, 2013 in United States
Now you generate a new file on one machine, and want to sync up across all machines. please design a system to accomplish this task and also analyze the error tolerance issue.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 5of 5 votes
Answersdesign a system to return an unique ID for each request. For most of requests, the ID value should increase as time goes, the system should handle 1000 requests per second at least.
- codingfunnyguy December 04, 2013 in United States
timestamps alone is not valid since there might be multiple requests with same timestamps.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design - 0of 0 votes
AnswersWrite the code in C for the series eg: If a3b2c4 ..is taken then output should be aaabbcccc
- guptapayal493 December 02, 2013 in India for Rainbow| Report Duplicate | Flag | PURGE
Wipro Technologies Software Engineer / Developer Coding - 0of 0 votes
AnswersGiven a list of unsorted numbers, can you find the numbers that have the smallest absolute difference between them? If there are multiple pairs, find them all.
- dn_coder November 30, 2013 in India
Sample Input
12
-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854 -520 -470
Sample Output #2
-520 -470 -20 30
Explanation
(-470)-(-520) = 30- (-20) = 50, which is the smallest difference.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a list of unsorted numbers, can you find the numbers that have the smallest absolute difference between them? If there are multiple pairs, find them all.
- dn_coder November 30, 2013 in India
Input Format
There will be two lines of input:
n - the size of the list
ar - the n numbers of the list
Output Format
Output the pairs of numbers with the smallest difference. If there are multiple pairs, output all of them in ascending order, all on the same line (consecutively) with just a single space between each pair of numbers.
Constraints
10 <= n <= 200000
-(107) <= x <= (107), x ∈ ar
Sample Input #1
10
-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854
Sample Output #1
-20 30
Explanation
30- -20 = 50, which is the smallest difference.
Sample Input #2
12
-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854 -520 -470
Sample Output #2
-520 -470 -20 30
Explanation
(-470)-(-520) = 30- (-20) = 50, which is the smallest difference.| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHaving the following interface
interface CharStream { boolean hasNext(); char next(); }
implement bracket string validation, e.g. "()(([]))" is valid and "(]" is not.
Recursive implementation is required and you have the following signature:
- Zjor November 27, 2013public boolean isValid(CharStream in) { // your code here }
| Report Duplicate | Flag | PURGE
Barclays Capital Software Engineer / Developer Algorithm - 0of 0 votes
AnswersA subscriber is allowed to make a certain number of telephone calls for a lumpsum charge of Rs.300. Beyond that, he is charged at a certain rate per call. Two subscribers together make 1400 calls, and were charged Rs.425 and Rs.925 respectively. If a single person had made all of the 1400 calls he would have been charged Rs.1550. How many telephone calls are allowed for the first Rs.300?
- PRASHANTGAURAV November 27, 2013 in United States
option
a)300
b) 350
c) 400
d) 450| Report Duplicate | Flag | PURGE
CGI-AMS Software Engineer / Developer Brain Teasers - 0of 0 votes
AnswersFollowing code is used by ONE producer and ONE consumer
- Karrie November 26, 2013 in India
public void Produce(queue<int> queue, ManualResetEvent mre){
while(true){
lock(queue){
queue.enque(3);
}
mre.set();
}
}
public void Consume(queue<int> queue, ManualResetEvent mre){
while (true){
mre.Reset();
if (queue.Count == 0)
mre.WaitOne();
lock(Queue){
var x = queue.Dequeue();
}
}
}
the last code line causes error, queue is empty-
"var x = queue.Dequeue();"
they asked me to suggest a fix for that.| Report Duplicate | Flag | PURGE
IBM Software Engineer / Developer Threads - 0of 0 votes
AnswersI have an unordered array of nodes. Each node has an id and parent_id. I want to pretty print out the nodes in an expanded format.
Assumptions:
There is only one root node in the array.
Don't worry about the white space.
Node has a toString() method.
All the ids are arbitrary and unique.
This is a tree and not a graph.
For example:
Sample input:
[{parentId: F, id:G}, {parentId: E, id: F}, {parentId: A, id: B}...]A (parent_id = null) B (parent_id = A) C (parent_id = B) D (parent_id = C) H (parent_id = B) E (parent_id = A) F (parent_id = E) G (parent_id = F)
Sample output:
- anonymous November 26, 2013 in United States
ABCDHEFG
Please write a more optimized solution and tell me the complexity.| Report Duplicate | Flag | PURGE
unknown Software Engineer / Developer Data Structures - 0of 0 votes
AnswersI have an unordered array of nodes. Each node has an id and parent_id. I want to pretty print out the nodes in an expanded format.
- anonymous November 26, 2013 in United States
Assumptions:
There is only one root node in the array.
Don't worry about the white space.
Node has a toString() method.
All the ids are arbitrary and unique.
This is a tree and not a graph.
For example:
Sample input:
[{parentId: F, id:G}, {parentId: E, id: F}, {parentId: A, id: B}...]
A (parent_id = null)
B (parent_id = A)
C (parent_id = B)
D (parent_id = C)
H (parent_id = B)
E (parent_id = A)
F (parent_id = E)
G (parent_id = F)
Sample output:
ABCDHEFG
Please tell me the naive solution and its complexity.
Please write a more optimized solution and tell me the complexity.| Report Duplicate | Flag | PURGE
unknown Software Engineer / Developer - 1of 1 vote
AnswersHow to represent a number in base -2? (negative -2 base) eg 6 can be 11010 i.e. 16 -8 +0 -2 +0 = 6.
- Roxanne November 23, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Math & Computation - 1of 1 vote
AnswersWrite a function that converts an int into its alpha-numeric equivalent represented as a null terminated string. The function should accept an int as input and return a string as output. For instance, calling the function with an int value of 324 would return a null terminated string containing "324". Ensure that your function checks for appropriate boundary conditions and edge cases. Assume you cannot use any standard libraries (for example, no itoa or sprintf).
- greeny.hapchap November 23, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersABC Inc is a private company focused on oil and exploration. Its net income has been fluctuating since inception. It plans to raise funding for new explorations. The financiers are seeking out if the company had successful runs. If so, which was the most successful one historically. A successful run being a set of consecutive years in which adding the net income year over year results in a value greater than zero. The most successful run would be the one with maximum value. How would you find the most successful run for ABC Inc?
- Abhijeet Muneshwar November 23, 2013 in India
The input would be an array with the net income for all years till date since inception. Output should be a pair of years <Y1 Y2> which represent the most successful run. For simplicity let Y1 and Y2 be array indices. If there wasn't a successful run return -1.
Sample Input1: 3 2 -6 2 1
Output1: 0 1
Sample Input2: -2 -3 -1 0 -6
Output2: -1
Make suitable assumptions and submit your code (programming language of your choice), with relevant comments and test cases.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWrite a function to check if two binary trees have the same structure. This means they look a like or overlap if placed over each other.
- nosyDeveloper November 22, 2013 in United States| Report Duplicate | Flag | PURGE
MicroStrategy Software Engineer / Developer Algorithm