Sherxon Developer

LinkedList Implementation and Basic Operations

2019-04-25T08:56:38.730Z

This is the first blog on linked lists that contains implementations in Java and introduces basic operation such as add, get and delete. You can also read about problems and their solutions on linked lists on LinkedList Common Problems and Solutions post.Linked List is a sequence of data that are connected by links. Each list item is commonly referred as Node. Every node stores certain data and a link to the next element. On the other hand, Linked lists can also have two links (previous and next) to optimize some operations. They are called doubly linked lists.Here is a simple illastration of singly linked lists.

and doubly linked list

Here is simple implementation of singly linked list in Java

class LinkedList<E> {

    private Node head; // the first element
    private Node tail; // the last element
    int size;

    public void add(E element) {
        // tail and head are the same node when list has only one item
        if (head == null){
            head = tail = new Node(element);
        }else {
        //assign new node to next of tail and make tail the last element
            tail.next = new Node(element);
            tail = tail.next;
        }
        size++;
    }

    public E get(int index) {
        if (index >= size && index < 0) // check boundaries
            throw new NoSuchElementException();

        // find element at given index
        Node node = head;
        for (int i = 0; i < index; i++)
            node = node.next;

        return node.elem;
    }

    public boolean delete(E element) {
        Node temp = new Node(null, head); // dummy element to avoid if checks
        Node dummy = temp;
        while (temp.next != null) {
            if (temp.next.elem.equals(element)) {
                // if found node is last node of the list, need to change tail
                if (temp.next == tail) tail = temp;
                temp.next = temp.next.next;
                // if found node is first node if the list, need to change head
                head = dummy.next;
                size--;
                return true;
            }
            temp = temp.next;
        }

        return false;
    }

    // wrapper class for list elements
    private class Node {
        E elem;
        Node next;
        public Node(E elem) {
            this.elem = elem;
        }
        public Node(E el, Node node) {
            this.elem = el;
            this.next = node;
        }
    }
  }

You can add addFirst and getFirst, addLast and getLast methods by changing references of head and tail respectively. They are easy and constant operations.And here is implementaion of doubly linked list. Every node stores element data and two links: prev and next.

class DoublyLinkedList<E> {
    private Node head; // the first element
    private Node tail; // the last element
    int size;

    public void add(E element) {
        if (element == null) throw new AssertionError();

        // tail and head are the same node when list has only one item
        if (head == null) {
            head = tail = new Node(element);
        } else {
            //assign new node to next of tail and make tail the last element
            tail.next = new Node(element, tail, null);
            tail = tail.next;
        }
        size++;
    }
    public boolean isEmpty() {
         return size == 0;
    }
    public int getSize() {
         return size;
    }
    public E get(int index) {
        if (index >= size && index < 0) // check boundaries
            throw new NoSuchElementException();

        // find element at given index
        Node node = head;
        for (int i = 0; i < index; i++)
             node = node.next;

        return node.elem;
    }

    public boolean delete(E element) {

        Node temp = head;
        while (temp != null && !temp.elem.equals(element)) {
            temp = temp.next;
        }
        // no node with given element is found
        if (temp == null) return false;

        size--;

        // if found node is head of the list, need to change to next element
        if (temp == head) {
            head = head.next;
            return true;
        }
        // if found node is last node of the list, need to change tail
        if (temp == tail) {
            tail = temp.prev;
            return true;
        }
        // change links
        temp.prev.next = temp.next;
        temp.next.prev = temp.prev;

        return true;
    }

    // wrapper class for list elements
    private class Node {
        E elem;
        Node next;
        Node prev;

        public Node(E elem) {
             this.elem = elem;
        }
        public Node(E elem, Node prev, Node next) {
            this.elem = elem;
            this.next = next;
            this.prev = prev;
        }
    }
   }

This is the first blog about linked lists, you can read LinkedList Advanced Operations blog for recursion, reversing and some other operation imlementations.

LinkedList Common Problems and Solutions

2019-04-24T14:49:11.517Z

