Puzzle - Highest product of 3 numbers in an array

Highest Product of triplets in array – Algorithm

Below is a puzzle I got from a colleague when he attended an interview. Trying to solve my way.

Question

• Find the triplet from integer array whose product is highest
• Use single loop.
• Language can be any

Samples

• Input [1,2,3,4] -> [2,3,4]
• Input [-5,-7,4,2,1,9]-> [-5,-7,9]
• Input [-10,-3,-5,0,-20]->[-10,-5,-20]

Approach

Since 2 negative numbers can produce positive product the approach taken was to find the lowest, second lowest, third highest, second highest and first highest numbers and compared their sums as follows.

---

            if (lowest * secondLowest * highest > highest * secondHighest * thirdHighest)
            {
                return new int[3] { lowest, secondLowest, highest };
            }
            else
            {
                return new int[3] { thirdHighest, secondHighest, highest };
            }

---

Finding the numbers is the trick. One implementation can be found in below location.
https://github.com/joymon/puzzles/tree/master/Numbers/HighestProductOfTripletInArray

Comment if there are any other simple implementations.

Happy coding...

Puzzle - Sales tax

Below is famous problem which could be asked in coding interviews. I got this problem when I attended ThoughtWorks long back and could pass to the next round of pair programming.  The solution what I sent to them is uploaded to Github and URL is given at the end of this post. The mail came up when I was cleaning my mail box.

PROBLEM SALES TAXES 

Basic sales tax is applicable at a rate of 10% on all goods, except books, food, and medical products that are exempt. Import duty is an additional sales tax applicable on all imported goods at a rate of 5%, with no exemptions.

When I purchase items I receive a receipt which lists the name of all the items and their price (including tax), finishing with the total cost of the items, and the total amounts of sales taxes paid. The rounding rules for sales tax are that for a tax rate of n%, a shelf price of p contains (np/100 rounded up to the nearest 0.05) amount of sales tax.

Write an application that prints out the receipt details for these shopping baskets...
INPUT:

Input 1:
1 book at 12.49
1 music CD at 14.99
1 chocolate bar at 0.85

Input 2:
1 imported box of chocolates at 10.00
1 imported bottle of perfume at 47.50

Input 3:
1 imported bottle of perfume at 27.99
1 bottle of perfume at 18.99

1 packet of headache pills at 9.75
1 box of imported chocolates at 11.25

OUTPUT

Output 1:
1 book : 12.49
1 music CD: 16.49
1 chocolate bar: 0.85
Sales Taxes: 1.50
Total: 29.83

Output 2:
1 imported box of chocolates: 10.50
1 imported bottle of perfume: 54.65
Sales Taxes: 7.65
Total: 65.15

Output 3:
1 imported bottle of perfume: 32.19
1 bottle of perfume: 20.89
1 packet of headache pills: 9.75
1 imported box of chocolates: 11.85
Sales Taxes: 6.70
Total: 74.68

Solution

The major pattern here applicable is decorator to structure the calculation rules. Full code is present in GitHub repo.

Puzzle - Pricing engine done for BarclayCard

Working as Software consultant than a full time employment is fun and make us up to date. We can see different architectures, coding practices, deployments and other software practices which will definitely help in case we have plans to start own company in future. But the down side is we had to attend interviews more often and there is no guarantee that when our assignment is over the market will be in good condition. Sometimes we may not get the job in the technology we want.

Recently I was attending many interviews. One of those was BarClay card. After 3-4 rounds of interview, I was asked to code a problem in production quality. It assumes 100% test coverage. Below is the problem.

---

Problem

An online retail company conducts market research to competitively price their products.Surveyed data contains Product code, Competitor and Price.

The retail company uses a Pricing engine which recommends most frequently occurring price. If multiple prices occur frequently, the least amongst them is chosen.

Products are classified based on parameters like Supply, Demand. Possible values are Low (L), High (H)

If Supply is High and Demand is High, Product is sold at same price as chosen price.
If Supply is Low and Demand is Low, Product is sold at 10 % more than chosen price.
If Supply is Low and Demand is High, Product is sold at 5 % more than chosen price.
If Supply is High and Demand is Low, Product is sold at 5 % less than chosen price.

Prices less than 50% of average price are treated as promotion and not considered.
Prices more than 50% of average price are treated as data errors and not considered.

