Software Engineer Interview Questions
 2of 2 votes
Given a sorted array, find all the numbers that occur more than n/4 times.
 1of 1 vote
How to randomly select a number in an array?
array: [15, 2, 4, 5, 1, 2, 0]
Followup:
Given a second array freq where freq[i] represents the occurrence of the ith number in array, how to randomly select a number in array based on the frequency.
Extra requirement:
Could you complete the selection in a singlepass(go through each array only once)?
 0of 4 votes
In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),
check whether the student qualifies for the reward.
e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.
@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True
Followup:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.
 0of 0 votes
In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time), check whether the student qualifies for the reward.
e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.
@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True
Followup:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure the student gets the reward.
 2of 2 votes
Find three nonoverlap windows of size k in an int array, that together has a maximum sum
of the 3k entries.
example
int[] nums = [1,2,1,2,6,7,5,1]
k = 2
output
[1,2],[2,6],[7,5]
 1of 1 vote
Given:
a encoded to 1
b encoded to 2
....
z encoded to 26
You can translate a number to a string:
'123' can be translated to 'abc'
but also can be translated to 'aw','lc' which gives 3 total translations
'12' can be translated to 'ab' and 'l' > 2 translations
Write a function to get the number of valid combinations from a number like '123123123'
 0of 0 votes
how to find leaf node value from preorder sequence of BST without rebuilding the tree
 0of 0 votes
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times).
, but each time you sell you need to pay transaction fee, please calculate the maximum profit you can take. However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
public int maxProfit(int[] prices, int fee) {
}
 0of 0 votes
for a binary tree, print the root to the leaf path, but add "_" to indicate the relative position.
example:A / \ B C / \ / \ D E F G output _ _ A _ B D _A B _E A _C F A _ C _ _ G
 2of 2 votes