This is my second blog on LinkedLists. In this blog, some of the most common problems and their solutions are discussed. You can also read about types of linked lists and implementations in Java in my prvious post, LinkedList Implementation and Basic Operations. To make a best use of this post, please read the question first and do little brainstorm before moving on to the solution. You can also try to implement solution once you are familiar with solution idea.1) Given a singly linked list, determine if it has a cycle in it.

Solution:a) We iterate the list and add each element into the hashtable until current element is null or current element is already in the hashtable. This solution uses O(N) space to store list elements in hashtable. Time complexity is also O(N).b) We can use two pointers: slow and fast. slow pointer moves step by step while fast pointer moves two steps at a time. If the linked list has a cycle slow and fast pointers meet at some point. This solution uses O(1) space, which is better than previous solution.Here is implementation of solution in Java.

boolean hasCycle(ListNode head) {
    if(head==null || head.next==null)return false;
    ListNode slow=head;
    ListNode fast=head.next;
    while(slow!=null && fast!=null && fast.next!=null){
        if(slow==fast)return true;
        slow=slow.next;
        fast=fast.next.next;
    }
    return false;
}

2) Given two singly linked lists, find the node at which the intersection of these lists begins. Below given illustration of linked lists with intersection

A:          a1 → a2↘
                    c1 → c2 → c3
                    ↗
B:     b1 → b2 → b3

Solution:

a) The easy solution is adding all elements of the first linked list into Hashset and checking one by one if an element of the second linked list is contained in the hashset.

Time Complexity is O(n+m) and Space Complecity is O(n)b) We iterate both lists and get length of each list. Then move pointer k steps forward on the longer list where k is the difference between lengths of lists. Now we need to move two pointers in both lists starting from head element in shorter list and kth element in longer list. We can find out intersection point the lists when two pointers meet at some point.

Time Complexity is O(max(m,n)) and Space Complecity is O(1)c) We maintain two pointers x and y at the head of A and B lists respectively. Then we move pointers one node at a time. When x reaches the end of a list, then redirect it to the head of B, similarly when y reaches the end of a list, redirect it the head of A. If at any point x meets y, then x/y is the intersection node.

Time Complexity is O(m+n) and Space Complecity is O(1)Below code snippet shows the third solution.

 ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA==headB) return headA;
    ListNode x=headA;
    ListNode y=headB;
    while (x!=y){
        x= x==null ? headB : x.next;
        y= y==null ? headA : y.next;
    }
    return x;
}

3) Given a linked list, return the node where the cycle begins without modifying the list. If there is no cycle, return null.

Solution:

a) We iterate the list and add every node into Hashset, if element is already in the set we can return this element as cycle starting point.

Time Complexity is O(n) and Space Complecity is O(n)b) This solution is combination of the first and the second problem solutions. We first find any point in the cycle if there is. Then break the list by setting next pointer of node to null and find intersection point of two lists. The intersection point is the point where cycle begins.

Time Complexity is O(n+m) and Space Complecity is O(1)4) Reverse a singly linked list.

Solution:

a) We can reverse singly linked list in two ways, using recursion and iteration. The idea is to recur until tail node is encountered and set current node as next element of returned element in recursion.

class Solution {
    ListNode newHead;
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)return head;
        reverse(head);
        head.next = null;
        return newHead;
    }
    ListNode reverse(ListNode current){
        if(current == null || current.next == null) {
            newHead = current;
            return current;
        }
        ListNode prev = reverse(current.next);
        prev.next = current;
        return current;
    }
}

5) Sort a singly linked list in O(n log n) time using constant space complexity.

Solution:

We can use merge sort to sort linked list here. First we need to find mid element of the linked list using two pointers as mentioned above. Then, we should break the link by setting null to the next of mid element. In this case we can have have two lists; left linked list starts from head to mid and right linked list that starts from mid+1 to end of the linked list. We divide linked list until it has only one element in both left and right lists. Then starts merging of left and right lists into one sorted list. You can find solution below in Java

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode slow = head;
    ListNode fast = head.next;

    while (fast != null && fast.next != null) { // slow in middle element
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode start2 = slow.next;
    slow.next = null; // break the link

    ListNode start1 = sortList(head); // sort first half
    ListNode start11 = sortList(start2); // sort second half

    return merge(start1, start11); // merge sorted arrays
}

