## 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 States`Eg. 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.

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

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