Software Engineer / Developer Interview Questions
- 0of 0 votes
Answerswrite a function to generate a random number in a given range.
- nagyuga October 19, 2013 in India
Condition:
Each number should be generated exactly n times, i.e., if each number has to be generated only 5 times and
the number 7 has already occured 5 times then your function should not generate 7 again.
Actual he asked question linking with array but it is bit confusion, he asked to do the above only| Report Duplicate | Flag | PURGE
Deshaw Inc Software Engineer / Developer Algorithm - 5of 9 votes
AnswersQ: Given a sorted 2D N x N array (where array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]), can you write a function that converts this to a sorted 1D array?
- pdoggeth October 18, 2013 in United States
The obvious and naive way that I thought of was to convert the entire array into a 1D and do a mergesort on it, but there must be a better way than that. I'm wondering what the better and more efficient way is.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHi,
- mailsubhranshu October 17, 2013 in India
Following was a question that was asked to me in one of the interviews.
We know anagram of eat is: tea and ate
The question is:
We have a program. We feed a list of 10 thousand alphabets to this program.
We run the program.
Now at run-time, we provide a word to this program eg. "eat"
Now the program should return the number of anagrams that exist in the list of 10 thousand alphabets. Hence for an input of "eat", it should return 2.
What will be the strategy to store those 10 thousand alphabets so that finding the number of anagrams becomes easy.| Report Duplicate | Flag | PURGE
Progress Software Engineer / Developer Algorithm - 3of 3 votes
AnswersImplement a stack with O(1) push, pop, and min
- msito October 14, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Stacks - 0of 2 votes
AnswersImplement a LRU cache with O(1) addCache and removeCache.
- msito October 14, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Cache - -1of 1 vote
Answerscreate a java api for mood detection for the image captured from webcam with approximate indexing
- kapooraniket2606 October 11, 2013 in India| Report Duplicate | Flag | PURGE
Student student Software Engineer / Developer - 0of 0 votes
AnswersSpiraly print n*n matrix.
- Prajna October 10, 2013 in India
Eg: [1,2,3,4]
[12,13,14,5]
[11,16,15,6]
[10,9,8,7]
Should print
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Java - -9of 9 votes
AnswersAn arraylist containing datatype studentsScores are given where studentId, and results are twostates of this datatype. Each student takes more than 10 exams. We need to return the averages score of each student as a Map<student, average score> where the average score is calculated by taking the average of top 5 exams of a student.
- sivaji8 October 08, 2013 in United States
First we iterate the arraylist and create another Map<Integer, ArrayList<>> where the inner ArrayList has values of test scores. Iterating the arrayList to find avergae score and adding it to the another Map<student, averageScore>. What is the complexity of this?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersWrite a program to find the reoccurence the character in a given string ,if it find in that given string , come out from the loop.
- sakthi.light October 08, 2013 in India for 2
For Example
char *str = "abcdefgha";
here a is occured second time, so comes out from the loop.| Report Duplicate | Flag | PURGE
Software Engineer / Developer C# - 8of 10 votes
AnswersComplete the below function which takes an arraylist and displays the list in the expected output
- AP October 07, 2013 in United States
public class TreePrinter {
public static void printTree(Iterable<Relation> rs) {
// your code
}
}
public static class Relation {
String parent;
String child;
public Relation(String parent, String child) { ... }
}
}
Example input:
List<Relation> input = newArrayList();
input.add(new Relation(“animal”, “mammal”));
input.add(new Relation(“animal”, “bird”));
input.add(new Relation(“lifeform”, “animal”));
input.add(new Relation(“cat”, “lion”));
input.add(new Relation(“mammal”, “cat”));
input.add(new Relation(“animal”, “fish”));
TreePrinter.printTree(input);
Expected output:
line 1: lifeform
line 2: animal
line 3: mammal
line 4: cat
line 5: lion
line 6: bird
line 7: fish| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 1of 1 vote
Answers// merge sorted arrays 'a' and 'b', each with 'length' elements,
- mikeldi10 October 07, 2013 in Spain
// in-place into 'b' to form a sorted result. assume that 'b'
// has 2*length allocated space.
// e.g. a = [1, 3, 5], b = [2, 4, 6] => b = [1, 2, 3, 4, 5, 6]
//how to do it without rearanging the b array| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 1 vote
Answersboolean isBST(const Node* node) {
- mikeldi10 October 07, 2013 in Spain
// return true iff the tree with root 'node' is a binary search tree.
// 'node' is guaranteed to be a binary tree.
}
n
/ \
a b
\
c| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - -1of 9 votes
AnswersImplement an algorithm to print all possible valid combinations of braces when n pairs of paranthesis are given.
- sivaji8 October 07, 2013 in United States
I tried this code executing. I checked with System.out.println statements too. But I couldn't understand how this prints ( ( ) ). I have two questions.
1) If we give count as 2, this code should generate only ( )( ). But how does it go for another execution of whole addParen to generate (( ))
2) The second if block(that is, if(rightRem > leftRem) within the else block of allParen is always after if(leftRem > 0), then how come this is able to generate
( ( ) )
public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
if (leftRem < 0 || rightRem < leftRem) return; // invalid state
if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
String s = String.copyValueOf(str);
// System.out.println(str);
list.add(s);
} else {
if (leftRem > 0) { // try a left paren, if there are some available
str[count] = '(';
addParen(list, leftRem - 1, rightRem, str, count + 1);
}
if (rightRem > leftRem) { // try a right paren, if there’s a matching left
str[count] = ')';
// System.out.println(str);
addParen(list, leftRem, rightRem - 1, str, count + 1);
}
}
}
public static ArrayList<String> generateParens(int count) {
char[] str = new char[count*2];
ArrayList<String> list = new ArrayList<String>();
addParen(list, count, count, str, 0);
return list;
}
public static void main(String args[]) {
ArrayList<String> list = generateParens(2);
for (String s : list) {
System.out.println(s);
}
System.out.println(list.size());
}
}| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 2of 2 votes
AnswersCan you predict the output of the following code?
- Prithvi October 06, 2013 in Nepal for Java Developerfor (int i = 0; i < 101; i++) { if (i % 2 == 0) { System.err.print(i); } else System.out.print(i); }
| Report Duplicate | Flag | PURGE
Software Engineer / Developer Java - 0of 4 votes
AnswersYou have been given a series of 'n' numbers and the series is in a random order. Write a program to find the median of the series with minimum complexity.
- Purushotham Kumar October 05, 2013 in Canada for Graduate Recruitement Team| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Java - -21of 23 votes
AnswersFinding the minimum in a BST.
- sivaji8 October 05, 2013 in United States
The known solution is
public Node minimum(){
Node current, last;
current = root;
while(current != null){
last = current;
current = current.left;
}
return last;
}
The above code doesn't find 0.5 as the minimum.
1 and 3 are children of 2, 0.5 is left child of 3 and 3.5 is right child of 3
2
/ \
1 3
/ \
0.5 3.5| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersYou have two arrays of integers, where the integers do not repeat and the two arrays have no common integers.
- Billy Jim October 05, 2013 in United States
Let x be any integer in the first array, y any integer in the second. Find min(Abs(x-y)). That is, find the smallest difference between any of the integers in the two arrays.
Assumptions: Assume both arrays are sorted in ascending order.| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm - -13of 15 votes
AnswersCheck if a binary tree is BST.
- sivaji8 October 04, 2013 in United States
I know the solution but I want to know will this code work
public boolean IsBST(Node root){
if(root.left <= root && root.right > root){
IsBST(root.left);
IsBST(root.right);
}else{
return false;
}
return true;
}| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 2 votes
AnswersQuestion 1 / 1 (Path Explosion EASY)
- MJRocks October 04, 2013 in India
You were given a Binary Tree (not necessarily a Binary Search Tree) to play with, say T. T had some special properties
Each internal node in T had exactly 2 children
Each internal node in T was represented by an uppercase English alphabet (A-Z)
Each leaf node in T was represented by a lowercase English alphabet (a-z)
You were told remember T as long as you could. Hence, you memorised the string formed by traversing T in post-order. You used something similar to the pseudocode below
toPostOrderString (node)
if node is leaf
return node.value
else
T = ""
T = T + toPostOrderString(node.left)
T = T + toPostOrderString(node.right)
T = T + node.value
return T
Now, time has come to use that string again. The Eye has contacted you. Yes, the secret organisation mentioned in "Now you see me" ( don't tell anyone they are real !! )
You remember the string you memorised back then. You must reconstruct the binary tree T. You are also given a string A. All the characters of A are uppercase English alphabets. Let us assume that T has L leaves. Then, there will be exactly L paths from the root to the leaves - 1 unique path to each leaf.
You have to tell The Eye the number of paths out of L, on which, A exists as a sub-sequence. Look at the explanation for the Sample Case 1 for clarity.
You have to implement the method explodePaths in the code. explodePaths is passed the following parameters, respectively
N, the number of nodes in T
S, the string representation of the post-order traversal of T. Of course, the length of S will be equal to N.
K, the length of the string A
A, the string you must find in the paths from the root of T, to the leaves in T.
Note
It is not necessary that T is balanced. But, each internal node always has exactly 2 children. It is possible that both those children are internal nodes also. It is possible that only one of those children is an internal node.
For the given string S, because of the constraint that each internal node has exactly 2 children, you will always be able to determine the tree T, uniquely.
It is not necessary that all characters in T are unique. There may be several nodes with the same value.
In this problem statement, by sub-sequence we mean not necessarily contiguous. This is different from a sub-string.
Do not print the answer in explodePaths. Just return the value. The code-template interviewstreet provides does the input and output itself.
Consider the following tree
A
/ \
t B
/ \
/ \
B A
/ \ / \
x y a b
This tree is given in Sample Case 1 as
N = 9
S = "txyBabABA"
K = 2
A = "AA"
Now, there are 5 leaf nodes, and hence, 5 paths from the root to leaves - 1 for each leaf.
- A-t
- A-B-B-x
- A-B-B-y
- A-B-A-a
- A-B-A-b
Out of these 5 paths, you have to find the number of paths, on which "AA" exists as a sub-sequence. Of course, there are only 2 such paths
- A-B-A-a
- A-B-A-b
Hence the expected answer is 2.
In the same T above
The answer for A = "BB", is 2
The answer for A = "BA", is 2
The answer for A = "AB", is 4
The answer for K = 1 and A = "A", is 5
The answer for K = 1 and A = "B", is 4
The Sample Case 2 has a little more complicated T. The string S in Sample Case 2 is yeBgeuCBxAB.
Constraints
N ≤ 10000
K ≤ 100
The expected time complexity of the algorithm is O(N).| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Trees and Graphs - -6of 6 votes
Answersarrange books in box, if box carry weight == books
- Satish October 04, 2013 in India
weight then take another box..... find the no of box required.| Report Duplicate | Flag | PURGE
MAQ Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven set of N threads generate sum of all numbers in an array of known size M
- vik October 04, 2013 in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Trees and Graphs - 0of 2 votes
AnswerWhat is high dynamic range rendering and why is it important for realistic rendering?
- vik October 04, 2013 in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Graphics - 1of 1 vote
AnswersWrite a function to generate a second array of numbers containing running average of N elements from the original array
- vik October 04, 2013 in United States
So for instance if the original array is,
2,6,4,2,3 and N=3
result = 2,4,3,4,3
you can assume the corner elements can be filled with original elements where there are not enough elements to take avg of N elements| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Algorithm Arrays - 4of 4 votes
AnswersYou have written a memory manager and after using it your coworker complains that he is facing severe issues of fragmentation. What could be the reason(s) and how can you fix it
- vik October 04, 2013 in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Computer Architecture & Low Level Debugging Operating System - -2of 2 votes
AnswersHow do you check if a binary tree is balanced or not? Please traverse through this code and explain how the complexity is O(N).
- sivaji8 October 03, 2013 in United States
public boolean isBalanced(Node root){
if(checkHeight(root) == -1){
return false;
}else{
return true;
}
}
private int checkHeight(Node root){
if(root == null){
return 0;
}
int leftHeight = checkHeight(root.left);
if(leftHeight = -1 ){
return -1;
}
int rightHeight = checkheight(root.right);
if(rightHeight = -1){
return -1;
}
int heightDiff = leftHeight - rightHeight;
if(Math.abs(heightDiff) > 1){
return -1;
}else{
return Math.max(leftHeight, rightHeight) + 1;
}
}
Please traverse for the following tree.
A
/ \
B C
/ \ / \
D E F G
\
H| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 5of 5 votes
AnswersInitially there is a number n written on board. Two players start playing a game turn by turn. Each player has to replace the number n written on the board by n-2^k (for some k >= 0 such that 2^k < n)?
- ACP Pradyuman October 03, 2013 in United States
Also the number n-2^k has to be as beautiful as n (The beauty of a number depends on the number of one's in its binary representation). The player loses the game when he can't select any such k.
Given the initial number n, determine which player will win the game if both players play optimally. n > 0 and n <= 10^9.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Bit Manipulation - 9of 9 votes
Answersyou are given n-strings 1you have to find whether a chain can be termed with all the strings given number n? A chain can be formed b/w strings if last char of the 1st string matches with 1st char of second string. For example you are given
- Rahul Sharma October 03, 2013 in India
number of strings = 3
first string=sdfg
second string=dfgs
third string=ghjhk
they can be concatenated as ->
second first third
dfgs sdfg ghjhk (characters at concatenation points are same)
so concatenated string is-dfgsdfghjhk| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 3 votes
AnswersI was asked this ques in my first phone interview.
- Anonymous October 03, 2013 in United States
Replace a string within another string WITHOUT LIBRARY FUNCTIONS.
I/p:
Str="anonymous";
O/p:
str1="anonykggse";| Report Duplicate | Flag | PURGE
Informatica Software Engineer / Developer - 2of 2 votes
AnswersOpen Ended: Design an email system
- techpanja October 02, 2013 in United States| Report Duplicate | Flag | PURGE
Apple Software Engineer / Developer Algorithm - 2of 4 votes
AnswersGiven two trees, find if tree 2 is the mirror image of tree 1.
- techpanja October 02, 2013 in United States| Report Duplicate | Flag | PURGE
Apple Software Engineer / Developer Data Structures