ListNode merge(ListNode a, ListNode b) {
        ListNode root = new ListNode(0); // helper node
        ListNode x = root;
        while (a != null || b != null) {
            if (a == null) {
                x.next = b;
                b = b.next;
            } else if (b == null) {
                x.next = a;
                a = a.next;
            } else if (a.val <= b.val) {
                x.next = a;
                a = a.next;
            } else {
                x.next = b;
                b = b.next;
            }
        x = x.next;
      }
    return root.next;
}

These are some other commonly asked questions in interviews.

Binary Tree Common Problems and Solutions

2019-04-24T09:27:48.371Z

In this post you can learn about binary tree common problems and their solutions in Java. You can also find interesting and elite problems solutions about Linked Lists in my previous post.

Short Introduction to Binary Trees.

Binary Trees are set of nodes in which one node is linked to two other nodes (left and right). Usually a reference or a pointer to topmost node is stored as a root, which can be used to traverse through all other nodes. In most cases Binary Trees are used as Binary Search Trees (BST) that have certain properties: the values in left sub tree is always smaller than or equal to its parent node's value and the values in right sub tree is always larger than its parent's value. Here is the illustration of BST.

1)Given Binary Tree, print node values in pre-order, in-order, post-order and level order.

Solution:

Unlike linear data structures such as ArrayList, LinkedList, Queue and Stack, Binary Trees can be traversad in several ways. Main traversal methods of Binary Trees are

Pre-order - traversing starts from root and goes to left subtree then to right subtree
In-order - traversing starts from left subtree and goes to root then to right subtree
Post-order - traversing starts from left subtree and goes to right subtree then to root
Level-order - traversing starts from root as level 1 and goes to every other level

Below are solution in Java for all 4 traversal methods.

public void postOrder(TreeNode root) {
    if(root == null)return;
    postOrder(root.left); // first left
    postOrder(root.right); // and right
    System.out.print(root.val + " "); // then process
}

public void preOrder(TreeNode root) {
    if(root == null)return;
    System.out.print(root.val + " "); // process first
    preOrder(root.left); // go to left
    preOrder(root.right); // then right
}

public void inOrder(TreeNode root) {
    if(root == null)return;
    inOrder(root.left); // first left
    System.out.print(root.val + " "); // process
    inOrder(root.right); // then go to right
}

public void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root); // add first level to queue
    int nodeCountInLevel = 1;
        while (!q.isEmpty()) {
            TreeNode x = q.remove();
            nodeCountInLevel--;
            if (x.left != null)
                q.add(x.left);
            if (x.right != null)
                q.add(x.right);

            // move to next level when all nodes are processed in current level
            if (nodeCountInLevel == 0 && !q.isEmpty()) {
                nodeCountInLevel += q.size();
                System.out.println(q);
            }
        }
}

2) Invert Binary Tree

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off. Here is motivation to learn how to invert Binary Tree.

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tempRight = root.right;
    root.right = invertTree(root.left);
    root.left = invertTree(tempRight);
    return root;
}

Solution:

The inverse of an empty tree is the empty tree. The inverse of a tree with root r and subtrees leftb and right is a tree with root r whose right subtree is the inverse of left and whose left subtree is the inverse of right.

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tempRight = root.right;
    root.right = invertTree(root.left);
    root.left = invertTree(tempRight);
    return root;
}

Time Complexity is O(n), becuase each node is vitised only once.

Space Complexity is O(n) because of recursion h (height) number of stack calls.

3) Given two binary trees, check if they are structurally identical and the nodes have the same value.

Solution:

To invert a Binary Tree, we do pre-order traverse both trees and check if values of the nodes in each tree is the same. Iterative and recursive approach can be used to solve this problem. Below I presented my recursive solution.

boolean isSameTree(TreeNode p, TreeNode q) {
        // base case
        if(p == null || q == null)return p ==q ;
        // recursion, check if values are equal
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Time Complexity is O(n), becuase each node is vitised only once.

Space Complexity is O(n) because of recursion h (height) number of stack calls.

4) Find Lowest Common Ancestor (LCA) of a Binary Search Tree

