Algorithm Interview Questions
- 1of 1 vote
AnswersWrite a preorder traversal of a binary search tree w/o recursion / stack / extra memory storage. Hint - you can augment the node data structure. However, you can't add a visited field to the node.
- goog August 04, 2010
I will let you guys ponder out a solution before answering with mine :o)
PS: Given the constraints, I believe its impossible to find a fix w/o augmenting the data structure. (If anyone else differs, please enlighten me).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
Answershow to divide an integer array into 2 sub-arrays and make their averages equal? e.g. a[left_portion]/left_portion_num == a[right_portion]/right_portion_num.
- AK47 November 08, 2007| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Math & Computation Data Structures Coding Algorithm - 1of 1 vote
AnswersGiven-an-array-of-length-n-having-integers-0-to-n-1-in-unsorted-order-we-have-to-modify-this-array-such-that-the-value-at-a-n-becomes-a-a-n-for-example-if-a-0-contains-5-then-a-0-will-have-value-a-5-and-so-on-condition-is-that-this-should-take-O-n-time-complexity
- 9811633187a November 15, 2015 in India for hr| Report Duplicate | Flag | PURGE
Adobe Field Sales Algorithm - 1of 1 vote
AnswersAssume we only take the least significant digit of each value in fibonacci sequence, and form the sequence of digits into pairs. In those pairs, the first value of one pair is the same as second value of its predecessor.
- evi March 22, 2015 in United States
As we know the fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21...
so the pair sequence is:
[1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 3], [3, 1] ...
Write a function to output the first n pairs of this sequence.
void Outputpairs(int n)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array of integers and a length L, find a sub-array of length L such that the products of all integers are the biggest.
- hongbin034 February 24, 2014 in United States
Example:
Input: {4, 1, -7, -8, 9}, 3
Output: {-7,-8,9}| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a BST, replace each node with the sum of the values of all the nodes that are greater than that node. Only constraint being that I was not allowed to use any global or static variable.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> February 19, 2014 in United States| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - 1of 1 vote
AnswersFind Whether a Input string had Palindrome?
- csenasa August 10, 2013 in India
Example :
Input Samples : "1234xyzyx5678" , "abcdefeabc"
Output : A Bool Value, True if Contains a Palindrome , False otherwise. ( In this Example input string conatins "xyzyx" and efe" Palindrome respectively)| Report Duplicate | Flag | PURGE
Intuit Senior Software Development Engineer Algorithm String Manipulation - 1of 1 vote
AnswersWe have two strings: a normal alphanumeric string and a pattern string. the pattern string can be composed by alphanumeric chars plus the char "?" and "*"
We want to check if the first string match the pattern, where the ? means that every char (alphanumeric) is permitted in that position, while * allows to have a sequence of alphanumeric chars.
as test we want to check that the function returns true to the following calls.
isMatching("abab","abab")
isMatching("abab","a**b")
isMatching("ababab","ab*b")
isMatching("","*")
isMatching("aaaaaab","*?*b")
i found this question hard, since the language we want to parse is not L1 (there's an ambiguity in the parsing tree) it means that a backtrack modality must be implemented.
Took me a while to find a reasonable solution (that, to be honest i was not happy with)
- Mark Ransew July 31, 2013 in United Statesfunction isLegal(string:String,pattern:String):Boolean{ if(pattern.length == 0 && string.length == 0) return true; if(pattern.length == 0 && string.length > 0) return false; // NOT PROUD OF THE FOLLOWING CONDITION if(pattern.length == 1 && string.length == 0){ if(pattern.charAt(0) == "*") return true; } if(isLetter(pattern.charAt(0))){ if(string.charAt(0) == pattern.charAt(0)){ // CHAR BY CHAR CONTROL return isLegal(string.substr(1),pattern.substr(1)); } return false; } else if(pattern.charAt(0) == "?"){ if(isLetter(string.charAt(0))){ // RECURSIVE CALL return isLegal(string.substr(1),pattern.substr(1)); } return false; } else if(pattern.charAt(0) == "*"){ var possibleSolution:Boolean = false; for(var i:int = 1; i< string.length && !possibleSolution;i++){ possibleSolution = isLegal(string.substr(i),pattern.substr(1)); } return possibleSolution; } else { // ILLEGAL PATTERN return false; } } function isLetter(s:String):Boolean{ return s.charCodeAt(0) > 96 && s.charCodeAt(0)<122; }
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWrite a program to remove duplicates from array of prime numbers.
- onlinesoumitra June 14, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 1 vote
AnswersHow to check num is power of 2?
- superffeng September 27, 2012 in United States for Site reliabilty| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer Algorithm - 1of 1 vote
AnswersGiven tree integers a, b,c. Write a function: int median (int a,int b,int c) to get the median number among a,b,c. Can not use sort, the times of integer operations (e.g. compare, + - * /, bit computing) the less the better. Analyze the best and the worst situation.
- gusuyucc September 24, 2012 in United States| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersFind the intersection of 2 unsorted arrays.
- crackit November 24, 2010
The interviewer asked me about the various methods possible and asked me to code one.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersFind a median of two sorted integer arrays.
- geeky_freak July 22, 2008| Report Duplicate | Flag | PURGE
VMWare Inc Amazon Software Engineer / Developer 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
AnswersSelect Kth largest value in the array. Given an unsorted array of size n, and a value k. Select the kth largest value from the array.
For example:
Array is [5, 3, 9, 1], n is 4
k = 0 => 9
k = 1 => 5
k = 3 => 1
- almunayer May 10, 2016 in United Statespublic int kthLargest(int array[], int k) { // ..... }
| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersAsked at Walmart Labs
- ayaskant.swain November 04, 2014 in India for R&D
----------------------------------
There is a row of seats. Assume that it contains 15 seats adjacent to each other. There is a group of people who are already seating in that row randomly. i.e. some are sitting together & some are scattered.
Take the row as a String in java.
The seat which is occupied is marked with a character 'X' & which is not occupied is marked with a dot '.'
Now your target is to make the whole group sit together i.e. next to each other and without having any vacant seat between them in such a way that the total number of hops or jumps at the end of the grouping them together should be minimum.
Ok let me try to explain you in details.
Here is the row having 15 seats represented by the String (0, 1, 2, 3, ......... , 14) -
. . . . x . . x x . . . x . .
Now to make them sit together one of approaches is - . . . . . . x x x x . . . . .
Following are the steps to achieve this -
1 - Move the person sitting at 4th index to 6th index - Number of jumps by him = (6 - 4) = 2
2 - Bring the person sitting at 12th index to 9th index - Number of jumps by him = (12 - 9) = 3
------------------------------------------------------------------------------------------------------------------------------------------------------------
So now the total number of jumps made = ( 2 + 3) = 5 which is the minimum possible jumps to make them seat together.
There are also other ways to make them sit together but the number of jumps will exceed 5 & that will not be minimum.
For example bring them all towards the starting of the row i.e. start placing them from index 0. In that case the total number of jumps will be ( 4 + 6 + 6 + 9 ) = 25 which is very costly and not an optimized way to do this movement.
Now write an algorithm which will return the minimum number of jumps required to make them sit together.| Report Duplicate | Flag | PURGE
Walmart Labs Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersGiven a NXN matrix, starting from the upper left corner of the matrix start printing values in a counter-clockwise fashion.
- Anon October 13, 2014 in United States
Eg: Consider N = 4
Matrix= {a, b, c, d,
e, f, g, h,
i, j, k, l,
m, n, o, p}
Your function should output: dcbaeimnoplhgfjk
Another example would be
C I P E
R N K U
U O W O
L E S Y
The function should print: EPICRULESYOUKNOW| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWrite a function to find the nth "ugly number". ugly numbers are numbers that can only be fully divided by 1, 2, 3, 5 and itself.
- ye.henry.tian October 01, 2014 in United States for logistics| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersI have 5 arrays with integer elements. I want to find the common elements in all 5 arrays. What is the logic?c
- sasivara January 30, 2014 in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a string, find the longest possible even palindrome (length of palindrome is even) from it.
- arun_lisieux May 10, 2013 in India
Eg:
Input: abcicbbcdefggfed
Output: defggfed (length is 8)
Available palindromes are
1) bcicb - has odd length
2) cbbc - even length
3) defggfed - longest palindrome with even length
This question was asked in a telephonic interview for my friend. I will be posting his solution in a day.| Report Duplicate | Flag | PURGE
Groupon Software Engineer / Developer Algorithm Arrays Coding String Manipulation - 1of 1 vote
AnswersYou are given a BST, and min, max elements. Your task is to trim this BST so that it contains the elements between the min and the max elements.
For example, given the mix and max elements [5, 13] and the tree below, you would return the output below.8 3 10 1 6 14 4 7 13
output should be :--->
- Abhishek Shrivastava April 20, 2013 in United States8 6 10 7 13
| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 1 vote
AnswersA circus is designing a tower routine consisting of people standing atop one another’s
- Priti May 27, 2011
shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people
in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a string as input, return the list of all the patterns possible:
'1' : ['A', 'B', 'C'], '2' : ['D', 'E'], '12' : ['X'] '3' : ['P', 'Q']
Example if input is '123', then output should be [ADP, ADQ, AEP, AEQ, BDP, BDQ, BEP, BEQ, CDP, CDQ, CEP, CEQ, XP, XQ]
- ngupta32@hawk.iit.edu March 30, 2018 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm Coding Data Structures - 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 - 1of 1 vote
AnswersGiven two words, determine if the first word, or any anagram of it, appears in consecutive characters of the second word. For instance, tea appears as an anagram in the last three letters of slate, but let does not appear as an anagram in actor even though all the letters of let appear in slate.
- jerinsebastian.punnamada April 08, 2014 in United States
Return the anagram of the first word that has appeared in the second word.
Sample Input 1
tea
slate
Sample Output1
ate
Sample Input 2
let
slate
Sample Output2
NONE
java solution| Report Duplicate | Flag | PURGE
Yahoo Applications Developer Algorithm Java - 1of 1 vote
Answersgiven a very large file with words. Reverse the order of all words. For Example: How are you doing today? -->>today? doing you are How I know you may say reverse the whole and reverse each word but, the interviewer said that the file is too big to fit into the memory and the file should be read through a inputStream object, then write the result file to harddisk.
- qq416603 November 30, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a seria of points (Xi, Yi), find the line containing the highest number of points from the list.
- Grr1967 November 29, 2012
Per my question he mentioned that I can assume that there is a given function that receives two points and returns the a and b of the line euqation (aX+b)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures - 1of 1 vote
AnswersYou are given 'n' appointments. Each appointment contains startime and
- topcoder99 November 12, 2011 in India
endtime. You have to retun all conflicting appointments efficiently
starttime and endtime can range from a few min to few years.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
Answersgiven a string find the number of distinct substrings of the string.
- Anonymous July 09, 2010
ex:
input-> aaaa
output-> 4(a, aa, aaa, aaaa)
input->abcd
output->10(a, b, c, d, ab, bc, cd, abc, bcd, abcd)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm