Algorithm Interview Questions
- 1of 3 votes
AnswersGiven an array, you should start at index 0, and you can jump
- codechamp March 27, 2014 in United States
from the current index to a max of " current index + arr[current index]
and make it out of the array at the other end in minimum number of hops.| Report Duplicate | Flag | PURGE
Zynga Software Engineer / Developer Algorithm - 1of 3 votes
AnswersGive a function
- mabid.mahmood July 15, 2014 in United States
getRandomTripplet()
which returns a random triplet of letters from a string. You don't know the string using calls to this function you have to correctly guess the string. the length of the string is also given.
Lets say the string is helloworld the function getRandomTriplet will return things like
hlo
hew
wld
owo
the function maintains the relative order of the letters. so it will never return
ohl since h is before o in the string.
owe since w is after e
The string is not known you are only given length of the string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 3 votes
AnswersDesign a telephone directory for large ppl (he gave example like design for India). fields will be , first name , last name , number . this should be searchable with first name , last name , number as welll.
- gopi.komanduri July 04, 2014 in India
later added more complexity like do the same for organisation where even it contains designations. so this should be searchable with designations.| Report Duplicate | Flag | PURGE
Analyst Algorithm Arrays C C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Dynamic Programming Hash Table Ideas Large Scale Computing Linked Lists Object Oriented Design Problem Solving Trees and Graphs - 1of 3 votes
AnswersA special palindrome is a palindrome of size N which contains atmost K distinct characters such that any prefix between the size 2 to N-1 is not a palindrome.
- Prashanthwagle360 September 08, 2019 in India
You need to count the number of special palindromes
For example, abba is a special palindrome with N=4 and K=2 and ababa is not a special palindrome because aba is a palindrome and its a prefix of ababa.
If N=3, K=3, possible special palindromes are aba, aca, bab, bcb, cac and cbc. So answer will be 6.
Input format
Two integers N and K
Output format
Answer modulo 10^9+9
Constraints
1<=N,K<=10^9
Sample TC
3 3
Output
6| Report Duplicate | Flag | PURGE
HackerEarth Problem Setter Algorithm - 1of 3 votes
AnswersDesign a library to map a string of [a-zA-Z]+ to a positive integer value.
- madhurjf November 03, 2015 in India
For the strings, there could be:
An exact match. Eg: "get" will match only "get"
A prefix match. Eg: "com" will match anything that begins with "com"
The conditions are:
An exact match takes preference over prefix match.
In cases of multiple matches, the longest match takes preference.| Report Duplicate | Flag | PURGE
Algorithm - 1of 3 votes
AnswerCongrats to F.L.
- aonecoding November 03, 2017 in United States
Got offers from - Youtube(G), LinkedIn, Airbnb, Square, Wish, Blend and NextDoor!
Thanks for sharing the interview experience with us.
LinkedIn
Phone:
- Questions from LC tagged LinkedIn.
Onsite:
- Get sqrt(x). Output a floored integer if result is not a perfect square. sqrt(18) = 4
- Implement BST, insert, delete, search.
- Design a dashboard for service logs stats (sort and aggregate). Scale from 1 to more machines. Discuss async and realtime as different scenarios.| Report Duplicate | Flag | PURGE
Linkedin Software Engineer Algorithm - 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 3 votes
AnswersGiven a matrix of integers where each row is sorted but the columns are not sorted, print each matrix element in sorted order.
Here's an example matrix:matrix = [ [20, 35, 900], [5, 40, 45], [50, 60, 75] ]
Your function should print:
5, 20, 35, 40, 45, 50, 60, 75, 900
Add on: Assume that we have limited memory such that we can only hold one row in memory at a time. Optimize your algorithm given such constraints.
- seanchen11235 March 06, 2015 in United States| Report Duplicate | Flag | PURGE
Algorithm - 1of 1 vote
AnswersPush all the zero's of a given array to the end of the array. In place only. Ex 1,2,0,4,0,0,8 becomes 1,2,4,8,0,0,0
- CheckThisResume.com March 09, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm Arrays C Coding - 1of 1 vote
AnswersYou are given an array ' containing 0s and 1s. Find O(n) time and O(1) space
- Anonymous August 25, 2010
algorithm to find the maximum sub sequence which has equal number of 1s and
0s.
Examples
1) 10101010
The longest sub sequence that satisfies the problem is the input itself
2)1101000
The longest sub sequence that satisfies the problem is 110100| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersImplement the plusplus operator when we are getting the input as integer array = { 9,9,9,9 }.output will be {1,0,0,0,0}
- JobHunter July 11, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Arrays C Coding Data Structures - 1of 1 vote
AnswersGiven an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141
- Anonymous February 18, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Arrays - 1of 1 vote
AnswersConsider a series in which 8 teams are participating. each team plays twice with all other teams. 4 of them will go to the semi final.How many matches should a team win, so that it will ensure that it will go to semi finals.?
- putta.sreenivas May 11, 2011| Report Duplicate | Flag | PURGE
Amazon Google Developer Program Engineer Software Engineer / Developer Algorithm Brain Teasers - 1of 1 vote
AnswersFind the first non-repeating character in a stream of characters?
- samotgun November 18, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Hash Table Software Engineer / Developer Algorithm - 1of 1 vote
Answersthere are two arrays named A and B , both of them with k size, they are sorted in acsending order. could you find k-th smallest combinations of ai, bj -->(ai+bj) . 0<=i,j <k.
- yingsun1228 January 16, 2013 in United States
for example: a = {1, 3, 6} b = {4, 5, 6} then we will get 1 + 4 = 5, 1 + 5 = 6, and 1 + 6 = 7,the result is 5,6,7. does it make you understood? and could anybody do it with less time and space complexity.
Hi guys, thanks for all your suggestions and idea, and finally I get my answer and here are my c++ codes, time complexity is O(k*lgk), and space complexity is O(k):
#include<iostream>
using namespace std;
typedef struct node{
int row;
int col;
int data;
}Node, *PNode;
void swap(PNode &a, PNode &b) {
PNode temp = a;
a = b;
b = temp;
}
void adjust_min_heap(PNode *bin, int i, int k) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int min_index;
if(left < k && bin[left]->data < bin[i]->data) {
min_index = left;
} else {
min_index = i;
}
if(right < k && bin[right]->data < bin[min_index]->data) {
min_index = right;
}
if(min_index != i) {
swap(bin[i], bin[min_index]);
adjust_min_heap(bin, min_index, k);
}
}
void build_min_heap(PNode *bin, int k) {
for(int i = k / 2; i >= 0; i--) {
adjust_min_heap(bin, i, k);
}
}
int *get_k_th_minimum(int *a, int *b, int k) {
PNode *bin = (PNode*)malloc(sizeof(PNode) * k);
int *result = (int*)malloc(sizeof(int) * k);
memset(result, 0, sizeof(int) * k);
int i;
int count = 0;
for(i = 0; i < k; i++) {
bin[i] = (Node*)malloc(sizeof(Node));
bin[i]->row = i;
bin[i]->col = 0;
bin[i]->data = a[i] + b[0];
}
build_min_heap(bin, k);
while(count < k) {
result[count++] = bin[0]->data;
bin[0]->col += 1;
bin[0]->data = a[bin[0]->row] + b[bin[0]->col];
adjust_min_heap(bin, 0, k);
}
for(i = 0; i < k; i++) {
free(bin[i]);
}
free(bin);
return result;
}
void main() {
int a[] = {1, 2, 4};
int b[] = {5, 9, 11};
int k = 3;
int *p = get_k_th_minimum(a, b, k);
for(int i = 0; i < k; i++) {
cout << p[i] << " ";
}
free(p);
getchar();
}| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm - 1of 1 vote
AnswersString getSentence(String text, Set<String> dictionary);
- Vincent October 29, 2012 in United States
// text is a string without spaces, you need to insert spaces into text, so each word seperated by the space in the resulting string exists in the dictionary, return the resulting string
// running time has to be at least as good as O(n)
// getSentence("iamastudentfromwaterloo", {"from, "waterloo", "hi", "am", "yes", "i", "a", "student"}) -> "i am a student from waterloo"| Report Duplicate | Flag | PURGE
Twitter Google Software Engineer / Developer Software Engineer in Test Algorithm - 1of 1 vote
AnswersYou are given a huge log file which holds the entry and exit time of each person entering and exiting the office on a given day
- evolution monkey June 03, 2012 in United States
format of file:
entry time exit time
09:12:23 11:14:35
10:34:01 13:23:40
10:34:31 11:20:10
.
.upto N entries for a given day
Design a function which returns the total number of persons in the office at any given time. e.g input to function is 11:05:20.
The interviewer said he could call the function every second with input 11:05:20, 11:05:21,11:05:22, 11:05:23..........14:30:30
I really did not understand how to optimize the function.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou are tasked with implementing a method that returns the lowest possible number that could be generated after removing n characters from a string of digits. The method signature should look like:
public static string GenerateLowestNumber(string number, int n)
Where the number parameter is a string that contains a number (e.g. “4205123”), and the n parameter represents the number of characters to remove from the string. The goal of this method is to return the lowest number that can be generated by removing n characters from the number provided while keeping the positions of the remaining characters relative to each other the same (i.e. the method should remove n characters from the string, but it cannot re-order the characters).
- JSDUDE March 14, 2015 in United States for Cloud + Enterprise
For example, if number is “4205123” and n is 4, the lowest possible number that can be generated after removing any 4 characters is “012”. If number is “216504” and n is 3, the lowest possible number that can be generated after removing 3 characters is “104”.| Report Duplicate | Flag | PURGE
Microsoft Software Developer Algorithm String Manipulation - 1of 1 vote
Answers1. A
- amklo December 30, 2010
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys.
So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a number in an array form, Come up with an algorithm to push all the zeros to the end.
- kiranpm86 February 24, 2014 in India
Expectation : O(n) solution| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer Algorithm Arrays C++ Coding - 1of 1 vote
AnswersGiven an array having positive integers, find a continous subarray which adds to a given number.
- brahmasani99 May 02, 2012 in India| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
Answers* You are given 2 eggs.
- dareyouspam May 06, 2012 in United States
* You have access to a 100-storey building.
* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.| Report Duplicate | Flag | PURGE
NVIDIA Morgan Stanley Software Engineer / Developer Brain Teasers Algorithm - 1of 1 vote
AnswersGiven an array of positive integers (excluding zero) and a target number. Detect whether there is a set of consecutive elements in the array that add up to the target.
- m.mirzamo October 28, 2015 in United States
Example: a = {1, 3, 5, 7, 9}
target = 8
output = true ({3, 5})
or target = 15
output = true : {3, 5, 8}
but if target = 6, output would be false. since 1 and 5 are not next to each other.| Report Duplicate | Flag | PURGE
Facebook Intern Algorithm - 1of 1 vote
AnswersGiven a dictionary of strings [ strings are in sorted order] you have to find the precedence of characters according to the dictionary..
- Anton April 21, 2012 in India
eat
bxy
e is ranked above b according to the dictionary.| Report Duplicate | Flag | PURGE
Google Amazon Software Engineer / Developer Algorithm Data Structures Trees and Graphs Brain Teasers - 1of 1 vote
AnswersCelebrity problem:
- sreemana@buffalo.edu March 26, 2012 in United States
You have a room with n people. A celebrity walks in. Everyone knows the celebrity, the celebrity knows no one. Non-celebrities may/may not know anyone in the room. Give an algorithm to find the celebrity. Discuss the complexity.| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a string with multiple spaces write a function to in-place trim all spaces leaving a single space between words
- employee11 June 09, 2014 in Israel
e.g.
_ _ _ Hello _ _ _ World _ _ _
Hello _ World _ _ _ _ _ _ _ _ _| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array with positive, negative and zeros, arrange the given array such that negatives are on left, zeros in the middle and positives on the right.
- babbupandey August 20, 2012 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm Arrays - 1of 1 vote
AnswersIf an N X N matrix is given, print it in spiral order.
- GKR April 07, 2013 in United States
Example: Below is 5 X 5 matrix
i l o v e
d i n t e
n i e e p
a v w r i
m a x e c
Print in spiral order. Output is iloveepicexamandinterview| Report Duplicate | Flag | PURGE
Epic Systems Algorithm C C++ C# Coding Java - 1of 1 vote
AnswersGiven an array of 0s and 1s, and k, Find the longest continuous streak of 1s after flipping k 0s to 1s.
- neer.1304 February 14, 2016 in United States
E.x array is {1,1,0,0,1,1,1,0,1,1}
k = 1 (which means we can flip ‘k’ one 0 to 1)
Answer: 6 (if we flip 0 at index 7, we get the longest continuous streak of 1s having length 6)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm