DEV Community: Amanda Fawcett

JavaScript Map and Set Tutorial: how to use new built-in classes

Amanda Fawcett — Tue, 20 Apr 2021 17:06:00 +0000

In the past, JavaScript was limited when it came to collections. While other languages offer lists, sets, associative maps, and dictionaries, JavaScript only offered only arrays. JavaScript programmers had to come up with workaround for creating sets or maps, which made the code hard to maintain.

Now, with ES6, JavaScript offers new built-in classes for sets and maps that make programming far easier to maintain. In this tutorial, we will introduce you to map and set in detail along with code examples, use cases, and hands-on exercises. This tutorial is ideal for JavaScript developers who want to modernize their JavaScript skills.

This tutorial at a glance:

What is map?
How to use map
What is set?
How to use set
Hands-on exercise with map
What to learn next

What is `map`?

Prior to ES6, JavaScript developers used objects to map keys to values. However, using an object as a map has its limitations. For example:

There is no foolproof way to iterate over keys, and the keys() method converts fields to strings, which leads to collision of keys.
There is no simple way to add new keys and values

ES6 introduced some new built-in classes, including a collection type called Map, which can hold key-value pairs of any type. Unlike the object approach, the new Map object can remember key insertion order.

In simple terms, a JavaScript Map is an associative collection of distinct keys and values. Both keys and values can be any primitive or object. This is a significant data structure with many valuable uses.

Note: A WeakMap is similar to a Map but all keys of a WeakMap are objects.

To create a new Map, we use the following syntax:


let map = new Map([iterable]);

Let's put this into practice with a more complex example. Below we have a Map that holds names as keys and scores as values.

'use strict';

//START:DEFINE
const scores = 
  new Map([['Sara', 12], ['Bob', 11], ['Jill', 15], ['Bruce', 14]]);

scores.set('Jake', 14);

console.log(scores.size);
//END:DEFINE

Output: 5

The scores Map has been initialized with names and scores. The initial data may be any iterable with a pair of keys and values.
We add a key and value to the Map using the set() method (line 7)
To figure out how many keys are currently in the Map, we use the size property (line 9)

Note: Map.has(key) above will return the Boolean value to indicate if the element associated with a specified key is in the map

How to use map

Once we know how to create maps with JavaScript, there are a lot of things we can do with them.

Iterate through maps

First, let's learn about iteration through maps. There are 3 methods we can use:

map.keys(): returns an iterable for keys
map.entries(): returns an iterable for entries [key, value]
map.values(): returns an iterable for values

We can iterate over the collection of keys and values with the entries() method, which returns an iterable, so we can use the enhanced for loop along with destructuring.

For example, below, we extract the name and score for each key-value pair:

'use strict';

//START:DEFINE
const scores = 
  new Map([['Sara', 12], ['Bob', 11], ['Jill', 15], ['Bruce', 14]]);

scores.set('Jake', 14);
//END:DEFINE                                                                   

for(const [name, score] of scores.entries()) {
  console.log(`${name} : ${score}`);
}

Output:
Sara : 12
Bob : 11
Jill : 15
Bruce : 14
Jake : 14

We can also use the forEach method, which is an internal iterator.

'use strict';

//START:DEFINE
const scores = 
  new Map([['Sara', 12], ['Bob', 11], ['Jill', 15], ['Bruce', 14]]);

scores.set('Jake', 14);
//END:DEFINE                                                                   

scores.forEach((score, name) => console.log(`${name} : ${score}`));

Output:
1.88s
Sara : 12
Bob : 11
Jill : 15
Bruce : 14
Jake : 14

The first parameter that the function receives is the value for a key that appears as the second parameter. The same forEach() method can be used to iterate over only the values:

'use strict';

//START:DEFINE
const scores = 
  new Map([['Sara', 12], ['Bob', 11], ['Jill', 15], ['Bruce', 14]]);

scores.set('Jake', 14);
//END:DEFINE                                                                   

scores.forEach(score => console.log(score));

Output:
1.85s
12
11
15
14
14

If you receive only one parameter, it will be the value, and if you receive two parameters, then it will stand for the value and key for each key-value pair.

Initialize a map with an iterable object

You can also pass an iterable object to the Map() constructor:

let userRoles = new Map([
    [sarah, 'admin'],
    [bob, 'editor'],
    [jill, 'subscriber']
]);

Get an element from a map by key

We can get an elements from a map by key with the get() method:

But if you pass a key that is not in that map, the it will return undefined.

userRoles.get(sarah); // admin

But if you pass a key that is not in that map, the it will return undefined.

let foo = {name: 'Foo'};
userRoles.get(foo); //undefined

Get the number of elements in the map

We can use the size property to get the number of elements in our maps.

console.log(userRoles.size); // 3

Convert map keys or values to array

At times, you may want to work with an array instead of an iterable object. We can use the spread operator to convert keys for each element into a new array.

var keys = [...userRoles.keys()];
console.log(keys);

This piece of code will convert the values of elements to an array:

var roles = [...userRoles.values()];
console.log(roles);

Other important Map methods

clear(): removes elements from the map object.
map.set(key, value): stores the value by the key
- delete(key): removes a specific element (as specified by the key)
set(key, value): sets the value for the key and returns the map object. Can be chained with other methods.
- forEach(callback[, thisArg]): invokes a callback for each key-value pair in insertion order. The thisArg parameter is optional and sets the this value for each callback.
has(key): returns true if a value associated with the key exists, otherwise, false.
keys(): returns a new iterator with the keys for elements in insertion order.
values(): returns a new iterator object with the values for each element in insertion order.
map.size: returns the current element count

What is `set`?

Set is another new collection introduced by ES6. The Array class of JavaScript can work with ordered collection of data, but not so well with unordered collections or when values held in the collection are unique. That's why JavaScript introduced Set.

A set is a unique collection of primitives and objects, and duplicates are not allowed. We can either create an empty set and add objects, or we can initialize a set with the contents of an iterable (like an array).

Let's explore this with an example. Below, we have a set of names with five values. One of the values is not included in the set due to duplication.

'use strict';

//START:CREATE
const names = new Set(['Jack', 'Jill', 'Jake', 'Jack', 'Sara']);
//END:CREATE

//START:SIZE
console.log(names.size);
//END:SIZE

Output: 4

We can add elements to an existing set, like below:

names.add('Matt');

The add() method returns the current Set, which is useful for chain operations, such as more calls to add() or other methods of Set:

names.add('Kate')
  .add('Kara');

How to use `set`

Once we figure out how to create sets, it's easy to work with them. First, let's look at the built-in functions for sets:

has(): to check if a set has a particular element.
clear(): to empty an existing set or remove an existing element using the delete() method.
keys(): to get all the values from a Set
entries(): to iterate over a Set using the enhanced for loop, like below:

'use strict';

//START:CREATE
const names = new Set(['Jack', 'Jill', 'Jake', 'Jack', 'Sara']);
//END:CREATE

//START:ADD
names.add('Mike');
//END:ADD

//START:ADD2
names.add('Kate')
  .add('Kara');
//END:ADD2

console.log(names.has('Brad'));                                         

console.log(names.entries());
console.log(names.keys());
console.log(names.values());

//START:ITERATE1
for(const name of names) {
  console.log(name);
}
//END:ITERATE1

`filter`/`map` with sets

Set does not yet offer methods like filter() and map(), but we can create an array from the set and use a functional style methods on that new array.

For example, below we use methods filter(), map(), and forEach() to pick only names that start with J and then transform them to uppercase.

'use strict';

//START:CREATE
const names = new Set(['Jack', 'Jill', 'Jake', 'Jack', 'Sara']);
//END:CREATE

//START:ADD
names.add('Mike');
//END:ADD

//START:ADD2
names.add('Kate')
  .add('Kara');
//END:ADD2


//START:FILTER
[...names].filter(name => name.startsWith('J'))
  .map(name => name.toUpperCase())
  .forEach(name => console.log(name));
//END:FILTER

Output:
JACK
JILL
JAKE

Get the size of a Set

Use the size property of the Set object to return its size.

let size = chars.size;
console.log(size);//  3

Remove elements from a set

To remove an element from a set, use the delete() method.

chars.delete('f');
console.log(chars); // Set {"a", "b", "c", "d", "e"}

And to delete all elements of a set, use the clear() method:

chars.clear();
console.log(chars); // Set{}

Invoke a callback function on each element

To invoke a callback on every element of your set, use the forEach() method.

roles.forEach(role => console.log(role.toUpperCase()));

Other important Set methods

new Set(iterable): creates a set.
set.add(value): adds a given value and returns the set
set.has(value): returns true if a value exists in the set, otherwise, returns false.
set.clear(): removes everything from a set

Hands-on exercise with `map`

To solidify your learning, let's do a hands-on exercise with map in JavaScript. Use Map to get the desired output as given below. When creating an object of createTodo(), it should return a map element.

Input calls	Output
`console.log(todo.get('learn JavaScript'));`	done
`console.log(todo.get('write elegant code'));`	work-in-progress
`console.log(todo.get('automate tests'));`	work-in-progress
`console.log(completedCount(todo));`	1

The solution to this challenge is given below.

'use strict';

const createTodo = function() {
  const todo = new Map();
  todo.set('learn JavaScript', 'done');
  todo.set('write elegant code', 'work-in-progress');
  todo.set('automate tests', 'work-in-progress');

  return todo;
}; 

const completedCount = function(map) {
  return [...map.values()]
    .filter(value => value === 'done')
    .length;
};

const todo = createTodo(); //Returns a Map

Solution Breakdown

Start by creating a map element. The Map object todo is created on line 4 using the built-in class. You can see that the map object, todo is calling Map.get() with different keys to get their values. This means that we need to add all the keys and values.

We add the new element in todo with the keys and associated values. On lines 5-7, we add the new elements by setting values for the keys.

For completedCount(), we define a new function with a map object parameter. The function will return the count of tasks that are completed. So, essentially, we are filtering all the values of elements in the map object to get the elements with the value equal to done (see line 14).

On line 15, the length property is used to get the count of the special elements.

What to learn next

Map and set are valuable additions to JavaScript, and they will make your code cleaner and easier to maintain. Now that you have a solid understanding of map and set, you're ready to tackle other features added in ES6 and beyond.

Some concepts to cover next to modernize your JavaScript are:

Async and Await (promises)
Metaprogramming
Object literals
Arrow functions
and more

To get up to speed on JavaScript's features, check out Educative's course Rediscovering JavaScript: ES6, ES7 & ES8. This course covers the modern JavaScript features to make your code elegant, concise, expressive, and less error prone. You will start by learning the basic features of modern JavaScript, and in the second half, you will dive deep into complex features, like destructuring, literals, inheritance, modules, promises, and metaprogramming.

By the end of this course, you will be able to add new features with minimum effort and write code more efficiently!

Happy learning!

Continue reading about JavaScript

Ruby Tutorial for Python Programmers: how to make the switch

Amanda Fawcett — Tue, 20 Apr 2021 16:52:40 +0000

Ruby is a general-purpose, dynamic, open source programming language that focuses on simplicity and productivity. The Ruby programming language is frequently compared to Python for their similarities. Many developers say that learning Ruby is easier if you know Python due to their similarities. However, these two languages differ in major ways.

We've created this basic introduction to help you make the transition from Python to Ruby. We'll go over their main differences and then take a dive into Ruby's syntax so you can get hands-on with Ruby code quickly.

Here's what we'll cover today:

Ruby vs Python
Summary of Main Code Differences
Hello World with Ruby
Ruby Syntax Quick Guide
What to learn next with Ruby

Ruby vs Python

Ruby and Python are both popular programming languages known for their speed, simplicity, and user-friendly syntax. Both languages are flexible, object-oriented , dynamic, and have a lot of useful frameworks and libraries to use, particularly for web applications and web development (Ruby on Rails for Ruby or Django for Python).

Ruby is a high-level, interpreted programming language, created in 1995 by Yukihiro Matsumoto. His goal was to make an object-oriented scripting language that improved on other scripting languages of the time.

Ruby also allows for functional programming and is known for being very similar to written human languages, making it easy to learn.

Python is an interpreted, high-level general-purpose language, created by Guido van Rossum with the goal of code readability. Python is know well-loved for its robust standard library.

Ruby	Python
No primitive data types. Everything is an object.	Has primitive types and objects
Mixins can be used	Mixins cannot be used
Less available functions. Relies mostly on methods.	Lots of available functions
Cannot modify built-in classes	Can modify built-in classes
Supports Tuples with Rinda. Other collections include Arrays, Hash, Set, and Struct.	Supports Tuples, Sets, Dictionary (Hash), and Lists
Iterators less common	Iterators are very common

Career

Both languages are used by big companies. Companies that use Python include YouTube, Instagram, Spotify, Reddit, Dropbox, while Ruby is used at Hulu, Basecamp, GitHub, and Airbnb. Ruby developers also tend to make higher salaries than Python developers. StackOverflow's 2020 survey lists Ruby's global average salary at $71k and Python's at $59k.

Both Ruby and Python offer higher annual salaries than other software development languages, including PHP, JavaScript, and Java.

Machine Learning

Python is currently the go-to language for machine learning (ML) and artificial intelligence (AI) due to its extensive libraries and visualization tools. Ruby does offer some competitive options, but there is a long way to go before it will hold a torch to Python. So, if you are looking to work in data science, Python is the winner.

Web Frameworks

The main web frameworks for both Ruby and Python, Django and Ruby on Rails, are rather similar. Both are based on the classic model-view-controller (MVC) pattern, and they both provide similar repositories (PyPi for Python and RubyGems for Ruby). Both frameworks perform well and are easy to learn.

Testing Environment

Test-driven development (TDD) is pretty standard for both Ruby and Python, but Ruby does offer behavior-driven development (BDD) while Python does not, which may be useful in some cases

Community

Both languages have large, active communities, which Python's community being a bit larger, namely because Ruby is most popular for its development tool Ruby on Rails. Both communities seem to be equally active and supportive.

One benefit to Ruby is that there are unique Ruby forums and job boards since the language is more specialized in some regards.

Summary of Main Code Differences

Now that we understand the difference between Ruby and Python at a high level, let's dive into the main code differences between the two. We've compiled the main things that differ from Python below.

In the Ruby programming language:

Strings are mutable
You can make constants
Parentheses for most method calls are optional
There’s only one mutable list container (Array)
There are no “new style” or “old style” classes
Only false and nil evaluate to false, and everything else is true
You never directly access attributes. Instead, we use method calls.
We use elsif instead of elif
We use require instead of import
We use mixins instead of multiple inheritance
yield executes another function that is passed as the final argument, then it resumes
We use public, private, and protected for access

Hello World with Ruby

Now that we understand how Ruby and Python differ at the code level, let's look at some actual Ruby code, starting with the classic Hello World program. Take a look below and note how simply Ruby's syntax is here.

puts "Hello World!"

Here, the puts keyword is used to print. Remember: Ruby's code is very readable, designed to emulate spoken English language.

There's even a simpler way to do this. Ruby comes with a built-in program that will show the results of any statements you feed it, called Interactive Ruby (IRB). This is the best way to learn Ruby. First, open IRB:

macOS: open Terminal and type irb. Hit enter.
Linux: open up a shel, type irb, and hit enter.
Windows: open Interactive Ruby from the Start Menu (see the Ruby section)

If you type:

"Hello World"

You will get the following:

irb(main):001:0> "Hello World"
=> "Hello World"

The second line tells us the result of the last expression. We can print this using the puts command we learned before.

irb(main):002:0> puts "Hello World"
Hello World
=> nil

Here, => nil is the result of the expression, since puts always returns nil.

Ruby Syntax Quick Guide

Let's now quickly go over the basics of Ruby's syntax that may be different from what you're used to in Python. Note how Ruby differs and how it is similar as you read.

Variable Assignment

In Ruby, you assign a name to a variable using the assignment operator =, like so:

puts number = 1

Here is a list of the different kinds of variables in Ruby:

Local variables (something)
Instance variables (@something)
Constants (Something or SOMETHING)
Global variables ($something)

Identifiers and Keywords

Keywords and identifiers are similar to Python. Identifiers are case sensitive, and they may consist of alphanumeric characters and underscore _.

Ruby's reserved keywords include the following:

Strings

In Ruby, a string is a sequence of characters inside quotation marks " ". We can also use single quotation marks.

You can concatenate strings with the plus sign +.

puts "snow" + "ball"

Output: snowball

In Ruby, multiplying a String by a number will repeat a String that many times.

puts "Ruby" * 3

Output: RubyRubyRuby

Some important methods for Ruby strings include:

size
empty?
include?
gsub
split

Pro Tip: Ruby's percentage sign % shortcut can be used with strings and arrays

%w will create an array of strings

%i with create an array of symbols

%q will create a string without quotation marks

Hashes

In Ruby, you can create a Hash by assigning a key to a value with =>. We separate these key/value pairs with commas and enclose the whole thing with curly braces.

{ "one" => "eins", "two" => "zwei", "three" => "drei" }

This defines a Hash with three key/value pairs, so we can look up three values (the strings "eins", "zwei", and "drei") using three different keys (the strings "one", "two", and "three").

Some important methods for Ruby hashes include:

key?
fetch
merge
new (for default values)

Array

In Ruby, we create an Array by separating values with commas and enclosing this list with square brackets, like so:

