## Adobe Interview Question for Field Saless

• 1
of 1 vote

Team: hr
Country: India

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

Simple approach by use % and / operator with size of array.
e.g {2, 4, 3, 1, 0}
1. new value of A[0]= A[2] ,
so newValue= A[2]%size; (old value of A[2])
A[0]= A[0]+newValue*size; by doing this step, we have old value of A[0]=A[0]%size , new Value of A[0] = A[0]/size;
do this for every element
2. When first loop complete and every element has updated value(both old and new value) then run another loop and do A[i]=A[i]/size;
then every index of array has new value.

code based on above aproach

int size=A.length;
int newValue=0
for(int i=0;i<size;i++){
newValue=A[A[i]]%size;
A[i]=A[i]+newValue*size;
}
for(int i=0;i<size-1;i++)
A[i]/=size;

Time complexity is O(n) and auxillery space complexity is O(1)

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

great!

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

``````// Program to assignments based on the index value of a given array
//  A[0...n-1] with elements [0,n-1] shuffle across array
// for example  Input : A[5] = { 2,4,3,1,0}
//   Output : A[5] = { 3,0,1,4,2}
// Solution 1 : Another array B[A[i]] = A[i]
// Solution 2 : In case of inplace

int[] Modify(int input[], int n){

// Boundary conditions
if(input == null || n<=0) return null;

// Declaration
int pIndex=0 , qIndex=0,counter = 0;

// Initialization
do{
pIndex= qIndex;
qIndex= input[pIndex];
//Swap(input,pIndex,qIndex);
input[pIndex] =    input[pIndex] +    input[qIndex] ;
input[qIndex] =    input[pIndex] -    input[qIndex] ;
input[pIndex] =    input[pIndex] -    input[qIndex] ;

}while(++counter != n);

// Returning function
return input;
}``````

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

really, the solution doesn't work.
On the input array {2, 1, 3, 5, 4, 0} it returns {0, 1, 3, 5, 4, 0}, but the correct output is { 3,1, 5, 0, 4, 2 }.

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

Nice try ..but the code is wrong .

At second time the loop gives p=q=2.
So it will keep on swapping the value p[2] with p[2] itself which is useless.

example:=

input array={2,4,1,3,0}

at first iteraqtion it will give = {1,4,2,3,0}

now what????????

p[2] with p[2]??

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

sorry for imconvinience... my question is following:

suppose we have an array having 0 to n-1 distinct integers example {2,1,4,3,5,0} our goal is to modify this array such that a[0] becomes a[a[0]] means a[ 0] has value 2 here so a[0] = a[2] and so on . having the following output
{4,1,5,3,0,2}. 3 things are to be noted here that a) positions have range 0 to n-1 and values have range 0 to n-1 too (obviously). b)no extra array or link list or any data structure should be taken .c) should hav time complexity O(n).

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

could you please write the task normally, it is impossible to understand it.

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

sorry for imconvinience... my question is following:

suppose we have an array having 0 to n-1 distinct integers example {2,1,4,3,5,0} our goal is to modify this array such that a[0] becomes a[a[0]] means a[ 0] has value 2 here so a[0] = a[2] and so on . having the following output
{4,1,5,3,0,2}. 3 things are to be noted here that a) positions have range 0 to n-1 and values have range 0 to n-1 too (obviously). b)no extra array or link list or any data structure should be taken .c) should hav time complexity O(n).

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

sure ...i will give an example suppose we have an array (2,1,3,5,4,0)(having n distinct integers starting from 0 to n-1). we have to modify it such that..

a[0] becomes a[a[0]] means a[0] having value 2 here so a[0] will become a[2] that is 3 here and rest all in the same way. so output should be following

3,1,5,0,4,2. got it?? here we have 0 to n-1 integers and 0 to n-1 positions as well.

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

sorry for imconvinience... my question is following:

suppose we have an array having 0 to n-1 distinct integers example {2,1,4,3,5,0} our goal is to modify this array such that a[0] becomes a[a[0]] means a[ 0] has value 2 here so a[0] = a[2] and so on . having the following output
{4,1,5,3,0,2}. 3 things are to be noted here that a) positions have range 0 to n-1 and values have range 0 to n-1 too (obviously). b)no extra array or link list or any data structure should be taken .c) should hav time complexity O(n).

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

