Posts

Showing posts from April, 2017

Dutch national flag problem in Javascript

Image
Dutch national flag problem and solution in Javascript Problem statement:   The Dutch national flag (DNF) problem is one of the most popular programming problems proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: white, red, and blue. The task is to randomly arrange balls of white, red, and blue such that balls of the same color are placed together. Now, let's consider an array with 3 distinct values say 0, 1 and 2. We won't be using any sort method and we need to sort this array in 0(n). Input Array :  let   arr  = [ 0 ,  2 ,  1 ,  0 ,  1 ,  2 ,  0 ,  2 ]; Expected Output: [ 0, 0, 0, 1, 1, 2, 2, 2 ] Solution Approach : When we see expected output, we can clearly see that sorted array is divided into 3 sections having values 0 , 1 and 2. So, let's divide the array in 3 sections: a) from 0th index to left boundary b) from left boundary to right boundary c) from right boundary to last index. Now we will create 2 pointers : left (starting from 0
Post a Comment
Read more

Just Smaller Number: Hackerearth Problem and Solution in java

Just Smaller Number: Hackerearth Problem Statement: Given an array  A A  of length  N N  and a number  K K , find the greatest number in the array  A A  that is smaller than  K K . Input: First line contains two space separated integer  N , ( 1 ≤ N ≤ 10 5 ) N , ( 1 ≤ N ≤ 10 5 )  and  Q , ( 1 ≤ Q ≤ 10 5 ) Q , ( 1 ≤ Q ≤ 10 5 ) , number of elements in the array  A A , and number of queries. Second line contains  N N  space separated integers  A i , ( 1 ≤ A i ≤ 10 9 ) A i , ( 1 ≤ A i ≤ 10 9 ) , elements of the array  A A . Next  Q Q  lines contains one integer  K , ( 1 ≤ K ≤ 10 9 ) K , ( 1 ≤ K ≤ 10 9 )  each. Output: For each query, print the number of the greatest number in the array  A A  that smaller than  K K . SAMPLE INPUT   5 3 3 5 7 2 3 10 7 6 SAMPLE OUTPUT   7 5 5 Explanation The greatest number that is smaller than  10 10  is  7 7 . The greatest number that is smaller than  7 7  is  5 5 . The greatest number that is smaller than  6 6  is 
Post a Comment
Read more

Recover the Arrays: Hourrank 19 Problem and Solution in java

Image
Recover the Arrays: Hourrank 19 Problem Dani is writing some arrays in her favorite text editor HackerEdit. Each line of the document describes an array in the following format: Here   is the array's number of elements and   are its contents. Dani wrote   arrays in the file and left for lunch. To her dismay, her little brother Nik deleted all the newline characters from the file while she was gone! For example, consider the file in the table below: Given the contents of Dani's HackerEdit file with all the newlines removed, find the value of   (i.e., the number of arrays in the initial file). Input Format The first line contains an integer denoting   (the number of integers in the file).  The second line contains   space-separated integers describing each respective value in the file. Constraints Output Format Print a single integer denoting  . Sample Input 0 11 5 4 5 4 3 3 2 1 4 1 4 Sample Output 0
Post a Comment
Read more