[1, 2, 3]

Note: Ruby Arrays always keep their order

Like in Python, there are all sorts of things you can do with Arrays. The most important methods being:

size
empty?
push / pop
join
flatten

Here is an example of the intersection operator &, which finds the intersecting parts of our arrays:

puts ([1, 2, 3] & [2, 3, 4])

Output: 2 3

Parenthesis

In Ruby, parenthesis and semicolons are not required, but we can use them. However, we follow these basic rules:

Do use parenthesis with method arguments: def foo(a, b, c)
Do use parenthesis to change the priority of an operation: (a.size + b.size) * 2
Don't use parenthesis when defining a method that has no arguments: def foo

Commenting

There are three main ways we can add comments to a Ruby program.

# Single line comment

# Multiple
# Lines

=begin
Block fashion
Commenting
=end

Methods

In Ruby, we define methods using the def keyword followed by method_name. IT ends with the end keyword.

def method_name
# Statement 
# Statement 
.
.
end

We pass parameters to our methods in parentheses.

def method_name(var1, var2, var3)
# Statement 
# Statement 
.
.
end

Classes

In Ruby, we create classes using the class keyword followed by the name of the class.

class Class_name

end

Note: The first letter of your class names should be a capital letter.

In Ruby, objects are created with the new method.

object_name = Class_name.new

Conditionals

Conditional statements are similar to most other languages with a few slight differences. Take a look at the examples below to get at sense of how they look in Ruby.

number = 5

if number.between?(1, 10)
  puts "The number is between 1 and 10"
elsif number.between?(11, 20)
  puts "The number is between 11 and 20"
else
  puts "The number is bigger than 20"
end

Output: The number is between 1 and 10

Note: The elsif and else statements are optional. You can have an if statement without elsif or else branches, an if statement only with an else, or you could have an if statement with one or more elsif statements.

Ruby also has a shorthand for working with conditional statements. So, we could write this bit of code:

number = 5

if number.odd?
  puts "The number is odd."
end

As this instead:

number = 5
puts "The number is odd." if number.odd?

What to learn next with Ruby

Now that you know the basics of Ruby and know how it differs from Python, you're ready to cover more advanced topics. We recommended studying the following concepts next:

Ruby inheritance
Using Ruby libraries
Nested arrays
Ruby blocks

To get started with these concepts and get hands-on with Ruby, check out Educative's course Learn Ruby from Scratch. This introductory course offers tons of hands-on practice on all the need-to-know topics, including variables, built-in classes, objects, conditionals, blocks and much more!

By the end, you'll be a confident Ruby developer, ready to take on complex projects!

Happy learning!

Continue reading about Ruby

Top 30 Apple Coding Interview Questions (with solutions)

Amanda Fawcett — Thu, 01 Apr 2021 17:50:13 +0000

Working at Apple is a dream for many developers, but preparing for coding interviews is no easy task. To make your life easier, we’ve compiled the top 30 interview questions you can expect during a technical interview with Apple.

We start with an overview of the interview process for software engineering and then break down the top Apple interview questions with in-depth code solutions and complexity measures. We’ll offer our solutions in C++.

This guide at a glance:

Apple interview process overview
Arrays and graphs questions
Linked Lists questions
Trees questions
Strings questions
Dynamic programming questions
Math, stats, and backtracking
Searching and design questions
Behavioral questions
Tips for preparing for interviews

Apple interview process overview

Apple’s software engineer interview process differs from other larger tech companies, like Amazon, due to the number of interviews they hold and their on-site process.

If you are asked to interview at Apple, the process generally looks like this:

Prescreen with Recruiter: It will take about a week from resume submission to first contact. A recruiter will usually reach out over LinkedIn or email to set up a time for a phone call. This phone screen will last from 15-30 minutes, and the questions will not be overly technical. You could expect questions like Why do you want to work for Apple? or What’s your favorite Apple product or service?
Technical phone interview: Usually a week later, they will schedule your next technical phone interview. There will be one or two technical phone screens with questions about your resume and a coding question on data structures and algorithms. The coding interviews are about 45-60 minutes, with 30 minutes to complete the challenge.
On-site interview: The onsite interview will last about 6 hours. You'll meet with 8-12 Apple employees, and interviews will be a mix of behavioral, domain knowledge, and coding challenges. Each interview is about 45 minutes to an hour where you will be posed with technical problems. Behavioral questions are also very important for hiring managers.

Data structures you should know: Arrays, Linked Lists, Stacks, Queues, Trees, Graphs, Heaps, Hash sets, Hash maps

Algorithms you should know: Depth first search, Breadth first search, Binary search, Quicksort, Mergesort, Dynamic programming, Divide and conquer

Arrays and graphs questions

Determine sum of three integers

The goal of this exercise is to determine if the sum of three integers is equal to the given value.

Problem statement: Given an array of integers and a value, determine if there are any three integers in the array whose sum equals the given value.

Consider this array and the target sums.

bool find_sum_of_two(vector<int>& A, int val,
  size_t start_index) {
  for (int i = start_index, j = A.size() - 1; i < j;) {
    int sum = A[i] + A[j];
    if (sum == val) {
      return true;
    }

    if (sum < val) {
      ++i;
    } else {
      --j;
    }
  }

  return false;
}

bool find_sum_of_three_v3(vector<int> arr,
  int required_sum) {

  std::sort(arr.begin(), arr.end());

  for (int i = 0; i < arr.size() - 2; ++i) {
    int remaining_sum = required_sum - arr[i];
    if (find_sum_of_two(arr, remaining_sum, i + 1)) {
      return true;
    }
  }

  return false;
}

int main(){
    vector<int> arr = {-25, -10, -7, -3, 2, 4, 8, 10};

    cout<<"-8: " <<find_sum_of_three_v3(arr, -8)<<endl; 
    cout<<"-25: "<<find_sum_of_three_v3(arr, -25)<<endl;
    cout<<"0: " <<find_sum_of_three_v3(arr, 0)<<endl;
    cout<<"-42: " <<find_sum_of_three_v3(arr, -42)<<endl; 
    cout<<"22: " <<find_sum_of_three_v3(arr, 22)<<endl; 
    cout<<"-7: " <<find_sum_of_three_v3(arr, -7)<<endl;
    cout<<"-3: " <<find_sum_of_three_v3(arr, -3)<<endl; 
    cout<<"2: " <<find_sum_of_three_v3(arr, 2)<<endl; 
    cout<<"4: " <<find_sum_of_three_v3(arr, 4)<<endl; 
    cout<<"8: " <<find_sum_of_three_v3(arr, 8)<<endl; 
    cout<<"7: " <<find_sum_of_three_v3(arr, 7)<<endl; 
    cout<<"1: " <<find_sum_of_three_v3(arr, 1)<<endl;

    return 0;
}

In this solution, we sort the array. Then, fix one element e and find a pair (a, b) in the remaining array so that required_sum - e is a + b.

Start with first element e in the array and try to find such a pair (a, b) in the remaining array (i.e A[i + 1] to A[n - 1]) that satisfies the condition: a+b = required_sum - e. If we find the pair, we have found the solution: a, b and e. Now we can stop the iteration.

Otherwise, we repeat the above steps for all elements e at index i = 1 to n - 3 until we find a pair that meets the condition.

Runtime Complexity: Quadratic, O(n^2)

Memory Complexity: Constant, O(1)

Merge overlapping intervals

The goal of this exercise is to merge all the overlapping intervals of a given list to produce a list that has only mutually exclusive intervals.

Problem statement: You have an array (list) of interval pairs as input where each interval has a start and end timestamp, sorted by starting timestamps. Merge the overlapping intervals and return a new output array.

Consider an input array below. Intervals (1, 5), (3, 7), (4, 6), (6, 8) are overlapping so they should be merged to one interval (1, 8). Similarly, intervals (10, 12) and (12, 15) are also overlapping and should be merged to (10, 15).

class Pair{
  public:
    int first, second;
    Pair(int x, int y){
      first = x;
      second = y; 
    }
};

vector<Pair> merge_intervals(vector<Pair>& v) {

  if(v.size() == 0) {
    return v;
  }

  vector<Pair> result;
  result.push_back(Pair(v[0].first, v[0].second));

  for(int i = 1 ; i < v.size(); i++){
    int x1 = v[i].first;
    int y1 = v[i].second;
    int x2 = result[result.size() - 1].first;
    int y2 = result[result.size() - 1].second;

    if(y2 >= x1){
      result[result.size() - 1].second = max(y1, y2);
    }
    else{
      result.push_back(Pair(x1, y1));
    }
  }
  return result;
}

int main() {
  vector<Pair> v {
                  Pair(1, 5),
                  Pair(3, 7),
                  Pair(4, 6),
                  Pair(6, 8),
                  Pair(10, 12),
                  Pair(11, 15)
                  };

  vector<Pair> result = merge_intervals(v);

  for(int i = 0; i < result.size(); i++){
    cout << "[" << result[i].first << ", " << result[i].second << "] ";
  }
}

This problem can be solved with a linear scan algorithm. The list of input intervals is given, and we’ll keep merged intervals in the output list. For each interval in the input list:

If the input interval is overlapping with the last interval in the output list, merge these two intervals and update the last interval of the output list with the merged interval.
Otherwise, add an input interval to the output list.

Runtime complexity: Linear, O(n)

Memory complexity: Linear, O(n)

Clone a Directed Graph

The goal of this exercise is to clone a directed graph and print an output graph using hash table and depth first traversal.

Problem statement: Given the root node of a directed graph, clone the graph by creating a deep copy. The cloned graph will have the same vertices and edges.

struct Node {
  int data;
  list<Node*> neighbors;
  Node(int d) : data(d) {}
};

Node* clone_rec(Node* root, 
        unordered_map<Node*, 
        Node*>& nodes_completed) {

  if (root == nullptr) {
    return nullptr;
  }

  Node* pNew = new Node(root->data);
  nodes_completed[root] = pNew;

  for (Node* p : root->neighbors) {

    auto x = nodes_completed.find(p);

    if (x == nodes_completed.end()){
      pNew->neighbors.push_back(clone_rec(p, nodes_completed));
    } else {
      pNew->neighbors.push_back(x->second /*value*/);
    }
  }

  return pNew;
}

Node* clone(Node* root) {
  unordered_map<Node*, Node*> nodes_completed;
  return clone_rec(root, nodes_completed);
}

// this is un-directed graph i.e.
// if there is an edge from x to y
// that means there must be an edge from y to x
// and there is no edge from a node to itself
// hence there can maximim of (nodes * nodes - nodes) / 2 edgesin this graph
void create_test_graph_undirected(int nodes, int edges, vector<Node*>& vertices) {
  for (int i = 0; i < nodes; ++i) {
    vertices.push_back(new Node(i));
  }

  vector<pair<int, int>> all_edges;
  for (int i = 0; i < vertices.size(); ++i) {
    for (int j = i + 1; j < vertices.size(); ++j) {
      all_edges.push_back(pair<int, int>(i, j));
    }
  }

  std::random_shuffle(all_edges.begin(), all_edges.end());

  for (int i = 0; i < edges && i < all_edges.size(); ++i) {
    pair<int, int>& edge = all_edges[i];
    vertices[edge.first]->neighbors.push_back(vertices[edge.second]);
    vertices[edge.second]->neighbors.push_back(vertices[edge.first]);
  }
}

void print_graph(vector<Node*>& vertices) {
  for (Node* n : vertices) {
    cout << n->data << ": {";
    for (Node* t : n->neighbors) {
      cout << t->data << " ";
    }
    cout << "}" << endl;
  }
}

void print_graph(Node* root, unordered_set<Node*>& visited_nodes) {
  if (root == nullptr || visited_nodes.find(root) != visited_nodes.end()) {
    return;
  }

  visited_nodes.insert(root);

  cout << root->data << ": {";
  for (Node* n : root->neighbors) {
    cout << n->data << " ";
  }
  cout << "}" << endl;
  for (Node* n : root->neighbors) {
    print_graph(n, visited_nodes);
  }
}

void print_graph(Node* root) {
  unordered_set<Node*> visited_nodes;
  print_graph(root, visited_nodes);
}

int main() {
  vector<Node*> vertices;
  create_test_graph_undirected(7, 18, vertices);

  print_graph(vertices[0]);

  Node* cp = clone(vertices[0]);
  cout << endl << "After copy" << endl;
  print_graph(cp);

  return 0;
}

We use depth first traversal and create a copy of each node while traversing the graph. Use a hashtable to store each completed node so we won’t revisit nodes that exist in that hashtable. The hashtable key will be a node in the original graph, and its value will be the corresponding node in the cloned graph.

Runtime Complexity: Linear, O(n)

Memory Complexity: Logarithmic, O(n), where n is the number of vertices in the graph.

To see the solution to any of these problems in Java, Python, Ruby, or JavaScript, go to our sister-site, Coding Interview.

Linked Lists questions

Add two integers

The goal of this exercise is to add two integers of two linked lists.

Problem statement: You are given the head pointers of two linked lists where each linked list represents an integer number (i.e. each node is a digit). Add them and return the new linked list.

// assuming both integers are stored in a linked list
// e.g. 415 is stored as 5->1->4
// 32 is stored as 2->3
LinkedListNode* add_integers(
    LinkedListNode* integer1, 
    LinkedListNode* integer2) {

  LinkedListNode* result = nullptr;
  LinkedListNode* last = nullptr;
  int carry = 0;

  while (
      integer1 != nullptr ||
      integer2 != nullptr ||
      carry > 0) {

    int first = 
        (integer1 == nullptr ? 0 : integer1->data);
    int second = 
        (integer2 == nullptr ? 0 : integer2->data);

    int sum = first + second + carry;

    LinkedListNode* pNew = 
          new LinkedListNode(sum % 10);

    carry = sum / 10;

    if (result == nullptr) {
      result = pNew;
    } else {
      last->next = pNew;
    }

    last = pNew;

    if (integer1 != nullptr) {
      integer1 = integer1->next;
    }

    if (integer2 != nullptr) {
      integer2 = integer2->next;
    }
  }

  return result;
}

int main(int argc, char* argv[]) {
    vector<int> v1 = {1, 2, 3}; // 321
  vector<int> v2 = {1, 2}; // 21

  LinkedListNode* first = LinkedList::create_linked_list(v1);
  LinkedListNode* second = LinkedList::create_linked_list(v2);

  // sum should be 321 + 21 = 342 => 2->4->3
  LinkedListNode* result = add_integers(first, second);
  vector<int> r = {2, 4, 3}; // 342
  LinkedListNode* expected = LinkedList::create_linked_list(r);
  assert(LinkedList::is_equal(result, expected));

  cout << endl << "First:";
  LinkedList::display(first);
  cout << endl << "Second:";
  LinkedList::display(second);
  cout << endl << "Result:";
  LinkedList::display(result);

  result = add_integers(first, nullptr);
  assert(LinkedList::is_equal(result, first));

  result = add_integers(nullptr, second);
  assert(LinkedList::is_equal(result, second));
}

To understand this better, let’s consider an example. Say we want to add the integers 9901 and 237. The result of this addition would be 10138.

The integers are stored inverted in the linked lists to make this easier. The most significant digit of the number is the last element of the linked list. To start adding, we start from the heads of the two linked lists.

At each iteration, we add the current digits of the two lists and insert a new node with the resulting digit at the tail of the result linked list. We’ll also need to maintain carry for each step.

We do this for all digits in both the linked lists. If one of the linked lists ends sooner, we’ll continue with the other linked list. Once both of the linked lists are done and no carry is left to be added, the algorithm will terminate.

Runtime Complexity: Linear, O(n)

Memory Complexity: Linear, O(n)

Merge two sorted linked lists

The goal of this exercise is to merge two sorted linked lists.

Problem statement: Given two sorted linked lists, merge them so the resulting linked list is also sorted.

typedef LinkedListNode* NodePtr;

NodePtr merge_sorted(NodePtr head1, NodePtr head2) {

  // if both lists are empty then merged list is also empty
  // if one of the lists is empty then other is the merged list
  if (head1 == nullptr) {
    return head2;
  } else if (head2 == nullptr) {
    return head1;
  }


  NodePtr mergedHead = nullptr;
  if (head1->data <= head2->data) {
    mergedHead = head1;
    head1 = head1->next;
  } else {
    mergedHead = head2;
    head2 = head2->next;
  }

  NodePtr mergedTail = mergedHead;

  while (head1 != nullptr && head2 != nullptr) {
    NodePtr temp = nullptr;
    if (head1->data <= head2->data) {
      temp = head1;
      head1 = head1->next;
    } else {
      temp = head2;
      head2 = head2->next;
    }

    mergedTail->next = temp;
    mergedTail = temp;
  }

  if (head1 != nullptr) {
    mergedTail->next = head1;
  } else if (head2 != nullptr) {
    mergedTail->next = head2;
  }

  return mergedHead;
}

void test(vector<int>& v1, vector<int>& v2, vector<int>& expected) {
  LinkedListNode* list_head1 = LinkedList::create_linked_list(v1);

  cout<<"List 1: "<<LinkedList::getList(list_head1)<<endl;

  LinkedListNode* list_head2 = LinkedList::create_linked_list(v2);

  cout<<"List 2: "<<LinkedList::getList(list_head2)<<endl;

  LinkedListNode* merged = merge_sorted(list_head1, list_head2);

  cout<<"Result: "<<LinkedList::getList(merged)<<endl;

  LinkedListNode* expected_list = LinkedList::create_linked_list(expected);


  assert(LinkedList::is_equal(merged, expected_list));
}