Input consists of number of products, followed by each Product's supply and demand parameters.

followed by number of surveyed prices, followed by competitor prices.

Output must be recommended price for each product.

Sample inputs and outputs

Input 1:
2
flashdrive H H
ssd L H
5
flashdrive X 1.0
ssd X 10.0
flashdrive Y 0.9
flashdrive Z 1.1
ssd Y 12.5

Output 1:
A 0.9
B 10.5

Input 2:
2
mp3player H H
ssd L L
8
ssd W 11.0
ssd X 12.0
mp3player X 60.0
mp3player Y 20.0
mp3player Z 50.0
ssd V 10.0
ssd Y 11.0
ssd Z 12.0

Output 2:

A 50.0
B 12.1

This has to be completed within 2 days.

Solution

There can be different solutions. Below are some point about the one I did.  

• For achieving pricing used decorator pattern
• Coded in C#
• Tests done using mUnit.
• Mocks done using Moq library
• Test coverage using ncover

Code is available in the puzzles repo. It took around 6-8 Hrs for me to complete. Please note that they didn't get back to me after I sent this code. So don't just copy paste the code and use for the same puzzle. May be there is something missing.

Finding N HigestRatedRelatedMovies- Amazon interview coding challenge via HackerRank

Below is a coding question from Amazon interview I had attended in the past. It was through HackerRank which I had to complete within 90 mins. There are now many sites like HackerRank which can be used to screen developers prior to the face to face or telephonic. That saves a lot of time for companies. But there are very less companies using these options including my previous company where I pressed hard to get this into interview process.

I am not copy pasting the question and initial code snippet as is from HackerRank as it may bring this page in case they reuse the question.Instead this version has slight modifications such as using property instead of Java like get methods etc...

Question

• Find highest rated N movies which are related to given movie
• Movie relation is two way
• The result list should not contain the Movie which we start with.
• The highest rated movie can be in any level of relation. 

Basically needs to fill code inside the function below function present in MovieFinder class

getHighestRatedRelatedMovies(Movie root,int numer)

Below is the code snippet. We can have helper methods if required.

---

public class Movie
{
    public int Id { get; private set; }
    public double Rating { get;private set; }
    public IList<Movie> RelatedMovies { get; private set; }
    public Movie(int id,double rating)
    {
        this.Id = id;this.Rating = rating;
        this.RelatedMovies = new List<Movie>();
    }
    public void AddRelatedMovie(Movie movie)
    {
        this.RelatedMovies.Add(movie);
        movie.RelatedMovies.Add(this);
    }
}
public class MovieFinder
{
    public IEnumerable<Movie> getHighestRatedRelatedMovies(Movie root, 

                                                           int numberOfMoviesToSelect)
    {
       //Logic to return appropriate movies
    }
}
class MovieFinderTests
{
    public void Test()
    {
        Movie a = new Movie(1,1.5F);
        Movie b = new Movie(2, 3.5F);
        Movie c = new Movie(3, 2.5F);
        Movie d = new Movie(4, 4.6F);
        a.AddRelatedMovie(b);
        a.AddRelatedMovie(c);
        b.AddRelatedMovie(d);
        c.AddRelatedMovie(d);
 
        Console.WriteLine("getHighestRatedRelatedMovies(a,2) returns Movies 2,4");
        LogMovies(new MovieFinder().getHighestRatedRelatedMovies(a, 2));
        Console.WriteLine("getHighestRatedRelatedMovies(a,1) returns Movie 4");
        LogMovies(new MovieFinder().getHighestRatedRelatedMovies(a, 1));
        Console.WriteLine("getHighestRatedRelatedMovies(a,4) returns Movies 2,3,4");
        LogMovies(new MovieFinder().getHighestRatedRelatedMovies(a, 4));
        Console.WriteLine("getHighestRatedRelatedMovies(c,3) returns Movies 1,2,4");
        LogMovies(new MovieFinder().getHighestRatedRelatedMovies(c, 3));
        Console.WriteLine("getHighestRatedRelatedMovies(b,2) returns Movies 3,4");
        LogMovies(new MovieFinder().getHighestRatedRelatedMovies(b, 2));
    }
 
    private void LogMovies(IEnumerable<Movie> movies)
    {
        foreach(Movie m in movies)
        {
            Console.WriteLine($"Id {m.Id}, Rating {m.Rating}");
        }
    }
}

