## 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

Comment hidden because of low score. Click to expand.
0

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)

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().

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

Any idea on logic for generating the power sequence ??

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

# 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]]``````

Comment hidden because of low score. Click to expand.
0

What's the running time?

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 () {
}

public void reset() {
elems.clear();
preSet.clear();
}

@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);
if (ip.b == 2) {
ip.b = 3;
} 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>

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;
}``````

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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.

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.

### 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.