Early on I prefer to post the interview questions with a simplified description or only present the algorithmic part of it. Because it's hard for our students to memorize the full description of a problem. Therefore often times only the algorithm behind the question is given.
But somehow a user of this site @concernedCoder gets unhappy with it. So from today on, we will try to recover the original version of the question as much as possible.
We assure you all of the questions we posted are real questions that you have a good chance to come across during a coding interview. Anyone who has experience in a coding interview should be able to see that.
Here is the full description of a recent Amazon OA question. The reason why we are able to provide the full description is because it's the online assessment. But for an onsite interview it's almost impossible to recover the questions perfectly.
Title: Item Recommendations
Amazon wants to recommend items to a customer who has just made a purchase. Amazon's recommendation algorithm is based on item 'connection'.
Two items are 'strongly connected' if a single customer bought both of them. Two items are 'weakly connected' if they are both strongly and weakly connected to some other third item.
Your task is to determine the number of the items strongly and weakly connected to a given item.
You are provided the item id represented as a string, as well as the list of customer purchases represented as an array of strings. Each element in the array consists of a customer id(represented as a string) and an item id (also represented as a string). The two ids are separated by a colon. For example, if they element in the array is "ABJA:Z42G" then that means customer ABJA purchased item Z42G.
Your output consists of an array, where the first element in the array represents the number of items strongly connected to the provided item id and the second element represents the number of items weakly connected to the provided item id.
For example, if you were provided with the following input:
determineRecommendation("ABC",["first:ABC", "first:HIJ", "sec:HIJ", "sec:KLM", "third:NOP", "fourth:ABC", "fourth:QRS", "first"DEF", "fifth:KLM", "fifth:TUV"])
You would return the following array:
[3, 2]
since ABC is strongly connected to 3 items: DEF, HIJ and QRS and is weakly connected to 2 items: KLM and TUV
Although the description is long, the problem is just asking for 'search (with either DFS or BFS) in a graph'.
 2of 6 votes
Q: Weighted meeting room
Given a series of meetings, how to schedule them. Cannot attend more than a meeting at the same time. Goal is to find maximum weight subset of mutually nonoverlap meetings.class Meeting: def __init__(self): self.startTime self.endTime self.weight
@concernedCoder
When you claim the questions as fake, provide evidence. These are no doubt questions asked in the coding interviews of the best companies and they definitely help interviewees to prepare for the interview.
Why do you have a problem with this?
 0of 0 votes
If a string is matched to any filter, it is in the black list, otherwise not.
Design a data structure and implement following two functions.
addFilter(filter)
isInBlackList(string)
filters are in the form of
“a*b”
“abc”
“aa*b”
having at most one star, which matches 0 or more chars.
 2of 2 votes
You have L, a list containing some digits (0 to 9). Write a function answer(L) which finds the largest number that can be made from some or all of these digits and is divisible by 3. If it is not possible to make such a number, return 0 as the answer. L will contain anywhere from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in the list may only be used once.
{{
Test cases
==========
Inputs:
(int list) l = [3, 1, 4, 1]
Output:
(int) 4311
Inputs:
(int list) l = [3, 1, 4, 1, 5, 9]
Output:
(int) 94311
}}
My Solution:
{{
package com.google.challenges;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class Answer {
public static int answer(int[] l) {
// Your code goes here.
ArrayList<Integer> list0 = new ArrayList<>();
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
int sum =0;
Arrays.sort(l);
for(int i = 0; i<l.length; i++){
if(l[i] % 3 == 0){
list0.add(l[i]);
}else if(l[i] % 3 == 1){
list1.add(l[i]);
}else{
list2.add(l[i]);
}
sum += l[i];
}
if(sum%3==0){
StringBuilder strNum = new StringBuilder();
for(int i = l.length1; i >= 0; i)
{
strNum.append(l[i]);
}
return Integer.parseInt(strNum.toString());
}else if(sum%3 == 1){
if(list1.size()>0){
Collections.sort(list1);
list1.remove(0);
}else if(list2.size() >= 2){
Collections.sort(list2);
list2.remove(1);
list2.remove(0);
}else{
return 1;
}
}else if(sum%3 == 2){
if(list2.size()>0){
Collections.sort(list2);
list2.remove(0);
}else if(list1.size() >= 2){
Collections.sort(list1);
list1.remove(1);
list1.remove(0);
}else{
return 1;
}
}
list0.addAll(list1);
list0.addAll(list2);
StringBuilder strNum = new StringBuilder();
Collections.sort(list0);
for(int i = list0.size()1; i >= 0; i)
{
strNum.append(list0.get(i));
}
return strNum.length() > 0 ? Integer.parseInt(strNum.toString()) : 1;
}
}
}}
But here I am able to pass 4 test cases out of 5. Therefore I am looking for scenario which is left to check.
Can someone help me?
 1of 3 votes
On google search, how to enable key word auto completion after a few letters typed.
Followup: How to rank the words if they are weighted by frequency?
 1of 1 vote
Cross the street
ABC Company is involved in the logistics business.
The company has many outlets and stockyards in a city. The city is like an
N
×
M
N×M grid. We consider a single cell of the given grid to be a single block in the city. The stockyard is at the upperleft corner and the outlet is located in the lower right corner. Everyday, one of the employees has to travel from the upper left to the lower right corner for supplies. Each block in the city has a height, where the height of the block located at position (i,j) in the grid is equal to
A
[
i
]
[
j
]
A[i][j]. The company wants to change the heights of some of the blocks, so that the employee can enjoy a highspeed drive from the stockyard to the outlet. But this change comes at a certain cost.
Specifically, if they change a block height from x to y, then they must pay exactly

x
−
y

x−y dollars. Please help them find the minimum cost, such that by spending that specific amount, they can get a path from stockyard to the outlet with all blocks along the path having the same height.
In a single move, the employee can move from a block to any of its adjacent blocks. Note that during this journey, the employee is allowed to move in all four directions, fulfilling the condition that he never goes out of the grid at any point in time.
Input :
First line contains two positive integers N and M  number of rows and columns in the city. Then, N lines follow, each containing M integers, where the
j
t
h
jth integer on the
i
t
h
ith line denotes
A
[
i
]
[
j
]
A[i][j].
Output :
The first and only line of output should contain minimum cost.
Constraints :
1<= N, M <=100
1<= height of blocks <=100
Sample Input
5 5
1 1 1 1 1
9 9 9 9 1
1 3 3 3 1
1 9 9 9 9
1 1 1 1 1
Sample Output
6
Explanation
Optimal path taken by the employee will be : (1,1) > (1,2) > (1,3) > (1,4) > (1,5) > (2,5) > (3,5) > (3,4) > (3,3) > (3,2) > (3,1) > (4,1) > (5,1) > (5,2) > (5,3) > (5,4) > (5,5) The height of each block along this path can be changed to
1
1, at a total cost of
6
6. There is no way to get a cost less than this.
 0of 0 votes
Alex has recently decided to learn about how to design compilers. As a first step he needs to find the number of different variables that are present in the given code.
So Alex will be provided N statements each of which will be terminated by a semicolon(;). Now Alex needs to find the number of different variable names that are being present in the given statement. Any string which is present before the assignment operator denotes to a variable name.
Input Format: :
The first line contains a single integer N
Each of the next N lines contains a single statement.
It is guaranteed that all the given statements shall be provided in a valid manner according to the format specified.
Output Format: :
Print the number of different variable name that are present in the given statements.
Sample Input
2
foo = 3;
bar = 4;
Sample Output
2
Explanation
Foo and Bar are only two variables used inside the statements so answer is 2.
 0of 0 votes
Design classes to represent the following problem and solve the questions 1,2,3
A user might have some outstanding auto loan amount and you have 3 types of offers: personal loan, credit card and auto loan offers. You need to provide the user
with the following details:
1. Send user all the offers to the user
2. Send user all eligible offers (where minCreditScore < userCreditScore < maxCreditScore)
3. Send user all offers which satisfied 2) and where the (userOutStandingLoanAmount < maxOfferedAutoLoanAmount)
personalloan = [{
"personalloan": {
"id": 1,
"provider": "Avant",
"term": 36,
"minimumCreditScore": 300,
"maximumCreditScore": 700,
"maximumAmount": 10000
}
}, {
"personalloan": {
"id": 2,
"provider": "Prosper",
"term": 24,
"minimumCreditScore": 600,
"maximumCreditScore": 700,
"maximumAmount": 5000
}
}]
creditcard=[{
"creditcard": {
"id": 2,
"provider": "CapitalOne",
"minimumCreditScore": 600,
"maximumCreditScore": 700
}
}, {
"creditcard": {
"id": 3,
"provider": "Chase",
"minimumCreditScore": 300,
"maximumCreditScore": 900
}
}]
autoloan = [{
"autoloan": {
"id": 1,
"provider": "CapitalOne",
"term": 36,
"minimumCreditScore": 300,
"maximumCreditScore": 700,
"maximumAmount": 10000
}
}, {
"autoloan": {
"id": 2,
"provider": "Blue Harbor",
"term": 24,
"minimumCreditScore": 600,
"maximumCreditScore": 700,
"maximumAmount": 5000
}
}]
 1of 1 vote
Consider that the driver with one trip want to pick up some peoples in different locations like this:
String[] locations ={
"person1, person2, person3, person4, person5",
" person6, person7, person8, person9",
"person10, person11, person12",
"person13, person14, person15",}
in each location there are different choice, so write a code present all possible way to pick up people in the different locations. you can use every data structure needs.
 2of 2 votes
given preorder traversal [5,3,2,4,8,7,9] of a BST, how do we identify the leaf nodes without building the tree ?
@Anonymous Thanks for the reply!
Please try other use cases like, only single leaf node
 0of 0 votes
There is dedicated Samsung software for coding test the question is given below:
There is one spaceship. X and Y coodinate of source of spaceship and destination spaceship is given. There are N number of warmholes each warmhole has 5 values.
First 2 values are starting coordinate of warmhole and after that value no. 3 and 4 represents ending coordinate of warmhole and last 5th value is represents cost to pass through this warmhole. Now these warmholes are bidirection.
Now the to go from (x1,y1) to (x2,y2) is abs(x1x2)+abs(y1y2).
The main problem here is to find minimum distance to reach spaceship from source to destination coordinate using any number of warmhole. It is ok if you wont use any warmhole.
 0of 0 votes
list1 >aaa,bbb,ddd,xyxz,...
list2>bbb,ccc,ccc,hkp,..
list3> ddd,eee,,ffff,lmn,..
Inside a list the words are sorted
I want to remove words which are repeated across the list and print in sorted order
If the words are repeated in same list its valid.
In the above case
it should print aaa>ccc>ccc>eee>fff>glk>hkp>lmn>xyxz
 0of 0 votes
Some questions about how to write a immutable class.
 0of 0 votes
Find top n cities which got most orders. For example, amazon got a list of orders, and these orders will be shipped to different cities.
 4of 4 votes
# There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room.
# For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words:
# Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
# For example:
# input = [(1,4), (2,3)]
# > 3
# input = [(4,6), (1,2)]
# > 3
# input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
# > 11
 0of 0 votes
I recently had a take home assignment for a optimization engineer position at FB. I got 24 hours to finish it however it was suggested to finish under 90 minutes. The problem was to calculate the dot product of sparse matrix (optimize for speed). I wrote following code but got dinged. Not sure what's wrong to not clear even first stage!
#include <iostream> #include <string> #include <map> #include <sstream> using namespace std; class SparseVector{ private: map<int, double> m_map; int m_size; public: SparseVector(int size){ this>m_size = size; this>m_map = *new map<int, double>(); } void setValue(int i, double value){ if( i < 0  i > m_size) return; if(value == 0.0){ map<int, double>::iterator it = m_map.find(i); if(it != m_map.end()) m_map.erase(it); } else m_map[i] = value; } double getValue(int i){ if( i < 0  i > m_size) return 0.0; else { map<int, double>::iterator it = m_map.find(i); if(it != m_map.end()) return it>second; else return 0.0; } } int getSize(){ return m_size; } static double s_dotProduct(SparseVector a, SparseVector b){ if (a.m_size != b.m_size) return 0.0; double sum = 0.0; if (a.m_map.size() <= b.m_map.size()) { for (map<int, double>::iterator it = a.m_map.begin() ; it != a.m_map.end(); it++) if ((b.m_map.find(it>first)) != b.m_map.end()) sum += a.getValue(it>first) * b.getValue(it>first); } else { for (map<int, double>::iterator it = b.m_map.begin() ; it != b.m_map.end(); it++) if ((a.m_map.find(it>first)) != a.m_map.end()) sum += a.getValue(it>first) * b.getValue(it>first); } return sum; } template <typename T> static string s_ToString(T val) { stringstream stream; stream << val; return stream.str(); } static string s_printSparseVector(SparseVector a) { string s = ""; for (map<int, double>::iterator it = a.m_map.begin(); it!= a.m_map.end(); it++) s += "(" + s_ToString(it>first) + ", " + s_ToString(it>second) + ") "; return s; } }; int main(int argc, char *argv[]){ int lenA = 0, lenB = 0, setValA = 0, setValB = 0; cout << "Enter length for Sparse vector A : " << endl; cin>> lenA; cout << "Enter length for Sparse vector B : " << endl; cin>> lenB; SparseVector v1 = SparseVector(lenA); SparseVector v2 = SparseVector(lenB); double y; int x; cout << "Enter number of set values for Sparse vector A : " << endl; cin >> setValA; cout << "Enter the set Index, Value pair in separate lines" << endl; for(int i = 0; i < setValA; i++){ cin >> x; cin >> y; v1.setValue(x, y); } cout << "Enter number of set values for Sparse vector B : " << endl; cin >> setValB; cout << "Enter the set Index, Value pair in separate lines" << endl; for(int j = 0; j < setValB; j++){ cin >> x; cin >> y; v2.setValue(x, y); } cout <<"Sparse Vector1 = " << SparseVector::s_printSparseVector(vectorA) << endl ; cout <<"Sparse Vector2 = " << SparseVector::s_printSparseVector(vectorB) << endl; cout <<"Dot product of two sparse vectors is = " << SparseVector::s_dotProduct(vectorA, vectorB) << endl; return 0; }
 4of 4 votes
Find the median of an unsorted array.
Have to do better than O(nlogn) time.
e.g.
Given [2, 6, 1] return 2
Given [2, 6, 1, 4] return 3 which is sum of the two elements in middle over 2
 1of 1 vote
You are given a series of moves as a string, such as ">^V<^". You need to output a list with all the series of moves that represent a loop if they were made by a robot for example.
A loop is defined as a series of moves that lead to the same position, for example "><" or "^V".
In the case of "^>V<^" the output should be ["^>V<", "^>V<"], essentially the last move generates a new loop because it leads to a position that was visited before and that naturally can be followed up to the same position and describe a loop.
 1of 1 vote
Giving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.
eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple"
I was thinking of the following approach,
Build a Trie for all words in the Dict  O( n * k) where k is the longest string in the dict
For each character c, in S check if there is a word in Trie that starts with it and has the letters that appear in S after c. We can short circuit based on remaining characters and the length of longest string found so far.
This should take O( N * k) where N is length of S.
 2of 4 votes
Find all comments in the Java (it could be Python or any other language of your choice) codes that’s parsed in as a string.
You may assume the codes given is valid.
Input is a single string, e.g.
String codes =
“/* file created by aonecode.com\\n” +
“ welcome to the tech blog*/ \\n” +
“//main method\\n” +
“public static void main(String[] args) { \\n“ +
“ System.out.println(“//welcome”); //output\\n” +
“}”
Output is a list of strings
List<String> ret =
[
“ file created by anecode.com\n welcome to the tech blog”,
“main method”,
“output”
]
 4of 4 votes
Q: If you were given a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C]
and then another series [A != C, D != H, ..., F != A ]
Check whether the equations combined is valid.
For the example given, your program should return 'invalid', because the first series implies that A = C, which contradicts the statement A != C in the second series.