Monday, December 1, 2014

FireMeUp Java Job Scheduler - Open Source

In one of the projects at my current employer me and my team were asked to use a Java Job Scheduling library to schedule some jobs doing some business at dynamically configured time. 

We decided to use Quartz as we were using Spring which provides a full integration to Quartz, and I was fascinated with the design and implementation of it.

I thought that I can start a new open source project that implements a Java Job Scheduler for learning purposes with some modifications/simplifications to the current design of Quartz library.

FireMeUp Scheduler is a simple Java scheduler that can be integrated within your application in a very simple way. The library is so simple and can be used in Small and Medium scale projects, and it provides the following functionality.

  •  Jobs that run every interval of time.
  • Jobs that run every day, week, biweekly, monthly, bimonthly, and yearly in a specific time of the day. (e.g., Every day at 12:00 AM).
  • Having more that a scheduler in your application.
  • Enable/Disable scheduler freely throughout your application life time.
  • Configuring more than one trigger and associating them to schedulers.
  • Triggers can be configured in more than one way either a simple trigger that is scheduled to be triggered every interval of time, and crontab trigger that is triggered either daily, weekly, biweekly, monthly, bimonthly, or yearly at specific time HH/MM/SS.
  • Implementing your jobs and associating them to triggers, more than one job to each trigger.
  • Register/Unregister triggers to schedulers.
  • Register/Unregister jobs to triggers.
  • Job can't overlap itself if its in a running state.
  • You can implement your own trigger by extending the AbstractTrigger that contains most of the business.
Future Functions

Here are some ideas I need to add to the current project, and anyone who needs to start his own open source life can start implementing them and be part of the project.
  • Adding state recovery functionality for the configured Schedulers, Triggers, Jobs, I think we can use in-memory (not recovered) and database (recovered) models.
  •  Threading management functionality, manage the number of concurrent running threads.
  •  Configuration management functionality, configuring the application programmatically and using a properties file.
  • Providing a crontab expression parser functionality.
  • Documentation of the whole project.
  • More complex examples and test cases.
Project Links

Wednesday, April 9, 2014

Maximum Triangle Area

Problem MaxTriangle SRM 449 Div-1 250 pts problem.

Here is the problem description:

A triangle with positive area has been positioned on the plane in such a way that all of its vertices are located at integer coordinates. The lengths of two sides of this triangle are equal to sqrt(A) and sqrt(B), where sqrt(X) denotes the squared root of X. Return the maximum area this triangle can have. If there is no such triangle, return -1 instead.

Solution to this problem:

We can use vectors to solve such kinds of problems, the input is the squared of magnitude of two vectors, so we need to get all vectors that can give a magnitude value equals to sqrt(A) and sqrt(B).

Given that magnitude of a two dimensional vector(x, y) can be computed using the following equation:

Magnitude = sqrt(x*x+y*y)

So we need to iterate all valid x and y that can evaluates to this x*x+y*y=c, where c equals the squared magnitude passed.

The following method takes a squared magnitude as a parameter and returns the list of vectors:


Note: For each valid x and y, the following are also valid as per the above equation (x, y), (-x, y), (x, -y), (-x, -y).

Now we can iterate for all pairs of vectors of both squared magnitudes A and B, to get the maximum area of a triangle. To compute the area of a triangle between two two dimensional vectors is done using cross product.

See the following video but this is for three dimensional vectors.

Cross product of two dimension vectors (x1, y1) and (x2, y2) = x1*y2-x2*y1

Read this.

Here is my code for this problem.


Monday, February 24, 2014

Sample ADF CRUD web application

In this post i will show you how to use ADF to create a simple CRUD application in just few minutes.

To know more about ADF "Application development framework" please go to this link.

1. Create an ADF web application.


2. Set application name "Sample Crud" and click finish.


3. Choose "Connect to a Database" and press "Create a Database Connection".


4. Put connection details, and connect to the Oracle Sample HR database, and make sure to test the connection.

Note: Make sure that the hr user is not locked, and if its locked you may need to unlock it.


5. Mark the "Connect to a database" step as Done.


6. Expand the "Build Business Services" step and click "Go to Substeps".


7. Expand "Create Entity Objects and Associations", Press "Create Entity Objects and Associations".



8. Choose the model project.


