NS
BAN USER- 0of 0 votes
AnswersGiven a string, determine if a permutation of a string can form a palindrome.
- NS in United States| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 4of 4 votes
AnswersLets say someone accidentally deleted all the whitespaces from a sentence. Write a program to reconstruct the sentence from that stripped out string. Assume you have access to a dictionary function that returns if a given string is a valid word or not.
- NS in United States
Example input: thisisavalidsentence
Output: this is a valid sentence
If multiple solutions are possible, any one valid solution should be given. Assume there is always a valid solution. No invalid input will be given.| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
AnswersImplement a solution nth_largest( array, n ) that takes in an array of arbitrary size and returns the nth largest element.
- NS in United StatesEg. array = [1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67] nth_largest( array, 2) = 55 nth_largest( array, 5) = 9
| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Problem Solving - 0of 0 votes
AnswersWrite a program to identify if a given binary tree is balanced or not.
- NS in United States| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersWrite a program to print all permutations of a given string.
- NS in United States| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Problem Solving - 0of 0 votes
AnswersIf you have the chapter of a book and you're supposed to build an index such that given a word, you can tell which pages the word occurs on, what data structure can you use? Optimize for space utilization.
- NS in United States| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWrite a Python program to print numbers from 1 to 100 except for multiples of 3 for which you should print "fuzz" instead, for multiples of 5 you should print 'buzz' instead and for multiples of both 3 and 5, you should print 'fuzzbuzz' instead.
- NS in United States| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Python - 0of 0 votes
AnswersImplement a function DoIt( o,a ) such that the following code:
Object o = SomeClass() O.first = 'fizz' O.second = 'buzz' print DoIt( o, 'first) print DoIt(o, 'second')
prints
- NS in United States
fizz
buzz| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Python - 0of 0 votes
AnswersWrite a iterative Python function to print the factorial of a number n (ie, returns n!).
- NS in United States| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Python - 0of 0 votes
AnswersWrite a recursive Python function to print the factorial of a number n (ie, returns n!).
- NS in United States| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Python - 0of 0 votes
AnswersBoard Game:
- NS in United States
1) Write a program that can take a board of N x N filled with alphabets and print/return all the words that can be constructed by connecting alphabets together. You're allowed to connect alphabets in any direction including diagonally, the only restriction is that you cannot cross over the same alphabet twice. So for eg:
A,B,C,D
E,K,L,A
C,A,M,N
D,I,N,G
So example words that can be made are: BEAD, CALM, CAN, DAMN, MAKE.
2) What's the run time for your algorithm? Does your algorithm scale for large sizes of the matrix? What optimizations can you make to improve the run time.| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven an array of integers (can be both +ve or -ve), find the three integers which multiply to give the largest product.
- NS in United States
My solution: Sort the array, separate out the negative part and the positive part.
prod1 = product of 3 largest +ve integers
prod2 = product of 2 smallest -ve integers with the largest +ve integer
Compare prod1 with prod2, whichever is larger, that is the solution.
Obviously taking care of boundary cases. Any ideas?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an array of size N consisting 3 distinct numbers, how would you sort them using swapping in O(n)?
- NS in United States
My answer: I initially came up with "Counting Sort", then came up with a linked list based solution. But he told me I could come up with a swapping based solution in O(n). Any ideas?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
We can implement the trie datastructure using a queue. So for any keypress, we push the corresponding letters in the queue. If no other key is pressed, it is our answer, else for the next key press, we dequeue the elements, add the the other letters to them like in a trie and insert them at the back of the queue.
e.g.
Keypress order - 415
key - 4
insert - jkl
key - 1
insert - ja jb jc ka kb kc la lb lc
key - 5
insert - jam jan jao / jbm jbn jbo / jcm jcn jco/ kam kan kao/ kbm kbn kbo/ kcm kcn kco .. so on...
If anymore numbers are pressed, keep repeating the process, else the queue is the solution.
I think the simplest solution can be this:
Create a datastructure which holds a numerical value and a flag. Flag can be boolean since there are only 2 words but for the sake of clarity lets say flag has states = a,b
1. Maintain lists with positions of those words. Each node of the list is the above datastructure. Flag denotes 'a' for 1st word, 'b' for second word.
2. Run merge sort on both the lists, so as to produce combined result.
3. Start from the beginning:
MinDist = 0
a. Compare flags
If flags are same, -> skip
If flags are diff -> If( abs( number for 'a' - number for 'b') < MinDist )
MinDist = abs( number for 'a' - number for 'b')
Keep traversing till the end. MinDist has the minimum distance between the words.
Complexity should be O( n log n ) for merge sort and O(n) for traversal where n = freq of 'a' + fre
However, if the immediately larger number is to be found.. I believe this solution should work:
1. Extract the numbers and save them in an array.
2. Starting from the right, start scanning the array such that you find a location where the array stops being sorted in an ascending order. ( asc from right )
3. At that position, find the difference between all the digits and the digit in question. Swap it with the digit which has the smallest difference.
4. For all the digits to the right of the digits in question, sort them in descending order.
e.g. lets say 126975
starting from left, 75 is sorted, 975 is sorted, 6975 is not.
x = 6
6-5 = 1
6-7 = -1
6-9 = -3
Since smallest negative difference is with 7, swap the digits 6 and 7, we get.. 127965
Beginning from the right of 7, i.e. position x, sort all the digits in asc order, i.e. smallest first.. we get.. 127569.
ArrayList allows for O(1) lookup time since its accessible via index just like arrays. Linkedlist requires you to traverse through the list to find the element so O(n) lookup time. ArrayLists are basically arrays that automatically resize. Resizing is expensive so typically an optimized solution is to double to the size as soon as the array gets full. Deletion is faster in Linkedlists though since unlike ArrayLists, you're not using contiguous memory.
- NS February 16, 2016