## Flipkart Interview Question for Software Engineer / Developers

• 0

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

0(1) space and o(n) time

for(i = 1 to n){

t = a[i] > 0) ? a[i] : a[i]*-1;
if( a[t] > 0 )
a[t] = a[t]*-1;

}

Traverse once again and print indices whose value is positive.

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

you have to find missing numbers and not only the duplicates

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

btw What your code is doing can you explain

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

@Aditya: His logic is correct and as he wrote:
"Traverse once again and print indices whose value is positive."
this will print all missing numbers in the array.

Here is the logic:
Scan through the array. Every time you encounter a number(call it N), make the number at index N negative(if it is not negative). Thus when whole array has been traversed, only indexes corresponding to missing numbers will be positive, which can be printed in another scan.
The basic trick is that all numbers are positive and by making numbers negative we are keeping track of all numbers visited. If negative numbers were allowed, the above trick wouldn't have worked.

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

@Aditya: His logic is correct and as he wrote:
"Traverse once again and print indices whose value is positive."
this will print all missing numbers in the array.

Here is the logic:
Scan through the array. Every time you encounter a number(call it N), make the number at index N negative(if it is not negative). Thus when whole array has been traversed, only indexes corresponding to missing numbers will be positive, which can be printed in another scan.
The basic trick is that all numbers are positive and by making numbers negative we are keeping track of all numbers visited. If negative numbers were allowed, the above trick wouldn't have worked.

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

if a number is repeated three times.. or odd number of times... then also this logic will fail..

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

use a bit vector and set the corresponding bit as you scan the numbers, and once we are done with the input, scan through the bit vector and print the integers, whose corresponding bits are not set ..

O(n) time ..

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

problems with aravinds86 code.

1) First it does not detect duplicate.
2) it is not O(1) in space as the file has to be read in array. Also the array can be much much bigger than n in case the number of numbers not very large though in the range from 1 to 1M.
3) The ideal solution would be O(n) in space and O(n) time. In case the nubmer of numbers is very less compared to 1M we shall use HashMap, otherwise we can use an array of size 1M.

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

better still we can use an array of size 1Million/32 if we use bitwise operations.

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

create a hashmap for numbers from 1 to million.print the keys whose value is 0.

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.