Questions in Adobe Tests n Interviews – Part 7

Here are few more questions for developer position. And this time with some answers and hints

——————————————————————–

You are given an array of n+2 elements..
All elements of the array occur once between 1 and n except two numbers which occur twice..
Find the two repeating numbers in O(n)

(eg) say for n = 5

array = 4 2 4 5 2 3 1

The above array has n+2=7 elements with all elements occuring once except 2 and 4 which occurs twice.. Find those repeating numbers in O(n) time and constant space.

The output should be 4 2.

I will start traversing array (n+2 size) (say Arr) from left.
So at any point I have an index of array & value(= Arr[index]) at that position. Now following are the cases

Compare value & index.
a) Value = index . ( do nothing , go ahead to next element of Arr)
b) Value > index . This case do as :
tmp = Arr[Value];
Arr[Value] = Value;
Arr[index] = tmp;
Now again start from comparing value & index, dont update the index.
c) index > value.
Then this value is being repeated. This is our one repeated no. As there can be more ( 2 in this question ) Lets store this at the end of the array.
tmp = Arr[index];
Arr[index] = Arr[n+2];
Arr[n+2] = tmp;
Again dont change index here & go back to compare the index & value. This way we will get all repeated numbers stored in the end. This algo will work for any such question with n+k size array (where k is no. of repeated numbers).

Here in my above explanation indexing for Arr starts from 1. ( So I assume my first elem of array is Arr[1] )

finding height of a binary tree
2) Displayin the fibonacci series (with recursion)
3) Flippin the 20th bit of a number
4) Flippin all the Odd bits of a number
5) ATOI() function
6) prdict the output of the following program :
***** some program (mainly recursion)
7)program to find if mc is little endian or big endian.
8)program to generate the mirror of the binary tree
8) program to swap two linked list nodes.
9) calculate the complexity of prg

search a string from bigger string,

write  a algorithm to compute X^n which is of complextity log n,

implement atoi function.

Wap to reverse a linked list and sort the same.

2) Given two integers A & B. Determine how many bits required to convert
A to B. Write a function int BitSwapReqd(int A, int B);

3) Write an algorithm to insert a node into sorted linked list.After inserting,
the list must be sorted.

4) Without using /,% and * operators. write a function to divide a number by 3.
itoa() function is available.

5) Wap to swap two integer pointers.

6)Write a funcn int round(float x) to round off a floating point num to int.

7) write an ALP to find sum of First n natural numbers using the following Instructions

LDA num ; load Accumulator with num
DCR R ; decrement Register R
INR R ; increment Register R
MOV x,y ; move the contents of register y into register x
JZ label ; jump to label if A=0
DJNZ label; Decrement & Jump if A <> 0
you can use B & C registers in addition to A register

8) Find the n th node in a Singly Linked list starting from the End in a Single Pass.

9)prove that a tree is BST.what is height of a tree?

10) Given A,B & C Boolean polynomials.Prove That (A+BC)=(A+B)(A+C)

1. given a tree generate its mirror image tree

2. print a number in hexademical notation without using sprintf

3.given a tree n a sum , calculate if there is a path from the root to a leaf with the sum of values at the node equal to the given sum .

-height of a tree,
-finding second largest number in an array
-questions using finite automata
– write a pgm to find whether a m/c is little endian or big endian
– lots on bit-wise manipulation

– print a number in hexadecimal format without using sprintf
– optimise the computations in the recursive “nth fibonacci number” algo without using iteration(fairly simple)
“Instead of using return(fib(n-2)+fib(n-1)), use init lofib=0,hifib=1, start with n=2,lofib=hifib;hifib=fib;fib=lofib+hifib”
-given any number say 12, find the next multiple of 8 eg 16 using bit-wise manipulations.
-exchange the integers in a matrix across the secondary diagonal(or non-major diagonal)

Complexity of binary search. and also write the algorithm to do the same.2) f(a,b) = 0 if ad){ stmt e; } if this loop is run 5000 times, and ad is true 70% of the times, how many times is stmt e executed.1

2) Some question on parallel computing, like if a code takes 100 seconds to execute ona single processor and if 40% of the code is sequential what is the time taken by to execute the code on systems with 2 processors and 4 processors

.In ‘C’ paper.

1) Write 3 examples of preprocessor tags.

2) What is the difference between char a[] = “hello” and char *a = “hello”;

3) how do you make sure a header file is not included twice in a program.

4) what is the output of the following programint a[] = {1,2,3,4);printf(“%d”, 2[a]);

5) implemenatation of atoi();

6) search a sub string in a string and return the index of the last occurence of the string.

7) Implement fibinocci search8) some question on conversion of hexadecimal number to binary

1.

If CURD is 321184 then MILK is –

Ans: 1391211