Nitin Agrawal
Contact -
  • Home
  • Interviews
    • Secret Receipe
    • InterviewFacts
    • Resume Thoughts
    • Daily Coding Problems
    • BigShyft
    • Companies
    • Interviews Theory
  • Programming Languages
    • Java Script >
      • Tutorials
      • Code Snippets
    • Reactive Programming >
      • Code Snippets
    • R
    • DataStructures >
      • LeetCode Problems >
        • Problem10
        • Problem300
      • AnagramsSet
    • Core Java >
      • Codility
      • Program Arguments OR VM arguments & Environment variables
      • Java Releases >
        • Java8 >
          • Performance
          • NasHorn
          • WordCount
          • Thoughts
        • Java9 >
          • ServiceLoaders
          • Lambdas
          • List Of Objects
          • Code Snippets
        • Java14 >
          • Teeing
          • Pattern
          • Semaphores
        • Java17 >
          • Switches
          • FunctionalStreams
          • Predicate
          • Consumer_Supplier
          • Collectors in Java
        • Java21 >
          • Un-named Class
          • Virtual Threads
          • Structured Concurrency
      • Threading >
        • ThreadsOrder
        • ProducerConsumer
        • Finalizer
        • RaceCondition
        • Executors
        • Future Or CompletableFuture
      • Important Points
      • Immutability
      • Dictionary
      • Sample Code Part 1 >
        • PatternLength
        • Serialization >
          • Kryo2
          • JAXB/XSD
          • XStream
        • MongoDB
        • Strings >
          • Reverse the String
          • Reverse the String in n/2 complexity
          • StringEditor
          • Reversing String
          • String Puzzle
          • Knuth Morris Pratt
          • Unique characters
          • Top N most occurring characters
          • Longest Common Subsequence
          • Longest Common Substring
        • New methods in Collections
        • MethodReferences
        • Complex Objects Comparator >
          • Performance
        • NIO >
          • NIO 2nd Sample
        • Date Converter
        • Minimum cost path
        • Find File
      • URL Validator
    • Julia
    • Python >
      • Decorators
      • String Formatting
      • Generators_Threads
      • JustLikeThat
    • Go >
      • Tutorial
      • CodeSnippet
      • Go Routine_Channel
      • Suggestions
    • Methodologies & Design Patterns >
      • Design Principles
      • Design Patterns >
        • TemplatePattern
        • Adapter Design Pattern
        • Proxy
        • Lazy Initialization
        • CombinatorPattern
        • Singleton >
          • Singletons
        • Strategy
  • Frameworks
    • Apache Velocity
    • React Library >
      • Tutorial
    • Spring >
      • Spring Boot >
        • CustomProperties
        • ExceptionHandling
        • Custom Beans
        • Issues
      • Quick View
    • Rest WebServices >
      • Interviews
      • Swagger
    • Cloudera BigData >
      • Ques_Ans
      • Hive
      • Apache Spark >
        • ApacheSpark Installation
        • SparkCode
        • Sample1
        • DataFrames
        • RDDs
        • SparkStreaming
        • SparkFiles
    • Integration >
      • Apache Camel
    • Testing Frameworks >
      • JUnit >
        • JUnit Runners
      • EasyMock
      • Mockito >
        • Page 2
      • TestNG
    • Blockchain >
      • Ethereum Smart Contract
      • Blockchain Java Example
    • Microservices >
      • Messaging Formats
      • Design Patterns
    • AWS >
      • Honeycode
    • Dockers >
      • GitBash
      • Issues
      • Kubernetes
  • Databases
    • MySql
    • Oracle >
      • Interview1
      • SQL Queries
    • Elastic Search
  • Random issues
    • TOAD issue
    • Architect's suggestions
  • Your Views
Below question was asked to me in interview for PTC Software & I made certain mistakes by not asking the follow-up
​questions & not optimizing the solution further.

Question : Find the square root of the given number without using the Math api in Java. If no complete square root exists then
​                   return 0.

Solution : Below is not the solution I gave in interview, in interview I wrote very naive solution without using Math.sqrt()
     Please let me know how can I correct it further as it is giving many wrong results & how we can optimize it further.
/**
 * Below is one sample to find the square root in Java.
 * It is not efficient one, neither a complete one. It just finds the square roots in whole numbers.
 * It returns only integer values if possible else will return 0, if no such square root exists for the
 * given number. So in that case, it works faster than Math.sqrt(), as shown.
 * @author nitin
 *
 */
public class SquareRoot {
 public static void main(String[] args) {
  int num = 99980001;
  long start = System.nanoTime();
  System.out.println(find(num));
  System.out.println("Time taken : " + (System.nanoTime() - start) + " ns");
  start = System.nanoTime();
  System.out.println(Math.sqrt(num));
  System.out.println("Time taken : " + (System.nanoTime() - start) + " ns");
 }
 public static int find(int num) {
  int digits = 0;
  String temp = Integer.toString(num);
  digits = temp.length()/2;
  int start = 1;
  while(digits > 0) {
   start *= 10;
   digits--;
  }
  int i = start;
  if(i*i <= num) {
   int res = i*i;
   while(res < num/4) {
    i = i * 2;
    res = i * i;
   }
   while(res < num) {
    i++;
    res = i * i;
   }
   if(res == num) {
    return i;
   } else {
    return 0;
   }
  } else {
   
   i = --start;
   while(i >= 1) {
    if(i*i == num) {
     return i;
    }
    i--;
   }
   return 0;
  }
 }
}


​Below is some improved version of above method & one can tweak the breakpoint as per the understanding, but for now it gave mostly correct results.
​Tested below code for numbers 1 to 10000000000 to get the perfect square root. And seems it is giving all correct answers.

​​/**
  * This method finds square root of the given number.
  * It will give the result if perfect square root exists, else
  * will return 0.
  * Till now no errors found & has been around 100 times faster
  * than Math.sqrt() for such requirements.
  * Though can skip break condition but have put here to give the option
  * to get the values in decimals also.
  * @param num
  * @return
  */
 public static long findSqrRoot(long num) {
  
  if(num < 0)
   return 0;
  if(num == 1)
   return 1;
  String str = Long.toString(num);
  int len = str.length();
  int proc = 0;
  if(len > 7) {
   proc = len/2-1;
  }
  long startMin = 1;
  long startMax = num/2l;
  
  long min = startMin;
  long max = startMax;
  long ans = 0;
  while(proc > 0) {
   startMax = startMax/10;
   proc--;
  }
  
  long start = (startMax-startMin)/2l;
  long i = start;
  while(ans == 0 && max > min) {
   if(max-min < 10) {
    break;
   } else if(i*i == num) {
    ans = I;
    break;
   } else if(i*i > 0 && i*i < num) {
    min = i+1;
    i = min + (max-min)/2l;
   } else if(i*i > num || i*i < 0) {
    max = i-1;
    i = max - (max-min)/2l;
   }
  }
  for(long k = min; k <= max; k++) {
   if(k*k == num) {
    ans = k;
    break;
   }
  }
  return ans;
 }


​A faster way and it worked faster than Math.sqrt(), though it is not responding for Integer.MAX_VALUE:-
Picture
Picture
Powered by Create your own unique website with customizable templates.