CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Interview Question


Country: India
Interview Type: Written Test



Comment hidden because of low score. Click to expand.
1
of 1 vote

A single element can be placed to its final location in log(n) time.

- Expressions April 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain the underlying logic?

- mahesh_ostwal@yahoo.in April 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We get nlogn to place n elements into their correct positions. So, in logn time, we place 1 element into its correct position.

- alex April 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This makes zero sense. Its not a straight division...

- Lite April 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

x elements can be sorted in O(x log x) time.
So, 1,000,000 elements can be sorted in O(1) time.
We want x such that x log x = log n.
So x = n / W(n) where W is the product log.
Input to WolframAlpha.com : inverse n log n

- Anonymous April 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The answer is zero.
Just to find the smallest element of N elements takes O(N) time.
So there is no way to even find the smallest element out of N elements would take more than O(log N) time.

- gen-y-s April 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

single element thats right

- Sandy April 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

xlogx = logx
x = 1

- DashDash April 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

x elements take theta(xlogx) time so in theta(logn) time heap sort sorts x^x elements

- Anonymous April 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

using heap sort to get the fist k elements out of N elements, it takes O(N)+O(k log N) time. The question clearly states there are N elements, so to sort the first k elements out of the N elements it would take O(N)+O(k log N) time using heapsort.

So O(log N) time is not enough even to find the first element of the array in sorted order.

- gen-y-s April 07, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More