9. Choose the database connection created in step 3.


10. Press the Query button, and move the Jobs table to the right column.


11. For the updatable views, chose JobsView and move it to the right column, then press finish.


12. Mark the "Build Business Services" step as Done.


13. Open the "adf-config" unbounded task flow.


14. From the "Component Palette" panel drag the view icon to the task flow.


15. Rename it to "jobsView" and double click on it, and then click Ok.


16. Drag a button from "Component Palette" panel into the page, and rename it from the property panel.



17. Do the same for the Edit, Delete, View buttons.



18. From the "Data Control" panel, drag the JobsView1 into the page, and insert it as a read only table.


19. Choose "Single Row" for selection, and click Ok.


20. Back to the "adf-config" unbounded task flow, and drag a new view for the job form.


21. Double click the new page, and drag the JobsView1 into it from the "Data Control" panel as a form.



22. Check the "Include submit button" checkbox, and click Ok.



23. Back to the "adf-config" unbounded task flow, and drag a new view for the job details.


24. Double click the new view, and add the JobsView1 into it as a read only form, and click Ok.


25. Back to the "adf-config" unbounded task flow, In the "Data Control" panel, expand the JobsView1 -> Operations and drag the "CreateInsert" operation into the task flow.



26. Do the same for "Delete" operation.

27. From "Data Control" -> Operations, drag "Commit" and "Rollback" operations into the task flow page.


28. From the "Component Palette" panel click the "Control Flow Case" icon and drag from "jobsView" page to the "viewJobDetails" page, and name it "view".


29. Do the following to complete navigation flow for our business case:

A. "create" flow from "jobsView" to "createInsert" operation.
B. "edit" flow from "jobsView" to "jobForm" page.
C. "delete" flow from "jobsView" to "delete" operation.
D. "CreateInsert" flow from "CreateInsert" operation to "jobForm" page.
E. "Delete" flow from "Delete" operation to "Commit" operation.
F. "save" flow from "jobForm" page to "Commit" operation.
G. "cancel" flow from "jobForm" page to "Rollback" operation.
H. "Commit" flow from "Commit" operation to "jobsView" page.
I. "Rollback" flow from "Rollback" operation to "jobsView" page.
J. "back" flow from "viewJobDetails" page to "jobsView" page.


30. Go to the "jobsView" page, and double click it, and from the property panel, change the action for each button to be as follow:

A. "View" button action = "view"
B. "Create" button action = "create"
C. "Delete" button action = "delete"
D. "Edit" button action = "edit"


31. In the "jobForm" page, add a new button and name it cancel, and the action = cancel, imediate=true.


32. In the "viewJobDetails" page add a new button and name it back, and the action = back.


33. Right click the adf-config unbounded task flow and click run, if prompted to choose the run configuration choose "jobsView" page to be the start page.

34. Screen shots for the application:



Done.

Configuring logging for ADF application

In this post i will show you how to configure ADF logger that logs your messages/errors to a specific log file.  Here are the steps needed to do the configuration.

1. In JDeveloper right click IntegratedWeblogicServer instance, and choose Configure Oracle Diagnostic logging for "IntegratedWeblogicServer".



2. Choose the root logger, and in structure window expand log_handlers, copy log_handler named "old-handler".

3. Paste the copied log_handler and name it XX-custom-handler, from property window change .



4. Choose the path property and change its default value.



5. In the overview tab of logging.xml file, click the add symbol to add a persistent logger. In the logger name select the class file or package for which you want to use this logger. example : xx.oracle.app select a level based on the severity you need.
 




6. Expand the Root logger and choose the newly created logger, and in the handler declarations window press the add icon, and choose the custom handler.



7. Now select your project in the application window, and double click it to change the run configuration java options -> Choose the default run configuration -> Edit -> Java options and add the following option "-Djbo.debugoutput=adflogger".







8. Now you can use the ADFLogger util to create a logger instance that logs to you log file.


Done.

Tuesday, February 4, 2014

How to prepare for an interview - 17

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.

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

Problems

161. Print a binary tree in infix order. Recursive and iterative.


162. Recursively reverse a Linked List.


163. Implement the div operator without using / or %.


164. How to traverse a binary tree in order iteratively.


