tag:blogger.com,1999:blog-6957414.post109840061746437225..comments2019-02-01T09:19:06.324-08:00Comments on Doing Boeing: Job update for the day.Adam Phillabaumhttp://www.blogger.com/profile/01798780122426727307noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-6957414.post-1155306604816919652006-08-11T07:30:00.000-07:002006-08-11T07:30:00.000-07:00You brought up very good points though. And the f...You brought up very good points though. And the fact that we have to track where every element came from... makes my solution kind of hokey (although, it is O(KN Log K)).Adamhttps://www.blogger.com/profile/01798780122426727307noreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1155239138816236972006-08-10T12:45:00.000-07:002006-08-10T12:45:00.000-07:00I think you redeemed your reputation. You're right...I think you redeemed your reputation. You're right and I'm wrong. I read too quickly. Good job!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1155229236127683792006-08-10T10:00:00.000-07:002006-08-10T10:00:00.000-07:00If you have the smallest element from every array ...If you have the smallest element from every array in the minheap, you will always end up with a sorted array.<BR/><BR/>If you remove an element from the minheap that originated from A, and replace with the element from the front of A... you'll always have the smallest item from each array in the minheap. <BR/><BR/>No scanning involved as long as you track the element's origination array.<BR/>right? Send me an email... so you can tell me I'm an idiot out of the public view :-)Adamhttps://www.blogger.com/profile/01798780122426727307noreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1155228796465697782006-08-10T09:53:00.000-07:002006-08-10T09:53:00.000-07:00Here is another caseA: 1 1 1B: 6 6 6C: 4 4 4worse ...Here is another case<BR/>A: 1 1 1<BR/>B: 6 6 6<BR/>C: 4 4 4<BR/><BR/>worse case, you still need to scan :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1155227945123073132006-08-10T09:39:00.000-07:002006-08-10T09:39:00.000-07:00Hmm... you're right.it'd be KN(K * log K)... which...Hmm... you're right.<BR/><BR/>it'd be KN(K * log K)... which would be O(K^2 * N).<BR/><BR/>If space weren't an issue (what? it could happen), you could keep track of heap elements origin. i.e.<BR/>Initial: Min heap = 1(b) 2(a) 3(c)<BR/>A: 4 5<BR/>B: 1 1<BR/>C: 6 7<BR/>RemoveMin(): Min heap = 2(a) 3(c)<BR/>A: 4 5<BR/>B: 1 1<BR/>C: 6 7<BR/>Add(<B>1(b)</B>): Min heap = 1(b) 2(a) 3(c)<BR/>A: 4 5<BR/>B: 1<BR/>C: 6 7<BR/>etc...<BR/><BR/>Now you can skip the step of scanning the arrays.<BR/>I'm not sure how practical that is though. If you're payload is an int and your origin information is a pointer, the size in memory of the heap has just doubled. If your payload is something larger (like a string or something), then the pointer to the array is negligible. <BR/><BR/>It seems like maybe there could be a better way. I need more time, and a pen and paper though :-)Adamhttps://www.blogger.com/profile/01798780122426727307noreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1155226202755945372006-08-10T09:10:00.000-07:002006-08-10T09:10:00.000-07:00"Everytime you pull off an element from the MinHea..."Everytime you pull off an element from the MinHeap, you put a new one in."<BR/><BR/>You can't do this in constant time. You got to go through and look for the smallest element. The complexity of this in O(K). Basically, You need to have all the elements in the Heap so that you don't keep rescanning the Arrays. You were close getting that job with Google. Maybe it's time for you to try again. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1155219016976549872006-08-10T07:10:00.000-07:002006-08-10T07:10:00.000-07:00I see what you mean. How about... everytime you p...I see what you mean. How about... everytime you pull off an element from the MinHeap, you put a new one in. And the new one that you put in is off of the array that the most recently sorted number was from.<BR/><BR/>Initial: Min heap = 1 2 3.<BR/>A: 4 5<BR/>B: 1 1<BR/>C: 6 7<BR/><BR/>RemoveMin(): Min heap = 2 3<BR/>A: 4 5<BR/>B: 1 1<BR/>C: 6 7<BR/><B>Add(1): Min heap = 1 2 3</B><BR/>A: 4 5<BR/>B: 1<BR/>C: 6 7<BR/>RemoveMin(): Min heap = 2 3<BR/>etc...<BR/><BR/>So, you're going to "re-heapify" into a MinHeap with k elements kn times... so O(KN log K)<BR/><BR/>Does that sound right? I haven't done anything like this in real life for a long time. I haven't even had a discussion about something like this since college... this is REALLY fun. I miss computer science :-(Adamhttps://www.blogger.com/profile/01798780122426727307noreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1155191588625956292006-08-09T23:33:00.000-07:002006-08-09T23:33:00.000-07:00The reason I think you need to put all the element...The reason I think you need to put all the elements in the array is because<BR/><BR/><BR/>A: 2 4 5<BR/>B: 1 1 1<BR/>C: 3 6 7<BR/><BR/>First run: Min heap = 1 2 3.<BR/>RemoveMin: Min heap = 2 3<BR/><BR/>You can not do RemoveMin to get the smallest element in the heap anymore. 2 is not the smallest. B still hold the smallest element.<BR/><BR/>Second Run: Min heap = 1 2 3 4 6<BR/>RemoveMin: Min Heap = 2 3 4 6<BR/><BR/>Third Run: Min Heap = 1 2 3 4 5 6 7<BR/><BR/><BR/>So do deal with the worse case, you need all the elements to be in the Min Heap. Am I missing something?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1154915112004941232006-08-06T18:45:00.000-07:002006-08-06T18:45:00.000-07:00I haven't thought about this in awhile... but I th...I haven't thought about this in awhile... but I think KN Log K is right. In the min-heap, you don't need to have every element, just the first element off of every array... which is K items. So, the size of the minheap is only K items.Adamhttps://www.blogger.com/profile/01798780122426727307noreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1154841501110457692006-08-05T22:18:00.000-07:002006-08-05T22:18:00.000-07:00isn't the complexity for your minheap algorithm O ...isn't the complexity for your minheap algorithm O (KN Log KN) since each insertion to the binary heap worst case is O (log KN)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1098671683160395802004-10-24T19:34:00.000-07:002004-10-24T19:34:00.000-07:00Thanks Ron!
I'll keep this up-to-date with any inf...Thanks Ron!<br />I'll keep this up-to-date with any info. Good luck with your interviews.<br /><br />At least you got an interview with Amazon, they never got back to me. Bastards.<br /><br />I hope you're having fun at school.Adamhttps://www.blogger.com/profile/01798780122426727307noreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1098671424609578032004-10-24T19:30:00.000-07:002004-10-24T19:30:00.000-07:00hrm... stupid IE, and double postinghrm... stupid IE, and double postingAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1098671267120183142004-10-24T19:27:00.000-07:002004-10-24T19:27:00.000-07:00This comment has been removed by a blog administrator.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6957414.post-1098671214364322802004-10-24T19:26:00.000-07:002004-10-24T19:26:00.000-07:00I blew my Amazon.com technical interview, I spent ...I blew my Amazon.com technical interview, I spent about 30 minutes in trying to explain what a hash table was, unfortunally I didn't get to the second lines of interviews. And for Bain, I should've done better on preparing for case study interviews.<br /><br />So the run down<br />Me vs. Companys<br />0 v 1 Harris<br />0 v 1 Bain<br />0 v 1 Amazon<br />0 v 1 Bank of America<br />? v ? Computer Science Corporation<br /><br />Well good luck with Google and Deloitte<br /><br />-RonAnonymousnoreply@blogger.com