william.brandon.lee83
BAN USER- 6of 6 votes
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 - 1of 1 vote
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
RepArnavPatel, abc at A9
Dedicated and energetic bakery assistant with a passion for flavor and a love for creating. Professional and dependable with more ...
RepNaomiAdams, abc at 8x8
Passionate educator for nearly 5 years with a strong desire to help students recognize the connection between learning and experience ...
RepAshleyDerri, Associate at Achieve Internet
I am Ashley, a highly qualified dynamic educator with experience educating and supporting students throughout the transition from high school ...
RepRoseReynolds, Analyst at 8x8
Hi everyone I am Lilla from the UK.I am passionate about two things, gym and book lover.Last topic ...
RepRuthOrvis, AT&T Customer service email at 8x8
Hey I am Ruth Working as a branch manager in a bank.I have worked here for the last 4 ...
Repdanikademers, HTML Experienced at Barclays Capital
I am Danika , working as a junior content writer with Jafco where I use my blog writing and social media ...
RepNancyDWilliams, abc at ABC TECH SUPPORT
I am NancyDWilliams. I work as a Personnel Administrator at Campbellsville university. I was born in India and currently, I ...
Repaalvinbrowne, Android Engineer at ASAPInfosystemsPvtLtd
Working as an Agricultural laborer at Mars Music I maintain yields like natural products, vegetables, grains, and nuts, or take ...
Repmarilyannrandall, Backend Developer at ABC TECH SUPPORT
As a Data input clerk, I deal with customers on a daily basis. Entering customer and account data from source ...
RepZoeyUhl, abc at 247quickbookshelp
With a highly experienced law clerk, well respected and writing proficient, detail oriented and proficient in preparing legal memos of ...
RepEileenBrown, Android Engineer at ABC TECH SUPPORT
Eileen Brown and I am a Product designer.And nowadays I am doing new research like istikhara for love marriage ...
RepNoraMiller, abc at A9
Confident and dedicated photographer with experience in both professional and freelance photography.. Prioritizes communication on the job to avoid errors ...
Repjosebowlin78, Aircraft engineer at CSK Auto
I am an Aircraft engineer . My role as an aircraft engineer involves the application of scientific and technological principles to ...
RepDessieBieri, Human Resource Executive at Bazaarvoice
I am Dessie, an academic advisor with more than 2 years of extensive field experience and a well-developed industry knowledge ...
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.