int main(int argc, char* argv[]) {

  vector<int> v1 = {1, 3, 5, 6};
  vector<int> v2 = {2, 4, 6, 20, 34};
  vector<int> expected = {1, 2, 3, 4, 5, 6, 6, 20, 34};

  test(v1, v2, expected);

  v1 = {1, 3, 5, 6};
  v2 = {};
  expected = {1, 3, 5, 6};

  test(v1, v2, expected);

  v1 = {1, 3, 5, 6};
  v2 = {2, 4, 6, 20};
  expected = {1, 2, 3, 4, 5, 6, 6, 20};

  test(v1, v2, expected);
  v1 = {4, 4};
  v2 = {4, 4, 4};
  expected = {4, 4, 4, 4 ,4};

  test(v1, v2, expected);
}

Maintain a head and a tail pointer on the merged linked list. Choose the head of the merged linked list by comparing the first node of both linked lists.

For all subsequent nodes, choose the smaller current node and link it to the tail of the merged list. Move the current pointer of that list one step forward.

If there are still some elements in only one of the lists, link this remaining list to the tail of the merged list. Initially, the merged linked list is NULL.

Compare the value of the first two nodes and make the node with the smaller value the head node of the merged linked list. In this example, it is 4 from head1. Since it’s the first and only node in the merged list, it will be the tail. Then move head1 one step forward.

Runtime Complexity: Linear, O(m + n), where m and n are lengths of our linked lists

Memory Complexity: Constant, O(1)

Trees questions

Determine if two binary trees are identical

The goal of this exercise is to compare two binary trees to determine if they are identical or not.

Problem statement: You are given the roots of two binary trees and must determine if these trees are identical. Identical trees have the same layout and data at each node.

Tip: Trees that have the same data aren’t necessarily identical. What’s important is their structure.

bool are_identical(
  BinaryTreeNode* root1,
  BinaryTreeNode* root2) {

  if (root1 == nullptr && root2 == nullptr) {
    return true;
  }

  if (root1 != nullptr && root2 != nullptr) {
    return ((root1->data == root2->data) &&
            are_identical(root1->left, root2->left) &&
            are_identical(root1->right, root2->right));
  }

  return false;
}

int main() {
  BinaryTreeNode *root1 = new BinaryTreeNode(100);
  insert_bst(root1, 50);
  insert_bst(root1, 200);
  insert_bst(root1, 25);
  insert_bst(root1, 125);
  insert_bst(root1, 350);

  display_level_order(root1);

  BinaryTreeNode *root2 = create_random_BST(15);

  display_level_order(root2);

  // Try changing the roots being passed
  if(are_identical(root1, root2)) {
    cout<< " the trees are identical" << endl;
  } else {
    cout<< "the trees are not identical" << endl;
  }
}

This problem can be solved recursively. The base case of recursion for this solution is if two compared nodes are null or one of them is null.

Two trees A and B are identical if:

Data on their roots is the same or both roots are null
The left subtree of A is identical to the left sub-tree of B
The right subtree of A is identical to the right subtree of B

Use a depth-first traversal on both trees simultaneously and keep comparing the data at each level to solve this problem.

Runtime Complexity: Linear, O(n)

Memory Complexity: O(h) in best case, or it will be O(log n) for a balanced tree and in the worst case can be O(n).

Mirror binary tree nodes

The goal of this exercise is to use depth first traversal and bottom up mirroring to mirror the nodes of a binary tree.

Problem statement: You are given the root node of a binary tree and must swap the left and right children for each node.

void mirror_tree(BinaryTreeNode* root) {
  if (root == nullptr) {
    return;
  }

  // We will do a post-order traversal of the binary tree.

  if (root->left != nullptr) {
    mirror_tree(root->left);
  }

  if (root->right != nullptr) {
    mirror_tree(root->right);
  }

  // Let's swap the left and right nodes at current level.

  BinaryTreeNode* temp = root->left;
  root->left = root->right;
  root->right = temp;
}

int main(int argc, char* argv[]) {

  BinaryTreeNode* root = create_random_BST(15);
  display_level_order(root);
  mirror_tree(root);
  cout << endl << "Mirrored tree = " << endl;
  display_level_order(root);
}

We do a post order traversal of the binary tree. For every node, swap its left child with its right child. We use DFS on the tree, so that before returning from a node, all its children have been visited (and mirrored).

Runtime complexity: Linear, O(n)

Memory Complexity: Linear, O(n) in the worst case

To see the solution to any of these problems in Java, Python, Ruby, or JavaScript, go to our sister-site, Coding Interview.

Strings questions

Find all palindrome substrings

The goal of this exercise is to find the palindrome substrings of a given string.

Problem statement: Given a string, find all non-single letter substrings that are palindromes. The string given is "aabbbaa".

Try it yourself below before checking the solution.

int find_palindromes_in_sub_string(const string& input, int j, int k) {
  int count = 0;
  for (; j >= 0 && k < input.length(); --j, ++k) {
    if (input[j] != input[k]) {      
      break;
    } 
    cout << input.substr(j, k - j + 1) << endl;
    ++count;
  }
  return count;
}

int find_all_palindrome_substrings(const string& input) {
  int count = 0;
  for (int i = 0; i < input.length(); ++i) {    
    count += find_palindromes_in_sub_string(input, i - 1, i + 1);
    count += find_palindromes_in_sub_string(input, i, i + 1);
  }
  return count;
}

int main() {
  string str = "aabbbaa";

  cout << "Total palindrome substrings: "  << find_all_palindrome_substrings(str) << endl;
}

For each letter in the input string, start expanding to the left and right while checking for even and odd length palindromes. Move to the next letter if we know a palindrome doesn’t exist there.

We expand one character to the left and right and compare. If both are equal, we print out the palindrome substring.

Runtime complexity: Polynomial, O(n^2)

Memory complexity: Constant, O(1)

Reverse words in a sentence

The goal of this exercise is to reverse the words in a given string. Be sure to note how the words are separated by whitespaces.

Problem statement: Reverse the order of words in a given sentence (an array of characters). The words given are "Hello World!".

void str_rev(char * str, int len) {

  if (str == nullptr || len < 2) {
    return;
  }

  char * start = str;
  char * end = str + len - 1;

  while (start < end) {
    if (start != nullptr && end != nullptr) {
      char temp = * start;
      * start = * end;
      * end = temp;
    }
    start++;
    end--;
  }
}

void reverse_words(char * sentence) {

  // Here sentence is a null-terminated string ending with char '\0'.

  if (sentence == nullptr) {
    return;
  }

  // To reverse all words in the string, we will first reverse
  // the string. Now all the words are in the desired location, but
  // in reverse order: "Hello World" -> "dlroW olleH".

  int len = strlen(sentence);
  str_rev(sentence, len);

  // Now, let's iterate the sentence and reverse each word in place.
  // "dlroW olleH" -> "World Hello"

  char * start = sentence;
  char * end;
  while (true) {
    // find the  start index of a word while skipping spaces.
    while (start && * start == ' ') {
      ++start;
    }

    if (start == nullptr || * start == '\0') {
      break;
    }

    // find the end index of the word.
    end = start + 1;
    while (end && * end != '\0' && * end != ' ') {
      ++end;
    }

    // let's reverse the word in-place.

    if (end != nullptr) {
      str_rev(start, (end - start));
    }

    start = end;
  }
}

int main() {

  string str = "Hello World!";
  char* a = const_cast<char*>(str.c_str());

  cout << a << endl;
  reverse_words(a);
  cout << a << endl;
}

There are two steps to this problem. First, reverse the string. Then, traverse the string and reverse each word in place.

Runtime complexity: Linear, O(n)

Memory complexity: Constant, O(1)

Dynamic programming questions

Largest Sum Subarray

The goal of this exercise is to use your dynamic programming skills and Kadane’s algorithm to find the largest sum subarray.

Problem statement: Find the largest sum subarray. In the array below, the largest sum subarray starts at index 3 and ends at 6, and with the largest sum being 12.

int find_max_sum_sub_array(int A[], int n) {
  if (n < 1) {
    return 0;
  }

  int curr_max = A[0];
  int global_max = A[0];
  for (int i = 1; i < n; ++i) {
    if (curr_max < 0) {
      curr_max = A[i];
    } else {
      curr_max += A[i];
    }

    if (global_max < curr_max) {
      global_max = curr_max;
    }
  }

  return global_max;
}

int main() {

    int v[] = {-4, 2, -5, 1, 2, 3, 6, -5, 1};
    cout << "Sum of largest subarray: " << find_max_sum_sub_array(v, sizeof(v) / sizeof(v[0])) << endl;
    return 0;
  }

We use Kadane’s algorithm to solve this. The basic idea of this algorithm is to scan the entire array and at each position find the maximum sum of the subarray ending there. This is achieved by keeping a current_max for the current array index and a global_max.

The algorithm is as follows:

current_max = A[0]
global_max = A[0]
for i = 1 -> size of A
    if current_max is less than 0
        then current_max = A[i]
    otherwise 
        current_max = current_max + A[i]
    if global_max is less than current_max 
        then global_max = current_max

Runtime complexity: Linear, O(n)

Memory complexity: Constant, O(1)

Math and stats

Power of a number

The goal of this exercise is to use divide and conquer and write a function that calculates the raised to the power of a number.

Problem statement: You are given a double, x and an integer n, write a function to calculate x raised to the power n.

power (2, 5) = 32

power (3, 4) = 81

power (1.5, 3) = 3.375

power (2, -2) = 0.25

double power_rec(double x, int n) {
  if (n == 0) return 1;
  if (n == 1) return x;

  double temp = power_rec(x, n/2);
  if (n % 2 == 0)  {
    return temp * temp;
  } else {
    return x * temp * temp;
  }
}

double power(double x, int n) {
  bool is_negative = false;
  if (n < 0) {
    is_negative = true;
    n *= -1;
  }

  double result = power_rec(x, n);

  if (is_negative) {
    return 1 / result;
  }

  return result;
}

bool test_power(double x, int n) {
  double r1 = power(0.753, n);
  double r2 = pow(0.753, n);
  double diff = r1 - r2;
  if (diff < 0) {
    diff = diff * -1;
  }
  if (diff > 0.00000000001) {
    cout << "Failed for " << x << ", " << n << endl;
    return false;
  }
  return true;
}
int main(int argc, char* argv[]) {

  bool pass = true;
  for (int n = -5; n <= 5; ++n) {
    bool temp_pass = test_power(0.753, n);
    pass &= temp_pass;
  }

  pass &= test_power(0, 0);

  cout << "Power(0, 0) = " << pow(0, 0) << endl;

  if (pass) {
    cout << "Passed." << endl;
  } else {
    cout << "Failed." << endl;
  }
}

We can use the divide and conquer approach to solve this problem most efficiently. In the dividing step, we keep dividing n by 2 recursively until we reach the base case.

In the combining step, we get the result r of the sub-problem and compute the result of the current problem using the two rules below:

If n is even, the result is r * r (where r is the result of sub-problem)
If n is odd, the result is x * r * r (where r is the result of sub-problem)

Runtime Complexity: Logarithmic, O(logn)

Memory Complexity: Logarithmic, O(log n)

Find all sum combinations

The goal of this exercise is to use your backtracking skills to find all sum combinations.

Problem statement: Given a positive integer, target, print all possible combinations of positive integers that add to the target number.

The output will be in the form a list of lists or an array of arrays, as each element in the list will be another list containing a possible sum combination.

For example, if you are given input 5, these are the possible sum combinations.

1, 4
2, 3
1, 1, 3
1, 2, 2
1, 1, 1, 2
1, 1, 1, 1, 1

void print(vector<vector<int>> output){
  for(int i = 0; i < output.size(); i++){
    cout << "[ ";
    for(int j = 0; j < output[i].size(); j++){
      cout << output[i][j] << ", "; 
    }
    cout << "]" << endl;
  }
}

void print_all_sum_rec(
    int target,
    int current_sum,
    int start, vector<vector<int>>& output,
    vector<int>& result) {

  if (target == current_sum) {
    output.push_back(result);
  }

  for (int i = start; i < target; ++i) {
    int temp_sum = current_sum + i;
    if (temp_sum <= target) {
      result.push_back(i);
      print_all_sum_rec(target, temp_sum, i, output, result);
      result.pop_back();

    } else {
      return;
    }
  }
}

vector<vector<int>> print_all_sum(int target) {
  vector<vector<int>> output;
  vector<int> result;
  print_all_sum_rec(target, 0, 1, output, result);
  return output;
}


int main(int argc, const char* argv[]) {
  int n = 4;
  vector<vector<int>> result = print_all_sum(n);

  print (result);
}

We recursively go through all possible sum combinations, and when the running sum equals the target, print that combination.
The algorithm will recursively check all the numbers that can sum up to the target.

In each recursive call, there is a for loop that runs from start to target, where start is initially 1. current_sum is the variable that is incremented with every recursive call.

Every time a value is added to the current_sum, it is also added to the result list. Whenever current_sum equals target, we know that the result list contains a possible combination for target, and this list is then appended to the final output list.

Base condition of recursion:

if current_sum equals target
  print the output contents

Before each recursive call, an element is added to result. However, after each call, this element is also removed from the list to reset the list.

Runtime Complexity: Exponential, O^2

Memory Complexity: Linear, O(n)

Searching and design questions

Search in rotated array

The goal of this exercise is to search in a rotated array for a given number in a sorted array. Try to solve the problem using binary search.

Problem statement: Search for a given number in a sorted array, with unique elements, that has been rotated by some arbitrary number, assuming that the array does not contain duplicates. Return -1 if the number does not exist.

Below is an original array before rotation:

After performing rotation on this array 6 times it changes to:

int binary_search(vector<int>& arr, int start, int end, int key) {
  // assuming all the keys are unique.

  if (start > end) {
    return -1;
  }

  int mid = start + (end - start) / 2;

  if (arr[mid] == key) {
    return mid;
  }

  if (arr[start] <= arr[mid] && key <= arr[mid] && key >= arr[start]) {
    return binary_search(arr, start, mid-1, key);
  }

  else if (arr[mid] <= arr[end] && key >= arr[mid] && key <= arr[end]) {
    return binary_search(arr, mid+1, end, key);
  }

  else if (arr[end] <= arr[mid]) {
    return binary_search(arr, mid+1, end, key);
  }

  else if (arr[start] >= arr[mid]) {
    return binary_search(arr, start, mid-1, key);
  }

  return -1;
}

int binary_search_rotated(vector<int>& arr, int key) {
  return binary_search(arr, 0, arr.size()-1, key);
}

int main(int argc, char* argv[]) {
    vector<int> v1 = {6, 7, 1, 2, 3, 4, 5};

    cout<<"Key(3) found at: "<<binary_search_rotated(v1, 3)<<endl;
    cout<<"Key(6) found at: "<<binary_search_rotated(v1, 6)<<endl;

    vector<int> v2 = {4, 5, 6, 1, 2, 3};

    cout<<"Key(3) found at: "<<binary_search_rotated(v2, 3)<<endl;
    cout<<"Key(6) found at: "<<binary_search_rotated(v2, 6)<<endl;    
}

The solution is like a binary search with some modifications. Notice that at least one half of the array is always sorted. If the number n lies within the sorted half of the array, then our problem is a basic binary search. Otherwise, discard the sorted half and examine the unsorted half.

Runtime complexity: Logarithmic, O(log n)

Memory complexity: Logarithmic, O(log n)

Implement a LRU cache

The goal of this design exercise is to implement Least Recently Used (LRU), a common caching strategy, using a doubly linked list and hashing.

Problem statement: Least Recently Used (LRU) defines the policy to evict elements from the cache to make room for new elements when the cache is full, meaning it discards the least recently used items first.

Take an example of a cache that has a capacity of 4 elements. We cache the elements 1, 2, 3, and 4. This diagram below represents the cache state after first access of all four elements.

We now need to cache another element 5.

Let’s see what happens when 2 is accessed again. Now 3 becomes the next in line to be evicted from the cache.

// Linked list operations
// void add_at_tail(int val)
// void delete_node(ListNode* node)
// void delete_from_head()
// void delete_from_tail()
// ListNode* get_head()
// void set_head(ListNode* node)
// ListNode* get_tail()
// void set_tail(ListNode* node)

// simple single threaded LRUCache
class LRUCache {

  unordered_set<int> cache;

  // each entry in linked list is the value of the element
  LinkedList cache_vals;
  int capacity; // total capacity
public:

  LRUCache(int capacity) {
    this->capacity = capacity;
  }

  ~LRUCache() {
    cache.clear();
  }

  ListNode* get(int val) {
    auto p = cache.find(val);
    if (p == cache.end()) {
      return nullptr;
    }
    else{
      ListNode* i = cache_vals.get_head();
      while(i != nullptr){
        if (i->value == val){
          return i;
        }
        i = i->next;
      }
    }
  }