According to WikiPedia definition , The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root==null)return null;
    if(root.val < p.val && root.val < q.val)
        return lowestCommonAncestor(root.right, p, q);
    else if(root.val > p.val && root.val > q.val)
        return lowestCommonAncestor(root.left, p, q);
    else return root;
}

Solution:

We walk down the tree as long as both p and q are in the same sub tree, in which case their values are both smaller than root's value or greater than root's value. Return when one of the p and q, are larger than root's value and the other is smaller than root's value.

Time Complexity is O(n), becuase each node is vitised only once.

5) Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Solution:

We subtract the value of current node from sum until it reaches a leaf node and the subtraction equals 0, then we can make sure there is a path. Otherwise the subtraction at the end could not be 0.

public boolean hasPathSum(TreeNode root, int sum) {
    if(root == null)return false;
    sum-=root.val;
    if(sum == 0 && root.left == null && root.right == null) return true;
    return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}

Here are some other mostly encountered Binary Tree problems and Solutions

File IO operation comparisons in Java

2019-04-23T17:15:29.235Z

When I have free time, I attend contests in Online Judge websites just for fun. To get AC (passed all test cases and accepted) result in these contests, your solution has to be time and memory efficient. Most of the problems have several test cases to evaluate solutions. So, reading those test cases from file and outputting your results into another file to check may take much time as File Input and Output (IO) operations are toooo slow compared to other operations in most programming languages.I decided to benchmark all possible ways of reading and writing data into files in Java. Now I present you some results I found. Note that this post only shows results without any tuning disk file IO such as low level caching. Here are some approaches in Java with explanations you can use for writing into file and reading from it. These benchmarks are done using Intel® Core™ i3-3120M CPU @ 2.50GHz × 4 in 64-bit Ubuntu 14.04 with Java SE 1.8.0_20 on SSD. There are several factors(CPU, Hard disk and OS) that can make these benchmark results different. Hovewer, the relative difference is almost the same in all machines.

Link 1 Link 3 Link 5

Link 2 Link 4

What the Difference! You may be wondering why the famous and mostly used input stream approach is so slow. Main reason for this is that FileInputStream calls native read() method for each next 1 byte (raw octet, 8 bit) of the file content. When the file size is 1 MB, read() method is called 1048576 times that is 1024 x 1024. Now you can imagine how many times it is called for 1000MB. So, when working with Files, the first rule that you need to consider to speed up your application is the number of method calls() to underlying system and disk.Rule 1. Try to reduce number of method calls to underlying system and disk.To reduce those method calls in FileInputStream, we can read some amount of data (1 MB or 2 MB) from disk and store it in memory then use this stored data. In this case, we dont make access to disk for each next byte. As accessing to memory is much faster than accessing to disk, we can speed up our reading operation. BufferedInputStream use the same strategy to make File IO faster by storing data in buffer (8192 bytes). When read() method is callled in BufferedStreams, data is read from buffered array in memory and rarely accesses to undelying system.We can create our own buffer array with bigger size and speed up reading. The Direct BufferedInputStream appraoch shows benchmark of using 2MB byte array as buffer. As you can see, that is nearly 10 times faster than Java's default Bufferedstream usage when it comes to read data from 1000 MB file. You can buffer the whole file into byte array as long as you have enough space in memory.Rule 2. Use your own buffer with certain size according to your business logic.If you pay attention above, we only discussed about reading bytes from file. Hovewer, there are many cases that we want to read content of the file as characters. Unlike BufferedStreams, BufferedReader is all about reading characters. In the background, it reads bytes (like streams) from disk and translates into characters. You can see the BufferedReader works little slower than BufferedStreams because of translaton proccess.Next comes MemoryByteBuffer, which is Memory Mapped IO Class in Java. So, What is Memory Mapped file in Java? Memory mapped files are new feature in Java nio package, which allows to access contents of file directly from memory. This is achieved by mapping whole file or portion of file into memory and operating system takes care of loading page requested and writing into file while application only deals with memory which results in very fast IO operations. Memory used to load Memory mapped file is outside of Java heap Space. We use MappedByteBuffer in Java to read and write from memory.Memory Mapped files are so fast that they are used when performance is very important. However, there are some tradeoffs such as occurance of page faults if requested page is not in memory.If your application is dealing with small size of files, choosing MappedByteBuffer or BufferedStreams does not make much difference. Hovewer, reading data from large files using and changing certain pages of the file using multiple cores makes huge impact in performance. As Mapped Files loads the whole or some region of the file into shared memory, every process does not have to load the file into memory.

