Posted on

in order traversal

this was the geeks for geeks problem of the day today


/* A Binary Tree node

class Node {
    int data;
    Node left, right;
   Node(int item)    {
        data = item;
        left = right = null;
    }
}
*/
class Solution {
    ArrayList<Integer> result = new ArrayList<>();
    // Function to return a list containing the inorder traversal of the tree.
    ArrayList<Integer> inOrder(Node root) {
        // Code
        
        inOrderHelper(root);
        return result;
    }
    
    private void inOrderHelper( Node root ){
        if( root == null ) return;
        
        inOrderHelper( root.left );
        result.add(root.data);
        inOrderHelper( root.right );

    }
    
}
Posted on

Find the Number of Distinct Colors Among the Balls

You are given an integer limit and a 2D array queries of size n x 2.

There are limit + 1 balls with distinct labels in the range [0, limit]. Initially, all balls are uncolored. For every query in queries that is of the form [x, y], you mark ball x with the color y. After each query, you need to find the number of distinct colors among the balls.

Return an array result of length n, where result[i] denotes the number of distinct colors after i<sup>th</sup> query.

Note that when answering a query, lack of a color will not be considered as a color.

Example 1:

Input: limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]

Output: [1,2,2,3]

Explanation:

  • After query 0, ball 1 has color 4.
  • After query 1, ball 1 has color 4, and ball 2 has color 5.
  • After query 2, ball 1 has color 3, and ball 2 has color 5.
  • After query 3, ball 1 has color 3, ball 2 has color 5, and ball 3 has color 4.

Example 2:

Input: limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]

Output: [1,2,2,3,4]

Explanation:

  • After query 0, ball 0 has color 1.
  • After query 1, ball 0 has color 1, and ball 1 has color 2.
  • After query 2, ball 0 has color 1, and balls 1 and 2 have color 2.
  • After query 3, ball 0 has color 1, balls 1 and 2 have color 2, and ball 3 has color 4.
  • After query 4, ball 0 has color 1, balls 1 and 2 have color 2, ball 3 has color 4, and ball 4 has color 5.

class Solution {
    public int[] queryResults(int limit, int[][] queries) {
        int[] result = new int[queries.length];
        HashMap<Integer, Integer> ballMap = new HashMap<>();
        HashMap<Integer, Integer> colorMap = new HashMap<>();
        for( int i = 0; i < queries.length; i++ ) {
            int[] q =  queries[i];
            int ball = q[0];
            int color = q[1];
            if( ballMap.containsKey( ball )){
                
                int prevColor = ballMap.get( ball );
                colorMap.put( prevColor, colorMap.get(prevColor)-1);
                
                if( colorMap.get( prevColor) == 0 )
                    colorMap.remove(prevColor);
                
            }
            
            ballMap.put(ball, color);
            colorMap.put( color , colorMap.getOrDefault(color, 0) + 1);
            result[i] = colorMap.size();
            
        }
        return result;
    }
}

Posted on

401. Binary Watch

A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

  • For example, the below binary watch reads "4:51".

Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.

The hour must not contain a leading zero.

  • For example, "01:00" is not valid. It should be "1:00".

The minute must consist of two digits and may contain a leading zero.

  • For example, "10:2" is not valid. It should be "10:02".

Example 1:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

Example 2:

Input: turnedOn = 9
Output: []

Solution

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> result = new ArrayList<>();

        // Iterate over possible hours (0 to 11)
        for (int hour = 0; hour < 12; hour++) {
            // Iterate over possible minutes (0 to 59)
            for (int minute = 0; minute < 60; minute++) {
                // Count the number of bits turned on
                int bitsOn = Integer.bitCount(hour) + Integer.bitCount(minute);
                
                // If the total bits on matches the turnedOn count
                if (bitsOn == turnedOn) {
                    // Format the time as "H:MM"
                    result.add(String.format("%d:%02d", hour, minute));
                }
            }
        }
        return result;
    }
}
Posted on

Letter Combinations of a phone number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Java Solution

