Amazon Interview Question
Financial Software DevelopersCountry: United States
no doubt answer is awsme..but u can't ask the students to pairup or something like that...its your work to count...
otherwise i will say that just start the counting from one corner to last....:D
nice solution..the same can actually be replicated by grouping 'n' number of students.
e.g take 4 students as a pair and find the total students%4..Then
total students/4 is used as the next input..
in simple terms n-ary division and find the decimal equiavlents
of the remainder in reverse form
number rows * (number of column - 1) + number of rows in last column - number of empty seats
Is it possible to check the attendance in O(1) ? I guess we need to sequencely count number of P's (for present) in the array .and that can be done in 0(n) .
Ask first row people to count number of students in their respective column.... and sum all columns...
Have each person stand up and find a partner.
If there is a single have him stand alone in the front of the class.
Assign one of the partners in each couple to remember the number 2 and have the other sit down.
Repeat this process and now have the person remember 4, then 8, then 16 and so forth until there is only one person standing.
Add 1 to the total if single person exists, and you have a O(lg(n)) solution.
Ask 1 student to go out of the class, then 2 students go out of the class, then 4 students, then 8 students... its a variation of binary search
Ask the class to stand up and make pairs, if one student is left out write '1' else write 0. tell the left out student to sit down and ask one person in each group to sit down. Repeat the process and append '1' or '0' to your number, until no student is left standing. You will get the binary representation of the number of students in reverse order.
- Luc March 16, 2012Eg: lets say there are 23 students in the class
Students standing 23 11 5 2 1 0
Solution 1 1 1 0 1 0
we have a string 111010, and the binary representation of 23 is 010111.
This is just using divide and conquer O(lg n)