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
RepMiraDavis, Computer Scientist at Accenture
I am School librarian and also teach students the fundamentals of using a library and its resources .I write and ...
Repallisonepollard, Applications Developer at Accenture
I am Allison from Germantown. I work as a Staff manager at The LawnGuru company. But my interest in blogging ...
What if the elements are not distinct?
- eng.ahmed.moustafa March 23, 2015