## william.brandon.lee83

BAN USER- 1of 1 vote

AnswersGiven a non-directed, strongly connected graph where the node values are letters of the alphabet, write an algorithm that prints out all possible permutations of strings. What is this called?

- william.brandon.lee83 in United States

For example:

V = A,B,C

Printout

ABC

ACB

BAC

BCA

CAB

CBA

BAC etc.| Report Duplicate | Flag | PURGE

IBM Software Engineer / Developer Algorithm - 1of 1 vote

AnswersGiven a sorted integer array, write a method that builds a balanced binary search tree. What is the runtime complexity?

- william.brandon.lee83 in United States

Hint: Recursion.

Follow-up: Non-recursive solution| Report Duplicate | Flag | PURGE

IBM Software Engineer / Developer Algorithm - 0of 0 votes

AnswersGiven a list of tuples {x, y, x' } that describe histograms on the X/Y axis, such that X is the X coordinate, Y is the Y coordinate, and X' is the distance from X, write a function that draws the skyline of these tuples.

- william.brandon.lee83 in United States

For example:

{3, 2, 4} , {4,5,3} will give the following points:

{3,0} - trivial

{3,2} - trivial

{4,5} -calculated

{7,0} -if list is done.

You cannot assume that the tuples are sorted. Provide runtime analysis.| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Algorithm - 0of 0 votes

AnswersGiven a string that represents an integer with no upper bound (billions, trillions, etc..), write a function "convert" that returns the integer value of the string. For example: "1000322" returns 1000322.Try to do this in O(1) space, and O(n) time. Better if possible.

- william.brandon.lee83 in United States| Report Duplicate | Flag | PURGE

Microsoft SDE-3 Algorithm - 0of 0 votes

AnswersGiven a binary tree, write a function LCA that returns the least common ancestor of two nodes. This is not a BST. Try not to use parent pointers in the custom Node class.

- william.brandon.lee83 in United States

Iterative solution takes O(1) space, recursive solution takes O(n) space.| Report Duplicate | Flag | PURGE

Microsoft SDE-3 - 0of 0 votes

AnswersGiven a list of IP address correspondences, such as

- william.brandon.lee83 in United States

IP1 = IP2

IP3 = IP4

IP3 = IP2

IP5 = IP6

IP7 = IP8

etc.

Return a list of unique IP addresses. In this case

IP1, IP5, IP7

Consider IPs as Strings or any other data type.| Report Duplicate | Flag | PURGE

Microsoft SDE-3 Algorithm - 0of 0 votes

AnswersGiven a list of integers (array or list), write a function that returns true if the list can be split into two lists that have an equal sum.

- william.brandon.lee83 in United States

Example: {4,2,2,0,-1, 1} returns true

{4}, {2,2,0,-1,1}

and {3,3,1} returns false.

Hints by interviewer:

- Complexity is 2^n| Report Duplicate | Flag | PURGE

Microsoft SDE-3 Algorithm

Aside from edge cases, this should be a good general solution. thx

- william.brandon.lee83 January 20, 2016Also correct, but the interviewer was looking for a specific answer (which is stupid...)

- william.brandon.lee83 January 19, 2016That's correct.

- william.brandon.lee83 January 19, 2016To answer you last question: It depends on the company. Amazon, Google, Facebook will respond in ~1 week. Microsoft can get back to you on the same day.

As for the first question:

The list does not need to be EVENLY split. So basically you can have a list

{1, 10, 2, 3, 4} that can be split into {10}, {1,2,3,4}

So you're basically looking at a permutation problem where you have to find lists of length 1-n such that Sum(subList) == Sum(List)/2

Also, another hint:

If sum(list) is odd then no such solution exists.

Also, it was the interviewer that said it cannot be resolved in polynomial time, so if you can disprove her, then good for you. I didn't get the answer because it was my 5th interview and I was completely burned out.

Edited the question. Thanks, good catch.

- william.brandon.lee83 January 18, 2016Yes there would be a physical limit on the upper bound of the integer (like Integer.MAX_INT in java), this doesn't change the algorithm. You can use the numbers provided as examples. And test for edge cases etc.

- william.brandon.lee83 January 18, 2016Sorry, I edited the question for clarity. All permutations

- william.brandon.lee83 January 18, 2016Sorry, I edited the question for clarity. All permutations

- william.brandon.lee83 January 18, 2016**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Hi, sorry for the late reply. Yes the feedback was given during the interview (meaning, she mentioned that she was looking for the minimum spanning tree solution).

- william.brandon.lee83 January 24, 2016As for the on-site interview (this was a phone interview) I am expecting an invitation soon (I hope). The recruiter said I did well.