Skip to main content

Posts

Showing posts from 2017

New Format

People have raised the idea of splitting up the group during the session into smaller groups to simultaneously tackle problems. I think the more participation we can get the better. Please, please bring some paper and a pencil to work out problems for next week. I will bring a few example problems. Feel free to PM me on Meetup with problems if you have any that you think we should cover.

Why Heaps?

There seemed to be a bit of confusion in regards to the utility of heaps. Let us recap some of the main distinctions of a heap and where it is typically useful and where it is not. Heaps are foremost a data structure for performing incremental calculations that involve ranking. Implementations of heaps are found as priority queues are found in nearly all programming languages. One practical use of heaps is priority scheduling. Heaps generally speaking aren’t great for one shot computations. For example, using heaps for a one time total sorting isn’t as helpful because it’s worst case running time of O(N log N) is no better than merge sort. If one was looking to sort unrelated arrays of ints, one won’t be able to benefit from heaps. Where heaps shine is if we can maintain the heap property each iteration and not having to redo work for each iteration. Consider the following example, we want to write a function that returns the top 5 most visited websites where for each function call w…

Solving Coding Problems, Part 1: Getting Started

Don't get intimidated by coding problems. Despite how daunting they appear, there is rhyme and reason to them. With experience solving and presenting them, you'll get much more comfortable. First, get comfortable with the format of the whiteboard coding interview. I went over this part in a previous post on format of the coding interview. Second, get familiar with the different types of problems which frequently occur in interviews. Coding interview problems are, despite all the bluster, coming from a finite pool. Interviewers may occasionally put their own twist on things, but usually the problems are variations on tried and true problem types. So it is important for you to recognize the popular types of problems and learn the main techniques for solving them cold. Consider the following problem: write a function that takes an integer as input, reverses the bits in that integer, and returns resultant integer. First thing, observe what are the data types involved as input …

Binary Trees

Trees Binary trees are widely used data structures. Similar to linked lists, they are inductively defined: a binary tree node is comprised of a value and two child binary tree nodes, left and right. A binary tree can also be empty. The node that a child of no subtree is called the root. Binary trees are most useful in contexts where data has some kind of ordering since one can put the lesser nodes (with respect to a given node) on the left and the greater ones on the right. Binary trees tend to show up quite a bit in interviews because there are a lot of interesting problems you can ask about them. The key concept you need to learn is the many ones one can traverse a binary tree. Tree in programming are more like family trees (without accounting for marriages) in that they grow downward. A diagram that lists your great great grandparent and all descendants would be a good example. Consider the following binary tree: 1 / \ 2 3 / \ \ 4 5 6 The four mo…

Code Reviews, Part 1

Why Code Reviews? Code review is a practical and important skill that truly distinguishes the highly experienced engineer. Knowing what are the common pitfalls, where to look for them, and how to understand someone else's code quickly is an invaluable skill to have. It is also a skill that is rarely taught in school. To really ramp up your programming skills, get out there and read other people's code. Reading high quality code is a good learning experience. Occasionally reading poorly written code is also insightful. What are the most common errors and where do you find them? Through code reviews, software engineers can spread knowledge through their teams as well as improve consistency and code quality. For the interviewee, you have to review your own code, so it helps to know what are the things you need to double check. One great way to evaluate a team's culture is to probe and understand their code review practices or lack thereof. Below, I will cover some of the best…

Problem Solving Checklist

Clarifying QuestionsAsk clarifying questions to make sure you understand the scope of the problem so that you'll be solving the right problem. The interviewer may be testing you to see if you know how to gather requirements and communicate. Don't rush into coding and risk solving the wrong problem or missing the interviewer's point. This is your chance to shine, to show the interviewer that you can communicate well and get to the heart of problems. Identify Pattern Identify patterns: does this problem look like a search, dynamic programming, graph, or sorting problem? Don't have to tell your interviewer. This step is for yourself. Examples and Test Cases Come up with examples and test cases. This will make the problem concrete and provide test cases with which you will test your solution later on.Brainstorm Approaches Come up with 2-3 approaches and briefly run them by the interviewer but don't write up any code yet. If you need some time to come up with the optim…

Data Structures: Stack and Queues

In the last session, we went over some basic stack and queue concepts. Stacks and queues are abstract data types meaning that they declare an interface of functions to manipulate but not the underlying implementation. Stacks are Last in first out (lifo): the last inserted (pushed) element will be the first to be extracted (popped). A stack implementation should define two operations: stack.push(element_type x) and element_type stack.pop(). Think of a stack of dishes in a buffet. You can push new plates onto the stack but when you grab a plate from the stack, it will be the last plate that was pushed onto it. Some variants of stacks will have three functions: push(element_type x), void pop(), and element_type peek() where the role of pop() is split into a function that returns the value but does not remove that element from the stack and one that just removes the element from the stack. A queue is first-in-first-out (fifo) data structure with functions: queue.enqueue(element_type x) a…