Microservice Architecture Pattern using Spring Boot and netflix technologies and helpful hints

2019-04-23T15:01:47.816Z

This project can be used as showcase or Proof of Concept to build and manage micro services using Spring Boot.

It includes:

Config Server => Spring Cloud Config

API GateWay => Zuul by Netflix

Service Registry => Eureka by Netflix

Sample Spring Boot Application

If you are not familiar with micro service architecture pattern, I recommend 3 min reading Microservice Architecture

first by Chris Richardson.

General Overview

All micro services are spring boot applications with dependencies managed by maven. Each Service has bootstrap.yml file which stores minimum required configuration for each service.

I have added all above mentioned micro services into one parent project just to make it easy to manage in one place

as it is just a POC project, without much business logic abd heavy requirements. You can still run each micro service independently.

This is Config First Bootstrap, so you should run Config Server first and Eureka Server second then Api Gateway and other micro services. You may see runtime exceptions thrown by Config Server when you run it until Eureka Server runs and Config server register itself.

Helpful Hints

Use .yml files instead of .properties, so you can write more than one profile configurations for each service with ---between them in one yml file and of course shorter code.
Keep all your source code always in certain package, not in source root to make it scanable by Spring DI

Config Server OverView

Config Server is used to store configurations of all micro services in one centralized place. You can keep and change

configuration of any micro service such as database credentials and network location in externalized place and restart the service to pull new configuration. To learn more about it check this out Externalized configuration

To implement externalized configuration pattern I used Spring Cloud Config Server and config clients. To make any spring boot application a config server you can just add one maven starter dependency and @EnableEurekaServer on configuration class. Spring cloud config server serves clients over rest api. Clients need to add spring-cloud-config-client dependency and config server or eureka server ( if you want config server to be discovered by eureka) location in bootstrap.yml

Once we run our config server at default 8888 port, we can get all configs using following rules in json format.

application is the name of service defined by spring.application.name (or spring.cloud.config.name) in config file.

profile is the name of profiles set by spring.profiles.active on the client side , separated by comma

label is the label name to pull remote config files. if remote config location is git, the label is master by default.

/{application}/{profile}[/{label}] such as http://localhost:8888/api-gateway/default

/{application}-{profile}.yml

/{label}/{application}-{profile}.yml

/{application}-{profile}.properties

/{label}/{application}-{profile}.properties

Attention

If you want to store remote config in filesystem, besides providing file path: spring.cloud.config.server.native.searchLocations=file:{path}, you should also use spring.profiles.active=nativeprofile.
You can just add spring.cloud.config.server.bootstrap=true to bootstrap.yml of config server to tell config server to get its configuration from remote file or repository on git.
Use @RefreshScope annotation in each client of config server, including config server itself, if you want changed configurations take an affect by sending post request /refresh endpoints. from remote location.
Config Server does not cache configurations, it reads from remote location (git or filesystem) for each request.

Service Registry Overview:

Service Registry is a service that keeps track of all other micro service instances, their location and health. All micro services register themselves with their information to Service Registry at startup and is deregistered if Service Registry cannot reach at certain point. Client Services such as Api Gateway ask Service Registry for location of available micro service instance. Eureka is used in this project as an implementation of Service Registry.

Attention

@EnableEurekaClient==@EnableDiscoveryClient makes spring boot app both instance (i.e. it registers itself and change eureka.instance.*) and a client (i.e. it can query the registry to locate other services and change eureka.client.* ).
if you want to enable eureka.client.healthcheck.enabled=true, use application.properties for this config, otherwise you can see UNKNOWN status on Eureka dashboard.