165. Print out all combinations of k numbers out of 1...N e.g. when k = 2, n = 4 Print out 12, 13, 14, 23, 24, 34.


166. Given a function for a fair coin, write a function for a biased coin that returns heads 1/n times (n is a param).


167. Given a binary tree, print out the elements in order. Without recursion.


168. Explain the difference between a LEFT and RIGHT SQL JOIN.


169. Extract the max 1000 record out of an array.


170. Code a text justification routine (Given a line length insert white space so text is uniformly displayed within the given length).


Done.

Read next post. Share this post to your Facebook, Twitter, LinkedIn.

How to prepare for an interview - 16

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.

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

Problems

151. Given an array of integers, now we want to erase all 0's (can be other value), and we want the result array condensed, meaning no empty cell in the array.


152. Given a list of words with a same size and a big string that contains one of the permutation of all the words combined(say p), find the start index of the string p in the big string.


153. Print out all prime numbers in a given string. abc2134kd31 -> 2, 13, 3, 3.


154. Generate a new array from an array of numbers. Start from the beginning. Put the number of some number first, and then that number, For example, from array 1, 1, 2, 3, 3, 1 You should get 2, 1, 1, 2, 2, 3, 1, 1.


155. Implement a function rotateArray(vector<int> arr, int r) which rotates the array by r places. Eg 1 2 3 4 5 on being rotated by 2 gives 4 5 1 2 3.