---

Thoughts on solution

• We have to visit all the related nodes anyway.
• We have to skip visiting previously visited nodes without adding extra flag on Movie class.

Approach 1-Depth first traverse, Sort and take N top movies

One of the method to solve this problem is given below. There are some more ways. May be I can  share later.

---

public IEnumerable<Movie> getHighestRatedRelatedMovies(Movie root, int numberOfMoviesToSelect)
{
        IList<Movie> movies = new List<Movie>();
        FillList(root, movies);
        movies.Remove(root);
        return movies.OrderByDescending(m => m.Rating).Take(numberOfMoviesToSelect);
} 
private void FillList(Movie node, IList<Movie> movies)
{
        if( movies.Contains(node) == false)
        {
            movies.Add(node);
            foreach(Movie m in node.RelatedMovies)
            {
                FillList(m, movies);
            }
        }
}

---

This is plain solution which satisfies the requirements. It may not be the high performing memory efficient logic. In next posts, lets see optimized version of this.

What if there are no looping constructs in your language?

Being a professional software engineer, we cannot say that we are done we cannot program without looping control flow. Developers who started their career in machine or assembly language don't get scared of this. Similarly who understood and practiced machine and assembly language in college in. They will simply use 'go to' along with if statement and get the things done.

Forgot to tell in the question 'go to' is banned as always.So how can we tackle it without goto.

Lets come to code. Here we are going to see the scenario in 2 famous languages C# and Javascript. Below is the code to display numbers 1,2,3...10 in descending order which is written using loops.

---

Javascript	C#
function LoopWithWhileKeyword(loopCount) {     while (loopCount > 0) {         logLine(loopCount);         loopCount -= 1;     } }	void LoopWithWhileKeyword(int loopCount) {     while (loopCount > 0)     {         logLine(loopCount);         loopCount -= 1;     } }

This is straight forward. The code to call these functions is omitted to get focus, Now lets think how we can avoid this loop.

What is happening here

If we step back and think we can see there are mainly 2 code blocks. 

• One block determines the continuation of execution.
• Second is the actual code to execute multiple times.

Some idea might have triggered in everybody's brain who had done some programming. Nothing but extracting those separate blocks to functions.

We can use 'if' statement to decide whether to continue execution or not based on the return value if we move the condition logic to function. Then how do we execute the repeatable code block again without go to?

Execute the same function again. All of us has tried this in college when dealing with Fibonacci series. If we call a function from inside same function we can simulate loops. Yes recursion!!!

Lets see the code below which is rewritten with recursion.

Javascript	C#
function LoopWithoutWhileKeyword(loopCount) {     WhileLoop(function () {         return loopCount > 0     },     function () {         logLine(loopCount);         loopCount -= 1;     }); } function WhileLoop(condition, action) {     if (condition()) {         action();         WhileLoop(condition, action);     } }	void LoopWithoutWhileKeyword(int loopCount) {     WhileLoop(         () => loopCount > 0,         () =>     {         logLine(loopCount);         loopCount -= 1;     }); } void WhileLoop(Func<bool> condition, Action action) {     if (condition())     {         action();         WhileLoop(condition, action);     } }

Good. Isn't it? For those who gets headache on seeing recursion please read the explanation.

Here the WhileLoop function accepts 2 functions. It checks whether I should continue or not. Similar to the evaluation inside the while loop condition check. If the result of condition check is true, it calls the action method which has the code  needs to be executed multiple times.

Then it calls the WhileLoop function again to repeat the cycle. Since the action function has the code to reduce the loop count, it will end when the loopCount becomes 0.

Higher Order Function

We learned a jargon in programming called Higher Order Function. Any function which accepts another function or returns a function can be called as higher order function. Thinking that its this simple refer wiki

Most of us might be thinking, why we learned the loops if functions can do the job of loops. Why there are many ways to do same thing in computer science?

Tail call optimization

Normally developers has a tendency to use new things learned in their day job because of excitement. They might have heard it or saw one demo which touched the good parts of the concept / feature / technology.

Before anybody apply this technique in your production app understand and test it properly. Let's test this code by given 100,000 to the function.

In C# your will encounter 

An unhandled exception of type 'System.StackOverflowException' occurred in mscorlib.dll

In browser, you will get 