  void set(int value) {
    ListNode* check = get(value);
    if(check == nullptr){
      if(cache.size() >= capacity){
        cache_vals.add_at_tail(value);
        int head_val = cache_vals.get_head()->value;
        cache.erase(head_val);
        cache_vals.delete_from_head();
      }
      else{
        cache_vals.add_at_tail(value);
        cache.insert(value);
      }
    }
    else{
      if(check == cache_vals.get_tail()){
        return;
      }
      if(check == cache_vals.get_head()){
        cache_vals.add_at_tail(check->value);
        cache_vals.delete_from_head();
        return;
      }
      if(check->prev != nullptr){
        check->prev->next = check->next;
      }
      if(check->next != nullptr){
        check->next->prev = check->prev;
      }
      cache_vals.add_at_tail(check->value);
      delete check;
    }
  }

  void print() {
    ListNode* i = cache_vals.get_head();
      while(i != nullptr){
        cout << i->value << ", ";
        i = i ->next;
      }
    cout << endl;
  }
};

int main(int argc, char const *argv[])
{
  LRUCache cache(4);
  cache.set(1);
  cache.print();

  cache.set(2);
  cache.print();

  cache.set(3);
  cache.print();

  cache.set(4);
  cache.print();

  cache.set(5);
  cache.print();

  cache.set(2);
  cache.print();

  return 0;
}

Caching is a technique to store data in a faster storage (usually RAM) to serve future requests faster. Cache stores are usually not big enough to store a full data set. We need to evict data from the cache when it becomes full.

LRU is very simple and a commonly used algorithm for this process. We evict the oldest data from the cache to accommodate new data.

To implement an LRU cache we use two data structures: a hashmap and a doubly linked list. A doubly linked list helps in maintaining the eviction order and a hashmap helps with $O(1)$ lookup of cached keys. Here is the algorithm:

If the element exists in hashmap
    move the accessed element to the tail of the linked list
Otherwise,
    if eviction is needed i.e. cache is already full
        Remove the head element from doubly linked list and delete its hashmap entry
    Add the new element at the tail of linked list and in hashmap
Get from Cache and Return

Note: The doubly linked list is for tracking the most recently accessed elements. The element at the tail of the doubly linked list is the most recently accessed element.

All newly inserted elements go to the tail, and any element accessed goes to the tail.

Runtime Complexity:

get (hashset): Constant, O(1)
set (hashset): Constant, O(1)
Deletion at head when adding a new element: Constant, O(1)
Search for deleting and adding to tail: Linear, O(n)

Memory Complexity: Linear, O(n), where n is the size of cache

Behavioral questions

Now that we’ve discussed the top technical questions, let’s look at the most common behavioral interview questions you can expect at an Apple interview, which are arguably just as important for your success.

As you’ll see from this list, Apple wants to understand what kind of thinker you are, how you handle conflict, and what investments you bring to the table.

What were some of your best and worst days over the last four years?
What is your favorite Apple product or service, and why?
Describe an achievement you are particularly proud of.
Have you ever disagreed with your manager about a decision at work? What happened? How did you handle the situation?
How have you overcome failure? What did you learn from it?
Why do you want to work for Apple?
What is the first thing you notice when walking into an Apple store?
Describe the most challenging software development problem you faced. How did you solve it?
If you accept a job at Apple, what will you miss most about your current role? What will you miss least?
Do you take any steps to enhance your skills outside of work?
Describe a time you went above and beyond for a customer
Explain to a 8 year old what a modem/router is and its functions.
How does this role fit into your 5 year career or life plan?
If we hired you, what would you want to work on?
How would you test your favorite app?
If a person called for tech support but had a dinosaur or legacy product, how would you handle it?

Tip: Regardless of the question or position, it is always recommended to use STAR method for answering their behavioral-based interview questions:

Describe the situation.

Describe the task.

Describe the action(s) taken to handle the task.

Explain the results you achieved.

Tips for preparing for interviews

Practicing for interviews takes tons of time and patience, and there is no golden ticket to cracking the coding interview. But there are some best practices we've learned over the years.

Practice with different tools. It's a good idea to combine whiteboard practice, online courses, and mock interviews to get the most out of your time. It's crucial that you practice talking aloud as you solve problems, so use different kinds of tolls to get practice.
Create a study plan. It is also recommended to create a detailed preparation plan for anywhere between 3-6 months. This way, you have a structure to follow and avoid missing essential concepts.
Avoid rote memorization. It is also recommended to avoid memorizing questions. Instead, practice by building real products that Apple might use. This is the ideal way to prepare for interviews: you learn the same concepts, practice problem-solving, and gain confidence actually building for Apple.

To get hands-on practice with 100+ real product features, check out Educative's interview prep series Decode the Coding Interview. Our team of experts has combed through the top interview questions and incorporated them into a carefully crafted set of scenarios for you to learn from.

After each project, we’ll show you what kinds of interview problems you’ll now be able to solve using the techniques you just applied.

Happy learning!

Continue reading about coding interviews

How to become a Product Manager: top three PM career paths

Amanda Fawcett — Fri, 19 Mar 2021 20:07:37 +0000

Becoming a product manager (PM) is a dream for many software developers. This role requires no coding but still allows you to work with modern technologies and build powerful products. Product management is all about having vision, managerial finesse, and the ability to see a project to the completion.

The role of PM varies widely depending on a number of factors, and there is no golden ticket to landing this role, making it hard to know how to get started. If you are considering pursuing a PM role, you're in the right place. Today, we will walk through a detailed PM career guide and examine some common career paths to help reach your goals.

This career guide at a glance:

What is a Product Manager?
Core competencies of a PM
Career Path #1: MBA program
Career Path #2: Specialized PM training
Career Path #3: Learn on the job
How to get started

What is a Product Manager?

A product manager's primary goal is to see a product to completion and support the stakeholders involved. They are responsible for the conception, creation, and launch of new products.

Essentially, the PM serves as the head of a product's development and lifecycle, so they are in charge of distributing information, keeping everyone on track, and communicating objectives clearly. A PM's daily routine varies a lot but has the primary focus of creating plans, launching products, and maintaining budgets.

A product manager's general objectives and tasks are to:

Decide what tools and software are needed

Specify technical and functional requirements

Manage research, design, and testing

Develop a go-to-market strategy

Mediate conflicts related to deadlines and communication

Initiate ongoing updates and new features

According to Glassdoor and Payscale, product managers can typically make anywhere from $63,000 to $200,000 annually, depending on the company, seniority, and location. The title of a PM may differ from company to company, and there are many other roles that share similar responsibilities, including:

Associate product manager
Senior product manager
Director of product management
VP of product management
Chief product officer (CPO)

Product management for software is not typically taught in formal education settings. Anyone can become a Product Manager, whether you come from a Graphic Design background or Computer Science track.

Core competencies of a PM

The three core competencies of a PM include: core skills, emotional intelligence, and a good company fit.

Core Skills

Let's start with the core skills. To be a successful PM, you'll need to demonstrate competency (or competency potential) with the following skills, most of which are developed through work experience:

Conducting user testing and customer interviews
Managing teams and sticking to deadlines
Designing and running design sprints
Prioritizing features strategically
Conducting market assessments
Resource allocation skills
Translating business requirements into technical features
Defining and tracking performance/success metrics

Emotional Intelligence

A good PM will also need to demonstrate emotional intelligence in order to build strong relationships with their teams, maintain organization, and navigate hurdles effectively. Emotional intelligence is a hard thing to measure, but some base qualities include:

Social awareness and social finesse: being socially aware empathetic, and aware of how people organize
Effective communication: being able to convey ideas accurately and in a way that others understand
Self-awareness: remaining objective with a product and their preferences
Self-starter mentality: being calm under pressure and initiating changes without direct instruction

Company fit

In terms of being a solid fit for a company, PMs need to demonstrate that they can work effectively in a specific organization. Even if you are highly skilled, you may not work well with certain culture or organizational structures.
It's important to understand what a company is looking for, such as:

Company stage and age: startups will look for different skillsets than a mature one, which will change your level of involvement.
Technical skills: different companies will look for experience with relevant technologies to their products. This will dictate what roles you can apply to.
Hierarchy: some companies have a lax, open environment, while others have rigid structures. This will dictate the values they expect a PM to have.
Company philosophy: some companies organize by the philosophy that engineering drives management, while others think the opposite. This will dictate the managerial approach they are looking for.

Career Path #1: MBA program

Many PMs start their career path by completing an MBA program. A common track is to:

Accrue 3-5 years of professional experience in a related industry, such as software engineering
Complete an MBA program (sometimes part-time while still working)
Land a junior/assistant product management role

An MBA program can be a great option for those looking to land a PM role at a big, well-known company, particularly those with more rigid hierarchies like Microsoft, which tend to exclude applicants that don't have formal business education.

Tip: Completing an MBA can also help you negotiate a higher starting salary.

MBA programs will help you build leadership skills, develop product vision, and learn the theories behind a product's lifecycle in the market. An MBA track also opens up many other doors if you choose not to become a PM down the line, as MBAs are widely recognized in almost every industry.

However, MBA programs will give you less hands-on experience with execution skills, as you will not be using the common tools for the job, such as Agile or Scrum. If you choose this path, it's essential that you demonstrate proof of hands-on experience through side projects, internships, part-time jobs, or additional accredited online courses.

Career Path #2: Specialized PM training

The specialized PM training path tends to be the fastest option. Many accredited sites offer online product management courses and certificates that are recognized by most companies big and small (and a lot cheaper than an MBA program). Think of this like a coding bootcamp for PMs.

This is a great option if you are sure you want to become a PM, as everything you learn is directly applicable to any PM job. You also get experience using real-world PM tools, and graduates usually complete programs with a product portfolio that is useful for interviews. Programs generally take 6 months to 1 year to complete.

Tip: Since there are many online or in-person certificates to choose from, it's important to pick one that aligns with your career goals.

For example, if you want to work closely with software as a PM, it's important to get a certificate from a technical educational platform or institution.

The trick here is to find a reliable, reputable program that is worth the time investment. Some programs teach older styles of product management that are less relevant to modern companies. You'll want to research programs carefully and look for skills like agile development, lean product management, and digital product management.

You should also examine the certificate syllabus closely to make sure that it'll be a successful learning environment. Some programs are text-based, which is a more effective way to learn, but does take more time to complete.

Career Path #3: Learn on the job & work your way up

This tends to be the slowest way to become a PM, but it is a great option for many. Instead of taking courses, you can seeks out a junior product management role, build up your experience, and work your way up to a product manager role (or higher).

Learning on the job is slow and requires patience, social finesse, and a self-starter mentality. It is a great option for those who want highly-specialized training or cannot afford to pursue a formal educational path. This is also a good option if you want to work with particular technologies, emerging technologies, or specific companies.

Tip: If this route sounds right for you, consider getting a mentor in your company. Convey your career goals and ask for ways to take on more responsibility. This way, you have someone higher-up to support you.

To work your way up to a PM role, you'll need to stand out at every stage of your career. For example, even as a software engineer, demonstrate your ability to focus on the customer and solve customer problems with good product design. Demonstrate leadership capabilities early on, and you're more likely to be promoted or reorganized.

It's important to note that getting into a product manager role with no prior experience is rare. A great option is to begin with a startup at an early stage and work your way up. You could also consider starting your own business or seeking a company that has an Associate Product Management program.

How to get started

Now that we know the core competencies of a PM and three common career tracks, how do you actually get started? Well, first, you'll need to decide what path is right for you, and that may take time to figure out. From there, you can flesh out exactly how you want to process.

But no matter your plan, there are some basic things you can start doing today to break into the industry:

Side projects: demonstrate your interest in product management by working on side projects that give you the experience with shipping a product.
Start thinking like a leader: Ask to work on new products where you can take a lead role according to deadlines
Develop a technical skillset: Learn new technical skills that you'll need as a PM, such as SQL, advanced Excel, and agile methodologies

You can start learning the technical skills of PM today and jumpstart your career. Educative's course Lean Product Management will teach you the modern product management techniques to bring products to the market as quickly as possible. This is the ideal place to start to build your resume and gain valuable insights.

By the end, you will have the foundations in place to bring products to the market that solve problems, generate revenue, and are built for the long haul.

Happy learning!

Continue reading about Product Management

Scala Tutorial for Java Programmers with examples

Amanda Fawcett — Thu, 18 Mar 2021 18:46:39 +0000

Scala is a general-purpose programming, type-safe JVM language language that offers support for object-oriented programming (OOP) and functional programming. Scala was designed to address some of the limitations and tediousness of Java.

Scala is a great option for Java developers who want to take their career to the next level (or for those who are just tired of Java’s quirks). Scala is now recognized by big companies as a powerful language, namely Twitter and LinkedIn. In fact, according to StackOverflow’s 2020 survey, US Scala developers have the highest paying salaries.

If you are a Java developer who wants to transition to Scala (or just see what it has to offer), you’re in the right place. Today, we will introduce you to Scala to make the transition.

This tutorial at a glance:

Scala vs Java
Hello World with Scala
Scala Syntax Quick Guide
Objects and Classes in Scala
Inheritance and Overriding
Traits in Scala
Next steps for your Scala journey

Scala vs. Java

Java is known for its complexity and verbosity. It requires a lot of lines of code to perform simple tasks. Scala was designed to create a “better Java”, much like other alternatives like Kotlin and Ceylon. Scala is unique, however, as it did not try to remain too close to Java’s syntax.

Scala shedded the restrictive and tedious aspects of Java in favor of making a better language overall.

This means that there are some notable distinctions and paradigm shifts between the two, so Scala has a bigger learning curve than Kotlin. But it’s worth the work: it produces clean, simple, organized code that boosts your productivity down the line and requires far less lines of code than Java.

There are several key differences between the languages. Let’s break them down.

Scala is a statically typed language
Scala uses an actor model for concurrency (instead of Java’s thread-based model)
Scala doesn’t use static members
Scala variables are immutable by default
Scala supports multiple inheritances with classes (not abstract classes)
Scala supports lazy evaluation unlike Java
Scala offers support for operator overloading
Scala doesn’t offer backward compatibility
Scala can be used for functional programming
Any Scala method or function is treated like a variable, whereas Java treats them as objects
Scala uses Traits instead of Java interfaces

One of the main advantages of Scala is that it can be executed on the Java Virtual Machine (JVM), making it very easy to interact with Java code. All classes from the java.lang package are imported by default with Scala.

One of its drawbacks, however, is community support: there is less detailed documentation, 3rd party libraries, and community presence than Java. However, this is changing as more Java developers add Scala to their toolbelt.

For a practical example of how Java and Scala differ, let’s see how we’d create a list of Strings in both languages:

// java
List<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
list.add("3");

// scala
val list = List("1", "2", "3")

As you can see, Scala is a lot more precise, requiring far less lines of code. Scala is also easier to skim, making it a great choice for teams.

Hello World with Scala

Now that we are familiar with the main differences between Java and Scala, let’s dive into some more code to understand how these two languages differ. First, look at the Hello World program in Java that we’re familiar with:

class HelloWorld {
    public static void main( String args[] ) {
        System.out.println( "Hello World!" );
    }
}

Now, look at an equivalent program in Scala. You’ll notice right away that it’s somewhat similar.

object HelloWorld {
  def main(args: Array[String]): Unit = {
    println("Hello, world!")
  }
}

So, what is going on here? Just like Java, the main method is the entry point for our Scala program, which takes an array of strings as its parameter. The method body has a single call to the method println with our greeting as the argument. Since the main method doesn’t return any value, its type is Unit.

The thing that may stand out to you is the use of the object declaration. This introduces a singleton object, which is a class with a single instance. Here, we are defining a class called HelloWorld and an instance of that class of the same name.

You may have also noted that the main method is not declared static. Scala does not support static members, so we define them as singleton objects.

Compiling code with Scala

Compiling our code is also a bit different here. For our Scala example above, we’d use scalac, which works like most compilers. For Scala, the object files that its compiler produces are Java class files.

So, say we saved our Hello World program in a file called HelloWorld.scala. We’d use the following command. This will generate some class files including one called HelloWorld.class.

> scalac HelloWorld.scala

Once we compile our program, we can run it with the scala command, which is just like the java command.

> scala -classpath . HelloWorld

Hello, world!

Scala Syntax Quick Guide

Now that we know the Hello World program with Scala, let’s quickly look at some basic Scala syntax that you’ll need to know. We won’t be defining terms here, as it’s assumed you already know them from Java or another language.

Variables

First, variables. Here’s how we declare a variable in Scala.

Compare this to Java's syntax, which follows this basic structure:

<variable type> <variable identifier>;

In our Scala code, we declare a variable with the name myFirstScalaVariable, which stores data of type Int and is assigned an initial value of 5. This is an immutable variable because we chose the keyword val.

In Scala:

Variables of type val are immutable

Variables of type var are mutable variables

Data Types

Scala has a type hierarchy with type Any at the top. Any is the super-type that defines universal methods such as equals, hashCode, and toString.

Any has two subclasses: AnyVal and AnyRef. AnyRef is for reference types, including types defined by Scala users. AnyVal represents our value types, of which there are nine:

Double
Float
Long
Int
Short
Byte
Char
Unit
Boolean

Below, we have a variable anyInAction of type Any. We can assign anyInAction a value of any type.

var anyInAction: Any = "A String" //String
println(anyInAction)

anyInAction = 5 //Int
println(anyInAction)

anyInAction = '☺' //Char
println(anyInAction)

anyInAction = 1.985 //Float
println(anyInAction)

anyInAction = true //Boolean
println(anyInAction)