156. Implement a function string balanceParanthesis(string s); which given a string s consisting of some parenthesis returns a string s1 in which parenthesis are balanced and differences between s and s1 are minimum. Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2" - ")))(((" -> "".


157. Write a C function to define strcmp(char *s1, char *s2) to return negative if s1 is smaller, positive if s2 is greater and 0 if they are equal.


158. Write a function that computes log2() using sqrt().


159. Design and implement an algorithm that would correct typos: for example, if an extra letter is added, what would you do?


160. Implement a power function to raise a double to an int power, including negative powers.


Done.

Read next post. Share this post to your Facebook, Twitter, LinkedIn.

How to prepare for an interview - 15

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.

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

Problems

141. Use basic arithmetic operations (+-*/) to implement sqrt function.


142. Intersection of n sets without using a hash table.


143. Given a matrix with 1's and 0's, find the number of groups of 1's. A group is defined by horiz/vertically adjacent 1's.


144. Given a file with 3-letter words, print all 3x3 with each row, column and diagonal being one of the words from given file.


145. Given n+1 buckets with n of them with ball inside and move(a,b) function, that moves ball from bucket a to bucket b. Each ball has a different number from [1,n] on it. Move balls, so each bucket has a ball with matching number in it.


146. Find the center of graph(vertex, that is connected with every other vertex, but edges are directed to the center of graph).


147. Insert a node in a singly linked circular list given any node in the list.


148. Given two sorted arrays, please merge them into a single array and still sorted. how to determine the size of array?


149. Multiply two big integers which don't fit into an built-in integer type. How would you represent big numbers as a data structure? Write the function to multiply two big integers.


150. Given set of coins and each coin has its unique probability to be head up, say double[] probs stores the probability values for all coins, print out all different cases and accordingly probability.


Done.

Read next post. Share this post to your Facebook, Twitter, LinkedIn.

How to prepare for an interview - 14

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.

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

Problems

131. How would you store and search 1 million names?

We can use HashTable. Or use External sorting to split the names and then merge them searching for the needed word.

132. Function to compute the number of ways to climb a flight of n steps. Taking 1, 2, or 3 steps at a time. Do it in Linear time and constant space.

Example:

Input:     n = 3.
Output:
     1 1 1
     1 2
     2 1
     3
     Ans = 4


133. Interweave a linked list. Do it in Linear time and constant space.

Input: A->B->C->D->E
Output: A->E->B->D->C


134. Merge 'k' sorted arrays, each array may have max 'n' elements.


135. You have 9 balls, one of which weighs less than the others, but identical in appearance. If you had one weighing scale, how would you find out which ball weighs less? What would be the time complexity.


136. Implement the "see and tell" algorithm with a given seed number x and a number of iterations y. Output the result on iteration y.


137. A period of time where users login and logout, given a sets of login and logout time pairs, write a function that can show the number of users online at any given time.


138. Given a sorted array, write a program to decide if two elements sum up to a third.


139. Determine the 10 most frequent words given a terabyte of strings.


140. Giving lots of intervals [ai, bi], find a point intersect with the most number of intervals.


Done.

Read next post. Share this post to your Facebook, Twitter, LinkedIn.

How to prepare for an interview - 13

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.

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

Problems

121. Divide two numbers a and b.


122. Sort a binary tree and give the complixty of that.


123. Find all sub sets of size k from given set.


124. Given a sorted array and number x, return the index of this number in the array and if not exist return the index it should be inserted in.


125. Implement a read/write lock, given a mutex that has lock() and trylock() interface.


126. Prints the best collection of N coins that minimize the average number of minimum coins needed to generate values from 1 to M. So, if M = 100, and N = 4, then if we use the set {1, 5, 10, 25} to generate each value from 1 to 100, so that for each value the number of coins are minimized, i.e. 1 = 1 (1 coin), 2 = 1 + 1 (2 coins),..., 6 = 1 + 5 (2 coins), ..., 24 = 10 + 10 + 1 + 1 + 1 + 1 (6 coins), and we take the average of these coins, we would see that the average comes out to ~4.7. But if we instead use {1, 5, 18, 25}, the average would come out to be 3.7. We are to find that set of N coins, and print them, that produce the minimum average.


127. Implement a stack using only queue(s).


128. Print a bst in a sorted order.


129. Write a function that returns the largest sum you can get by adding together numbers in non-adjacent indices from the array. I.e. you if you include the things stored in arr[i] in your sum, you can't include what is stored in arr[i-1] or arr[i+1].


130. Given a m*n grid starting from (1, 1). At any point (x, y), you have two choices for the next move:
     1) move to (x+y, y);
     2) move to (x, y+x);
From point (1, 1), how to move to (m, n) in least moves? (or there's no such a path).


Done.

Read next post. Share this post to your Facebook, Twitter, LinkedIn.

Sunday, February 2, 2014

How to prepare for an interview - 12

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.

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

Problems

111. Check if 3 points are collinear.


112. Given coins of values 1, 5, 10, 25 and Sum S, give the min number of coins that can represent S.


113. Given an array of integers, return the number of longest increasing subsequence.


114. A table composed of N x M cells, each having a certain quantity of apples, is given. You start from the upper-left corner. At each step you can go down or right one cell. Find the maximum number of apples you can collect.


115. 0-1 Knapsack problem.


116. Fractional Knapsack problem.


117. Matrix multiplication.


118. Given a sorted array with duplicates, search for the start index and end index of an element using binary search.


119. Find different combinations of all the digits of an integer number with some conditions like sum < k and they can be grouped together to form a combination.


120. Given two sorted arrays, no duplicates, could be any size, return the median number in faster than O(n) time.


 Done.

Read next post. Share this post to your Facebook, Twitter, LinkedIn.

How to prepare for an interview - 11

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.

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

101. Given an array of distinct integers, and a target integer t, compute all of the subsets of the array that sum to t, where order matters.


102. Given an undirected graph and a node, modify the graph into a directed graph such that, any path leads to one particular node.


103. Reverse an array.


104. Two texts are considered to "match" if they have a common substring of at least length n. Describe an algorithm to determine if two strings are matches.


105. Given N credits cards, determine if more than half of them belong to the same person/owner. All you have is an array of the credit card numbers, and an api call like isSamePerson(num1, num2).


106. Compress a string.


107. Given an integer, return all sequences of numbers that sum to it. (Example: 3 -> (1, 2), (2, 1), (1, 1, 1)).


108. Given an unsorted array, extract the max and min value using the least number of comparison.


109. Max sum of adjacent value combination in an array.


110. Provided a phone number (654-876-0987), return all possible strings that the phone number could represent if 2 -> {A, B, C}, 3 -> {D, E, F}, and so on.


Done.

Read the next post. Share it on Facebook, Twitter, LinkedIn.

How to prepare for an interview - 10

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.


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

Problems

92. Combinations(n, k).


93. Write a program to sum two binary numbers represented as strings.


94. Compute the cubic root.


95. You have two lists with meetings scheduling (start time, end time) Meetings in single list don't intersect. Find all intersecting meetings across the two lists.


96. Given a binary search tree, write an algorithm to find the kth smallest element.


97. Given a string, return true if it's a palindrome. Only alphanumeric characters considered. Do this in one pass through the string.


99. Write a function that calculates input strings with operators +,-,*,/ eg. "5+5*6" should output 35.


100. Longest common substring between two strings A and B.


101. Find the predecessor of a binary search tree.


Now we finished this post, Read next post. Please share this post on your Facebook, Linkedin, and Twitter.

How to prepare for an interview - 9

Welcome back with a new set of problems. If you didn't check previous posts please start from here. Also if you didn't read previous post read it here.

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

Problems

82. Search a word in a character matrix.


83. Levenshtein Distance - Edit distance: Given two strings and you can only delete, insert, replace a character - return the minimum number of operations to make s1 = s2.


84. Solve the skyline problem, http://uva.onlinejudge.org/external/1/p105.pdf.


85. Sort an array of 3 numbers.


86. Write a function to calculate the hamming distance between two binary numbers.


87. Write a function that takes a list of binary numbers and returns the sum of the hamming distances for each pair -> O(n) solution.


88. Return the value of a roman number given a string.


89. Print out the paths to all leaves of a binary tree.


90. Given a set of n jobs with [start time, end time] find a subset so that no 2 jobs overlap and the length is maximum?


91. You are given a string with each English character translated to its alphabetical position (e.g., the string "ABC" --> "123"). Provide a function that, when provided the string as an argument, will return the maximum number of strings the encoded string could represent (for example, "123" could represent "ABC", "LC", or "AW").


Now we finished this post, Read next post. If you liked this post please share it on Facebook, Linkedin, and Twitter.

Saturday, February 1, 2014

How to prepare for an interview - 8

Welcome back with a new post and new problem set. You may need to read previous posts from here. Or read previous post from here.


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

Problems

72. Given an array of integers, find the sub array with the largest sum.


73. Palindromes possible from a string without extra space.


74. Prime factors of a given number.


75. Implement strstr().


76. Convert a binary number to its gray code.


77. Convert a gray code to its binary representation.


78. Given two unsorted arrays, one with event start times and one with end times, find out if any two events overlap.


79. Reverse double linked list.


80. Given a bipartite graph, separate the vertices into two sets.


81. Given two strings representing integer numbers ("123" , "30") return a string representing the sum of the two numbers ("153").


Now we finished today's set of problems, Read next post. Please share the post on your Facebook, Linkedin, and Twitter.

How to prepare for an interview - 7

Welcome to the seventh post in the How to prepare for an interview series. If you didn't read previous post please read it from here.


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

Problems

62. Given a List structure where each node contains a Next node and optionally a pointer to another list, flatten that list.

Input:

 L1 --> L2 --> L3 --> L7 --> L8
                          |
                         v
                         L4 --> L5-->L6

Output: 

L1 --> L2 --> L3 -->L4 -->L5-->L6-->L7-->L8


63. Interleave two linked lists (e.g. {1, 2, 3} & {4, 5, 6} would return {1, 4, 2, 5, 3, 6}).


64. Write a simple regular experession parser using ., *, +, ?.


65. Given a list of strings, return a list of lists, where each list consists of words that are anagrams." Example: Given ["cab", "cz", "abc", "bca", "zc"] the output should be: [ [ "abc", "bca", "cab"] , [ "zc", cz"]].


66. Given a string write a function which prints all the subsets of the string. Now make the function to return only unique solutions for example if they give you "abc" you print out {a, ab, abc, ac, b, bc, c}.


67. Method to return sqrt of a number.


68. Program "atof", which means convert a string float (e.g. "345.44E-10") to an actual float without using any existing Parse Float functions. This is not hard but gets messy.


69. Function to check if any 3 numbers sum to x.


70. Merge two sorted arrays together.


71. Given an array, remove the duplicates and return a unique array keeping the first occurrence of the duplicates and the order. [@2, @1, @3, @1, @2] --> [@2, @1, @3].


Now we finished this post, Read next post. Please share the post in case you liked it.

Friday, January 31, 2014

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.

Tuesday, January 28, 2014

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.

Wednesday, January 22, 2014

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.

Tuesday, January 21, 2014

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.

Wednesday, January 15, 2014

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.

Monday, January 13, 2014

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.