Blog Lang thang

Posts

Showing posts with the label interview

Generating a random number between 1 and 6 using only a function which generate 0 or 1

Suppose you have a function toss, which returns 0 or 1 randomly. Now you need to write a function which uses toss () to generate a random integer number between 1 and 6. The idea is: you toss 3 times, and if the value is outside of first six values, you toss 3 times again. The Python code is following: #suppose we have a function called "toss" which return 0 and 1 randomly #we need to write a function to generate number between 1 and 6 #means 1 <= x <= 6 use only the function "toss" from random import randint def toss (): return randint (0, 1) def generateRandomBetween1And6 (): while (True): sum = 0 for i in range (3): sum += toss () * (2 ** i) if (sum >= 1 and sum <= 6): return sum #test res = [0] * 6 for i in range (10000): num = generateRandomBetween1And6 (); res [num - 1] += 1 for i in range (6): print(str(res[i]) + '\n')

How to check if a linked list is cyclic or not

It is a regular interview question: given a one - direction linked list, how to check if there is a cycle inside the list or not. As usual, you will receive a pointer to the head of the list, and you write a function to return a Boolean value which indicates there is a cycle inside the list or not. The obvious way is creating another list / array to store all the elements of the list you visited, but in some cases it is not possible. You can always use this approach, even in the case the node element has no data but a pointer to the next one. If so, you can just store the pointer (i.e, the address). But of course it is not the intention of the interview. If the interviewer asked you to write an algorithm with time complexity is O(n) or space complexity is O(1), the above approach is not suitable. There is a better algorithm: using two pointers, one fast and one slow. Slow pointer moves one element per iteration, while fast pointer moves two. If they meet, it means there i...

Finding a room of the princess

There is an interview question as following: There are 17 rooms line up from 1 to 17. There is a princess who start at a room, then every night she will move to the room next to the previous one (i.e, she has to move to the left or right room - she cannot say at the same room). You are a beast who has to find the princess to be back a prince. Every night, you can open one and only one room to check if the princess is inside or not. You have 30 nights to find the princess, otherwise ... boom! Below is the number of the room the beast (or the future prince) should follow to check during 30 nights: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 Explaining why it is a good strategy might be an interesting task for the reader. I wrote a small application to simulate this strategy at: http://www.codeskulptor.org/#user38_wKWpYR0yZ3_2.py Probably you cannot run the simulation online, but you can get the Python code and try in your computer.

What doors are closed?

There is an interesting interview question, which has been asked at many US companies. There are 500 doors, initially closed. There are 500 people, one by one goes through all the doors. The 1st person change the status of all the doors (i.e, open all of them). The 2nd person change the status of all the doors with number can divide to 2 (i.e, he will change the status of doors number 2, 4, 6, 8, 10, ... 500) The 3rd person change the status of doors 3, 6, 9, ... ... The 500th person change the status of the door 500 Change the status means: close the opening door, and open the closing door. The question is: in the end, how many doors are close? You can solve this problem by using mathematics, but it may be faster to simulate it. You can check my simulation at: http://www.codeskulptor.org/#user38_rrZv4nVRno_1.py and easy to see, the opening doors are the doors with the number are square number.