Sorry for the inconvenience . My question is following :
Suppose we have an array of length n. The array has distinct values from 0,1,2....n-1 in any order(sorted or unsorted). for example lets take the array as {2,1,3,5,4,0}.

we have to modify it such that a[i]=a[a[i]] which means a[0] becomes a[a[0]] and so on..in the following example the output should be:-

a[0] = 2 so a[0]=a[2]=3
a[1] = 1 so a[1]=a[1] = 1
a[2] = 3 so a[2] = a[3] = 5
.
.
and so on.
we will get the following output:
{3,1,5,0,4,2}. got it?

3 things are to be noted here
a) values of elements lies in the set {0 to n-1} and positions are also 0 to n-1 obviously.
b) Time complexity = O(n)
c) No extra array or any DS should be used .

Solve it if you can .

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

the idea is the following:
at each iteration we dynamically increase the size of the array and write new values a[ a[ i ] ] to the end of that array.
After the cycle we just move the array head pointer to the middle of the array.
O(n).
But I suspect you will say, that it is not permitted to dynamically increase the size of the array, though there is no such prohibition in the initial task.

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

below I provide the solution without dynamical modifications of the initial array's size.

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

ok, here is the solution you wanted.
c# implementation.
All restrictions are observed. No additional data structures, no dynamical modifications of the initial array's size.
Time complexity O(n).

``````using System;

namespace ArrayTrick {

class Program {

static void Main(string[] args) {

var arr = new[] { 2, 1, 3, 5, 4, 0 }; // output should be { 3, 1, 5, 0, 4, 2 }

Process( arr );

for ( int i = 0; i < arr.Length; i++ ) {
Console.Write(\$"{arr[i]} ");
}

}

private static void Process( int[] arr, int i = 0 ) {
int index = i;
if (i < arr.Length ) {
var val = arr[ arr[ i ] ];
i++;
Process( arr, i );
arr[ index ] = val;
}
}
}
}``````

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

Hey..

1 st the time complexity is n^2. as the loop will run n*n times in ur program.

second the output will not be correct .

here is the simple iteration when i analyse ur program:-

{213540}
1st iteration = {3,1,3,5,4,0} here the value 2 is lost which should be at a[5] in the output .

So a wrong program and wrong logic

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

Let's think.
How can it be n^2 ? And why will loop run n*n times ?
This program contains only 1 loop. As you know, 1 loop performs exactly N iterations, where N is the number of items in collection. So, the time complexity of 1 loop is O(n).
N*N times is true for nested loops, when 1 loop is outer one and the 2nd loop is inner one. Where do you see nested loops in the program? Nothing of that kind.
It is very easy to check the number of times of loop execution.
Do you see the incrementor there (i++), so if time complexity is O(n^2), then the value of "i" will be exactly n*n at the last iteration. In my program its value at the last iteration is exactly 6, which is N in my case (but not 36, which is N*N).
So, the time complexity is O(n).
This is absolutely definitely.

Second.
You write here the result of first 1st iteration = {3,1,3,5,4,0}.
This is not true.
Here is the full list of iterations' results:
1 - {2,1,3,5,4,2}
2 - {2,1,3,5,4,2}
3 - {2,1,3,0,4,2}
4 - {2,1,5,0,4,2}
5 - {2,1,5,0,4,2}
6 - {3,1,5,0,4,2}

So, you tested some other program, but not mine.

Then, what is it - "The result is incorrect after the 1st iteration" ??
This is bullshit.
Because the result of the algorithm must be verified only after the whole algorithm is finished. These are basics of computer science.

So: I observed all your restrictions, and created the solution with time complexity O(n). Your task is to wait until the algorithm finishes its work and gives you the output, then you can check the output with predefined correct value.
For input array { 2,1,3,5,4,0 } my solution gives output array {3,1,5,0,4,2}.
And it is absolutely correct.

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

your order space is O(n).You store data in val variable. It runs O(n) times. So space complexity is O(n). Can we do in O(n) time and O(1) space?

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

I don't see such possibility, if you have ideas, share them here.

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

hmmm my mistake . but here you are using a recursive function that means extra stack space in memory. moreover can u give the algo for what u wrote

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

