Linkedin Interview Question for Software Engineer / Developers






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

Given a number n, if at all it can be written as ab (b > 1), then b<log(n)+1. And for every fixed b, checking if there exists an a with ab=n can be done using binary search. The total running time is therefore O((logn)^2) I guess.

from cstheory.stackexchange.com/questions/2077/how-to-check-if-a-number-is-a-perfect-power-in-polynomial-time

- jin May 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

First, we know the starting number is 4
Then, we need to scan numbers between 4 and 16 (4^2) see if any of them is the asking next.

If there is a^b = n (4<m<16), then b <= logn.
for b in logn - o(n)
use binary search to pick a (<logn) so that a^b ==n - o(logn)

o(n* nlogn)

- fydango March 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

This is very similar to Jason's idea, but I didn't preprocess all of the 2^n values.

1) Use a minheap
2) Upon reset (or instantiation), make sure heap is cleared with 4 on the top with {2,2} for m^n as metadata.
3) When next is called, pop the min and add 8 {2,3} and 9 {3,2}
4) Repeat for {m,n+1} when you pop {m,n}. If a {m,2} is popped, then add {m+1,2}
5) For any existing values, push {m,n+2} instead
6) Rinse and repeat for each next().

- nothing special here November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Any idea on logic for generating the power sequence ??

- seeksree May 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from __future__ import generators
from pprint import pprint

def mypower():
    # cache of all presented numbers
    presented = set()
    # list of m and its current n not yet generated
    elist = []
    # first m = 2, n = 2
    elist.append([2, 2])
        
    while True:
        min_idx = -1
        min_v = 0
        for i, e in enumerate(elist):
            m, n = e
            v= m**n
            if min_v == 0 or min_v > v:
                min_v = v
                min_idx = i

        presented.add(min_v)
        # expand elist only if min_idx is the last guy in elist 
        # and we export its m^n in this run 
        if elist[min_idx][1] == 2:
            nextguy = elist[min_idx][0]+1
            # use cache to prevent duplicate
            while nextguy in presented:
                nextguy += 1
            elist.append([nextguy, 2])
            
        elist[min_idx][1] += 1
        pprint (elist)
        #print min_v
        print "="*20
        print min_v
        yield min_v
        
if __name__ == '__main__':
    a = mypower()
    while True :
        a.next()

####### print out

[[2, 3], [3, 2]]
====================
4
[[2, 4], [3, 2]]
====================
8
[[2, 4], [3, 3], [5, 2]]
====================
9
[[2, 5], [3, 3], [5, 2]]
====================
16
[[2, 5], [3, 3], [5, 3], [6, 2]]
====================
25
[[2, 5], [3, 4], [5, 3], [6, 2]]
====================
27
[[2, 6], [3, 4], [5, 3], [6, 2]]
====================
32
[[2, 6], [3, 4], [5, 3], [6, 3], [7, 2]]
====================
36
[[2, 6], [3, 4], [5, 3], [6, 3], [7, 3], [10, 2]]
====================
49
[[2, 7], [3, 4], [5, 3], [6, 3], [7, 3], [10, 2]]
====================
64
[[2, 7], [3, 5], [5, 3], [6, 3], [7, 3], [10, 2]]
====================
81
[[2, 7], [3, 5], [5, 3], [6, 3], [7, 3], [10, 3], [11, 2]]
====================
100
[[2, 7], [3, 5], [5, 3], [6, 3], [7, 3], [10, 3], [11, 3], [12, 2]]
====================
121
[[2, 7], [3, 5], [5, 4], [6, 3], [7, 3], [10, 3], [11, 3], [12, 2]]
====================
125
[[2, 8], [3, 5], [5, 4], [6, 3], [7, 3], [10, 3], [11, 3], [12, 2]]

- redroof June 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What's the running time?

- Stephen December 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey11712" class="run-this">package linkedin;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

public class NextPowers implements Iterator<Long> {
private static class IntPair {
public IntPair(int a, int b) {
this.a = a;
this.b = b;
}
public int a;
public int b;

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[').append(a).append(',').append(b).append(']');

return sb.toString();
}
}
private ArrayList<IntPair> elems = new ArrayList<IntPair>();
private HashSet<Integer> preSet = new HashSet<Integer>();

public NextPowers () {
elems.add(new IntPair(2, 2));
}

public void reset() {
elems.clear();
preSet.clear();
elems.add(new IntPair(2, 2));
}

@Override
public boolean hasNext() {
return true;
}

private long prev = -1;
@Override
public Long next() {
long n = next_();
while (n == prev) {
prev = n;
n = next_();
}
prev = n;
return n;
}
public long next_() {
long min = Long.MAX_VALUE;
int minI = Integer.MAX_VALUE;
for (int i = 0; i < elems.size(); ++i) {
IntPair ip = elems.get(i);
long v = (long)Math.pow(ip.a, ip.b);
if (v < min) {
min = v;
minI = i;
}
}
IntPair ip = elems.get(minI);
preSet.add(ip.a);
if (ip.b == 2) {
ip.b = 3;
elems.add(new IntPair(ip.a + 1, 2));
} else {
ip.b ++;
}

return min;
}

@Override
public void remove() {
// TODO Auto-generated method stub

}

public static void main(String[] args) {
NextPowers np = new NextPowers();
for (int i = 0; i < 20; ++i) {
System.out.println(np.next());
}
}
}
</pre><pre title="CodeMonkey11712" input="yes">
</pre>

- Anonymous August 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private long n = 4;
private int i = 2;
public Long next() {
        long j = n;
        for (j = n; j < n * n; j++) {
            for (int k = i; k < n; k++) {
                int s = (int) (Math.log(j) / Math.log(k));
                if ((Math.log(j) / Math.log(k)) == s) {
                    n = j + 1;
                    return j;
                }
            }
        }
        return n;
    }

- inheritance February 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using a priority queue or min-heap, stores the values of 2^2, 2^3, 2^4, .... 2^32. In each iterator, return the first element in the queue/heap, suppose the element is a^b, push (a+1)^b into the queue/heap. It takes (O(32log32)) to initialize the queue/heap, and each query takes O(log32) steps.

- Jason November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are you saying to preprocess all of the 2 base values? Seems unnecessary, but I could be misunderstanding.

I suspect your algorithm will be adding unnecessary space. When you pop 2^4, you don't need to add 3^4 until 3^3 has been popped. It's just wasted space. This becomes increasingly a problem when you pop something like 2^8 and having 3^4-3^8 in the heap, too.

I believe the only time you need to add (a+1)^b is when you pop a^2.

- nothing special here November 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@nothing spacial here´╝îyou are right. When popping a number (a^b), pushing (a+1)^b, if a==2, pushing 2^(b+1). Be careful of duplicate numbers like 2^4 and 4^2.

- Jason November 04, 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