I dont have to write a lot about Eureka Server, you can read this awesome Spring Cloud Netflix Eureka - The Hidden Manualblog by Abhijit Sarkar and get thorough understanding about Eureka Server.

In this project, Eureka server loads its configuration from Config Server and at the same time Config Server is eureka client.

Api Gateway Overview

Api Gateway (Zuul) is the implementation of Backend for Front-End pattern. Main motive to use Api Gateway is to have one edge service for clients and still manage a number of service instances and their locations (host+port) which change dynamically. To learn more about this, check this out Pattern: API Gateway

Disclaimer

This project is Shareware and distributed under GSL(General Sharewire Licence), which means you can do whatever you want with it once you share it with at least one person :). Most of ideas and "hints" are just my opinions and solutions to problems I have faced up. Thanks to stackoverflow and netflix community.

If you think improvement or a change is needed in any part of the project, feel to contribute !

How to write clean code

2019-04-23T12:47:36.530Z

In this article, I am going to talk about a few key points on how to write clean code by avoiding some common mistakes. The term clean code is very broad and subjective, but there are conventions, standards and points to consider in coding that makes it more human readable.

Before starting talking about the key points to write clean code, I want to emphasize that It does not take one or two days to be good at clean coding. You need to practice until it becomes a second nature.

You are author and reader. While writing code, keep in mind that you are author and your target audience is not computer, it is you, your coworkers and millions of other developers in case it is open source. Writing every line of code with this idea in mind helps you use your knowledge to its fullest.

Let's start with very simple one-naming convention. Depending on your programming language choice, try to implement using only one (not mixed) naming convention across your team. Most popular ones are camelCase favoured by Java, C# community and snake_case which is popular among php and python programmers.

The next step on appropriate naming is that you should start paying attention to naming variables. The variable names should answer only one question with less word possible - what is the value of this variable to programmer. It should never answer why this variable is created or how this variable is used. Here are couple of bad examples you have have seen.

As you read, variable names with single letter, unpronounceable words or generic names such as data and total are all very confusing when dealing with this variable. These types of naming leads to assumptions when reading it and assumptions create bugs. Sometimes, these bad naming comes from thinking too much about appropriate names eventually it loses its meaning.

When it comes to naming methods/functions, there is one simple rule. We know that a function does one job. Similarly, the function name should only answer to one question- What does this function do?As you guess, it should have one verb and only tells about its purpose. If you create a function with nice name and the function does more than it suggests on its name, then you should reconsider renaming or moving extra logic into another function. The more atomic functions you have, the less arguments they will have as those functions do not need many arguments to do a single job. This makes code more beautiful and easy to reuse.

Next comes naming classes. You may think this is the easiest one because you usually have more options to name a class compared to variable. This is not always true. One of the biggest issues with class naming is long sentence-like names. Here are couple of examples

SimpleBeanFactoryAwareAspectInstanceFactory

HasThisTypePatternTriedToSneakInSomeGenericOrParameterizedTypePatternMatchingStuffAnywhereVisitor

To avoid such names, you may try locating classes in right packages with concise documentation. Class names dont have to say anything about how/when/where to use. The only question class name should concern is what this class is about.

Habitual class naming such as ending exceptions with Exception keyword is another big issue among programmers. In most cases it completely makes sense to remove exception suffix from classes and the meaning does not change. IllegalArgumentException, NullReferenceException or EntityNotFoundExceptionare nice examples that can be used without the exception suffix. So, you may think about that not all big company libraries are appropriately named all the time.

White space is nice space. Often I see people writing smashed-up code without leaving any white space or line anywhere. This makes really hard to read and my eyes get strained while reading such code. If you’re implementing more logic in one block, and then try to separate the code chunks into logical pieces with a white line break. Maybe have all of your code that use data fetching from database, then a line of whitespace, and then write another chunk where you do process them. Things like this might seem annoying at the time of writing, but are crucial when trying to quickly find something in a large section of unfamiliar code.

Commenting, it saves time for programmer and money for company. The easiest way of contributing to project success is by commenting existing code. Sometimes, it seems daunting to write couple lines of comments after implementing performant algorithm or solving huge problem. But the commenting this adds more value to the solution.