Chicago Tech Jobs - August, Part 1

For August, there are a few new opportunities and some companies continuing to hire. This is part 1 of 2. Skip to part 2.
Workiva Boulder, Denver, Scottsdale, Chicago, Bozeman, Missoula, Ames, Amsterdam | Onsite | www.workiva.com/careers
About: Workiva is a growing SaaS company headquartered in Ames, IA with offices in 16 different locations. Workiva developed Wdesk, an all in one platform that simplifies complex collaboration while keeping data in sync, thus reducing risk. Thousands of organizations, including over 70% of the 500 largest U.S. corporations by total revenue, use Wdesk. Openings: * Software Engineer / Sr. Software Engineer (Ames, Bozeman, Boulder, Denver) * Site Reliability Engineer (Ames, Amsterdam, Chicago, Bozeman) * Software Development Engineer in Test (Bozeman) * Quality Assurance Analyst (Ames, Bozeman)
Technologies: Javascript/Golang/Dart/React/HTML5/Python/Clojure/Elm
Tech Blog: https://techblog.workiva.com/ GitHub: https://github.com/Workiva
AddStructure A…

Tail Recursion and Iteration

In the last session on linked list problems, we went over how to take a recursive function and transform the recursive call into a tail recursive one. The reason we do this is because tail recursive calls can be fairly straightforwardly optimized into a loop (and often automatically by a suitable compiler), thus removing any overhead from the recursive call. Regular recursive calls can get expensive in terms of space complexity if the recursion call stack gets deep, because the program needs to store information about the context for each recursive call. Recursion is a powerful tool of abstraction like any other. Functions on recursive data structures such as trees and linked lists lend themselves naturally to recursive solutions, and may be more readable and maintainable than their iterative counterparts. Thus, it is an important and even foundational concept to master. General Recursion The example we used was the reverse function which reverses a singly linked list. The straight…

Top 5 Books for Language-Specific Interview Questions

Shrunk and White of Programming When you put down that you know a certain programming language or languages on your resume, you are setting certain expectations for the interviewer. I would strongly caution against putting down "expert" in a language unless you invented or are one of the language's maintainers. You are giving your interviewer the license to quiz you on programming language lore. There are a handful of concepts that are considered "standard" knowledge for each language which go broadly beyond syntax and general semantics. These concepts commonly involve major pitfalls in a given language and the idiomatic technique for negotiating these pitfalls and writing efficient and maintainable code. Note, although the concepts are considered idiomatic, you can seldom infer them from knowledge of syntax and semantics alone. The tricky part here is that most courses that teach a particular programming language do not cover these idiomatic techniques and eve…

Complexity Analysis for Interviews, Part 1

This is part 1 of a two part series. Skip over to part 2 you'd like . For coding interviews, we are interested in gauging the asymptotic efficiency of algorithms both in terms of running time and space. The formal study of analysis of algorithms is called complexity theory, a rich field with fascinating and complicated math. For interviews, we only need a few basic concepts. Asymptotic efficiency is concerned with how the running time or memory requirements of an algorithm grows with the input size, so it is intimately concerned with how well algorithms scale to larger inputs. This is important in Computer Science and in practice because whereas some algorithms work well enough for small inputs of say < 10 inputs, the running time and space grows far faster than the input size and thus large inputs of say 10s to millions of inputs becomes impractical (usually meaning taking hours or even years of execution time). Consider sorting. Say for the sake of argument that sorting alg…

How to ace a tech coding interview (top 5 small things that help)

There is no shortcut. You have to know your stuff cold. However, keep it manageable. You have a finite amount of time to prepare so find out what are your weaknesses and double down on those until you know the material cold. I mean, to ace the interview, you really need to feel comfortable and be able to knock out problems with confidence. There are some important steps to take to improve your chances, but they all revolve around making yourself comfortable and knowing the material. Here are a few ideas for small steps that could make your next interviewing experience better: Get comfortable with the environment You can't control much about the environment of the interview. Who knows, maybe you run into a particularly pathological scenario where the AC just happened to break down and the interviewer is unwilling to open the window despite sweltering summer heat. There is little you can do about that except dress with contingency plans. More practically, you need to get comfortabl…

What Are The Types of Questions Asked In Tech Interviews?