Output:
A String
5
☺
1.985
true

Strings and Literals

Strings do not fall under anyVal. Rather, they are literals. Strings literals include a combination of characters that are surrounded by double quotation marks. The syntax for declaring a String is the same as declaring a variable of any basic value type.

val stringLiteral: String = "Hello"

// Driver Code
println(stringLiteral)

Integer Literals are used with the value types Long, Int, Short, and Byte. Scala will always print an integer literal as decimal regardless of how it is declared. Floating-point literals are used with Double and Float.

val floatLiteral: Float = 1.2345F // The F at the end is for Float
val somethingBigger: Double = 1.2345e1
val evenBigger: Double = 1.2345e4

// Driver Code
println(floatLiteral)
println(somethingBigger)
println(evenBigger)

Output:
1.2345
12.345
12345.0

Control Structures

Scala’s control structures are if, while, for, try, match, and function calls. In Scala, control structures return values like functions.

The if expression has the following syntax:

var arrayOfEmotions = Array("happy","sad","angry","excited")
if (!arrayOfEmotions.isEmpty) {
  arrayOfEmotions(0) = "joyful"
}

 // Driver Code   
 arrayOfEmotions.foreach(println)

The while expression uses the following syntax:

var count = 1
while (count <= 10) {
  println(count)
  count += 1
}

The general syntax of a for expression is as follows:

A generator defines a named variable and assigns it to a set of values. We construct it with three parts: a variable, a <-, and a generator expression.

for (i <- 1 to 5) {
  println(s"iteration $i")
}

User-defined functions

We can define functions in Scala. Take a look at this example, which takes two integers and returns their sum:

def sum(x: Double, y: Double): Double ={
  x+y
}

def is the keyword for defining a function
sum is the given name of the function
sum is followed by (). This is where you define the function parameters separated by commas.
(x: Double, y: Double) tells us that our function takes two parameters: x of type Double and y of type Double.
We define the return type of the function,Double, by inserting : Double after the (). Inserting the return type is not required.
Then we insert a =. Whatever comes after this is the body of the function. The body of the function is wrapped in curly brackets {}.

Note: You can choose not to use the curly brackets if the function’s body only consists of a single expression.

Objects and Classes in Scala

Unlike Java, which distinguishes primitive and reference types, Scala treats everything as an object, since Scala is a pure OOP language. In Scala, numbers are also treated as objects, so they also have methods. Take the following arithmetic expression:

1 + 2 * 3 / x

This expression is made with method calls since it is the same as the following expression, so + and * are valid identifiers in Scala.

1.+(2.*(3)./(x))

Classes

In Scala, classes are declared much like Java, but Scala classes can have parameters. Look at this basic class definition in Scala using the class keyword and var keyword to define our properties (called fields in Scala).

class Person{
  var name: String = "temp"
  var gender: String = "temp"
  var age: Int = 0
}

To define the methods of our class, we use this syntax:

class Person{
  var name: String = "temp"
  var gender: String = "temp"
  var age: Int = 0

  def walking = println(s"$name is walking")

  def talking = println(s"$name is talking")

}

And now we can create instances of our classes using val.

// Creating an object of the Person class
val firstPerson = new Person 

firstPerson.name = "Mary"
firstPerson.gender = "female"
firstPerson.age = 25


println(firstPerson.name)
println(firstPerson.gender)
println(firstPerson.age)

Calling functions within functions

In Scala, functions are also treated as objects, so we can pass functions as arguments, store them in variables, or return them from other functions. This is one valuable feature of functional programming that Scala provides.

Take a look at this example below where we are calling the function square in the other function SquareSum.

def square(x: Double) = {
  x * x
}
def squareSum(x: Double, y: Double) = {
  square(x) + square(y)
}

val result = squareSum(2,5)

// Driver Code
println(result)

Inheritance and Overriding

There are several types of inheritance supported by Scala:

Single-level Inheritance: One class inherits from a single other class
Multilevel Inheritance: One class extends another which then extends another
Multiple Inheritance: One class inherits from multiple base classes

In Scala, all classes inherit from a superclass, and when no superclass is declared, Scala uses scala.AnyRef. You can override methods that are inherited from a superclass, but you must explicitly specify this using the override modifier. For example:

class Complex(real: Double, imaginary: Double) {
  def re = real
  def im = imaginary
  override def toString() =
    "" + re + (if (im >= 0) "+" else "") + im + "i"
}

Traits with Scala

Scala uses Traits, which are similar to Java interfaces. Much like inheritance with Scala like above, a class can also import code from one or more traits. When this happens, a class implements the given trait’s interface and all code in that trait.

Think of this as a way to implement reusable behavior in Scala code.

The basic properties of a Trait are:

Traits specify the signature of the methods that a given supports.
Traits are declared like classes with the trait keyword Take a look at this example:

trait Iterator[A] {
  def hasNext: Boolean
  def next(): A
}

In Scala, we can use the extends keyword to extend a trait. Then, we implement any abstract members with the override keyword:

// from Scala documentation 
trait Iterator[A] {
  def hasNext: Boolean
  def next(): A
}

class IntIterator(to: Int) extends Iterator[Int] {
  private var current = 0
  override def hasNext: Boolean = current < to
  override def next(): Int = {
    if (hasNext) {
      val t = current
      current += 1
      t
    } else 0
  }
}


val iterator = new IntIterator(10)
iterator.next()  // returns 0
iterator.next()  // returns 1

Next steps for your Scala journey

Congrats on making it to the end. You're now well on your way to transitioning to being a Scala developer. As you can see, Scala empowers you to utilize your existing Java skills. There is still a lot to learn about Scala, and hands-on practice will be essential to mastering this language.

For next steps, we recommend the following concepts:

Generics with Scala
Higher-order functions
Currying
Scala's Collection Library

To get started with these concepts and start building with Scala, check out Educative's course Learn Scala from Scratch.
This course will help you stay ahead of the curve, make awesome, scalable apps, and learn a highly coveted new programming language. By the end, you'll be fully transitioned from Java to Scala!

Happy learning!

Continue learning about Scala and Java

How and why to change to a different software track

Amanda Fawcett — Mon, 15 Mar 2021 20:23:39 +0000

Many developers choose to stick with their programming domain, but others venture out and shift their career trajectory in the tech space. Educative’s recent community survey, in fact, reports that nearly 59% of users plan to change careers in the coming year.

Career shifts in the IT space are a great option for many people, though they come with a unique set of challenges. To make a transition to a new tech specialty, you need a record of projects, training, and skills.

No matter your end goal, I want to help you take that new step and begin your journey of reshifting your career. I will discuss some important options to consider and recommend some steps for building out a new career path.

This guide at a glance:

When to change software specialities
Consider switching roles internally
Consider a smaller company
Fill your knowledge gaps strategically
Take the first step

When to change software specialities

There are many reasons that you may choose to change IT specialities in your career, and the reason behind your transition can drastically change the way you approach a shift. This is a big decision, so it’s important to understand your motivations.

Let’s look at three common reasons that someone might want to switch their career specialities and discuss some outcomes of each.

You’re experiencing burnout

Some people want a career shift because they are burnt out with their current role or company. Burnout is real, so don’t ignore the signs, but do think strategically.

The challenge here is to seek a job that really meets your needs rather than rushing into the next thing. Oftentimes, those with burnout jump at the first opportunity to try something new instead of planning strategically.

If you find yourself in this boat, consider your options before making a sudden career change. A shift in career speciality can be risky, so if you’re burnt out, consider a safer option. Perhaps look into other companies with similar roles or adjacent occupations that utilize the skills you already have.

You’ve lost interest in your speciality

Sometimes, we lose interest in things that once excited us, and there is nothing wrong with that. Maybe a new technology has come out since you first became a programmer, and it really interests you. Or maybe you’re just bored with the language and tools you’re using.

If you fall into this category, the main challenge is about eliminating knowledge gaps. After all, you want to work with new technologies, so you need to learn them! But before making a sudden shift in IT specialization, first consider ways to integrate new technologies with your current tasks or workflow. You can also request training at your current job for a new technology and make a case for why it’s essential.

If that isn’t an option to you, it may be time to start filling your knowledge gaps on your own, which we will discuss later.

You want to increase income potential

Fact: some technologies and IT specialities pay more than others. According to StackOverflow’s 2020 survey, for example, data scientists make an average of $58k annually while frontend developers make $49k annually. There is nothing wrong with wanting a higher salary, especially if you can master the skills to take you there. And some specialities, let’s face it, don’t necessarily propose higher salaries for the future.

The challenge here is to seek a speciality shift based on income potential, in other words, the potential salary you could make with a certain speciality down the line. According to Dev Skiller, a front end developer can earn $87,564 after accruing 10-19 years of experience, while a data scientist with only 4-8 years of experience can earn, on average, $128,750 annually.

If you are unable to negotiate a higher salary at your current role, or if you don’t see much payout down the line, it may be time to forge a new path.

Note: Keep in mind that you’ll likely be starting at a lower level, but your salary will grow over time, so you’ll need to be patient.

Consider switching roles internally

Switching IT specialities doesn't necessarily mean you have to start from scratch. This may not be possible for everyone, but those looking to switch IT specialities could consider moving roles within your current company. It is okay to ask your manager for chances to try out another IT specialities or field, though you may have to argue your case a bit here.

The benefits to this are security. You can retain the benefits, familiarity, and security of your current place of employment while still branching out to new ventures. A solid organization that is invested in its employees should welcome a transition like this.

If you are not yet comfortable requesting a shift in your role, you could start by advocating for ongoing learning opportunities. For example, if you want to transition from web apps to machine learning, consider a reskilling initiative on how to use ML in your companies' web apps. This way, you learn new skills and demonstrate a dedicated interest in new topics.

Consider a smaller company

Bigger companies do offer a wide variety of opportunities, but smaller companies are often on the lookout for a jack-of-all-trades developer who can wear multiple hats and develop new ideas on the job. If you want to switch careers but don’t have the flexibility to re-learn a new technology, then consider looking into a startup or small company.

A smaller company may provide you with the chance to develop skills or topics outside your area of expertise.

On top of that, applications to technical roles at smaller companies tend to be less stringent in terms of formal experience and requirements. Since roles at small companies and startups shift more regularly, they are more interested in a person’s potential than finding an exact match to a role.

This way, you can gain more experience with new technologies, fields, and specialities on the job and build a portfolio as you go. You'll also get to experiment with multiple roles to see what suits you best, as there is more flexibility.

Fill your knowledge gaps strategically

No matter how you choose to switch career specialities in tech, there will be things to learn. But filling your knowledge gaps should be done strategically, since it requires a lot of time investment. Here is some basic advice about learning strategically:

Research: Don't just jump into the first thing that interests you. Start by asking people who work with certain technologies how they learned those topics. Read detailed career roadmaps to understand what you really need to master to make the transition.
Leverage your current skills: Some technologies are easier to learn off of others. If you already know C#, for example, you can more easily learn Python in tandem. Or, if you want to learn JavaScript, learn it alongside a popular library like React to double your skills.
Find time to learn at work: If you are switching roles internally, consider re-skilling initiative within your company. This way, you don't have to spend time outside of work learning the skills you need. Check what programs your company has and advocate for one that meets your needs.
Build things and get certificates: If you are trying to get a new role with a new company, you should learn in a way that you can prove to a new employer. You proof that you've learned new skills, so I recommend either contributing to open-source projects or taking courses that offer accredited certificates.

Take the first step

Transitioning to a new software speciality is a great option for many developers, and an exciting one! Have the confidence to forge a new path. The first step to take on this new journey largely depends on your end goal, but filling knowledge gaps will be part of any plan.

I recommend starting with a curated learning path to aid your learning. This way, you can explore new fields, skip sections you already know, and leverage your current programming skills. Educative offers over 15, hand-crafted learning paths aimed at career development, including React for Front End Developers, Python Data Visualization, and more.

Explore a new IT speciality and learn the skills you need to get there with hands-on practice and real-world projects. By the end, you'll be ready to jump into a new tech speciality and reach your goals.

Happy learning!

8 tricks and best practices for improving your Ruby code

Amanda Fawcett — Thu, 11 Mar 2021 19:00:21 +0000

Software developers sometimes think that productivity means writing code as fast as possible. But true productivity with a programming language comes down to the quality of your code.

Ruby is a unique, versatile language that can be used to build just about anything. Ruby, though simple and easy to learn, requires in-depth knowledge and experience to be used to its full potential.
So, today, we’ve compiled our best tips, tricks, and best practices to help you make the most of Ruby.

This guide at a glance:

Tip 1: Avoid hidden structures
Tip 2: Avoid while !(not)
Tip 3: Use loop do over while(true)
Tip 4: Use Double Pipe Equals ||= for your methods
Tip 5: Patch the Garbage Collector (GC)
Tip 6: Use Hash[...] to create a hash from a list of values
Tip 7: Avoid functions that don’t work well with iterators
Tip 8: Follow Ruby best practices
Next steps for your learning

Tip 1: Avoid hidden structures

Hidden structures will make your Ruby code hard to maintain in the long run, and it is best to avoid them. Take a look at this code:

class ObscuringReferences
  def initialize(data)
    @data = data
  end

  def calculate
    data.collect do |cell|
      cell[0] + (cell[1] * 2)
    end
  end

  private

  attr_reader :data
end

ObscuringReferences.new([[100, 25], [250, 22], [984, 30], [610, 42]])

What’s the problem here? We are using the array’s index positions to get information for the calculate method. However, it’s hard to tell what information we are gaining, because 0 and 1 are not clearly defined and therefore not too useful.

Instead, we can use constants to assign meaningful information to our values, like this:

class RevealingReferences
  HEIGTH  = 0
  WIDTH = 1

  def initialize(data)
    @data = data
  end

  def calculate
    data.collect do |value|
      value[HEIGTH] + (value[WIDTH] * 2)
    end
  end

  private

  attr_reader :data
end

We can also avoid hidden Ruby structures by using Struct to represent the data in a meaningful way.

Tip 2: Avoid `while !(not)`

The while !(not) loop can be used to test code until a condition is not met. In the example below, the condition is essentially saying “while download is not finished (execute the code block)”.

while !download.is_finished?
  spinner.keep_spinning
end

Clearly, this can lead to some confusion because it isn’t natural to the way we think about negatives and positives. Instead, we can use until, which is essentially like the the negative version of while.

until download.is_finished?
  spinner.keep_spinning
end

In this revised version, the until condition reads more naturally: “until download is finished (execute the code block)”. This will help make your code more readable and easier to skim.

Tip 3: Use `loop do` over `while(true)`

The loop do offers much cleaner syntax than the while(true) conditional for many cases. Take a look at the comparison here:

# while 
def play
    get_guess
    while true
        ...
        ...
    end
end

# loop do
def play
    get_guess
    loop do
        ...
        ...
    end
end

In general, loop do offers cleaner, better syntax when you're handling with external iterators. Similarly, loop do also allows you to loop through two collections simultaneously, which leads to cleaner, easier Ruby code.

iterator = (1..9).each
iterator_two = (1..5).each

loop do
    puts iterator.next
    puts iterator_two.next
end

#=> 1,1,2,2,3,3,4,4,5,5,6.

Tip 4: Use Double Pipe Equals `||=` for your methods

Double Pipe Equals is a great way to write concise Ruby code. It is equivalent to the following:

a || a = b

a ||= b works like a conditional assignment operator, so if a is undefined or false, then it will evaluate b and set a to that result. Or, if a is defined and true, then b will not be evaluated.

This operator is great for creating methods in your classes, especially for calculations.

def total
  @total ||= (1..100000000).to_a.inject(:+)
end

Tip 5: Patch the Garbage Collector (GC)

Ruby’s Garbage Collector (GC) is known for being slow, especially in versions before 2.1. The algorithm for Ruby’s GC is “mark and-sweep” (the slowest for garbage collectors), and it has to stop the application during garbage collection processes.

To fix this, we can patch it to include customizable GC extensions. This will really help with speed when your Ruby application scales.

You can use tuning variables based on which version of Ruby you use, and many patches are available on GitHub if you don’t want to hard-code them in. Here are three as an example:

RUBY_GC_HEAP_INIT_SLOTS: initial allocation slots
RUBY_GC_HEAP_FREE_SLOTS: prepare at least this number of slots after GC, and allocate slots if there aren’t enough.
RUBY_GC_HEAP_GROWTH_MAX_SLOTS: limit allocation rate to this number of slots.

Tip 6: Use `Hash[...]` to create a hash from a list of values

You can easily create a hash from a list in Ruby using Hash[...], for example:

Hash['key1', 'value1', 'key2', 'value2']

# => {"key1"=>"value1", "key2"=>"value2"}

Imagine that we’ve collected data in a tabular format. It is organized with one array representing the column headers and an array of arrays representing the values of our rows.

columns = [ "Name", "city", "employed"]

rows = [ 
  [ "Matt",   "Seattle",    true ], 
  [ "Amy",  "Chicago", true], 
  [ "Nice", "Lahore",     false ]
]

The keys for our final hashes will be the column array that holds our column names, and the tabular data is our array of arrays, holding the rows data. We want to create an array of hashes so that each hash key is the column name, and the row is the value.

# Hard way 
results = []

for i in (0...rows.length)  
  h = {}
  for j in (0...columns.length)    
    h[columns[j]] = rows[i][j]    
  end
  results << h
