How to prepare for an interview - 6

Welcome to a new post of the How to prepare for an interview series, In this post I will solve a new set of problems. If you didn't read previous post, Read it from here.

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

Problems

52. Implement a hash table.


53. How to validate is a binary search tree is legit?


54. Implement a pow(base, exp) function.


55. Implement the pow function iteratively.


56. Given like -77288.100, a772sb, 2000.00.11. return if it's a number.


57. Find maximum successive sum in an array.


58. Reverse words in a sentence.


59. Check if an element is present in a completely sorted 2D array.


60. Determine if a graph is bipartite.


61. How would you implement division without +, - or *?


Now we finished this post. Read the next post. Please share this post to your Facebook, Linkedin, Twitter if you liked it.

How to prepare for an interview - 5

This is the fifth post in How to prepare for an interview series. If you didn't read the previous post please read it here.

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

Problems

43. There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon

44. Given two lines on a Cartesian plane, determine whether the two lines would intersect.

45. Write a method to implement *, - , / operations You should use only the + operator.

46. Given two squares on a two dimensional plane, find a line that would cut these two squares in half.

47. Given a two dimensional graph with points on it, find a line which passes the most number of points.

48. Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.

49. Methods of a binary search tree.

50. Program an iterator for a Linked List which may include nodes which are nested within other nodes. i.e. (1)->(2)->(3(4))->((5)(6). Iterator returns 1->2->3->4->5->6.

51. Implement an algorithm to convert an integer into a roman numeral string.

Now we finished today's set of problems, Read the next post. Please if you liked the post share it on Facebook, Twitter, Linkedin.

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.

How to prepare for an interview - 3

Today I will solve a new set of technical interview questions, as you may know this is the third post in the How to prepare for an interview. If you have not study the last post please read it here.

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

Problems

21. Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree Avoid storing additional nodes in a data structure NOTE: This is not  necessarily a binary search tree.

22. You have two very large binary trees: T1, with Millions of node, and T2 with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

23. Given a binary tree, in which each node contains a value. Design an algorithm to print all paths that sums to that value. Note that it can be any path in the tree - it doesn't have to start at the root.

24. You are given two 32 bit numbers N and M, and two bit positions i, and j. Write a method to set all bits between i and j in N to M.

(e.g., M becomes a substring of N located at i and starting at j).

Example:

Input: N = 10000000000, M = 10101, i = 2, j = 6

Output: N = 10001010100

25. Write a method to generate the nth Fibonacci number.

26. Imagine a robot sitting on the upper left hand corner of N*N grid. The robot can only move in two directions: Right and Down How many possible paths are there for the robot.

27. Same problem at 26, but if there are some blocks in some cells, print out how many paths are there.

28. Write a method that returns all subsets of a set.

29. Write a method to compute all permutations of a string.

30. Implement an algorithm to print all valid (properly opened, closed) combinations of parentheses.

Example:

Input: 3

Output: ()()(), ()(()), (())(), ((()))

31. Implement the paint-fill function that one might see on many image editing programs. That is, given a screen (represented by 2 dimension array of colors), a Point, and a new color, Fill in the surrounding area until you hit a border of that color.

Now we have solved all today's problems. I know it were harder than the previous one, But i'm sure you will enjoy solving them, read the next post here.

How to prepare for an interview - 2

This is the second post in the How to prepare for an interview series, If you haven't read the last post you may like to read and practice previous problems here.

Today i will put another set of problems with its solutions in C++, again and again in order to get the best out of this training, you should read the problem, try to solve it and then read my solution, discuss it with me.

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

Problems

11. Given a circular linked list, implement an algorithm to return the beginning of the loop in that list.

Example:

Input: A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C



12. Design a CustomStack data structure which in addition to push, pop, also has a function min to return the minimum value in the stack, and should be in O(1).



13. Implement an algorithm to solve Tower of Hanoi puzzle. What is Tower of Hanoi?



14. Implement a queue data structure with two stacks.



15. Given a stack, sort it.



16. Given a tree data structure, implement a function to check if this tree is balanced or not, for the purpose of this problem a balanced tree is a tree such that no two leaf nodes differ in distance from root by more than one.



17. Given a directed graph, design an algorithm to find out whether there is a route between two nodes.



18. Given a sorted array (increasing order), write an algorithm to create a binary tree with minimal height.



19. Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth, (i.e., If you have a tree of depth D, you will have D linked lists).



20. Write an algorithm to find the next node (i.e., in-order successor) of a given node in a binary search tree where each node has a link to its parent.

Now we have solved all today's problems. I know it were harder than the previous one, But i'm sure you will enjoy solving them, read the next post.

How to prepare for an interview - 1

In this series of posts i will talk about How to prepare for an interview, by interview i mean (Google, Facebook, Linkedin, Amazon, Imo.im, and Pocket Gems ...) interviews.

In this series i will only talk about the technical part of interview preparation. You will find lots of interview problems which i collected from lots of references like:

• Glassdoor
• Cracking an interview book
• Hacking a Google interview handouts

In this series i will solve in each post about 10 problems, may be more or less based on the difficulty of each problem then write my own solution for each problem. To get the best out of this training you should think about each problem, code it, test it and then check my solution, In case you couldn't solve the problem feel free to read/think/test/recode/discuss my solution.

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

Note: I will use C++ to solve all of the coming problems, feel free to use other programming languages. 

Problems

1. Determine if a string has all unique characters.


2. Reverse a string in place.


3. Remove duplicates in a string in place.


4. Write a method to decide if two strings are anagrams or not.


5. Given an image represented by N*N matrix can you rotate it 90 degrees in place.


6. Write an algorithm such that if an element in an M*N matrix is 0, its entire row and column is set to 0.


7. Assume you have a method isSubstring which checks if one word is a substring of another string. Given two strings s1, and s2. write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”).


8. Write a function that (insert, remove, search, print, reverse, removeDuplicates) a linked list.


9. Write a method to delete a node in the middle of a linked list given only access to that node:

Input: The node 'c', from the linked list a->b->c->d->e
Output: Nothing is returned but the linked list becomes: a->b->d->e


10. You have two numbers represented by a linked list, where each node contains a single digit. The digits are sorted in reverse order, such that the 1's digit is at the head of the list. Write a function that adds two numbers and returns the sum as a linked list.

Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8


To discuss and solve more problems please read the next post.