yes, that is true, the program uses extra stack space in memory, but there are no restrictions in the initial task about this issue.
And I didn't understand: "moreover can u give the algo for what u wrote".

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

nothing you are right . I think this is the perfect solution thanks a lot.

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

thanks for the discussion!

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

hey if u can solve without recursion

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

Here is the complete program O(n), (1)
#include<iostream>
using namespace std;
int main()
{
int a[]={2,1,3,5,4,0};
//OutPut: {3,1,5,0,4,2}
int n=6;
int index=0;
for(int i=0;i<n;i++)
{
index=a[a[i]]%n;
a[i]=a[i]+n*index;
//cout<<a[i]<<" ";
//index=i;
//call(a,i,n,b)
}
for(int i=0;i<n;i++)
{
a[i]=a[i]/n;
cout<<a[i]<<" ";

}

return 0;
}

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

``````#include<iostream>
using namespace std;
int main()
{
int a[]={2,1,3,5,4,0};
//OutPut: {3,1,5,0,4,2}
int n=6;
int index=0;
for(int i=0;i<n;i++)
{
index=a[a[i]]%n;
a[i]=a[i]+n*index;
//cout<<a[i]<<" ";
//index=i;
//call(a,i,n,b)
}
for(int i=0;i<n;i++)
{
a[i]=a[i]/n;
cout<<a[i]<<" ";

}

return 0;
}``````

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

``````#include<iostream>
using namespace std;
int main()
{
int a[]={2,1,3,5,4,0};
//OutPut: {3,1,5,0,4,2}
int n=6;
int index=0;
for(int i=0;i<n;i++)
{
index=a[a[i]]%n;
a[i]=a[i]+n*index;
//cout<<a[i]<<" ";
//index=i;
//call(a,i,n,b)
}
for(int i=0;i<n;i++)
{
a[i]=a[i]/n;
cout<<a[i]<<" ";

}

return 0;``````

}

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

int a[]={2,1,3,5,4,0};
//OutPut: {3,1,5,0,4,2}
int n=6;
int index=0;
for(int i=0;i<n;i++)
{
index=a[a[i]]%n;
a[i]=a[i]+n*index;
//cout<<a[i]<<" ";
//index=i;
//call(a,i,n,b)
}
for(int i=0;i<n;i++)
{
a[i]=a[i]/n;
cout<<a[i]<<" ";

}

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

``````int a[]={2,1,3,5,4,0};
//OutPut: {3,1,5,0,4,2}
int n=6;
int index=0;
for(int i=0;i<n;i++){
index=a[a[i]]%n;
a[i]=a[i]+n*index;
}
for(int i=0;i<n;i++)
{
a[i]=a[i]/n;
cout<<a[i]<<" ";}``````

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

public static void main(String args[]) {
System.out.println("Ques2");

int A[] = {2, 1, 3, 5, 4, 0};

System.out.println(Arrays.toString(A));

recursive(0, A, 0);

System.out.println(Arrays.toString(A));
}

static void recursive(int len, int A[], int currIndex) {

if(len == A.length) {
return;
}

int save = A[A[currIndex]];
recursive(len+1, A, A[currIndex]);

A[currIndex] = save;

}

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

I think we are dealing with only time complexity here not space. Following would do it in O(n) time
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
//declare/define all the required local variables first
int a[] = {2,1,3,5,4,0}, i = 0, n = 0, *out = NULL, err = 0;

//find out he size of orginal
n = sizeof(a)/sizeof(int);

//allocate the memory for temp array
out = (int *)calloc(n, sizeof(int));
if(out == NULL)
{
err = -1;
printf("ERROR: Internal error.\n");
goto exit;
}

//clone the array in temp array
for(i=0; i<n; i++)
{
out[i] = a[i];
}
//solution
for(i=0; i<n; i++)
{
if(a[i] > n)
{
err = -1;
printf("ERROR: Array contains invalid value\n");
goto exit;
}
a[i] = out[a[i]];
}

//display the output
printf("\nOUTPUT:");
for(i=0; i<n; i++)
{
printf(" %d", a[i]);
}

exit:
if(out)
{
free(out);
out = NULL;
}
return err;
}

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.