Here are some ways that can help you to make habit of writing clean code. You can always download nice coding style Google coding style guide and integrate it your powerful IDE. This makes sure that you have right naming convention and indentation to some extend.

Happy clean coding!

Google ga software engineer bo'lib ishga kirish haqida

2019-04-23T12:10:40.955Z

Google ga qanday qilib kelib qoldim :)

Intro

Bu blogimda doimgi mavzulardan tashqariga chiqib, qanday qilib, Google ga software engineer bo'lib, ishga kirganim haqida yozmoqchiman. Interview process haqida o'zbek tilida (bilmagan joylarimni ingliz tilada :) yozib, to'liq ma'lumot berishim, O'zbekistonlik va boshqa o'zbek tili so'zlovchilariga ozgina bo'lsa-da, motivatsiya bo'lishiga umid qilaman. Iloji boricha, detailed yozishga harakat qilaman va agar yana savollaringiz bo'lsa, bemalol yozib qoldirishingiz mumkin. Imkoni boricha, javob berishga harakat qilaman.

Background

Bundan 3-4 yil avval dasturchi do'stlarim bilan qat'iy qaror qildik: o'z sohamizning yuqori cho'qqisiga chiqamiz! Maqsadga erishishdagi rejalarimiz ichida eng yaxshi dasturchilar ishlaydigan kompaniyalardan biriga ishga kirish va u yerdagi tajribali insonlar bilan birga ishlab, yanada rivojlanish ham bor edi.

Shu niyatlar bilan 2016-yil Toshkentdagi Xalqaro Westminster Universitetida bakalavrni bitirib, shu yilning kuzida Amerikada magistratura o'qish uchun Iowa shtatidagi Maharishi Management Universitetiga o'qishga keldim. U yerda 1 yil universitet campusda full time o'qidim. Ikkinchi yilni online o'qish imkoniyati borligidan foydalanib, Chicagodagi bir kichikroq kompaniyada software engineer sifatida ish boshladim. Maharishi Universiteti ishga kirish uchun juda katta yordam berdi: kuchli o'qitiladigan fanlardan tashqari, Amerikada ishga kirish jarayonlarini tushuntirib, ish ruhsatnomasini ham qilib berdi.

Online o'qib yurgan paytlarimda ishlaganim uchun, o'qish pulini to'lash unchalik qiyin bo'lmadi. Ma'lumot uchun, masterga tuition fee 40,000$ atrofida ketdi.

Interview preparation

Masterning birinchi yilida campus da o'qib yurgan vaqtimda, asosan algorithm/data structure va system design ga oid mavzular o'rgandim/masalalar yechib practice qildim. Bunda Cracking the coding interview by McDowell, Algorithm design manual by Skiena va Algorithms By Sedgwick katta yordam berdi. Leetcode va hackerrank/timus dan similar problems yechib, kitoblardan o'rgangan theoriyalar ustida shug'ullandim. Interview da o'zimni qanday tutishni esa Pramp da mock intervyular qilib o'rgandim.

Interview process

Google da interview process boshqa katta tech company larnikidan farq qiladi va o'rtacha 3-6 oy vaqt oladi. Men o'zimda bo'lgan process haqida yozaman. Qaysi level/position ga apply qilinganiga qarab, ba'zida bundan sal farqli bo'lishi mumkin.

Birinchi step interview da, recruiter email yoki linkedin profilga message yozadi va open position borligi haqida ma'lumot berish uchun telda gaplashishga vaqtingiz borligini so'raydi. Online application topshirganlarga ham xuddi shunaqa steps bo'ladi. Kelishilgan vaqtda telda gaplashib, qiziqish bor-yo'qligini va qachon ish boshlay olishingiz mumkinligini so'raydi. Shundan keyin, candidate qiziqishiga qarab, ikkinchi stepga o'tiladi. Ya'ni online/phone screening technical interview. O'rtacha 45 min bo'ladi. Video yoki audio chat qilib, Google dagi biror software engineer bilan har xil coding problemalar yechiladi. Mening holatimda 45 minut faqat technical savollar bo'ldi. Behavioral savollar deyarli so'rashmaydi. 2-3 ta masala beriladi and/or common algorithms and data structure concept larni tushuntirib berishingiz so'ralishi mumkin.

