## eng.ahmed.moustafa

BAN USER- 0of 0 votes

AnswersWrite a program that reverses a linked list without using more than O(1) storage.

- eng.ahmed.moustafa in United States| Report Duplicate | Flag | PURGE

Facebook - 1of 1 vote

AnswersWrite a program that answers YES/NO search queries containing * placeholders. Example: if the data you have is (hazem, ahmed, moustafa, fizo), then you should answer as follows for:

- eng.ahmed.moustafa in United States

ahmed: YES

m**stafa: YES

fizoo: NO

fizd: NO

*****: YES

****: YES

**: NO

Your program should be able to answer each search query in O(1).| Report Duplicate | Flag | PURGE

Facebook - 2of 2 votes

AnswersConsider the 52 cards of a deck. You generated a random sequence for these cards and want to send that sequence to a receiver. You want to minimize the communication between you and the receiver, i.e., minimize the number of bits required to send the sequence.

- eng.ahmed.moustafa in United States

What is the minimum number of bits required to send the sequence?

Hint: It is not 6 x 52| Report Duplicate | Flag | PURGE

Google Software Engineer Arrays

Equivalent to getting the longest common subsequence.

- eng.ahmed.moustafa March 02, 2015Yes, I agree.

So, one way to go is to go ahead and verify the length by doing binary search for the number below and number above.

So, the solution is valid, but O(log n).

Look at 9 positions:

1, n/8, n/4, 3n/8, n/2, 5n/8, 3n/4, 7n/8, n

If a number is repeated n/4 or more, two consecutive elements (from above) will have its value.

Answer is the value common between any two consecutive elements.

That's O(1).

Not correct. Your code will return NO for a*hm*d, or m*o*s*t*fa although it should return YES.

- eng.ahmed.moustafa February 25, 2015Nice way of thinking. I agree that this is the theoretical limit. But practically, how can you decode the 226 bits in order to determine the sequence?

- eng.ahmed.moustafa February 24, 2015The solution is to look at the sequence from the end to start.

For the last card, the receiver does not need any bits because he can already determine what the remaining card is given the 51 received card. Thus, this last card needs 0 bits.

Similarly, for the one before last card, the receiver needs 1 bit because there are two remaining possibilities.

Following this paradigm

Thus, the number of bits is

0 + 1x1 + 2x2 + 3x4 + 4x8 + 5x16 + 6x20 = 249 bits

The stack solution is essential only if you have parentheses and more complex operators.

I think you should take advantage of being limited to + and *. I believe it can be done in a sequential scan of the string without the need for a stack.

Your code assumes that there is no more than one consecutive multiplication.

Trace it for:

2 * 3 * 4 * 5 * 6 + 7 + 8 + 9

I think you get the idea. But the question was intended without writing code.

- eng.ahmed.moustafa February 23, 2015

RepSpent 2001-2008 licensing methane in Jacksonville, FL. Uniquely-equipped for working on swimming pool builders Katy TX. Spent 2002-2009 licensing junk ...

Rep**allisonepollard**, Applications Developer at AccentureI am Allison from Germantown. I work as a Staff manager at The LawnGuru company. But my interest in blogging ...

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

Open Chat in New Window

What if the elements are not distinct?

- eng.ahmed.moustafa March 23, 2015