Nitin Agrawal
Contact -
  • Home
  • Interviews
    • Secret Receipe
    • InterviewFacts
    • Resume Thoughts
    • Daily Coding Problems
    • BigShyft
    • CompanyInterviews >
      • InvestmentBanks >
        • ECS
        • Bank Of America
        • WesternUnion
        • WellsFargo
      • ProductBasedCompanies >
        • CA Technologies
        • Model N India
        • Verizon Media
        • Oracle & GoJek
        • IVY Computec
        • Nvidia
        • ClearWaterAnalytics
        • ADP
        • ServiceNow
        • Pubmatic
        • Expedia
        • Amphora
        • CDK Global
        • CDK Global
        • Epic
        • Sincro-Pune
        • Whiz.AI
        • ChargePoint
      • ServiceBasedCompanies >
        • Altimetrik
        • ASG World Wide Pvt Ltd
        • Paraxel International & Pramati Technologies Pvt Ltd
        • MitraTech
        • Intelizest Coding Round
        • EPAM
    • Interviews Theory
  • Programming Languages
    • Java Script >
      • Tutorials
      • Code Snippets
    • Reactive Programming >
      • Code Snippets
    • R
    • DataStructures >
      • LeetCode Problems
      • AnagramsSet
    • Core Java >
      • Codility
      • Program Arguments OR VM arguments & Environment variables
      • Java Releases
      • Threading >
        • ThreadsOrder
        • ProducerConsumer
        • Finalizer
        • RaceCondition
        • Executors
        • Future Or CompletableFuture
      • Important Points
      • Immutability
      • Dictionary
      • 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
        • Decorator
        • Proxy
        • Lazy Initialization
        • CombinatorPattern
        • RequestChaining
        • Singleton >
          • Singletons
  • Frameworks
    • Apache Velocity
    • Spring >
      • Spring Boot >
        • CustomProperties
        • ExceptionHandling
        • 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
  • Databases
    • MySql
    • Oracle >
      • Interview1
      • SQL Queries
    • Elastic Search
  • Random issues
    • TOAD issue
    • Architect's suggestions
  • Your Views

Moving the particular numbers to one side of the Array

9/3/2019

0 Comments

 
There is one interesting programming question asked like -
a) You are given an array containing 1 & 0 only & you need to write the code to move all 1s in 
     start of the array & 0s at the end of the array.

b) You are given an array of numbers & you need to write the code to move all the even                numbers in the start of the array & all the odd numbers at the end of the array.

So both the problems are quite easy to suggest the solution & to tell the approach.
But you will see the 1-2 issues when you implement that for the first time & depending on the twist the interviewer adds to it, makes it tricky.
Below is the code I am giving for the above 2 problems to cover different scenarios & please let me know if it fails for any case or you see any more scenario in the same problems & not getting covered below -


​/**
 * @author nitin
 *
 */
public class Defragmentation {

 public static void main(String[] args) {
  //  int[] array = {1,1,1,0,0,1,0,1};
  //    int[] array = {1,0,1,0,1,0,1,0,1,0,1,0};
  //    int[] array = {0,0,0,0,0,0,0};
  //    int[] array = {1,1,1,1,1,1};
  //    int[] array = {1,1,1,1,1,1,0,0,0,0,0,0,0,0};
//  int[] array = {10,12,9,8,7,90,6};
//      int[] array = {2,4,6,8,10,12};
//      int[] array = {1,3,5,7,9};
//    int[] array = {1,3,5,7,9,2,4,6,8,10,12};
  int[] array = {1,3,5,7,9,12};
  defragEven(array);
  System.out.println(array);
 }

 // Below method moves all 1's in the start & all 0's to the end of the Array.
 // It is like stable sort as it will preserve the order of 0's in the Array,
 // if number of 0's & 1's is equal else one element will out of order.
 // Complexity = O(n)
 public static void defrag(int[] array) {

  int second = 0;
  int len = array.length;
  for(int i = 0; i < len; i++) {
   if(array[i] == 0 && array[second] != 0) {
    second = i;
   }
   if(array[i] == 1 && array[second] == 0) {
    int temp = array[i];
    array[i] = array[second];
    array[second] = temp;
    second++;
   }
  }
 }

 // Below method moves all 1's in the start & all 0's to the end of the Array.
 // But will not preserve the order.
 // Complexity = O(n)
 public static void defrag2(int[] array) {

  int len = array.length;
  int zero = len-1;
  for(int i = 0; i < zero;) {
   if(array[i] == 1)
    i++;
   else if(array[zero] == 0)
    zero--;
   else {
    int temp = array[i];
    array[i] = array[zero];
    array[zero] = temp;
    zero--;
    i++;
   }
  }
 }

 // Below method will move all the even numbers to the start & odd numbers to the end of the Array.
 // While doing this it is keeping the order same irrespective of the number of even & odd numbers.
 // Keeping the order same adds to the complexity.
 // Complexity = O(2n) = O(n)
 public static void defragEven(int[] array) {
  int second = 0;
  int len = array.length;
  for(int i = 0; second < len && i < len;) {
   if(array[i]%2 == 0 && array[second]%2 != 0 && i != len-1) {
    int temp = array[i];
    array[i] = array[second];
    array[second] = temp;
    i++;
    second++;
   }
   else if(array[i]%2 == 0 && i < len-1) {
    i++;
   } else if(array[i]%2 != 0 && i < len-1) {
    if(array[second]%2 == 0)
     second = i;
    i++;
   } else {
    while(i > second && array[second]%2 != 0 && array[i]%2 == 0) {
     int temp = array[i-1];
     array[i-1] = array[i];
     array[i] = temp;
     i--;
    }
    break;
   }
  }
 }
 
 // Below method will move all the even numbers to the start & odd numbers to the end of the Array.
 // It doesn't care for the order, so it is bit simpler.
 // Complexity = O(n)
 public static void defragEven2(int[] array) {

  int len = array.length;
  int odd = len-1;
  for(int i = 0; i < odd;) {
   if(array[i]%2 == 0)
    i++;
   else if(array[odd]%2 != 0)
    odd--;
   else {
    int temp = array[i];
    array[i] = array[odd];
    array[odd] = temp;
    odd--;
    i++;
   }
  }
 }

}
0 Comments

    Author

    Nitin Agrawal

    Archives

    September 2019

Powered by Create your own unique website with customizable templates.