O(n^2) vs O(n) techniques for finding the max count of a digit in the given numerical String.


Hello Buddies

Came across this question related Java String handling, so thought of sharing.

Question:
Given a string made up of n number of digits, find the digit having the maximum number of occurrence.
Eg. "12333123654"
Here, 3 is the digit being repeated for the maximum number of times.

Answer:
First approach can be to scan the string as a character array, maintain a map that can update the occurrence count. In the end find the max value and then the corresponding key.


Question:
What is the complexity of this solution?

Answer:
O(n^2) since we are iterating and using contains check.


Question:
Any better approach?

Answer:
Solution with O(n) complexity, i.e. having a lookup array.
We have digits 0 to 9, which can be related to each index of an array. For the values, update the occurrence count in the values.

For complete solution, refer to this link.

Happy Coding!!


Cloning in java - An interviewer's perspective






Wassup Buddies!



'Cloning' is the topic we will be cloning down for this blogpost.


To save time and memory, coders often prefer to re-use already existing objects. Commonly, a new reference pointing to an existing object, or talking about veterans of Java, techniques like cloning are used.


Digging deeper in this context, we will understand what are the repercussions and whats are the various ways of cloning. Core java interviewers find it an interesting topic to engulf the candidates by asking various pros and cons.



I have placed the sample Java class that I created for my understanding and the differentiation of types, here



Please feel free to get your hands dirty. Many of our readers might find the topic repetitive, but I hope they will find a new perspective of seeing or explaining the concepts or would love to share their thoughts and suggestions for improving the knowledge of others.




A brief primer for better understanding of the code is as follows:



Scenario 1: Assigning the reference.


Test ob1 = new Test();


Where Test.java is -


class Test {
int var1, var2;
Dummy dummy = new Dummy();
Test() {
var1 = 10;
var2 = 20;
dummy.aVar = 30;
dummy.bVar = 40;
}
}


Simply straight forward, an object is having its reference.

ob1 original -- 10 20 30 40



Scenario 2: Creating a new reference for the same object, using the earlier created reference.


Test ob2 = ob1;


Now make some changes using the second reference to see the impact on the object created.


ob2.var1 = 100;
ob2.dummy.aVar = 1000;


What do we get?

ob1 original -- 10 20 30 40
ob1 changed -- 100 20 1000 40
ob2 original -- 100 20 1000 40


So clearly, as expected, reference will impact the original object.




Scenario 3: Shallow Cloning


CloneableTest cloneableTest = new CloneableTest();


Where CloneableTest.java is -


class CloneableTest implements Cloneable {
int var1, var2;
Dummy dummy = new Dummy();
CloneableTest() {
var1 = 10;
var2 = 20;
dummy.aVar = 30;
dummy.bVar = 40;
}
public Object clone()
throws CloneNotSupportedException {
return super.clone();
}
}


Note: For using cloneableTest.clone(), we need to have the class implementing Cloneable interface, else we will get ''CloneNotSupportedException".



Bringing in a new reference for testing -


CloneableTest newCloneable = null;
try {
newCloneable = (CloneableTest) cloneableTest.clone();
newCloneable.var1 = 99;
newCloneable.var2 = 99;
newCloneable.dummy.aVar = 99;
newCloneable.dummy.bVar = 99;
} catch (CloneNotSupportedException e) {
// e.printStackTrace();
System.err.println
("Exception since Cloneable interface is not implemented!!");
}


Changes have been made, but what about the original object? Let's check!



Original Before : 10 & 20 & 30 & 40

Cloned   : 99 & 99 & 99 & 99
Original After : 10 & 20 & 99 & 99


Hence take away from this example - original primitive attributes won't change, but non primitives will change. 

Still the cloned object is not yet completely change proof.



Scenario 4: Deep Cloning



CloneableDeepTest cloneableDeepTest = new CloneableDeepTest();

Where CloneableDeepTest.java is -

class CloneableDeepTest implements Cloneable {
int var1, var2;
Dummy dummy = new Dummy();
CloneableDeepTest() {
var1 = 10;
var2 = 20;
dummy.aVar = 30;
dummy.bVar = 40;
}
public Object clone()
throws CloneNotSupportedException {
CloneableDeepTest cloneableDeepTest
= (CloneableDeepTest) super.clone();
cloneableDeepTest.dummy = new Dummy();
return cloneableDeepTest;
}
}


Bringing in new reference again -



CloneableDeepTest cloneableDeepTest2 = null;
try {
cloneableDeepTest2 =
(CloneableDeepTest) cloneableDeepTest.clone();
cloneableDeepTest2.var1 = 55;
cloneableDeepTest2.var2 = 66;
cloneableDeepTest2.dummy.aVar = 77;
cloneableDeepTest2.dummy.bVar = 88;
} catch (CloneNotSupportedException e) {
// e.printStackTrace();
System.err.println
("Exception since Cloneable interface is not implemented!!");
}

What should be the impact on the original object now? Let's check!


Original Before : 10 & 20 & 30 & 40

Cloned   : 55 & 66 & 77 & 88
Original After : 10 & 20 & 30 & 40


Sigh! The cloned object still retains the expected original values for both primitive and non primitive attributes.


Major difference between the implementation of shallow and deep clonings can be seen in the overridden clone() methods -

For shallow we simply call super.clone() as follows -

public Object clone()
throws CloneNotSupportedException {
return super.clone();
}


While for deep cloning, we need to go a bit further and control the way how inner objects are being generated as follows -

public Object clone()
throws CloneNotSupportedException {
CloneableDeepTest cloneableDeepTest =
(CloneableDeepTest) super.clone();
cloneableDeepTest.dummy = new Dummy();
return cloneableDeepTest;
}

That's all I have for now.

Happy Coding!!

Featured post

Oracle SQL Scheduled Jobs - An Interesting Approach

  Oracle SQL Scheduled Jobs A DB Scheduler is the best way to automate any backend database job. For instance, if you want to process the p...