class Solution {
     public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return new ArrayList<>();
        }
        Map<Character, String> digitToLetters = new HashMap<>();
        digitToLetters.put('2', "abc");
        digitToLetters.put('3', "def");
        digitToLetters.put('4', "ghi");
        digitToLetters.put('5', "jkl");
        digitToLetters.put('6', "mno");
        digitToLetters.put('7', "pqrs");
        digitToLetters.put('8', "tuv");
        digitToLetters.put('9', "wxyz");

        List<String> result = new ArrayList<>();
        backtrack(digits, 0, new StringBuilder(), result, digitToLetters);
        return result;
    }

    private void backtrack(String digits, int index, StringBuilder path, List<String> result, Map<Character, String> digitToLetters) {
        if (index == digits.length()) {
            result.add(path.toString());
            return;
        }

        char digit = digits.charAt(index);
        String letters = digitToLetters.get(digit);
        for (char letter : letters.toCharArray()) {
            path.append(letter);
            backtrack(digits, index + 1, path, result, digitToLetters);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

C++ Solution

//
// Created by robert on 12/20/24.
//
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;
void backtrack(string & digits, const int index, string & current, vector<string> & result, const unordered_map<char,string> & map) {
if (digits.length() == index) {
result.push_back(current);
return;
}
char digit = digits[index];
string letters = map.find(digit)->second;
for( char letter : letters ) {
current.push_back(letter);
backtrack( digits, index+1, current, result, map );
current.pop_back();
}

}
vector<string> letterCombinations(string digits) {
vector<string> result;
string current;

if (digits.empty()) return result;

unordered_map<char, string> map;

map.insert(make_pair('2', "abc"));
map.insert(make_pair('3', "def"));
map.insert(make_pair('4', "ghi"));
map.insert(make_pair('5', "jkl"));
map.insert(make_pair('6', "mno"));
map.insert(make_pair('7', "pqrs"));
map.insert(make_pair('8', "tuv"));
map.insert(make_pair('9', "wxyz"));


backtrack(digits, 0, current, result, map);
return result;

}

int main(){
vector<string> result = letterCombinations("23");
for (const auto & i : result) {
cout << i << endl;
}
}
Posted on

PhantomJS + Jasmine vs Selenium Web Driver

Recently I started using phantomjs, which is a headless browser based on web-kit, for automated JavaScript testing.

Now when I was playing around with Selenium @ ABC Family, I really liked how the web driver started a browser instance and executed the test suite within it. This means Selenium is actually a better, or closer match, in terms of automated testing, because the browser is not headless. Although I don’t know all the internals of Selenium, that was my first impression.

But the positive thing about using the grunt, jasmine, phatomjs combo to run unit tests, is that we can start a jasmine server, which lets you check your code in many other browsers. That means you are not limited by the Selenium browser library of supported browsers. You can actually pick up your phone, or tablet, and point the browser to the test server, and see how your code executes on that particular system ( Device, OS, Browser). True this is not something that can be used with 100% automation on its own, but it does give you the freedom to experiment and see the behavior of code in a large variant of systems. This means that with services like DeviceAnywhere, you maybe able to cover and automate the testing of all kinds of strange fringe devices.

Something else that is interesting is that in Selenium, you can’t really hook, or spyOn member methods. While a lot of the tests written in jasmine, can be executed similarly with Selenium, because they just check for a class that has been added or removed from a DOM element, jasmine provides more integration with the code base.

The classes are loaded, along with a html fixture, and then executed. This is how the server works, by creating a #sandbox div where it loads the html fixtures for each test, loading the javascript into the page, instantiating the class, and then begins execution of the test suite. Now the opposite argument is, again, this is not how the site would be like in the wild. Other components would live on the page. So Selenium gives a more accurate assessment of how the code actually works on the end user’s system, since it loads the entire site, via a client side browser.

Now as a Computer Scientist, Java vs JavaScript argument is mute to me when it comes to choosing a “platform”. Because ultimately its like comparing apples to oranges, when you really look at the language structure and what they are designed to accomplish. Two different tools for different jobs. As a front end developer, who wants everything to be easy, there is definitely a benefit to having a unified language for creating build tools, server side applications, and user interfaces. So at some shops, where ROI is important, it’s a good idea to keep the tools all in the skill set of the human resources currently on staff. For UI people, this means JavaScript > Java. This is a good argument for using tools like grunt, and phantomjs, and jasmine, since they are all JavaScript based, they empower the new kingmakers (Open Source Developers).

Which is actually still not a big argument against Selenium Web Driver, because Java is very easy to install, you are not going to be making many changes to the driver itself, and the interface for running the Selenium Web Driver could potentially still be written in JavaScript.

Therefore the argument could be made that Selenium and Jasmine don’t have to be mutually exclusive, while it would bloat the build time to include both systems, a separate box, and process, could be used, to test with both, or the one that is missing in the build process.

While its too soon for me to say, “Dude, Selenium is old news.” I can say that all this merits more experimentation and testing. A very exciting time for Computer Scientists indeed. So much Brain Candy!