## iLabs Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

This should work..

``````public int maxSum(int[] A , int currIndex , int sum){

if(index == A.length){
return 0;
}
return  sum+max(maxSum(A,i+1,sum),A[currIndex]+max(A,i+2,sum));
}``````

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

it seems, some variable not defined:
from where I get 'index','i' and 'max' method

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

same as question?id=14809839

follow up question: output the numbers which constitutes the max sum

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

The idea is right, although the code will not run as written. I like the solution because it is so simple. Here are a few small corrections:

public static void main(String[] args)
{
// TODO code application logic here
int[] array = {-10, -3, -2, -9, -1, -8};

int startIndex = 0;
int startSum = 0;
int maxSum = maxSum(array, startIndex, startSum);
if(maxSum == 0)
{
maxSum = maxElementInArray(array);
}

System.out.println(maxSum);

}

public static int maxElementInArray(int[] A)
{
int max = Integer.MIN_VALUE;
for (int index = 0; index < A.length; index++)
{
if (A[index] > max)
{
max = A[index];
}
}
return max;
}

public static int max(int a, int b)
{
if (a > b)
{
return a;
}
else return b;
}

public static int maxSum(int[] A , int currIndex , int sum)
{

if(currIndex >= A.length)
{
return 0;
}

return sum+max(maxSum(A,currIndex+1,sum),A[currIndex]+maxSum(A,currIndex+2,sum));

}

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

Can you explain "max sum". An example would help.

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

Considering 'max sum' means subarray with maximum sum and also that this subarray is composed of alternate numbers(since two numbers should not be adjacent to each other) here is the solution I have in mind.
Split the array into two.
First array has all elements at even index, 2nd array has elements in odd index.
Then apply largest contiguous subarray sum method to both.
Return the higher one as the result

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

Futher Memoise to decrease complexity

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

I think that the non-adjacent numbers condition is trickier than

{10, 1, 2, 9, 3, 8}

Correct solution: {10, 9, 8}
Your method: {1, 9, 8}

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

Keep two variables to store the 'max till the boundary' and 'max before the boundary'. Iterate over the elements of the array one by one and keep updating the variables. This is similar to the O(n) maximum subarray problem.

``````static int getMaxSubSeqNonAdjacent(int[] array) {
int sumTillBoundary   = array;
int sumBeforeBoundary = array;

for (int i = 2; i < array.length; i++){
int sumBeforeBoundary2 = sumBeforeBoundary;

sumBeforeBoundary = Math.max(sumTillBoundary, sumBeforeBoundary);
sumTillBoundary   = Math.max(sumBeforeBoundary2 + array[i], array[i]);
}

return Math.max(sumTillBoundary, sumBeforeBoundary);
}``````

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

This is dynamic programming question
Let S[j] be the max sum till index j
Base case, S = A, S = A
S[j] = max (S[j-i] + S[i], S[j]), where i goes from [0, j-2], since it cant be adjacent elements.

The answer would be at S[n].

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

This is dynamic programming question
Let S[j] be the max sum till index j
Base case, S = A, S = A
S[j] = max (S[j-i] + S[i], S[j]), where i goes from [0, j-2], since it cant be adjacent elements.

The answer would be at S[n].

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

This is dynamic programming question
Let S[j] be the max sum till index j
Base case, S = A, S = A
S[j] = max (S[j-i] + S[i], S[j]), where i goes from [0, j-2], since it cant be adjacent elements.

The answer would be at S[n].

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

``````int main()
{int maxsum=0;

for(int j=1;j<=n;j++)
{
for(int k=0;k<=(n-j);k++)
{
for (int i=k; i<=j; i++)
sum=sum + a[i];
if (sum>maxsum)
maxsum=sum;
}
}
}``````

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

C++11:

``````// TASK: write a insert method for singly linked list, so that it will insert elements in the ascending order.

template <typename T>
class Node {
public:
using Type = T;

template <typename... Args>
Node(Args&&... args) : value_(args...) {}

void setNext(Node *next) {
this->next_ = next;
}

const Node * next() const {
return next_;
}

Node * next() {
return next_;
}

void setValue(const Type &value) {
this->value_ = value;
}

const Type & value() const {
return value_;
}

Type & value() {
return value_;
}

private:

enum class ConstructorType { Clone };

Node(const Node &other, ConstructorType) {
this->next_ = other.next_;
this->value_ = other.value_;
}

public:

Node * clone() const {
return new Node(*this, ConstructorType::Clone);
}

private:

Node *next_ = nullptr;
Type value_;
};

template <typename T>
class List {
public:

using Type = T;
using Node = ::Node<T>;

const Node * operator [](unsigned long index) const {
Node *ptr = first_;
while (ptr->next() && index > 0) {
ptr = ptr->next();
index--;
}
return ptr;
}

List & operator <<(Node node) {
//    return this->operator <<(node);
//}
//
//List & operator <<(Node &node) {
if (!first_) {
first_ = node.clone();
} else {
Node *ptr = first_;

while (ptr->next() && ptr->next()->value() < node.value()) {
ptr = ptr->next();
}

if (ptr != first_) {
ptr->setNext(node.clone());
ptr->next()->setNext(ptr);
} else {
ptr = node.clone();
ptr->setNext(first_);
first_ = ptr;
}

return *this;
}
}

Node * first() {
return this->first_;
}

private:

Node *first_ = nullptr;
};

#include <assert.h>

int main() {
// TEST: basic usage of list
{
List<int> list;
list << 3 << 2 << 1;
Node<int> *ptr = list.first();
assert(ptr->value() == 1);
ptr = ptr->next();
assert(ptr->value() == 2);
ptr = ptr->next();
assert(ptr->value() == 3);
assert(ptr->next() == nullptr);
}

// TEST: operator []
{
List<int> list;
list << 3 << 2 << 1;
assert(list->value() == 1);
assert(list->value() == 2);
assert(list->value() == 3);
}
}``````

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

/crackprogramming.blogspot.com/2012/10/find-largest-contiguous-sub-array-sum.html

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.