Bundan successful o'tilgandan keyin, interviewer feedback iga qarab, yana boshqa screening interview bo'lishi mumkin yoki directly onsite interview ga chaqirilishi mumkin. Men bilan interview feedback yaxshi bo'lgani uchun, to'g'ri onsite ga kelishni taklif qilishdi. Meni vaqtimga qarab, airplane tickets va inteview joyiga yaqin mehmonxonadan xona band qilishdi. Bir kun oldin kelib, mountain view ga, ertasiga ertalab soat 10 da inteview uchun yetib bordim va har biri 45 daqiqalik 5 round technical interview bo'ldi.

Uchinchi round interviewdan keyin orada tushlik uchun 1 soat ajratishadi. Interview dagi aniq savollarni confidential bulgani uchun yozolmayman, lekin mavzular: algorithms, data structures, system design doirasida bo'ldi. O'rganishni maslahat berishim mumkin bo'lgan mavzular all common data structures and algorithms:stack, queue, heap, list, hashtables, trees and graphs; sorting and searching algos, graph and tree traversals and common related problems, little bit knowledge of dynamic programming and bit manipulation. Tepada eslatgan kitoblarimni o'qib, tushunilsa, bemalol yetarli bo'ladi va faqat qolgani practice bilan interview ga kelsa bo'ladi. System design uchun aniq bir kitob hozircha maslahat berolmayman. Chunki men o'zim, asosan, online da article lardan va bloglardan o'qib o'rganganman. Qiziqqanlar contact qilsa, system design uchun resource larimni yuboraman.

Onsite interview dan keyin, recruiter 1-2 haftada aniq javobni aytish uchun tel qiladi va benefits/compensation/relocation packages haqida deal qilinadi. Va undan keyin team matching boshlanadi: Google da resumeyingizni o'qib, sizni o'z komandasiga olishga qiziqqan team manager lar bog'lanib, ular bilan ishlashga fikringizni so'rashadi. Bu step da candidate o'zi uchun qiziq bo'lgan savollar so'raydi: komanda haqida, nima ish qilishi, project development process va career growth opportunities haqida.

Aniq sizga yoqadigan team va project/product topilgandan keyin, recruiter 1 haftalarda official job offer yuboradi va background check boshlanadi. Bu stepda resumeyingizda ko'rsatilgan experience va education lar haqiqiy ekanligini tasdiqlash uchun ularga bog'lanib, confirmation olishadi.

Impression working here so far

Birinchi 3 hafta training dan keyin komandada haqiqiy ish boshlandi. Trainingda Google dagi muhitni va ishlatiladigan tool lar bilan tanishtirishdi. Boshlaganimga endigina 2 oy bo'lgan bo'lsa ham, juda ko'p narsa o'rgandim. Eng muhimi, o'rganish va o'rganganlaringizni amalda qo'llash uchun barcha imkoniyatlar yetarli.

Google ishchilar haqida juda care qiladi: 3 mahal ovqat, entertainment, gym/pool resources, flexible work life balance, great benefits package, yaxshigina oylik ham beradi. To'g'risini aytsam, perks ko'pligidan hali hammasini try qilib ko'rmadim.)

Engineerlar juda professional va tajribali. Manager larning ko'pchiligi engineer likdan boshlashgan va o'zlarini hali ham engineer deb bilishadi. Solution topishga va product delivery qilishga nisbatan ham boshqa companylarga qaraganda ancha farqli usullardan foydalanishadi. Yana bir-ikki yildan keyin, Google haqida ko'proq yoza oladigan bo'lganimda boshqa postda batafsil yozaman.

That's is it for now.

O'zimda juda ko'p "qanday qilib" degan savollar bo'lardi. Savollar bo'lsa, istalgan vaqt facebookda contact qilinglar. Imkoni boricha javob beraman, Xudo xohlasa)

PS. No judging on typos.