Dynamic Programming Interview Questions
- 2of 2 votes
AnswersYou have 81 balls. 80 balls have the same weight. 1 ball is the lightest one. What would be the minimum possible way to find the lightest ball ?
- AlgoBaba November 23, 2014 in United States
(Use Dynamic Programming)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Dynamic Programming - 9of 9 votes
AnswersGiven a string (1-d array) , find if there is any sub-sequence that repeats itself.
- for.anonymous.usa October 22, 2014 in United States
Here, sub-sequence can be a non-contiguous pattern, with the same relative order.
Eg:
1. abab <------yes, ab is repeated
2. abba <---- No, a and b follow different order
3. acbdaghfb <-------- yes there is a followed by b at two places
4. abcdacb <----- yes a followed by b twice
The above should be applicable to ANY TWO (or every two) characters in the string and optimum over time.
In the sense, it should be checked for every pair of characters in the string.| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm Brain Teasers C C++ Coding Data Structures Dynamic Programming Problem Solving String Manipulation - 0of 0 votes
AnswersLets assume I have a paper in the size of 8" by 11". How would I go about designing an algorithm that optimally fit smaller cards onto the paper.
- emptypeace October 14, 2014 in United States
Now I don't have the actual card dimensions but for this example lets assume the smaller cards are 3" by 4", 7" by 2" and 5" by 3".| Report Duplicate | Flag | PURGE
Dynamic Programming - 2of 2 votes
AnswersThe stepping number:
- Anon October 13, 2014 in United States
A number is called as a stepping number if the adjacent digits are having a difference of 1. For eg. 8,343,545 are stepping numbers. While 890, 098 are not. The difference between a ‘9’ and ‘0’ should not be considered as 1.
Given start number(s) and an end number(e) your function should list out all the stepping numbers in the range including both the numbers s & e.| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm Data Structures Dynamic Programming Java Online Test - 0of 0 votes
AnswersGiven an array[0, n-1], each number of the array is positive int. Your task is adding the operators,"+","*", "(",")" (add, multiply, parenthesis) to maximize the result . The position in the array is Fixed.
- justtest August 19, 2014 in United States
For example, "2,1,1,2", you can get (2+1)*(2+1)=9.
Follow up, if the number may be negative , how to solve it ?| Report Duplicate | Flag | PURGE
Algorithm Brain Teasers Coding Data Structures Dynamic Programming - 0of 2 votes
AnswersDesign a system like friend's functionality in facebook. should have all features of facebook's friends functionality. like for each person , he can have any number of friends , he will get suggestions for new firends , showing common friends if we visits any other profile . algo should be scalable , robust .
- gopi.komanduri August 02, 2014 in United States| Report Duplicate | Flag | PURGE
Computer Scientist Algorithm Android Application / UI Design Arrays Bit Manipulation C# C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Database Distributed Computing Dynamic Programming Hash Table Java Large Scale Computing Linked Lists Math & Computation Object Oriented Design Problem Solving Sorting SQL Stacks System Design Trees and Graphs XML - 0of 2 votes
AnswersHow to design a multi key hash map ( key count can be dynamic. if there are two keys , initiallly which can be used to find the value , keys can be increased to three as well ex: consider school structure. Intially , consider , student id is key , later , should be searchable even with key name , later with grade.
- gopi.komanduri July 05, 2014 in India| Report Duplicate | Flag | PURGE
Analyst Algorithm Arrays C# C++ Coding Data Structures Dynamic Programming Experience Hash Table Large Scale Computing Linked Lists Problem Solving Sorting Trees and Graphs - 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 9 votes
AnswersFind minimum number of steps to reach the end of array from start (array value shows how much you can move).
- byteattack May 19, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Dynamic Programming - 0of 0 votes
AnswersCoin Change Problem
- hulk April 26, 2014 in India
-----------------------------
Given an unlimited supply of coins of denominations C1, C2, ..., CN we wish to make change for a value V. Give an algorithm for producing change with minimum number of coins.
You have to print the denominations selected.| Report Duplicate | Flag | PURGE
Collective Software Engineer / Developer Dynamic Programming - 2of 2 votes
Answersgive me the code for :
Given a string say "I am a human being" the output should reverse all letters of each word but not the whole string as such.
Eg: O/p should be "I ma a namuh gnieb"
I somewhat wrote the code, but i was asked what if there are extra spaces etc.
(i am able to write the code sitting at my desktop at one short but there front of interviewer i am struggling. Need to build up my confidence)
let me know the best and optimised way of writing this code.
Also i suggest people to aviod using inbuilt functions as much as possible
My Answer is as below in perl
- i_learn April 11, 2014 in India#i want the reverse of the letters of all words in a string #eg Input is "I am a human being" then o/p shud be "I ma a namuh gnieb" $str="I am a human being"; @arr=split(' ',$str); print @arr; for($i=@arr-1;$i>=0;$i--) { $_=@arr[$i]; ####intead of above for loop if we use foreach(@arr) then it will reverse the whole string @word=split('',$_); { foreach $n (@word) { unshift(@final,$n); } } } print "\n @final \n";
| Report Duplicate | Flag | PURGE
Amazon Testing / Quality Assurance Algorithm Android Application / UI Design Arrays Automata Coding Data Structures Dynamic Programming Perl - 0of 2 votes
AnswersGiven an array say [0,1,2,3,5,6,7,11,12,14,20]
- i_learn April 11, 2014 in India
given a number say 5.
Now find the sum of elements which sum to 5
eg:2+3=5, 0+5=5 etc.
I guess the interviewer wanted all possible combinations eg 0+2+3=5, etc| Report Duplicate | Flag | PURGE
Amazon Testing / Quality Assurance Algorithm Android Application / UI Design Arrays Coding Data Structures Dynamic Programming Perl Sorting test Testing - -4of 4 votes
Answersasked me about assembly line problem.
- Mohit March 23, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Dynamic Programming - -4of 4 votes
Answersasked me to solve Knapsack Problem
- Mohit March 23, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Dynamic Programming - 2of 2 votes
AnswersGiven a mapping configuration such as:
- meh March 23, 2014 in United States
1:a
2:b
...
26:z
And a string like "12632", print the number of different ways you can map such string to alphabet characters.
For example, given "111" the answer is 3 because you can make "aaa", "ak" and "ka" different mappings. However, given "101" the answer is 1 because you can only make "ja" as a possible mapping (01 is not valid).| Report Duplicate | Flag | PURGE
Software Engineer / Developer Dynamic Programming - 0of 2 votes
AnswersFrog can jump 1 or 2 steps write the code to find out number of ways to go up to n steps
- pavan February 27, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Dynamic Programming - 0of 0 votes
AnswersFind the presence of a given word in a given grid, word can be matched in any direction up-down, down-up, left-right, right-left, both diagonals up and down etc.
- amnesiac February 24, 2014 in United States| Report Duplicate | Flag | PURGE
Epic Systems Dynamic Programming - 0of 0 votes
AnswersGiven a bunch of floors....and egg will break only if it is thrown from a floor and any floor above that....what least number of eggs u would need if total floors are say 32..
- cvb February 20, 2014 in India
I went with binary search..where I strt from middle...throw the egg, if it doesnt break...
go to middle of upper half and if it does break..i know I should go to middle of lower half.| Report Duplicate | Flag | PURGE
Myntra Senior Software Development Engineer Dynamic Programming - 0of 0 votes
AnswersYou're given 50 cups of sugar water. Each cup has the same volume but different amount sugar in it. Each cup is labeled with the ratio. Write an algorithm that tells us if it is possible to mix together different cups and get sugar water with perfect 1:1 ratio
- RabbitDawn September 12, 2013 in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer Dynamic Programming - -5of 7 votes
Answersneed to implement a weather report functionality. user will provide the city name , need to return the weather report.
- gopi.komanduri May 29, 2013 in India
if weather station exists n functioning properly , will return the weather report of that station .
else ,
will return the nearest available weather station report.
interviewer looking for optimized manner.
looking for datastructures to stores the cities n algo to return the report.| Report Duplicate | Flag | PURGE
Mentor Graphics Analyst Algorithm Arrays Bit Manipulation Brain Teasers C C# C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Dynamic Programming General Questions and Comments Graphics Hash Table Ideas Linked Lists Math & Computation Object Oriented Design Problem Solving Sets Sorting Stacks String Manipulation Terminology & Trivia Threads Trees and Graphs XML - -1of 1 vote
AnswersRound 2 :
- sonesh January 03, 2013 in India
Q 3 : you are given some nodes, and for each node a probability is given which will tell its importance, you need to design an efficient data structure such that the expected search time as minimum as possible. (Hint : Use dynamic programming + binary tree).| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Dynamic Programming Trees and Graphs - 0of 0 votes
AnswersRound 2 :
- sonesh January 03, 2013 in India
Q 2 : You are given finitely many intervals in 1D, you have to design a data structure an efficient data structure which can answer queries of the form “In how many intervals the point P belong ?”, P is an input point, and all intervals are closed. I answer B tree(think why) which is most efficient.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Data Structures Dynamic Programming Probability Trees and Graphs - 2of 2 votes
AnswersRound 1 :
- sonesh January 03, 2013 in India
Q 2 : longest palindrome in a string ? (Need to tell in O(n) time complexity + O(1) space complexity)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Coding Dynamic Programming String Manipulation - 0of 0 votes
Answersgiven 3 by 3 matrix ( all the entries are 1,2,3) defining 9 multiplication relationships. e.g Matrix(1,2) = 1 means 1*2 = 1.
- mark5907 December 07, 2012 in United States
For a sequence 112333222111, determine wether you can put parentheses on it to make it equals to 1?| Report Duplicate | Flag | PURGE
Dynamic Programming - 0of 0 votes
AnswersThere is a river and stones are distributed at certain distance .For example at x1 distance D1 stone present (Start-(x1)-D1--(x2)-.....Dn-2-(xn-1)--Dn--(xn)—end). We have given a value Z, which is much greater then sum of all distances (Z > x1+x2 ... xn). Question is to find out all possible patterns via which we can reach from start to end of river. Note Z distance required to be travelled, when we at end
- shashank September 16, 2012 in India for Bangalore| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Dynamic Programming - 0of 0 votes
AnswersThe aim is to find the optimal solution which packs the pieces in 4x4 unit square.
- jaipster September 14, 2012 in India for SDE
a jig saw puzzle is made up of exactly 4 pieces.
size of the completed puzzle is always 4 units x 4 units. This is given
There is no picture printed on the pieces; any solution would be valid, as long it is a 4 x 4 unit square.
The pieces can be only triangles, or quadrilaterals. Nothing else.| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm Brain Teasers Coding Dynamic Programming - 0of 0 votes
AnswersGiven two char arrays X="ZTANBMBLAUCY " and Y ="GABVCBKLAMNC", write an algorithm to find the longest subsequence that is present in both of them.
- ashok.singh.sairam August 24, 2012 in India
In the above case the common subsequence is "ABBAC".
Also describe the time complexity of your algorithm.| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Dynamic Programming - 0of 0 votes
AnswersWe are given a list of numbers A= {5,9,12,16,25,30,45} and their fixed probability of occurance P={0.22,0.18,0.20,0.05,0.25,0.02,0.08} where sum(p) =1. The problem is to arrange the numbers in a binary search tree in a way that minimizes the expected total access time. Note: In a binary search tree, number of comparisions needed to access element at depth d is (1+d)
- samant.bit August 02, 2012 in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Dynamic Programming - 0of 2 votes
AnswersGiven a character array. Find if there exists a path from O to X. Here is an example
- jinalshah2007 April 11, 2012 in United States
. . . . . . .
. . . . . . .
w . . . . . .
w .w.w..
. . . . O . .
. . w. . . .
. . . X . . .
You have to just keep in mind that you cannot go through 'W'.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Brain Teasers Dynamic Programming