Software Engineer Interview Questions
- 0of 4 votes
AnswersYou 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.
- Parth Patel February 21, 2017 in United States
{{
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.length-1; 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?| Report Duplicate | Flag | PURGE
Google Software Engineer Google FooBar 24x7 Google chrome technical support number 1-888-201-2039 Arrays Computer Science Java Problem Solving - 1of 3 votes
AnswerOn google search, how to enable key word auto completion after a few letters typed.
- aonecoding February 19, 2017 in United States
Follow-up: How to rank the words if they are weighted by frequency?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersCross the street
- pbox February 18, 2017 in United States
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 upper-left 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 high-speed 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.| Report Duplicate | Flag | PURGE
abc Software Engineer Coding - 0of 0 votes
AnswersAlex 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.
- misterraj.ruchit February 18, 2017 in India
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.| Report Duplicate | Flag | PURGE
Aricent Software Engineer Java - 0of 0 votes
AnswersDesign classes to represent the following problem and solve the questions 1,2,3
- lks February 18, 2017 in United States
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)
personal-loan = [{
"personal-loan": {
"id": 1,
"provider": "Avant",
"term": 36,
"minimumCreditScore": 300,
"maximumCreditScore": 700,
"maximumAmount": 10000
}
}, {
"personal-loan": {
"id": 2,
"provider": "Prosper",
"term": 24,
"minimumCreditScore": 600,
"maximumCreditScore": 700,
"maximumAmount": 5000
}
}]
credit-card=[{
"credit-card": {
"id": 2,
"provider": "CapitalOne",
"minimumCreditScore": 600,
"maximumCreditScore": 700
}
}, {
"credit-card": {
"id": 3,
"provider": "Chase",
"minimumCreditScore": 300,
"maximumCreditScore": 900
}
}]
autoloan = [{
"auto-loan": {
"id": 1,
"provider": "CapitalOne",
"term": 36,
"minimumCreditScore": 300,
"maximumCreditScore": 700,
"maximumAmount": 10000
}
}, {
"auto-loan": {
"id": 2,
"provider": "Blue Harbor",
"term": 24,
"minimumCreditScore": 600,
"maximumCreditScore": 700,
"maximumAmount": 5000
}
}]| Report Duplicate | Flag | PURGE
Uber Software Engineer - 1of 1 vote
AnswersConsider that the driver with one trip want to pick up some peoples in different locations like this:
- sonya.abdoli February 17, 2017 in United States
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.| Report Duplicate | Flag | PURGE
Uber Software Engineer - 2of 2 votes
Answersgiven preorder traversal [5,3,2,4,8,7,9] of a BST, how do we identify the leaf nodes without building the tree ?
- Raj February 16, 2017 in United States
@Anonymous Thanks for the reply!
Please try other use cases like, only single leaf node| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 0of 0 votes
AnswersThere is dedicated Samsung software for coding test the question is given below:
- pbox February 09, 2017 in India
There is one spaceship. X and Y co-odinate 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 co-ordinate of warmhole and after that value no. 3 and 4 represents ending co-ordinate of warmhole and last 5th value is represents cost to pass through this warmhole. Now these warmholes are bi-direction.
Now the to go from (x1,y1) to (x2,y2) is abs(x1-x2)+abs(y1-y2).
The main problem here is to find minimum distance to reach spaceship from source to destination co-ordinate using any number of warm-hole. It is ok if you wont use any warmhole.| Report Duplicate | Flag | PURGE
Samsung Software Engineer Algorithm - 0of 0 votes
Answerslist1 -->aaa,bbb,ddd,xyxz,...
- codemarathon February 09, 2017 in United States
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| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 0of 0 votes
AnswersSome questions about how to write a immutable class.
- yankeson2013 February 08, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer - 0of 0 votes
AnswersFind top n cities which got most orders. For example, amazon got a list of orders, and these orders will be shipped to different cities.
- yankeson2013 February 08, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 4of 4 votes
Answers# 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.
- aonecoding February 08, 2017 in United States
# 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| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersI 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!
- Ad February 07, 2017 in United States for Advertisement optimization#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; }
| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - -1of 1 vote
AnswersYou 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.
- Ray February 01, 2017 in United States
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.| Report Duplicate | Flag | PURGE
Software Engineer Algorithm - 3of 3 votes
AnswersGiving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.
- IKnowThings January 28, 2017 in United States
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.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 4 votes
AnswersFind all comments in the Java (it could be Python or any other language of your choice) codes that’s parsed in as a string.
- aonecoding January 27, 2017 in United States
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”
]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 6of 6 votes
AnswersQ: If you were given a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C]
- aonecoding January 27, 2017 in United States
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.| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 1of 1 vote
AnswersGiven an input string "aabbccba", find the shortest substring from the alphabet "abc".
- shalu January 25, 2017 in United States
In the above example, there are these substrings "aabbc", "aabbcc", "ccba" and "cba". However the shortest substring that contains all the characters in the alphabet is "cba", so "cba" must be the output.
Output doesnt need to maintain the ordering as in the alphabet.
Other examples:
input = "abbcac", alphabet="abc" Output : shortest substring = "bca".| Report Duplicate | Flag | PURGE
Facebook Software Engineer String Manipulation - 1of 1 vote
AnswersGiven an array of integers, design an algorithm that moves all non-zero integers to the end of the array. Minimize the number of writes or swaps.
- pygrammer January 21, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm Arrays - 1of 1 vote
AnswersWrite code to decode strings. For example, String str = "3[a2[bd]g4[ef]h]", the output should be "abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh".
My solution is as follows.
- yankeson2013 January 18, 2017 in United Statespublic class StringDecoder { public static void main(String[] args){ String s = "3[a2[bd]g4[ef]h]"; System.out.println(decode(s)); } public static String decode(String s){ if(s == null || s.length()==0) return s; int indexOfFirstNumber = findIndexOfFirstNumber(s); int indexOfFirstBracket = findIndexOfFirstBracket(s); int indexOfClosingBracket = findIndexOfClosingBracket(s, indexOfFirstBracket); if(indexOfFirstNumber == -1) return s; String subStr1 = s.substring(0, indexOfFirstNumber); String subStr2 = decode(s.substring(indexOfFirstBracket+1, indexOfClosingBracket)); String subStr3 = decode(s.substring(indexOfClosingBracket+1, s.length())); int duplicates = Integer.parseInt(s.substring(indexOfFirstNumber, indexOfFirstBracket)); StringBuilder sb = new StringBuilder(); sb.append(subStr1); while(duplicates>0){ sb.append(subStr2); duplicates--; } sb.append(subStr3); return sb.toString(); } public static int findIndexOfFirstNumber(String s){ int index = -1; for(int i=0; i<s.length(); i++){ char c = s.charAt(i); if(c>=47 && c<=58){ index = i; break; } } return index; } public static int findIndexOfFirstBracket(String s){ int index = -1; for(int i=0; i<s.length(); i++){ char c = s.charAt(i); if(c=='['){ index = i; break; } } return index; } public static int findIndexOfClosingBracket(String s, int indexOfBracket){ int index = -1; int numberOfBracket = 1; for(int i=indexOfBracket+1; i<s.length(); i++){ char c = s.charAt(i); if(c == '[') numberOfBracket++; if(c==']'){ numberOfBracket--; if(numberOfBracket==0){ index = i; break; } } } return index; } }
| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersGiven a list of system packages, some packages cannot be installed until the other packages are installed. Provide a valid sequence to install all of the packages.
- aonecoding January 15, 2017 in United States
e.g.
a relies on b
b relies on c
then a valid sequence is [c, b, a]| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 3of 5 votes
AnswersPhone screen Q: String encoding and decoding: Design a method that converts a list of strings into a single string which can be later converted back to the list.
- aonecoding January 15, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Programming Skills - 3of 5 votes
AnswersQ: Find the absolute paths to all directories with image files, given a file system that looks like this. The subdirectory is one indent over.
- aonecoding January 15, 2017 in United States/usr /local profile.jpg /bin config.txt dest.png /rbin image.gif /sys /re /tmp pic.jpg ..... ……
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersYou are given an array of integers(with all valid input) You have to write a function which will produce another array, where the value in each index of the array will be the product of all values in the given array accept that index.
- Azarbaizan January 10, 2017 in United States for Market Place
Example
Array 1: 1 2 3 4 5
Array 2: 120 60 40 30 24.
Come up with a solution of O(n^2) can you improve it?| Report Duplicate | Flag | PURGE
Amazon Software Engineer Arrays - 0of 0 votes
AnswersRandom generate a NxN matrix with only four types of element: 1,2,3,4.
- wtcupup2017 December 30, 2016 in United States
However, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)
ex:
valid:
1 2 1 1
3 1 4 2
1 2 4 2
3 1 2 3
invalid because the first column has element 1 appears three times and all 1s are connected to each other :
1 2 1 3
1 3 4 2
1 2 4 4
2 3 2 2| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersAn interesting question asked in Google’s phone interview : suppose a row of parking lot with n spots, one of them is empty and n-1 spots are occupied with cars. Only one operation is allowed: move one car from its position to the empty spot. Given a initial order of cars and a final order, output steps needed to convert initial order to final oder with that operation.
- wtcupup2017 December 28, 2016 in United States
Follow up: Minimize steps needed.
ex:
{1 2 3 -1 4 5}
move car 1 to empty spot(denoted as -1) will make it {-1,2,3,1,4,5}
push 1 to the output list because you move car 1 to the empty spot
suppose you have a initial order {1 2 3 -1 4 5} and a final order {5,1,-1,3,2,4}, you need to transfer {1 2 3 -1 4 5} to {5,1,-1,3,2,4}, push each car moved into a output list.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven two big files merge the files on to a third file such that the lines interleave.
- santakdalai90 December 20, 2016 in India| Report Duplicate | Flag | PURGE
EFI Software Engineer design - 0of 0 votes
AnswersGiven an array of random numbers, shuffle the numbers once again with the least possibility of it being same as previous configuration.
- santakdalai90 December 20, 2016 in India| Report Duplicate | Flag | PURGE
EFI Software Engineer Arrays - 0of 0 votes
AnswersGiven two linked lists find if they are making a shape of 'Y' or a shape of 'V'.
- santakdalai90 December 20, 2016 in India| Report Duplicate | Flag | PURGE
EFI Software Engineer Linked Lists - 0of 0 votes
AnswersIf you can hop 1, 2, or 3 steps at a time, calculate the total number of possible combinations for `n` steps.
- noitidart December 10, 2016 in United States| Report Duplicate | Flag | PURGE
Linkedin Software Engineer Algorithm