end

results

# Easier way
correlated = rows.map{|r| Hash[ columns.zip(r) ] }

Tip 7: Avoid functions that don’t work well with iterators

When working with iterators in Ruby, complexity is important. So, we need to avoid slower methods and find an alternative that offers better performance but leads to the same result.

Notably, the method Date#parse method is known for poor performance. Instead, we should specify an expected date format when parsing our code. For example, say we want to work with the dd/mm/yyyy format:

Date.strptime(date, '%d/%m/%Y')

In terms of type checks, Object#class, Object#kind_of?, and Object#is_a? can lead to poor performance as well when used with loops. Instead, it’s better to write the function calls away from iterators that are frequently called.

Tip 8: Follow Ruby best practices

Best practices with Ruby help us to write code that is concise and easy to work with down the line. Let’s look at a few that you can implement today.

When possible, use existing gems instead of writing code from scratch for more optimized code.
To avoid using for loops, use the each method for a block
Use ternary operators to write shorter code
Instead of writing length if statements, use case/when and unless/until/while conditionals
Use the splat * operator to group inputs into an array when your methods have an unfixed number of inputs. use symbols instead of strings in hashes
Avoid using comments unless they are necessary. Ideally, your code should be clear enough on its own to not need commenting.
Use the double bang !! to write methods that determine if a given value exists
Use an APM during development. This will help you immediately know when something new to your code has caused a drop in performance.
When writing methods yourself, remember two simple rules: a method should only do one thing, and it needs a clear name that reflects this singular purpose.

Next steps for your learning

These tips and best practices will help you write more readable and clearer Ruby code for improved performance. Ruby is a great language, with a lot of quirky syntactical tricks. To make the most of this language, you should study everything you can about it.

Some good things to look into with Ruby are:

Concurrency and multithreading techniques
Tracking running processes
When to use nil
Converting base numbers

To help you make the most of Ruby, Educative has created two courses on Ruby for different skill levels, (beginner) Learn Ruby from Scratch and (more advanced) Ruby Concurrency for Senior Engineering Interviews. These courses use hands-on practice and real-world examples to teach you how to use Ruby most effectively.

Happy learning!

Continue reading about Ruby and programming tips

How to become a Golang developer: 6 step career guide

Amanda Fawcett — Tue, 09 Mar 2021 21:39:19 +0000

Note: We recognize that every person has a different career path when it comes to Go. This is not meant to be a definitive guide but rather a rough outline of the skills to learn. If you've had a different experience as a Go developer, please share them below.

Golang (also called Go) is an in-demand programming language, especially for people working with Google products. Go is used by many big companies, like Uber Medium, Dropbox, Salesforce, Netflix, IBM, and Twitter.

Go is a great option for job seekers of all levels. But how do you get started? What do you need to know? Today, we will discuss the best path for learning Go and building a solid portfolio.

This career guide at a glance:

What is a Go developer?
Step 1: Learn the basics of Go
Step 2: Master Go libraries and other tools
Step 3: Learn testing with Go
Step 4: Understand Go patterns
Step 5: Start building your portfolio
Step 6: Practice Go coding interview questions
What to learn next

What is a Golang developer?

Golang (also called Go) is a statically typed, compiled programming language that was developed by Google in 2009. The language combines the efficiency of C++ efficiency and the readability of Python.

Golang developers use the Go language to build webpage and software products. A Go developer's general duties include working with Go and using its full suite of tools and frameworks. Most Go developers also do testing and debugging.

Most job postings for Golang developers require a wide variety of other skills as well, the most common being:

Experience with scripting (Shell/PERL)
Experience in application design using design patterns
Javascript, SOAP, REST Webservices, or Microservices
Experience using Git
Knowledge of DevOps practices

The entry threshold for Go is relatively low. It's an easy language to learn and comes with a detailed technical documentation. Switching to Go is relatively easy for those who have C-language experience. So, if learning Go is easy, how do you actually get a job working with the language? Let's break it down.

Step 1: Learn the basics of Go

To become a Go developer, you need to have a solid understanding of the language and syntax. You can start by installing the language and teaching yourself, or you can take an online course to guide your learning. The good path for learning Go will look something like this:

Filenames, keywords, identifiers
Operators, types, functions, and constants
Pointers, structures, methods
Maps, arrays, slices
Go CLI
Interface
Error handling
Goroutine, Channel, Buffer
Panic, Defer, Error, Recover
Go design patterns

Your learning path will largely depend on your background. If you are completely new to programming, Go is a great first choice. It is easy to learn and mimics other popular languages like Python and C++. For new learners, it's best to start with the basics like filenames, keywords, and identifiers. Then, you can build your foundation with data types, operators, and and strings.

If you already have some programming experience, it's also recommended to learn Go from scratch, starting with the unique characteristics of Go. Go is built on a different model than what you're used to, and it treats object oriented programming differently.

Go aims to reduce typing and complexity using a minimal amount of keywords, so you will code less than other languages like Java. Keywords can be parsed without a symbol table, as its grammar is LALR(1). Go acts like a hybrid, imperative language, but it is built with concurrency in mind. Here are some of the unique features of Go:

No function or operator overloading
No implicit conversions to avoid bugs
No classes or type inheritance
No variant types
No dynamic code loading or dynamic libraries
No assertions or immutable variables

package main
import "fmt"

func main() {
    fmt.Printf("Hello World")
}

Step 2: Master Go libraries and other tools

Once you have the basics of the language down, you should move onto the add-on libraries and tools that make Go easier to use. Most companies will expect that you have experience with:

Go dependency management tools
Semantic versioning
Scripts and repositories
Go libraries
SQL fundamentals
GIT
Basic authentication
HTTP/HTTPS
Web frameworks and routers
Relational databases (PostgreSQL)

If you already have some programming experience, you may have some of these under your tool-belt already. If not, don't panic! You will learn most of these skills as you learn how to build with Golang and related technologies.

The most important extra things to learn are frameworks, Go libraries, and databases. Many of the other skills can be learned along the way or on the job.

In terms of frameworks, is recommended to start with the web frameworks Echo, Beego, Gin, Revel, and Chi, with Echo being the most important for Go.

In terms of libraries, the most popular Go libraries are Go Kit, GORM, Gen, and CLI. Using good libraries and packages will make working with Go even easier. Each will have their own unique features, so it's a good idea to pick one that aligns with your goals.

In terms of databases, it's important to have some experience with relational databases, such as PostgreSQL or MySQL. Beyond that, knowledge of log frameworks can be useful, with Zap being the most important for Go.

Step 3: Learn testing with Go

Testing is an important skill that most companies will be looking for. Software testing is how we check if the actual software product matches requirements and actually runs properly once distributed.

As a Go developer, you'll be building products for the real-world, so you need to test your products for usability and reliability. This includes:

Unit testing
Integration testing
Behavior testing
E2E testing

Unit testing is arguably the most important for new Go developers. There is a built-in testing package in Go’s standard library. But, Go errs on the side of minimalism, so you may need additional tools for more robust testing, such as popular frameworks Ginkgo and GoCheck. Ginkgo can also be used to behavior testing and integration testing.

Step 4: Understand Go patterns

Most employers want to see that you understand Go's design patterns. A design pattern is a repeatable, general solution to a commonly problem in software design. Different design patterns help to divide business logic or define structure to help with certain tasks.

Go offers similar design patterns to other languages that fall under these general categories:

Structural
Creational
Behavioral
Concurrency
Stability

The most important are creational (such as builder, factory, singleton), behavioral (such as iterator, observer, command), and structural (such as adapter, bridge, decorator).

If you are already a programmer, you may be familiar with design patterns and can start learning them in the context of Go. If you're new to programming, the best way to learn these is to actually begin coding with them. Borrow some sample implementations and build around them.

Step 5: Start building your portfolio

Once you have these steps down, it's time to start building things for your portfolio. This is how a company will see that you have real experience working with Golang. Also, it's proven that the best way to master a language is to build functioning products with it, so the more you build, the more you learn.

Building out a portfolio includes:

Completing online courses on Go
Contributing to open source Go projects
Building Go projects from scratch
Implementing Go units in existing projects
Coding classic algorithm problems with Go
Completing courses on adjacent technologies (i.e. SQL)

You can really build anything you want to put your skills into practice, such as to do lists for personal needs, demo websites, puzzles, games, and coding challenges.

Start with an online course that offers a certificate. You can add this to your resume to prove you have the basics down. Then, focus on open source contributions on GitHub. This demonstrates that you can build real projects and know how to use a popular version control system.

Step 6: Practice Go coding interview questions

Once you have a solid portfolio, you can start practicing Go interview questions. This will help you prepare for interviews and learn more about the language you've just learned. Coding interview questions are not the end-all-be-all since they tend to be abstract, but they can really improve your code and help you work under pressure.

When you get an Go developer interview, you'll be expected to answer these questions in time, so getting practice early on can't hurt! It'll also help reveal any gaps in your knowledge.

Some common questions include:

What is a goroutine? How do you stop it?
How do can check variable type at runtime?
How do you format a string without printing?
How do you concatenate strings in Go?
What is Go 2?
How do you initialize a struct in Go?

What to learn next

Congrats on making it to the end! You should be well on your way to becoming a Golang developer. Clearly, there is a lot that lies ahead. Where you start largely depends on your base knowledge, but it's recommended to learn Go from scratch. Your next steps should be:

Learn Go syntax
Understand basic data types
Build something using control structures
Get practice with functions

To get started with Go, check out Educative's course The Way to Go. You will learn the core constructs and techniques and dive intro advanced Go concepts like error-handling, networking, and templating.

Happy learning!

Continue learning about Golang and Google

Crack coding interviews by building these 5 real-world features

Amanda Fawcett — Fri, 05 Mar 2021 23:45:55 +0000

Preparing for coding interviews is no easy task. You need the skills to break down the problem and to deploy the right tools. Trying to memorize 1500+ Leetcode problems is not the best way to succeed.

That’s why we want to approach interview prep a bit differently today by tackling some real world problems faced by tech companies. Learning how to build real world features (like “how to merge recommendations on Amazon”) is more fun, and it's much easier to remember what you learned. If you can understand a problem’s underlying pattern, you can apply it to just about any question.

We will dive into the solutions for a few common real world coding problems and build 5 features. We will offer our solutions in Java. If you'd like to see them in Python, check out my original post.

This tutorial at a glance:

Netflix Feature: Group Similar Titles (hash maps)
Facebook Feature: Friend Circles (DFS)
Google Calendar Feature: Find Meeting Rooms (heaps)
Amazon Feature: Products in Price Range (BST)
Twitter Feature: Add Likes (strings)
Where to go from here

Netflix Feature: Group Similar Titles (hash maps)

Netflix is one of the biggest video streaming platforms out there. The Netflix engineering team is always looking for new ways to display content. For this first problem, imagine you’re a developer on these teams.

Task: Our task here is to improve search results by enabling users to see relevant search results without being hindered by typos, which we are calling the "Group Similar Titles" feature.

First, we need to determine how to individually group any character combination for a given title. Let’s imagine that our library has the following titles: "duel", "dule", "speed", "spede", "deul", "cars". You are tasked to design a functionality so that if a user misspells a word (for example speed as spede), they will still be shown the correct title.

First, we need to split our titles into sets of words so that the words in a set are anagrams. We have three sets: {"duel", "dule", "deul"},{"speed", "spede"}, and {"cars"}. The search results should include all members of the set that the string is found in.

Note: It’s best to pre-compute our sets rather than forming them when a user searches.

The members of each set have the same frequency of each alphabet, so the frequency of each alphabet in words in the same group is equal. For example, in our set {{"speed", "spede"}}, the frequency of the characters are the same in each word: s, p, e, and d.

So, how do we design and implement this functionality? Let’s break it down.

For each title, we need to compute a 26-element vector. Each vector element represents the frequency of an English letter in a title. We can represent frequency using a string that is fixed with # characters. This mapping process generates identical vectors for the strings that are anagrams. For example, we represent abbccc as #1#2#3#0#0#0...#0.
We then use this vector as a key for inserting titles into a Hash Map. Our anagrams will all be mapped to the same entry. When a user searches a title or word, it should compute the 26-element English letter frequency vector based on input. It will then search the Hash Map and return all the map entries using the vector.
We then store a list of calculated character counts as a key in a Hash Map and assign a string as its value.
Each value is an individual set, so we return the values of the Hash Map.

import java.util.*;
class Solution {
    public static List<List<String>> groupTitles(String[] strs){
      if (strs.length == 0) 
            return new ArrayList<List<String>>();

        Map<String, List<String>> res = new HashMap<String, List<String>>();

        int[] count = new int[26];
        for (String s : strs) {
            Arrays.fill(count, 0);
            for (char c : s.toCharArray()){
                int index = c - 'a';
                count[index]++;
            }

            StringBuilder delimStr = new StringBuilder("");
            for (int i = 0; i < 26; i++) {
                delimStr.append('#');
                delimStr.append(count[i]);
            }

            String key = delimStr.toString();
            if (!res.containsKey(key)) 
                res.put(key, new ArrayList<String>());

            res.get(key).add(s);
        }

        return new ArrayList<List<String>>(res.values());
    }

    public static void main(String[] args) {
        // Driver code
        String titles[] = {"duel","dule","speed","spede","deul","cars"};

        List<List<String>> gt = groupTitles(titles);
        String query = "spede"; 

        // Searching for all titles
        for (List<String> g : gt){
            if (g.contains(query))
                System.out.println(g);
        }
  }
}

Complexity measures

n is the size of the list of strings, and k is the maximum length of a single string.

Time Complexity: O(n*k), since we are counting each letter for each string in a list

Space Complexity: O(n*k), since every string is stored as a value in the dictionary, and the size of the string can be k.

Facebook Feature: Friend Circles (DFS)

Facebook is the biggest social media company in the world. They also own and operate Instagram. Pretend you are a Facebook engineer team, and you are tasked to improve integration among their sister platforms.

Task: Our task here is to find all the people on Facebook that are in a user’s friend circle, which we are calling the “Friend Circles” feature.

We need to first identify the people that are in each user’s friends circle, which includes users that are directly or indirectly friends with another user. Let’s assume there are n users on Facebook. The friendship connection is transitive.

Example: If Nick is a direct friend of Amy, and Amy is a direct friend of Matt, then Nick is an indirect friend of Matt.

We will use an n*n square matrix. For example, cell [i,j] will hold value 1 if these users are friends. If not, the cell will hold the value 0. In the illustration below, there are two friend circles in the above example. Nick is only friends with Amy, but Amy is friends with Nick and Matt. This forms a friend circle. Mario makes another friend circle on his own.

Think of our symmetric input matrix as an undirected graph. Both the indirect and direct friends who are in one friend circle also exist in one connected component in our graph. This means that the number of connected graph components will give us how many friend circles we have.

So, our task is to find the number of connected components. We treat the input matrix as an adjacency matrix. So, how do we design and implement this? Let’s break it down.

First we initialize an array, named visited. This will track the visited vertices of size n with 0 as the value for each index.
Then, we traverse the graph using DFS if visited[v] is 0. If not, we move to the next v.
Then, set visited[v] to 1 for every v that our DFS traversal runs into.
When the DFS traversal is done, we should increment the circles counter by 1. This means that a connected component has been fully traversed.

class Solution {

  public static void DFS (boolean[][] friends, int n, boolean[] visited, int v) {
    for (int i = 0; i < n; ++i) {

        // A user is in the friend circle if he/she is friends with the user represented by
        // user index and if he/she is not already in a friend circle
        if (friends[v][i] == true && !visited[i] && i != v) {
            visited[i] = true;
            DFS(friends, n, visited, i);
        }
    }
  }

  public static int friendCircles(boolean[][] friends, int n) {
    if (n == 0) {
        return 0;
    }

    int numCircles = 0;     //Number of friend circles

    //Keep track of whether a user is already in a friend circle
    boolean visited[] = new boolean[n];

    for (int i=0;i < n; i++){
      visited[i] = false;
    }

    //Start with the first user and recursively find all other users in his/her
    //friend circle. Then, do the same thing for the next user that is not already
    //in a friend circle. Repeat until all users are in a friend circle. 
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            visited[i] = true;
            DFS(friends, n, visited, i); //Recursive step to find all friends
            numCircles = numCircles + 1;
        }
    }

    return numCircles;
  }

  public static void main(String args[]) 
  { 
      int n = 4;
      boolean[][] friends = {
        {true,true,false,false},
        {true,true,true,false},
        {false,true,true,false},
        {false,false,false,true}
      };
     System.out.println("Number of friends circles: " + friendCircles(friends, n)); 
  } 

}

Complexity measures

Time Complexity: O(n^2) because we traverse the complete matrix of size n^2

Space Complexity: O(n) because the visited array that stores our visited users is of size n.

Google Calendar Feature: Find Meeting Rooms (heaps)

The Google Calendar tool is part of the GSuite used to manage events and reminders. Imagine you are a developer on the Google Calendar application team, and you’re tasked with implementing some productivity enhancing features.

Task: Your goal is to create a functionality for scheduling meetings. You need to determine and block the minimum number of meeting rooms for these meetings.

To do this, we are given a some meeting times. We need to find a way to identify the number of meeting rooms needed to schedule them all. Each meeting will contain positive integers for a startTime and an endTime.