Many interview prep books focus on the bread and butter coding interviewing questions, but in real interviews your interviewer may pose other types of questions. It is important to be comfortable and come prepared for these other types of questions which depart dramatically for coding questions yet still may bear considerable weight in your interview evaluation. Behavioral & experienceThese are the standard non-technical interview questions where the interviewer asks about what you did in particular scenarios and how you performed in the roles listed on your resume.Language specific knowledge questionsThere is a manageable set of questions for each common programming language. There are questions for uncommon languages too should to encounter a company that emphasizes their use of some of the lesser known languages. Usually these questions attempt to probe for your knowledge of some differentiator and key feature of the programming language. For example, virtual functions often …

How to interview your interviewer, Part 1

You past the gauntlet, having nailed every single question your interviewer threw at you, and now the interviewer asks if you have any questions for him or her. Still recovering from the ordeal, your mind draws a big blank. You blurt out something incoherent about benefits and their mission. Before you get yourself into this situation, just as with coding questions, it is helpful to be prepared to interview your interviewer. Though we never can be sure of the outcome of interview, organized interviewers will leave time for you to ask questions about the company, nature of the work, and their experience. It is important that you make the best of this opportunity to show your sincere interest and to learn more about the company and team to determine if it is a right fit and what to expect. Of course, given this is a team member or even the supervisor, you may have to take what they say with a grain of salt, but asking some well thought out questions can help tease out what the work and…

Tricky, tricky integer overflow

In today's session, I show the group a tricky, tricky integer overflow detail that is pervasive in binary search and mergesort implementations. How tricky is this whole thing? According to the Google Research blog, most of the first year CMU Ph.D. students' implementations of the rudimentary algorithms were flawed due to overflow problems. Moreover, various cybersecurity lists name integer overflow as one of the top software flaws. The Google blog also recommends Jon Bentley's classic Programming Pearls (Amazon affiliate link) book which motivates this and other Google-style large scale questions such as sorting billions of integers efficiently limited memory. You can probably snag that book in the local library, but we'll cover these and other popular interview questions. But back to the main point, integer overflow is a popular conceptual interview question in some quarters. The interviewer wants to see if you understand integer overflow and by extension an understa…

Complexity Analysis for Interviews, Part 2

This is the second part of a series. Go back to part 1 if you haven't read it already. In a fast paced interview, running time analysis is often about recognition of common running times of basic operations and combining them together, since you won't have time to derive the running time of each subcomponent of your algorithm. For example, say you had an algorithm that first sorted an array and then made a constant number of passes through the sorted array. You should point out to your interviewer that the sorting took O(nlogn) assuming mergesort or heapsort and the constant number of passes took O(n) which is dwarfed by O(nlogn) for large n. Therefore the whole algorithm is O(nlogn) . This is the kind of thing you have to learn to recognize. As we go over common algorithms and algorithms for specific real interview questions, I will point out the running times of the various parts. Remember that O(1) constant &lt O(log n) logarithmic &lt O(n) linear &lt O(…

Chicago Tech Jobs - More for July

Lightstream Lightstream | Lead Full-Stack Engineer | Chicago, IL | Onsite, Remote, Full-Time, https://www.golightstream.com/lead-full-stack-engineer/
Lightstream | Senior Backend Engineer | Chicago, IL | Onsite, Remote, Full-Time, https://www.golightstream.com/senior-backend-engineer/
Lightstream | Senior Frontend Engineer | Chicago, IL | Onsite, Remote, Full-Time, https://www.golightstream.com/senior-frontend-engineer/
-
Lightstream is a simple, powerful, and collaborative live video production suite in your browser. We are a small, but rapidly growing team of gaming, esports, and video industry veterans. Members of our team have contributed to the success of brands like SteelSeries, Machinima, Open Broadcasting Software, Major League Gaming, ESL, Beyond Gaming, and even old school brands like GotFrag & World Cyber Games. If you have a passion for gaming, video, and bleeding edge technologies, let us know! https://www.golightstream.com | jobs@golightstream.com Avant Avant (https:…

Chicago Tech Openings - July

Openings in the Neighborhood Outernet | Full Time | Onsite | Embedded Linux Developer I'm the founder of Outernet, a satellite broadcasting startup that provides a global data delivery service. We are building a universal information service to ensure that everyone in the world can have access to information, education, and entertainment—in even the most remote and disconnected environments. It’s the modern version of shortwave radio. More About Us: Startup Beams the Web’s Most Important Content from Space, FreeTHE PLAN TO BEAM THE WEB TO 3 BILLION UNCONNECTED HUMANS We are looking for an embedded Linux developer to join our small team of four. Responsibilities Include Creating board support packages/system images for ARM-boards with integrated radiosPackaging and developing applications for targeted embedded Linux platformsDealing with GPIOs, SPI, I2C, embedded displays, sound, etc Bonus points Ham radio license or SDR enthusiastA loose understanding of digital signal processin…