## Salesforce Interview Question for Software Engineer / Developers

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

Fib(n) denotes the 'n'th element in the fibonacci series
Sum(n) denotes summation of first n elements in the fibonacci series.

Algo :
Always maintain an array of (k+1) summations.

If you are calculating Fib(n+1) the array should have Sum(n-k),Sum(n-k+1) ... Sum(n-1),Sum(n)
Now Fib(n+1) = Sum(n) - Sum(n-k)

Now update the summations array so that it contains Sum(n-k+1),Sum(n-k+2) ... Sum(n),Sum(n+1)
Sum(n+1) = Sum(n) + Fib(n+1)
Now Fib(n+2) = Sum(n+1) - Sum(n-k+1)

Again update the summations array and continue with same thing

Example : Let k=3. Fib(1)=1, Fib(2)=2, Fib(3)=3
Fibonacci series : 1,2,3,6,11,20,37,68 ...

Summations array [1,3,6, dont have the 4th summation yet]

Fib(4) = 6
Summations array [1,3,6,12]

Fib(5) = Sum(4) - Sum(1) = 12 - 1 = 11
Summations array [3,6,12, 12+11 ] = [3,6,12,23]

Fib(6) = Sum(5) - Sum(2) = 23 - 3 = 20
Summations array [6,12,23, 23+20 ] = [6,12,23,43]

Fib(7) = Sum(6) - Sum(3) = 43 - 6 = 37
Summations array [12,23,43, 43+37 ] = [12,23,43,80]

Fib(8) = Sum(7) - Sum(4) = 80 - 12 = 68
Summations array [23,43,80, 80+68] = [23,43,80,148]
... So on ...

This runs in O(n) time and takes O(k) space.

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

Nice Solution :)

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

I guess you did not understand T's solution.

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

I did not. Did you? If so, please explain why it works. It would be helpful.

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

We need to know what the intial k values are, i.e. it should be part of the input.

Call the list of initial values the vector f = [f(k) f(k-1) ... f(1)]

Let A be the k by k matrix

A = [ 1 1 ... 1] [1 0 0 ..0] [0 1 ...0] [0 0 1 ...0] ... [0 .... 1 0]

Calculate A^n * f . One of the entries (I will let you figure out which one) is Fib(n,k)

This has O(k^3 log(n)) running time.

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

why do we need vector and matrix? fib(n,k) is just a series which extends 2 to k, right?

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

Fib(n,k) is a particular term in an infinite sequence. What do you mean extends 2 to k?

Also, the matrix is used to give a very efficient algorithm, using only integer multiplication/addition.

The normal iterative methods will be O(kn) i suppose. That matrix if O(logn * M(k)) where M(k) is the complexity of multiplying two k by k matrices. The trivial algo for multiplication is O(k^3), but better ones exist.

Another aspect of using matrices is that it can be parallelized very easily. Try doing that with the iterative version.

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

That's a nice technique. It's called memoization. http://en.wikipedia.org/wiki/Memoization
We can re-use the space for keeping track of k terms. Hence, o(k) space.
The running time however is O(nk) and not O(n) since we have to traverse k locations in the array to find the current sum.

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

how is the running time = O(nk) ? we have to traverse k locations but we keep moving forward to cover the n spaces. Also k is a constant compared to n. So imo this is O(n)

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

Can a recursive algo work here:

fib(int n, int k)
{
for(i=0; i<k; i++)
{
if(n==i) return i;
}
if(n>k)
{
for(j=0; j<k; j++)
{
ans += fib(n-1, k);
}
return ans;
}
}

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

Can you share your programming exam experience in Sales Force?

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

int fib_n_k(int n, int k)
{

if (n<k) {
return n;
}
else {
int sum=0;
for (int i=1; i<=k; i++) {
sum+=fib_n_k(n-i,k);
}
return sum;
}

}

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

//Alternate implementation

void fib(int n, const int type)
{
vector<int> track;

// Insert first K number of series in vector
for(register int i =0 ;i < type ;i++)
track.push_back(i);

// check if N is less then type
int t = n>=type?type:n;
for(register int i =0 ;i<t;i++)
cout<< track[i] <<" ";

//Start series
for(register int i=2;i< n;i++)
{
int newNum =0;

for(register int j = 0 ;j <type;j++)
newNum += track[j];

cout<< newNum <<" ";

track.erase(track.begin()); //remove the first number so that all number shift by 1 postion
track.push_back(newNum); // insert a new fib number
}

}

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

<pre lang="" line="1" title="CodeMonkey54649" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
String s;
}
}

</pre><pre title="CodeMonkey54649" input="yes">
</pre>

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

<pre lang="" line="1" title="CodeMonkey98982" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
String s;
}
}

</pre><pre title="CodeMonkey98982" input="yes">
</pre>

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

``````public class ModifiedFibonacci{
public static void main(String[] args) {
int n = 10;
int k = 3;
int [] array = new int[n];
fibonacci(n-1,k,array);
System.out.println("dss");
for(int i = 0;i<array.length;i++){
System.out.println(array[i]);
}
}

private static int fibonacci(int n, int k,int[] array){
if(n <= 0)
return 0;
if(n == 1){
array[1] = 1;
return 1;
}
/*if(n == 2)
return 1;

*/
if(array[n]>0){
return array[n];
}
int sum =0;
for(int i =k;i>=1;i--){
sum += fibonacci(n-i, k, array);//+ fibonacci(n-1, k, array);// +fibonacci(n-3, k, array);
}
array[n]= sum;
return array[n];``````

}}

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

``````function fib(n, k){
var sum = 0;
if (n<k) {
return n;
} else {
for (var i=1; i<=k; i++) {
sum += fib(n-i,k);
}
}
return sum;
}
fib(6, 3); // 20``````

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

``````def fib(n, k):
# assume it is all initialized to 0
last_k = [1] * k

for i in xrange(k, n+1):
last_k[i%k] = sum(last_k)

return last_k[n%k]

# test cases
for i in xrange(0, 10):
print 'fib(%d, 3): %d' % (i, fib(i, 3))

for i in xrange(0, 10):
print 'fib(%d, 4): %d' % (i, fib(i, 4))``````

Comment hidden because of low score. Click to expand.

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.