Our meeting times can be listed as follows: {{2, 8}, {3, 4}, {3, 9}, {5, 11}, {8, 20}, {11, 15}}. We could schedule each meeting in a separate room, but we want to use the minimum amount of rooms. We observe that three meetings overlap: {2, 8}, {3, 4}, and {3, 9}. Therefore, at least these three will require separate rooms.

To solve this, we use either a heap or priority queue for storing meeting timings, using end_time of each meeting as a key. The room at the top of our heap would become free earliest. If the meeting room from the top of the heap is not free, then no other room is free yet.

So, how do we build this functionality? Let's break it down.

Sort the meetings by startTime.
Allocate the first meeting to a room. Add the endTime as an entry in the heap.
Traverse the other meetings and check if the meeting at the top has ended.
If the room is free, extract this element, add it to the heap again with the ending time of the current meeting we want to process. If it is not free, allocate a new room and add it to our heap.
After processing the lis of meetings, the size of the heap will tell us how many rooms are allocated. This should be the minimum number of rooms we need.

import java.util.Arrays; 
import java.util.PriorityQueue;
class Solution {

    public static int minMeetingRooms(int[][] meetingTimes){

        if(meetingTimes.length == 0){
            return 0;
        }

        Arrays.sort(meetingTimes, (a, b) -> Integer.compare(a[0], b[0]));       
        //min Heap keeps track of earliest ending meeting:
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((A, B) -> A - B);

        minHeap.add(meetingTimes[0][1]);

        for (int i = 1; i < meetingTimes.length; i++) {
            int currStart = meetingTimes[i][0];
            int currEnding = meetingTimes[i][1];
            int earliestEnding = minHeap.peek();

            if (earliestEnding <= currStart) {
                minHeap.remove();
            } 
            //update heap with curr ending
            minHeap.add(currEnding);
        }
        return minHeap.size();
    }

    public static void main( String args[] ) {
        // Driver code
        int[][] meetingTimes = {{2, 8}, {3, 4}, {3, 9}, {5, 11}, {8, 20}, {11, 15}};
        System.out.print(minMeetingRooms(meetingTimes));
    }
}

Complexity Measures

Time complexity: O(n*log(n))

Space complexity: O(n), where n is the number of meetings

Amazon Feature: Products in Price Range (BST)

Amazon is the largest online store around the world, and they are always on the lookout for better ways to recommend products to their customers. Imagine you are a developer for Amazon's store.

Task: Implement a search filter to find products in a given price range. The product data is in the form of a binary search tree. The values are the prices of products.

The parameters we are working with are low and high, which represent a user's price range. The example list of products below are mapped to their prices.

They are then stored in a binary search tree:

We can assume that the selected price range is low = 7 and high = 20, so our function solution should only return the prices {9, 8, 14, 20, 17}. So, how do we implement this? Let's break it down.

We will solve this problem using a variation of a preorder traversal on a binary tree, but other binary tree traversals would work as well.

Implement a recursive helper function for a preorder traversal.
Check heck if the current node value is in our given range. If so, add it to the output array.
Recursively call the preorder function on the left child of the node if the current node value greater than or equal to low.
If the current node value is less than or equal to high, recursively traverse the right child of the node.
When traversal is completed, the output array will be returned.

main.java

class Solution {
    public static void preOrder(Node node, int low, int high, List<Integer> output){
        if (node != null) {
            if (node.val <= high && low <= node.val)
                output.add(node.val);
            if (low <= node.val)
                preOrder(node.leftChild, low, high, output);
            if (node.val <= high)
                preOrder(node.rightChild, low, high, output);
        }
    }
    public static List<Integer> productsInRange(Node root, int low, int high){
        List<Integer> output = new ArrayList<Integer>();
        preOrder(root, low, high, output);
        return output;
    }
    public static void main( String args[] ) {
        // Driver code
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(9);
        bst.insert(6);
        bst.insert(14);
        bst.insert(20);
        bst.insert(1);
        bst.insert(30);
        bst.insert(8);
        bst.insert(17);
        bst.insert(5);

        System.out.println(productsInRange(bst.root, 7, 20));
    }
}

BinarySearchTree.java

public class BinarySearchTree{
    public Node root;
    public BinarySearchTree(){
        this.root = null;
    }

    public void insert(int val){
        if (this.root == null)
            this.root = new Node(val);
        else
            this.root.insert(val);
    }
}

class Node{
    public int val;
    public Node leftChild;
    public Node rightChild;

    public Node(int val){
        this.val = val;
        this.leftChild = null;
        this.rightChild = null;
    }

    public void insert(int val){
        Node current = this;
        Node parent = current;
        while (current != null){
            parent = current;
            if (val < current.val)
                current = current.leftChild;
            else
                current = current.rightChild;
        }
        if(val < parent.val)
            parent.leftChild = new Node(val);
        else
            parent.rightChild = new Node(val);
    }
}

Time complexity

Time complexity: O(n)

Space complexity: O(n)

Twitter Feature: Add Likes (strings)

Twitter is a popular social media platform. Imagine you're a Twitter developer, and your team must create an API that calculates the number of likes on a given person’s Tweets.

Task: Create an API that calculates the total number of likes on a person’s Tweets. Create a module that takes two numbers and returns the sum of the numbers.

The data is already extracted and stored in a simple text file for you. All of the values should remain strings and cannot be converted into integers. We must do digit-by-digit addition due these restrictions. So, how do we create this module? Let's break it down.

Initialize an empty res variable and the carry as 0.
Then, set two pointers, p1 and p2, that will point to the end of like1 and like2.
Traverse the strings from the end using these pointers. Set it to stop when both strings are done.
Set x1 equal to a digit from string like1 at index p1. If p1 has reached the beginning of like1, set x1 to 0. Do the same for x2 with like2 at index p2.
Compute the current value using value = (x1 + x2 + carry) % 10. Then update the carry so that carry = (x1 + x2 + carry) / 10.
Append the current value to the result.
If both of the strings are traversed but the carry is still non-zero, append the carry to res.
Lastly, reverse the result and convert it to a string. Return the final string.

class Solution {
    public static String addLikes(String like1, String like2){
        StringBuilder res = new StringBuilder();

        int carry = 0;
        int p1 = like1.length() - 1;
        int p2 = like2.length() - 1;
        while (p1 >= 0 || p2 >= 0) {
            int x1, x2;
            if(p1 >= 0)
                x1 = like1.charAt(p1) - '0';
            else 
                x1 = 0;
            if(p2 >= 0)
                x2 = like2.charAt(p2) - '0';
            else 
                x2 = 0;
            int value = (x1 + x2 + carry) % 10;
            carry = (x1 + x2 + carry) / 10;
            res.append(value);
            p1--;
            p2--;    
        }

        if (carry != 0)
            res.append(carry);

        return res.reverse().toString();
    }
    public static void main(String args[]) {
        System.out.println(addLikes("1545", "67"));
    }
}

Complexity measures

Time complexity:
O(max(n^1,n^2)), where n^1 and n^2 are the lengths of the input.

Space complexity: O(max(n^1,n^2))

Where to go from here

Congrats on making it to the end! You just build 5 real-world features, using skills like DFS, BST, heaps, and more. As you can see, this is a powerful way to prepare for coding interviews that tends to be more effective. If you can understand a problem’s underlying pattern, you can solve just about any question.

There are still dozens of other practice problems like this out there, like:

Merge Tweets in Twitter Feed
AT&T Determine Location
Zoom: Display Lobby Meeting
Search Engine: Fetch Words

If you want practice with problems like these, check out Educative's one-of-a-kind course Decode the Coding Interview: Real-World Examples. Available in multiple languages, this course takes you through 100+ real-world questions like these. After each project, you'll better understand what techniques you just applied.

This is coding interview prep reimagined, with your needs in mind!

Happy learning!

Continue reading about coding interviews

“Why Amazon?” How to Answer Amazon’s Trickiest Interview Question

Amanda Fawcett — Tue, 23 Feb 2021 19:26:19 +0000

During the interview process, big tech companies like Amazon want to determine if you are a good fit for the company. This means that recruiters will test your technical prowess with coding challenges, and they will also assess you through behavioral interviews.

One of the most frequently asked behavioral interview questions is "Why do you want to work at Amazon?". While it might seem like a straightforward question, a lot of people struggle to answer it, even if they are very eager about a position at Amazon.

In this article, we will discuss how to answer this tricky Amazon interview question. We will discuss how to construct an impressive answer and walk through sample answers based on Amazon's leadership principles.

This guide at a glance:

Understanding the "Why Amazon" question
Amazon's Leadership Principles
Examples of good answers
Common mistakes to avoid
How to practice your answer

Understanding the "Why Amazon" question

Many software engineers want to work at Amazon for its competitive salaries and benefits. But when Amazon recruiters or hiring managers ask “Why Amazon?”, they are looking to see what else compels you to join their teams.

At this point in the hiring process, interviewers already know about your work experience. Instead, this is a chance for them to assess if you are a fit for their culture and if you will stick around for the long-haul.

In other words, the "Why Amazon" interview question is assessing your motivations.

That's why it is better to answer this question emotionally. With an emotional answer, you have the chance to discuss your goals and values and goals as they pertain to Amazon’s principles. According to the recruitment slogans and goals set forth by Jeff Bezos (now former CEO), Amazon is looking for people who have an investment in the company beyond just a paycheck.

So, what makes a good response to this question? While there is no one right answer, a good response should be as specific as possible to Amazon and your experiences. You could touch on these topics:

Amazon's Products: If there is a particular produce that interests you, this is the time to mention it. For instance, if you're interviewing for AWS, mention that it's your default cloud development platform.
People: If you know employees who worked at Amazon, you should mention it. You could discuss how their positive experiences inspired you to apply. This conveys that you have a solid understanding of what Amazon is all about.
Values/Mission: If you are a big fan of Amazon's mission or leadership principles (which we discuss below), mention that you align closely with them. You could give examples of times where these values shined in your past job experiences. This also shows that you've done your research. > Note: Your response should not be interchangeable with other companies. For example, if you are also interviewing at Microsoft, your "Why Microsoft" answer should be about Microsoft's values, missions, and products. This job interview question is not a one-size-fits-all situation, unlike many other behavioral questions.

Amazon's Leadership Principles

Before you construct your answer to the "Why Amazon" question, it's important to align your response with Amazon's 14 leadership principles. A good answer will fit with Amazon's values and mission. Obviously, you cannot mention every leadership principle in your response, but addressing two of three indirectly will help you stand out.

Important: The Amazon onsite interviews will include a Bar Raiser interview (this is also true of virtual interviews during the COVID pandemic). This is an objective, third-party interviewer who evaluates you on these Leadership Principles. They have complete veto power over whether or not you will be hired.

Here are the 14 values that you be evaluated on:

Customer Obsession: Leaders start with the customer and work backwards. They work vigorously to earn and keep customer trust. A customer-centric approach to solutions is always preferred.
Ownership: Leaders are owners. They think long term and don’t sacrifice long-term value for short-term results. They act on behalf of the entire company. An Amazonian will never say “that’s not my job."
Invent and Simplify: Leaders expect and require innovation and invention from their teams and always find ways to simplify. They are externally aware, look for new ideas from everywhere, and are not limited by “not invented here."
Are Right, A Lot: Leaders are right a lot. They have strong judgment and good instincts. They seek diverse perspectives and work to disconfirm their beliefs.
Learn and Be Curious: Leaders are never done learning and always seek to improve themselves.
Hire and Develop the Best: Leaders raise the performance bar with every hire and promotion. They recognize exceptional talent, and willingly move them throughout the organization.
Insist on the Highest Standards: Leaders have relentlessly high standards — many people may think these standards are unreasonably high. Leaders are continually raising the bar.
Think Big: Thinking small is a self-fulfilling prophecy. Leaders create and communicate a bold direction that inspires results.
Bias for Action: Speed matters in business. Many decisions and actions are reversible and do not need extensive study. We value calculated risk taking.
Frugality: Accomplish more with less. Constraints breed resourcefulness, self-sufficiency, and invention.
Earn Trust: Leaders listen attentively, speak candidly, and treat others respectfully. They are vocally self-critical, even when doing so is awkward or embarrassing.
Dive Deep: Leaders operate at all levels, stay connected to the details, audit frequently, and are skeptical when metrics differ. No task is beneath them.
Have Backbone; Disagree and Commit: Leaders are obligated to respectfully challenge decisions when they disagree with co-workers, even when doing so is uncomfortable or exhausting.
Deliver Results: Leaders focus on the key inputs for their business and deliver them with the right quality and in a timely fashion. Despite setbacks, they rise to the occasion and never settle.

Examples of good answers

As I mentioned, a good answer should be specific to Amazon. It should capture an emotional response that is rooted in Amazon's leadership principles, values, and products. Let's take a look at a few sample answers to the "Why Amazon" questions. I will outline why each are a good response.

Sample Answer #1: Machine Learning Engineer/Data Scientist

I want to work at Amazon for three main reasons. First, I admire that Amazon values customer obsession. I believe that putting the customer first leads to better product and software. I am eager to design products that meet real human needs, and I like that Amazon puts that first. For example, I value that AWS is accessible at an enterprise and personal level so that analytics are available to anyone.

Secondly, a lot of my career has been devoted to creative applications of machine learning, which you can see throughout my resume. I am interested in Amazon's use of machine learning and its unique position in the market. In my last role, I was always seeking new ways to implement ML technologies but felt that the culture didn't make space for that. That's why this team excites me. They are looking for new collaborative ideas.

Lastly, a former co-worker now serves as a Product Manager at Amazon. She has told me all about the ongoing learning opportunities she had there, and I am eager to be immersed in a workspace that values my learning and development.

This is a great answer to the "Why Amazon" question. It is specific to Amazon and its products. It also naturally integrates three leadership principles: Customer Obsession, Think Big, and Learn and Be Curious.

This response is also emotional and personal: the respondent uses emotion-based adjectives like "excites" and mentions several personal experiences with Amazon as a company.

Lastly, this answer makes the respondent seem experienced and capable without being arrogant. Their response doesn't focus too much on themselves, yet they naturally integrate that they have relevant experience.

Sample Answer #2: Software Engineer

I am interested in working at Amazon because I want to help this division of Alexa develop new business opportunities in the realm of voice recognition. This is a topic that excites me on a personal and professional level. In fact, I did my Master's research thesis on new uses of Big Data in voice recognition software. That's why I was drawn to this role specifically.

More broadly, I am attracted to Amazon's culture of diving deep and taking ownership. I see a lot of value in taking projects seriously and trying to find clever ways to improve results as a team. These are some of the values I implement in my work, and I'd like to join a team that is already reaching for those standards.

I think that Amazon is at a very unique and interesting place in the market, and the resources Amazon has makes it possible to explore ideas with a good chance of success. Voice recognition is huge right now, but Amazon offers tools and metrics that make it unique, as compared to other big names, which draws me to the company.

This is a good answer to the "Why Amazon" question. It is specific to the role and job description. It also aligns the respondent's experiences with the values that drive those goals.

The respondent also expresses broad ideas about Amazon as a company, showing that they are already meeting their leadership principles. The respondent also focuses on the team aspect of Amazon and explains that they want to collaborate.

Lastly, this answer demonstrates that the respondent is aware of the market. They're not just there to get the job done. They are already thinking about the big picture.

Common mistakes to avoid

Now that we've seen two good examples, let's discuss some common mistakes that candidates make with the "Why Amazon?" question. In general, poorly constructed answers are not specific and focus on past experiences rather than values and goals.