Uncaught RangeError: Maximum call stack size exceeded

In my machine I got javascript error when the recursion reaches 17911 and c# 4.0 failed after 12202 iterations.

Don't think that this issue will occur always. There are technologies and languages in which this issue will never occur. If we we are getting this, that tells us that our run-time or compiler does not do tail call optimization. Google for what is tail call optimization.

Conditional insert query without duplicates

This is just a sql puzzle which raised during a long wait for the QA results on a build day.The puzzle seems simple.

1. Need to insert the records with out duplicates.
2. The query should consider all the fields.
3. The query should be single line.ie single statement of query execution.

At first it feels simple as a simple where query. But when we start writing we realize that can we write a where clause in a insert query? Simply speaking how can we write a conditional insert query in sql.After we play with the sql server and queries we automatically come to the below query.

INSERT INTO Person (Name , EMail,Id) 
select 'joy', 'joymon@gmail.com',1
WHERE (
    SELECT COUNT(*) 
    FROM Person 
    WHERE Name = 'joy' and email='joymon@gmail.com' and id=1) = 0;

The table can be created using.

CREATE TABLE [dbo].[Person](
    [Name] [nchar](50) NULL,
    [Id] int NOT NULL,
    [EMail] [nchar](50) NULL)

Calling explicitly implemented function using object of concrete class

The question : Are you able to call explicitly implemented method of an interface using object of concrete class?

This was one of the topic for discussion in our office, last week.Look at the below code.

public interface I1
{
    public void Foo();
}
public class C1 : I1
{
    #region I1 Members
    void I1.Foo()
    {
        Console.WriteLine("In Foo method");
    }
    #endregion
}

If we have a structure like above can we call the method Foo as follows?

C1 c = new C1(); c.Foo();

In the initial look we may think what is wrong in it? But this is not possible.Most of us were really new to this particular scenario because we are all working in VB.Net for last one year.There were so many comments such as bug in .net,.net is not good etc…But after a while we got the solution from another question.What was that question?

In the above example add one more interface say I2 with same method Foo() and implement the same in class C1.Now if we try to call method Foo() by using variable of class C1 obviously there will be an ambiguity and the solution to avoid that state is the limitation of this call.

Everybody became happy like ending of an old Indian movie.

In VB.Net this is avoided by using the implements keyword.ie function Foo1() in class can implement an interface function Foo() and hence the concrete class variable can call the interface method as Foo1().See the code snippet below.

Public Interface I1
    Sub Foo()
End Interface
Public Interface I2
    Sub Foo()
End Interface
Public Class C1
    Implements I1, I2
    Public Sub Foo() Implements I1.Foo
    End Sub
    Public Sub Foo1() Implements I2.Foo
    End Sub
End Class

Happy coding...

Odd or even

Last couple of weeks were comparatively cool in the office because we had delivered a stable build of our application to QA team.Like in any other software company, the free hours turned into the learning sessions.Some peoples started learning new technologies and some utilized the time to strengthen their basics in programming.

Our circle is into refreshing the programming logics.Everybody were into screen development in the project and started forgetting the real coding which does problem solving using logics.The refreshing session started with famous sql questions such as how to find out the duplicates in a table,how to insert values into table without duplication using single line query etc…After some time it reached to .net coding.The first question was simple.

Display the string “Odd” or “Even” for a given number without using any conditional operators,looping and built-in or custom methods .NO GOOGLING!!!

Oh its simple…The first response was this.But after sometime people recognized that they forget even how to find whether a number is odd or even..ie they forgot the operator “%”.Remember that they are the senior developers who are designing their tracks.

If one person learns how to ride a bicycle or learns swimming he will not forget it in his life time.In his older ages he may not perform due to health problems.But the knowledge will be there with him.The same principle applies in the case of programming too…It took some time to get answers.

The first answer was the traditional one.Use an array.

MessageBox.Show(new string[] { "Even", "Odd" }[inputVale % 2]);

Next answer was to use enumeration

public enum Result
{
    Even=0,
    Odd=1
}
MessageBox.Show(((Result)(inputVale % 2)).ToString());

There is a small confusion…ToString() is a built in function???The next answer was also using function.

MessageBox.Show((inputVale % 2).ToString().Replace("0","Even").Replace("1","Odd"));

A humble request to all developers who are working on the screen development, please don’t spoil your real coding skills…