Algorithm Interview Questions
- 0of 0 votes
AnswersFind the first and last occurrence of a number in a sorted array of integers
- testsync012345 October 23, 2015 in United States for Kindle
For Example: int[] a = {1,2,3,4,5,5,7,8}| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer Algorithm - 4of 4 votes
AnswersGiven a linkedlist, write an algorithm to divide the linkedlist into two linkedlists, the first contains the Fibonacci numbers in the list and the second contains the non-Fibonacci numbers.
- a.ahmed.shalabey October 23, 2015 in United States for Software Development
Test the algorithm after developing the code| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm C Data Structures - 0of 0 votes
AnswersHow to find kth prime number with k<=500000 and time limit - 1s?
- Shuboy October 22, 2015 in United States| Report Duplicate | Flag | PURGE
Algorithm - 2of 2 votes
AnswersYou are given a set of points on x axis (consumers)
- emb October 22, 2015 in United States
Also you are given a set of points on a plane (producer)
For every consumer print the nearest producer.
Wanted something better than O(n^2) time.
Example:
consumers: 1 5 7
producers: (0, 3), (1,1), (3, 2), (8, 10), (9, 100)
Answer:
for 1 nearest producer is (1, 1), for 5 nearest is (3, 2), for 7 nearest is (3, 2)
Follow-up question: now both sets are sorted by x coordinate. Could you come up with a linear algorithm?| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersFind a counter example proving that the following substring algorithm is incorrect:
- awayes October 20, 2015 in United Statesconst char* findSubstr(const char* str, const char* substr) { int len = strlen(str); int substrlen = strlen(substr); int j = 0; const char* result = NULL; for (int i = 0; i < len; ++i) { if (str[i] != substr[j]) { j = 0; result = NULL; } else { if (j==0) result = &str[i]; ++j; if (j >= substrlen) break; } } return result; }
| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersCount the Mines Problem:
- jsduder October 19, 2015 in United States
Your program will first read an integer N from stdin.
Then it will then read N lines of N integers separated by spaces.
Each integer in this Grid will be either 1 or 0.
The program then outputs an N x N Grid where each Grid element represents the number of 1's surrounding that element, (excluding the element itself).
For (column, row) = (0, 0), surrounding element indices are (0,1) (1,0) and (1,1).
Similarly for (1,1), surrounding element indices are (0,0) (0,1) (0,2) (1,0) (1,2) (2,0) (2,1) and (2,2).
Constraints:
Your output lines should not have any trailing or leading white space
Maximum Dimension of Grid = 1000 x 1000
Example Input:
"3 0 1 0 0 0 0 1 0 0"
Expected output:
1 0 1
2 2 1
0 1 0| Report Duplicate | Flag | PURGE
xyz Software Developer Algorithm - 1of 1 vote
AnswersInput argument of a method is a list of char array. The method have to print all the possible combination of input char(s)...For example if the input argument has ['A','B','C','D'] the output should be A,B,C,AB,AC,AD,BC,BD,CD,ABC,ACD,BCD,ABCD
- kumar October 19, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersGiven an array of "array range", return an optimized array by deleting subarrays.
- dark_knight October 19, 2015 in United States
NOTE: Array range (2,6) represents (2,3,4,5,6)
INPUT: [(2,6),(3,5),(7,21),(20,21)]
OUTPUT: [(2,6),(7,21)]
Reason: (3,5) is a subarray of (2,6) and (20,21) is a subarray of (7,21)| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 1of 1 vote
AnswersGiven a sentence in a form of a string, reverse the words in the string and return a string. Handle a case where there might be period at the end of the sentence. If there is a period, the period has to come to the end of the reversed sentence. Discuss the time complexity of your algorithm.
- dark_knight October 18, 2015 in United States
INPUT: "This is a sentence"
OUTPUT: "sentence a is This"
INPUT2: "This one has period."
OUTPUT2: "period has one This."| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Intern Algorithm - 0of 0 votes
Answers2. VeryLongInt
- siva.sai.2020 October 18, 2015 in India
Design a class which can add and subtract integers up to 1000 digits. You can make the following assumptions
No need to handle overflow or underflow (extra credit if you do)
Copy constructor is available
“+” and “-” are binary operators| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 2of 2 votes
Answers1. Balanced Parentheses
- siva.sai.2020 October 18, 2015 in India
Given a string s of parentheses (ex: “(()”), return the minimum number of parentheses that need to be inserted to make it into a well formed string
A well formed (balanced) string of parentheses is defined by the following rules: ● The empty string is well formed. ● If s is a well formed string, (s) is a well formed string. ● If s1 and s2 are well formed strings, their concatenation s1s2 is a well formed string.
Implement
int MinNumInsersertionsForBalancing(const string& s)| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 0 votes
AnswersFind if the characters of the sample string is in the same order in the text string.. Give a simple algo..
- sachin.and3 October 18, 2015 in United States
Eg.. TextString: abcNjhgAhGjhfhAljhRkhgRbhjbevfhO
Sample string :NAGARRO| Report Duplicate | Flag | PURGE
Nagarro Java Developer Algorithm Arrays Brain Storming Brain Teasers Coding Hash Table String Manipulation - 1of 1 vote
AnswersSort an array of 0s, 1s and 2s
- NoMind October 18, 2015 in India
Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.
Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
The problem is similar to http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
But they have added 1 trick into the question, You cannot use high = n;
It means don't calculate the length of array.
Can anyone help me in writing the code for this problem ?| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
Answerthere are n ranges of numbers, we need to find the kth smallest element.
- avishkar11 October 17, 2015 in India
One way to find it is to perform a merge sort and return the kth element. but we don;t have extra space. For that we need to write the algorithm,
eg:
[2-8]
[5-10]
[7-20]
5th smallest element is 5. 10th smallest element is 7.| Report Duplicate | Flag | PURGE
NetApp SDE-3 Algorithm - 0of 0 votes
Answersdesign a bit map of 16K bit
- capricornkmu October 17, 2015 in United States for Networking
get_bit, should get a free bit in this bit map
clear_bit, should clear a bit in this bit map| Report Duplicate | Flag | PURGE
Hewlett Packard Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou have some money in your bank account, the only function to withdraw money is uint16 Withdraw(uint16 value), if the value is greater than the money you have it returns 0, otherwise it withdraws the requested amount and returns the "value"
- mike.radula October 13, 2015 in United States
Write a function that withdraws all your money.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - -1of 3 votes
AnswersLong getTime() // monotonically unique and increasing time
- xyz11 October 12, 2015 in India
// Implement
put(k, v)
get(k, t) // Return the value for k as it was at time t
// Example
At Time 0:
insert "Henry" -> "Ireland"
At Time 5:
insert "Henry" -> "Dublin"
At Time 10:
insert "Jim" -> "Edinburg"
get("Henry", -1) = null
get("Henry", 0) = "Ireland" // Times 0 -> 4 return "Ireland"
get("Henry", 1) = "Ireland"
get("Henry", 2) = "Ireland"
get("Henry", 5) = "Dublin" // All times >= 5 return "Dublin"
get("Henry", 10) = "Dublin"
get("Jim", 7) = null
get("Jim", 10) = "Edinburg"
get("Jim", 25) = "Edinburg"
We are not worried about space complexity but very much concerned with Time complexity| Report Duplicate | Flag | PURGE
Algorithm - -3of 3 votes
Answers.
- exist October 11, 2015 in United States| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersGiven two identical dom trees and an element in one of those trees, find the corresponding element in the other tree and highlight it.
- killdos October 11, 2015 in United States| Report Duplicate | Flag | PURGE
Ebay Java Developer Algorithm Trees and Graphs - 0of 0 votes
AnswersGiven a list of sorted arrays, like List<int[]>. Prepare and return a single sorted list.
- teli.vaibhav October 11, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 4of 4 votes
AnswersRearrange characters in a string so that no character repeats twice.
- pcinterview October 10, 2015 in United States
Input: aaabc
Output: abaca
Input: aa
Output: No valid output
Input: aaaabc
Output: No valid output| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersRearrange characters in a string so that no character repeats twice.
- pcinterview October 10, 2015 in United States
Input: aaabc
Output: abaca
Input: aa
Output: No valid output
Input: aaaabc
Output: No valid output| Report Duplicate | Flag | PURGE
Algorithm - 3of 5 votes
AnswersThere are several people sitting in the cinema, some of them are couples, some are not, they decide to swap their seats so that the couples can seat together, please calculate the minimal swap numbers.
- xblwyc October 07, 2015 in United States
1. the swap can happen between any two position.
2. E.g. AABCCDB -> AADCCBB, ans is 1| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersYou are building a small command-line application to calculate hotel availability for a city. Your application reads in two (2) data files, and outputs its answer to STDOUT.
- amusing October 06, 2015 in United States
Your application will read in:
· a list of hotels along with how many rooms each contains (in no particular order)
· a list of bookings that have been made (in no particular order)
Your application will then print the list of all hotels which have availability for check-in and check- out date range, if any.
Do not worry about whether a specific room is available in a hotel for the entire booking period without switching rooms: availability is defined as the hotel having at least one (1) available room for each night of the target stay, regardless of whether it's the same room from day to day.
Data Files
hotels.csv
# Name, Rooms
Westin, 10
Best Western, 20
Hilton, 10
...
bookings.csv
# Name, Checkin, Checkout
Hilton, 2015-04-02, 2015-04-03
Hilton, 2015-04-02, 2015-04-04
Westin, 2015-05-01, 2015-05-20| Report Duplicate | Flag | PURGE
Booking.com Software Engineer / Developer Algorithm - 2of 2 votes
Answersthere are N cities (numbered from 1 to N) in the game and connect them by N-1 highways. It is guaranteed that each pair of cities are connected by the highways directly or indirectly.The game has a very important value called Total Highway Distance (THD) which is the total distances of all pairs of cities. Suppose there are 3 cities and 2 highways. The highway between City 1 and City 2 is 200 miles and the highway between City 2 and City 3 is 300 miles. So the THD is 1000(200 + 500 + 300) miles because the distances between City 1 and City 2, City 1 and City 3, City 2 and City 3 are 200 miles, 500 miles and 300 miles respectively.
- hulei660066 October 06, 2015 in United States for bing
During the game the length of some highways may change. you want to know the latest THD.
sample input
3 5
1 2 2
2 3 3
QUERY
EDIT 1 2 4
QUERY
EDIT 2 3 2
QUERY
sample output
10
14
12| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 2of 2 votes
AnswersYou are given a permutation arr[N]. E.g. arr[3] = {2, 1, 0} or arr[5] = {0,1,2,4,3};
- emb October 05, 2015 in United States
Then you can prepare somehow and then start serving requests: request(a, b, k) = sorted(arr[a:b])[k], that is, k-th order statistic on slice [a:b] of arr.
E.g. if arr is [3,4,5,0,1,2] and a = 2 and b = 5, then arr[a:b] = [5,0,1] and let k = 2, so we sort it - get [0,1,5] and take k-th element, that is - 5.
Implement request(a, b, k) function. You can preprocess input data, that is, assume there will be only one array and many request() calls.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersA nXn matrix consisting of 0 and 1 only is given. n is always odd. A variable k is also given as input. You have to find the minimum vaue of a function F(x,y) over k contiguous row wise elements such that arr[x][y] is 1 for all k contiguous elements.
- ritwik_pandey October 04, 2015 in India
F(i,j) for any index (i,j) is (n/2-i)^2 + (n/2-j)^2.| Report Duplicate | Flag | PURGE
Cadence Inc Development Support Engineer Algorithm - 0of 0 votes
AnswersGiven two Binary Trees (not BST). Each node of both trees has an integer value. Validate whether both trees have the same integers, there could be repetitive integers.
- teli.vaibhav October 02, 2015 in United States
ex-
Tree1:
5
1 6
5 4 3 6
Tree2:
1
3 4
6 5
have identical integers.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersGiven a string which may contain parenthesis. We must verify the validity of the string.
- teli.vaibhav October 02, 2015 in United States
ex-
1) "<ad675+-fkmfd>" is a valid string
2) "<[((kskfhdbh7)" is invalid
3) "[<<((shfs8))>>]" is valid
Extension to the question -
Suppose you had a hash table that told you how a parenthesis starts and how it ends as a key value pair, how would you then validate the string.
ex - <key,value> = < '(' , ')' > indicates '(' is a start parenthesis and ')' should be the end of that paranthesis.
<'A','&'> indicates that 'A' is a start parenthesis and '&' is the end parenthesis.
Note: Validity means a parenthesis that starts, must end.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersFind the largest substring palindrome in a given string.
- revanthpobala October 01, 2015 in United States
ex: input: abbac output: abba
Solution: Use Hashmap| Report Duplicate | Flag | PURGE
Amazon SDET Algorithm