How to prepare for an interview - 4

Back with a new list of problems, wish you enjoyed reading previous post. If you are not a follower so you missed lots of problems, start from here.

Remember you should discuss these solutions with me, and refer if there are mistakes or other good solutions.

Problems

32. Given an infinite number of quarters (25 cents), dimes (10 cents), nickles (5 cents), and pennies (1 cent), write code to calculate the number of ways of representing N cents.

33. Same question above but find the least number of coins to represent N cents.

34. Write an algorithm to print all ways of arranging 8 queens on a chess board so that none of them share the same row, column, diagonal.

35. Given two sorted arrays, A and B, and A has large enough buffer at the end to hold B. Write a method to merge A and B in sorted order.

36. Write a method to sort an array of strings so that all anagrams are next to each others.

37. Given a sorted array of n integers that has been rotated an unknown number of times, give an O(log n) algorithm that finds an element in the array, you may assume that the array was originally sorted in increasing order.

Example:

Input: Find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)

Output: 8

38. If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?

39. Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.

   

Example: 

Input: Find  “ball”  in  [“at”,  “”,  “”,  “”,  “ball”,  “”,  “”,  “car”,  “”,  “”,  “dad”,  “”,  “”]  

Output: 4

40. Given a matrix in which each row and each column is sorted, write a method to find an element in it.

41. A circus is designing a tower routine consisting of people standing atop one another’s shoulders For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her Given the heights and weights of each  person in the circus, write a method to compute the largest possible number of people in such a tower.

Example: 

Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)

Output:  The  longest  tower  is  length  6  and  includes  from  top  to  bottom:  (56,  90) (60,95) (65,100) (68,110) (70,150) (75,190)

42. You have a basketball hoop and someone says that you can play 1 of 2 game:

Game #1: You get one shot to make the hoop

Game #2: You get three shots and you have to make 2 of 3 shots

If P is the probability of making a particular shot, for which values of P should you pick one game or the other?

Read the next post, with a new set of questions. If you liked this post please share it on FB, Twitter, Linkedin.