Prestige: Amazon does have some clout, and a lot of developers are drawn to its reputation. But liking a strong brand name doesn't prove anything about the value you bring. Amazon is looking for a motivation that goes deeper. In fact, an answer that's all about prestige may come across as immature.
Company size: You may be drawn to Amazon because you want to work for a big tech company rather than a startup, and that's great! But this answer doesn't align with you with Amazon any more than it does Google or Facebook. A hiring manager or interviewer wants to learn why Amazon is the right choice for you, not what size of company is right for you.
Finances: You may be drawn to Amazon because of their salaries or rising stock prices, and that's totally okay. But this isn't a long-lasting reason. This answer doesn't really say anything about you as a worker, and it isn't specific to Amazon. You could discuss rising stock prices, but this shouldn't be the main motivation.
"I hate my current job": "I want to work at Amazon because my current job is limiting me." It's okay if you're unhappy with your current role, but this isn't a good motivator. If you use this approach, you may come across as desperate, and you don't get to showcase why you're a fit for Amazon specifically.
Past experiences: "I have the experience you're looking for." Similar to above, this question doesn't dive deep enough, and it may come across as arrogant. At this stage, you are selling them your motivation, not your expertise, so this isn't the time to discuss this. You can naturally integrate your experiences as long if they are supported by deeper motivations or values (like Sample #1).

How to practice your answer

You should now have a good idea what makes a strong answer and what makes a poor answer. So, how do you prepare your own? It's simpler than you may think.

Start by researching Amazon as a company. Brainstorm some specific ideas.

What interests you about this company beyond the salary?
What leadership principles are you eager to apply?
What products do you like from Amazon?

Then look at the job description.

What interests you about this role?
How does this role align with your career goals?
What do you bring to the table?
What does this job offer you?

Start drafting a 2-3 paragraph response that captures your motivations. Try free-writing first, or just record yourself talking. Then, once you get the basics down, you can go add more specificity. Be sure to name a few leadership principles and a few of Amazon's products. Add personal touches and emotional verbs (such as "excite", "thrill", "eager", "motivate").

It is recommended to create a basic outline with keywords to make this easier to remember. That way, if you're doing a virtual interview, you can have a sticky note with the main points you want to address.

Let's reuse our sample answer #1 from above with this brainstorm process. This should give you an idea of how you get from the "Why Amazon" question to a solid, thoughtful response.

Brainstorm

What do I like about Amazon? customer-centric, ongoing learning for employees, creative ML applications
What tools do I like or use? AWS
What do I like about this role? they're looking for new ideas, they use customer-needs to create designs
What leadership principles do I embody? Customer-Obsession, Think Big, Be Curious
What personal connections do I have to Amazon? former co-worker

Bullet Point Outline

Reason 1: customer obsession
- Support: AWS services, real customer needs
Reason 2: ML experience
- Support: Amazon's unique place in the market, excitement about ML
Reason 3: ongoing learning opportunities
- Support: personal anecdote with former co-worker

Now that you have your outline it's time to practice, practice, practice until it feels natural. After all, when you're doing the actual interview, you won't be reading a script. Instead, you should memorize the main points, facts, and words you want to mention in your response.

Don't think you can wing this question on the spot. Behavioral interviews are very important and surprisingly challenging.

So, if you are looking for a place to construct answers and get tons of practice, check out Educative's course Grokking the Behavioral Interview.

You'll be able to use Educative's video recording widget to record yourself answering questions and assess your performance.
By the time you’ve completed the course, you'll be able to answer any behavioral question that comes your way with confidence.

Happy learning!

Continue reading about Amazon Interview

Quick Guide: Developer News and Tech Updates for 2021

Amanda Fawcett — Fri, 19 Feb 2021 19:10:40 +0000

2021 is already proving to be a fast-paced year. The tech industry has seen new and exciting developments in a variety of industries. To get you up to speed, we’ve summarized some of the top news and updates that you might have missed.

You’ll see what companies have had big announcements, what programming tools will be getting updates, and more.

This guide at a glance:

Bezos steps down as CEO of Amazon
Office 2021 will soon be available for MacOS and Windows
Microsoft's Excel programming language is now Turing Complete
The Rust core team announced the creation of Rust Foundation
Cats 2.4.1 hotfix release resolved critical issue in Cats 2.4.0
Java 8 update released with new features
Google announces increasing support for the Python Software Foundation
Visual Studio Code 1.53 released with new feature tools

Bezos steps down as CEO of Amazon

In early February, Amazon announced that founder Jeff Bezos will be stepping down as chief executive officer that he started nearly 30 years ago. Bezos has announced that he will remain involved with Amazon as an executive chairman. This change will officially occur in the second half of 2021 (Q3).

“As Exec Chair I will stay engaged in important Amazon initiatives but also have the time and energy I need to focus on the Day 1 Fund, the Bezos Earth Fund, Blue Origin, The Washington Post, and my other passions”.

Jeff Bezos

Bezos appears to be following Microsoft's lead by promoting the chief executive of Amazon Web Services, Andy Jassy to CEO of Amazon. Jassy joined the company back in 1997 and has led the AWS cloud team from its earliest days. With a cloud expert at the head of the company, many news outlets are predicting success. Others say that this transition will not necessarily bring significant changes to Amazon’s business.

In his announcement email to Amazon employees, Bezos stated that “Amazon couldn’t be better positioned for the future. We are firing on all cylinders, just as the world needs us to. We have things in the pipeline that will continue to astonish.”

Office 2021 will soon be available for MacOS and Windows

On February 18th, Microsoft announced that two new versions of Office will soon be available: a consumer Office 2021 version and Office LTSC for enterprise customers. Available for both Windows and macOS, Office 2021 is designed for users who don’t want to rely on cloud-powered Microsoft 365 tools.

Jared Spataro, head of Microsoft 365, states that they want to meet customers where they are at: “We certainly have a lot of customers that have moved to the cloud over the last 10 months. At the same time, we definitely have customers who have specific scenarios where they don’t feel like they can move to the cloud.”

Some potential features updates Office 2021 may include dark mode support, improvements to accessibility, and features like Dynamic Arrays and XLOOKUP in Excel. Both versions will include the OneNote app and ship both 32- and 64-bit versions. Microsoft has announced that it will not change pricing for the time being.

Microsoft's Excel programming language is now Turing Complete

On February 9, 2021, Microsoft announced that Excel formulas are now Turing Complete. A Turing Complete language is one that can perform any computation. This is exciting news for data scientists who use Excel.

Now, with the use of lambda, you can write reusable functions using the Excel formula language we all know so well. In Microsoft's announcement, they show how to use Excel to recursively reverse a string and fixed-point combinator. They even plan to add functionality for fully nestable arrays soon.

They also plan to define functions by a whole worksheet, which they are calling sheet-defined functions. These will allow users to define large functions using multiple formulas that are spread out over multiple Excel cells.

The Rust core team announced the creation of Rust Foundation

The Rust core team recently announced the formation of the Rust Foundation. The announcement by Ashley Williams, the Interim Executive Director, stated that the Rust Foundation is “a new independent non-profit organization to steward the Rust programming language and ecosystem, with a unique focus on supporting the set of maintainers that govern and develop the project”.

Rust has gained a lot of popularity in recent years, and was even voted the “most-loved” language in Stack Overflow’s developer survey five years in a row. This is an important step for Rust. The Rust Foundation aims to become an organization that hosts the language’s infrastructure and drives progress for the future.

Companies like Mozilla have heralded their support for the Rust Foundation, stating that they are proud to see Rust “outgrow its origins” and evolve to meet developer needs. Other members include AWS, Google, Huawei, and Microsoft.

Cats 2.4.1 hotfix release resolved critical issue in Cats 2.4.0

Cats is a Scala library that provides abstractions for functional programming and an ecosystem of pure, typeful libraries. A critical issue in the Cats 2.4.0 update led a quick update. The official Twitter account for Cats urged users to skip 2.4.0 and download the newest hotfix release, Cats 2.4.1.

Some of these fixes include:

Removed and replaced inconsistent Parallel derivation for EitherT
Deprecate Free.inject to emit new deprecation warnings
Added EmptyK instance for Map, which marks a non-implicit method as implicit

Java 8 update released with new features

Java Development Kit (JDK) is getting an update. In March 2021, Java Development Kit16 is set to release new features, including support for C++ 14, concurrent thread-stack processing for garbage collection, and “elastic metaspace” for returning unused class metadata to the OS.

You can find early-access builds of JDK 16 for most operating systems at jdk.java.net. JDK 16 is a short-term release, and JDK 17, which is targeted for September 2021, will be a long-term support (LTS) release.

Java 8 Update 281 was also released to address security concerns and bug fixes. Oracle strongly recommends that Java SE 8 users upgrade. Some other new features include:

groupname option added to keytool -genkeypair. Now, you can specify a named group when creating a key pair.
Apache Santuario library has been upgraded to version 2.1.4. This brings the new property com.sun.org.apache.xml.internal.security.parser.pool-size, which sets the pool size of the internal DocumentBuilder cache for processing XML Signatures.
Added support for certificate_authorities extension

Google announces increasing support for the Python Software Foundation (PSF)

On February 11th, Google announced that it will be increasing its support for the Python Software Foundation (PSF), making Google a Visionary Sponsor. Their aim is to aid and improve the Python language and ecosystem. Python is a key tool for Google Cloud and is a common runtime for many of their hosted services.

Google will be donating more than $350,000 to support PSF projects, such as malware detection for PyPl and a full-time CPython Developer-in-Residence, amongst other goals.
Google has supported Python for many years, stating that they are “big believers in Python”. They want to ensure that the Python ecosystem continues to have a viable, exploratory future.

Visual Studio Code 1.53 released with new feature tools

Visual Studio Code, a popular code editor, just released version 1.53 with new feature tools, such as:

JavaScript debugging support for conditional exception breakpoints and Node.js worker_threads
Notebook UX updates
Markdown preview image auto update
Support for searching in open editors (experimental)
Wrap tabs: wrap editor tabs in the workbench instead of using a scrollbar.
Configure tab decorations Emmet improvements for faster performance
And more

Now, you don’t need to edit keybindings to configure a default search UI. The new search.mode setting that allows you to configure UI search commands like “Search: Find in Files” or “Find in Folder". Some of the options include:

view: search using the search view in the sidebar
newEditor: search in a new Search Editor
existingEditor: reuse an existing search from Search Editor

Continue reading about technology

What is Lean Product Management and How to Apply it Today

Amanda Fawcett — Thu, 18 Feb 2021 17:40:40 +0000

Did you know that 72% of all new products do not meet their revenue goals? Most new products fail. And start up companies have the odds stacked against them. In fact, 75% of new businesses fail or cannot achieve a significant adoption in the market.

Many companies, large and small, make critical mistakes when it comes to building and managing products. That's why Lean Product Management was created.

Lean Product Management is a management methodology that follows the entire lifecycle of a product. This modern style will help you to be an effective product manager in the complex 21st century. In this article, we will introduce you to Lean Product Management and teach you how to apply these concepts today.

This article at a glance:

What is Lean Product Management?
Understanding a product's lifecycle
How to apply Lean Product Management today

What is Lean Product Management?

Lean Product Management is a modern leadership style that follows a product from idea to launch. This methodology is an evolution of many years of product development.

As we know, products don't really increase value for customers or businesses. 21% of products fail to meet customer's needs. Even at companies like Microsoft, Amazon and Netflix, the failure rate remains between 50% and 70%.

Clearly, we are using the wrong organization, structures, and processes.

Modern companies are changing the way they lead so that value can flow rapidly to the market. Lean Product Management is the solution in the modern, digital era. Lean Product Management is an evolution of management that focuses on best practices, lifecycles, customer satisfaction, and the tools of Lean Startup and Behavioral Economics.

A lean product manager must curate excellent customer experiences and scalable business growth by blending vision, strategy, and implementation.

Simplified: Lean Management is about getting products to the market faster by using a product that delivers more value to your customers. Lean Product Management ensures that a product is successful throughout its entire lifecycle.

What does Lean Product Management entail?

Lean Product Management is not just one thing but a collection of processes and techniques. The following principles and tools are used to ensure that a product is successful at every stage of its lifecycle.

Lean Startup

Lean Startup is a key part of this modern methodology. Lean Startup is a movement that emerged in Silicon Valley in the early 20th century. Most startups begin a product idea before ever speaking with prospective customers.

The Lean Startup method purports that to succeed in product development, you must change your perspective away from valuing the product to the actual business model.

This approach to managing helps get a desired product into the market faster and with less uncertainty. These methodologies are implemented for customer development, measuring success, and learning about a product at every stage.

Product Ideation

Another key part of Lean Product Management is ideation. This is a collection of processes that focus on how a product will be received by potential customers. It is concerned mostly with exploration and identifying solutions to customer problems.

In-depth exploration of the market and customers is crucial. You need to know what your customer's needs are before you can develop a product. This aspect of Lean Product Management, then, is all about one question: how will our product add value to a customer's life?

Market Analysis

Lean Product Management includes evaluating if a product fits in a current or future market. Managers survey potential customers to gain feedback, do continual research on trends, and wholly understand competitors.

This aspect of Lean Product Management focuses on critical thinking and thoughtful analysis. This is where Lean Product Management differs from traditional styles. Rather than simply pushing a product, a lean product manager knows when to stop, slow down, or change direction.

Product Strategy

Lean Product Management is all about strategy and encourages innovative, flexible strategies. Lean product managers are willing to carefully push for new approaches based on their research and analysis.

This aspect of Lean Product Management is also about scaling. A good manager understands the scale of a product's team and future outcomes. This requires a leader to implement the right techniques at the right time based on how well a product is performing.

Understanding a product's lifecycle

Any product follows a product lifecycle. Product lifecycle represents the time when a product is first conceived to when it's no longer relevant in the market. Lean Product Management focuses on every stage of this cycle. Every decision should depend the stage of a product in its lifecycle.

A lean product manager must always have two things in mind:

What stage of the product lifecycle is a product at?

How does this relate to their business model?

There are many models to explain the lifecycle of a product. We will be using Ash Maurya’s model, which breaks down a lifecycle into three phases:

Problem-solution fit
Product-market fit
Scale

1. Problem-solution fit

The goal of this phase is to identify your target customer and their specific needs or problems. There are two big questions to consider:

Is there a customer problem worth solving?
Do we create a solution for that problem?

In this phase, you will discover your target customers and what their unmet needs are before investing in developing a solution. This stage involves building an effective product through research, measuring quantitative data, and exploring new tools that yield better results.

2. Product-market fit

The goal of this phase is to identify which market is the right fit for your product. The right market fit also includes room to scale and grown. This is arguably the most important milestone in the life of a product.

In this phase, you will quantitatively verify that you are delivering monetizable value to a given market. There are three big questions to consider:

Is there a viable market for this product? (validating viability)
Is the market profitable? (traction)
Can it be built at scale? (feasibility)

These questions cannot be properly addressed without first understanding your product's purpose from the Product-solution fit.

3. Scale

The goal of this phase is to grow and scale a product to continue offering a viable solution to an evolving market. There is no one right way to do this. However, we have two recommendations for this phase:

Before considering scaling, you must prove a product-market fit with data.
- Recognize that your business model is never finished. Incremental innovation is essential for staying relevant in the market.

Many companies try to scale too quickly. Your growth goals must be realistic. For example, your team must be big enough for continuous technical improvement, and your business model must already be adaptive to infrastructural change.

How to apply Lean Product Management today

Now that we understand Lean Product Management, you may be wondering, but how do I actually apply this? As a Product Manager (PM), it's important to recognize that change begins with you, but it will be slow. Here are three things you can implement today:

Increase transparency: Having more visibility across your team will aid with understanding a project's lifecycle and identify blockers or delays. This discovery process can be aided with all kinds of software or cloud-based tools. Consider implementing processed-based changes, such as new tracking software.
Focus on prioritization: This will help you better understand what stage a product is at so you can better adapt. It can also offer insight into what the customer prioritizes. Perhaps time is being wasted developing tools that do not add to the overall product-solution fit. Are you trying to get the something out as soon as possible? Or are you focused on the highest value?
Pay attention to flow: You can use metrics to gauge how long it takes for an idea to be tested and adapt the flow of work from there. Flow should always point towards the right product in the right market. So, pay attention to where flow is not efficient for these goals. You may need to adjust requirements so that work flow points to better products and faster results.

Lean methodologies will help your team get value to the market faster. At a time where market competition is intense and fast, it is critical to use these modern management methodologies. Becoming a modern, efficient leader will require a shift in your perspective.

If you are ready to get a strong foundation in these concepts, check out Educative's course Lean Product Management. You will learn modern product management techniques that will help you bring products to the market quickly. You’ll start by understanding the mistakes that your team is making and understand how to solve them through practical examples.

By the end, you will have the foundations in place to bring products to the market that solve problems and are built for the long haul.

Happy learning!

DEV Community: Amanda Fawcett

JavaScript Map and Set Tutorial: how to use new built-in classes

What is map?

How to use map

Iterate through maps

Initialize a map with an iterable object

Get an element from a map by key

Get the number of elements in the map

Convert map keys or values to array

Other important Map methods

What is set?

How to use set

filter/map with sets

Get the size of a Set

Remove elements from a set

Invoke a callback function on each element

Other important Set methods

Hands-on exercise with map

Solution Breakdown

What to learn next

Continue reading about JavaScript

Ruby Tutorial for Python Programmers: how to make the switch

Ruby vs Python

Career

Machine Learning

Web Frameworks

Testing Environment

Community

Summary of Main Code Differences

Hello World with Ruby

Ruby Syntax Quick Guide

Variable Assignment

Identifiers and Keywords

Strings

Hashes

Array

Parenthesis

Commenting

Methods

Classes

Conditionals

What to learn next with Ruby

Continue reading about Ruby

Top 30 Apple Coding Interview Questions (with solutions)

Apple interview process overview

Arrays and graphs questions

Determine sum of three integers

Merge overlapping intervals

Clone a Directed Graph

Linked Lists questions

Add two integers

Merge two sorted linked lists

Trees questions

Determine if two binary trees are identical

Mirror binary tree nodes

Strings questions

Find all palindrome substrings

Reverse words in a sentence

Dynamic programming questions

Largest Sum Subarray

Math and stats

Power of a number

Find all sum combinations

Searching and design questions

Search in rotated array

Implement a LRU cache

Behavioral questions

Tips for preparing for interviews

Continue reading about coding interviews

How to become a Product Manager: top three PM career paths

What is a Product Manager?

Core competencies of a PM

Core Skills

Emotional Intelligence

Company fit

Career Path #1: MBA program

Career Path #2: Specialized PM training

Career Path #3: Learn on the job & work your way up

How to get started

Continue reading about Product Management

What is `map`?

What is `set`?

How to use `set`

`filter`/`map` with sets

Hands-on exercise with `map`

Tip 2: Avoid `while !(not)`

Tip 3: Use `loop do` over `while(true)`

Tip 4: Use Double Pipe Equals `||=` for your methods

Tip 6: Use `Hash[...]` to create a hash from a list of values