Skip to main content

Posts

Find the Town Judge

Problem In a town, there are 'n' people labelled from 1 to 'n'. There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: The town judge trusts nobody. Everybody (except for the town judge) trusts the town judge. There is exactly one person that satisfies properties 1 and 2. The given input is an array of pairs trust[i] = [a, b] representing that the person labelled 'a' trusts the person labelled 'b'. If the town judge exists and can be identified, return the label of the town judge.  Otherwise, return '-1'. Solution To solve the problem we can use a simple array of size N+1 (we will use N+1 to avoid maintaining numbers as arrays starts with index 0 and we have people numbered from 1). Every index starting one represent a member of the town. We can use following logic to solve the problem. Lets go through the entire list of trust values and do following things For every ...
Post a Comment
Read more
Recent posts

Check If It Is a Straight Line

Problem Given a list of x, y coordinates, find if all the coordinates are on a straight line. if YES return 'True' otherwise return 'False' Solution   Equation for the straight line is  y = mx + c where y and x are the coordinates and m and c are integer constants. if all the inputs are on the same straight line they should follow the above formula. We can use first two points to find the value of m and c and check other following points using the formula. if first point is x1, y1 and second point is x2, y2 y1 = m * x1 + c y2 = m * x2 + c m = (y2-y1)/(x2-x1) c = y1-(m*x1) one we have above values for every point we can check if y3 = m*x3+c ...  If we put above logic in the java code it will look like this
Post a Comment
Read more

Cousins in Binary Tree

Problem Two nodes of a binary tree are  cousins  if they have the same depth, but have  different parents . We are given a binary tree made of positive integers where every node have unique values which is greater than 1.   If we get two integer values x and y, return TRUE if and only if the nodes corresponding to x and y are cousins otherwise return FALSE. Solution We can solve the problem by using any tree traversing mechanism. We just need to keep track of the parent of the node as well as the depth level of the node.  In the sample code we are using pre order traversal where we are looking at the node first followed by left and the right node.
Post a Comment
Read more

First Unique Character in a String

Problem Find the first non-repeating character in a given String and return it's index. If it doesn't exist, return -1. Solution We can execute the logic in two steps Find the frequencies of every letter how many times they appear in the string Using those frequencies find the the first letter which has value as 1 We need to use a Map to keep track of the first index of a letter and separate storage to maintain the frequency count. Example code is as below:
1 comment
Read more

Number Complement

Number Complement For Positive Integer For a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation. Solution  To solve above problem we need to generate the binary representation of a number and go through the bits to find the complement of the bit.  To get the complement a simple logic can we do the XOR the bit with 1 which will give its complement  i.e.  1 ^ 1 = 0 0 ^ 1 = 1 Sample Code  
2 comments
Read more