## King@Work

BAN USER- 8of 8 votes

AnswersYou are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.

- King@Work

Fastest way to find that single integer

-- using memory.

-- not using any external memory.

eg: [2,1,4,5,1,4,2,2,4,1]| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm

I really doubt that you can determine the size of the stack.

1. you really dont know how many elements it contains? (if you know the data type).

2. The way stack is implemented is they can grow as much as they want limited by your RAM size or may be the virtual environment in which your program is running like JVM or CLR. Thats why so many times we get stakoverflow error.

Can be done using array.

1. Determine the maximum degree out of the provided polynomials.

2. Make the array/arraylist of that size.

3. a[0] represents the constant and a[2] represents the x^2 coefficient.

4. Add the same index values of both arrays in the third array.

Complexity: O(n)+O(m)

Correct me if I am wrong in the complexity.. Just started DAA,, so still learning.

Nice solution. We can transform the arrays in 2D array say... {5,3,1} will become {[5,A][3,A][1,A]}.

We can sort them using 0th index and then find the duplicates or near to duplicates.

So the complexity will become O(n log n)+O(n)

O(n) to find the numbers giving minimum value..

What I was thinking is we have a pointer to pPath which is an array and we never delete any element from it. Also the printing is done from 0 to index. So say if we consider right sub tree it should give correct results but when it comes to the left sub tree what will happen?

Try to help me that where I am going wrong.

Rep**charlesndouglass**, Employee at VANSI am Michael from Nantucket USA. I am working as a Power plant dispatcher in Matrix Design company. I am ...

Rep**sylviarashtons**, Accountant at ASAPInfosystemsPvtLtdI am a journalist. Outside the office, I enjoy additional writing time in a different genre of historical fiction. I ...

Rep**susanaminick**, Research Scientist at CapitalIQI am Susan from Dallas, I am working as a Property manager in Kohl's Food Stores company. I love ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Bit Vector

- King@Work February 02, 2012hash Map

Bit vector can save space as we already know the range. 1 means the number is there and 0 means it is not there. inserting a number ans checking a num is O(1).

also searching is O(1)