kdn251 / interviews

Everything you need to know to get the job.

Hello, World! 👋

Hey everyone, I'm Kevin, and I'm a software engineer at Google in New York City!

I make videos on YouTube about coding interviews and anything else related to programming and tech. I hope my content helps you land the job of your dreams and become a better engineer!

If you need help with interview prep check out the interviewing service I created to help teach people, The Daily Byte.

Free Software Engineer newsletter
Twitter Instagram LinkedIn

interviews's Issues

Interview

Interview

How did you guys visualize all those algorithms?

Which software did you use I mean? Or were they just copied from wikipedia and other places online? Thanks

Master is not compiling, Missing import statements(Java 8)

FindMissingInteger is not compiling with java 8. Many classes like TreeNode are missing. Am I missing anything? Also, can we follow the maven or Gradle project structure

Compilation Error in FindMissingInteger class

After Importing the required packages in FindMissingInteger class there are compilation issues for BigInteger.INTEGER_SIZE and BigInteger.fetch

Bug in google/3sumsmaller

I think the implementation forget to remove duplicates.

consider following test cases:
* Test cases:
* [-1,-1,0,1,2] , 1 -> [-1,-1,0],[-1,0,1],[-1,-1,2],[-1,-1,1]
* [-1,0,0,0,1,1,1], 1 -> [-1,0,0],[-1,0,1],[0,0,0]
* [0,0,0,0], 1 -> [0,0,0]

your output is
5, 13, 4 for these cases

LeetCode Python Solutions

Can we contribute with Python Solutions for Leetcode

SearchInRotatedSortedArray Invalid Solution

Doen's work for below Input:
[1,1,3,1]
3

Expected: 2
Actual: -1

Misleading example for the Greedy Algorithms section

In the Greedy Algorithms section, coin change problem is provided as an example. This creates an impression that every coin change problem can be solved with greedy approach. This is incorrect since using greedy approach in some coin sets gives the incorrect result and needs to be solved with dynamic programming.

More info: https://stackoverflow.com/questions/13557979/why-does-the-greedy-coin-change-algorithm-not-work-for-some-coin-sets

Open a catalog：interviews/company/Alibaba

It is known that Alibaba is a great international company.Maybe @kdn251 can open a catalog：interviews/company/Alibaba.
For example,a 2019 Alibaba interview question.
//Question: you need to caculate sqrt(2) to 10 decimal places accurately without math library.
double sqrt2( ) { double low = 1.4, high = 1.5; double mid = (low + high) / 2; while (high – low > 0.0000000001) { if (mid*mid < 2) { high = mid; } else { low = mid; } mid = (high + low) / 2; } return mid; }

Should be min of min and value at indes

interviews/leetcode/array/BestTimeToBuyAndSellStock.java

Line 30 in a70c225

min = prices[i];

should be
min = Math.min(min, prices[i])

Update Java code to follow Java 8 syntax

I wonder if it would be more beneficial for people to use Java 8 syntax for coding in interviews (many of them prefer it), and if so, if we should update our codebase to Java 8. I am up for making the changes.

Dijkstra's Time Complexity

Hi,

I recently finished an algorithm course, and here is my understanding about Dijkstra's algorithm.

For a directed graph G=(E,V), Dijkstra's involves heap initialization, |V| times EXTRACT-MIN operations (node expansion) and |E| times DECREASE-KEY operations (node generation).

While using a binary heap, the time complexity should be O(|E|log|V| + |V|log|V|) = O(|V|log|V|). While using a Fibonacci heap(O(1) for DECREASE-KEY), the time complexity should be O(|E| + |V|log|V|).

BST incorrect time complexity

Insertion, deletion, access and search time complexities of BST are incorrect, they must be O(h) where h = height of the BST, and not O(log(n)). In cases, where BST is a balanced BST, h will be log(n) and the time complexities will be O(log(n)), else h can be n (no of nodes) in worst case so the time complexities will be O(n).

run length encoding

Uber:

Classic run length encoding problem. Given an alphanumeric input - you are to apply run length encoding to encode the input argument.

Caveat:
The encoded value has to be <= input length.
Should pass test case for following inputs:
abcde
141414

Add Elements of Programming Interviews Book

Elements of Programming Interviews is also a highly recommended book.
http://elementsofprogramminginterviews.com/

It has an exhaustive list of solutions as well
http://elementsofprogramminginterviews.com/solutions/

Code missing

Relation class code missing

Alternate code for AllPermutations

"Good code for AllPermutations, but i thought that maybe you will like to see a different approach for the code. private void permute(String str, int l, int r)
{
if (l == r)
System.out.println(str);
else
{
for (int i = l; i <= r; i++)
{
str = swap(str,l,i);
permute(str, l+1, r);
str = swap(str,l,i);
}
}
}
public String swap(String a, int i, int j)
{
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i] ;
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}"

links to the ACM

The Association of Computing Machinery (ACM) has a ton of computer science news and journals and conference papers.

The Communications of the ACM is a great resource, along with ACM Queue. Could you link to those?

• http://cacm.acm.org/ - Communications of the ACM
• http://queue.acm.org/ - ACM queue
• http://technews.acm.org/ - tech news

They've also got a nice list of webinars happening: https://learning.acm.org/webinar/index.cfm

Big O Notation image

The example graph for the Big O Notation is wrong.
C*g(n) should be bigger than f(n) not the other way around.

Replace String Concatenation with StringBuilder

Writing DAX for comparing result of

Can someone send how to write dynamic code in DAX to retrieve first week of data for previous month to compare it to first week of data of current month.

For example . i want to find out total trips of a car in 1-Sep-2022 to 7 -Sep-2022 to total trips of a car in 1 -Oct 2022 to 7-Oct 2022

https://github.com/cmgraff/grafland

https://github.com/cmgraff/grafland

Translation

Can I fork and translate into korean version?

Specify the license

This is an awesome project. Could you please clarify the license?

Adding more problems for Adobe

Adding more problems from my Adobe interview experience

WordBreak

tips?

Can you provide general interview tips?
Example: https://github.com/yangshun/tech-interview-handbook/blob/master/preparing/cheatsheet.md

And

https://github.com/yangshun/tech-interview-handbook/blob/master/preparing/README.md

NPE bugs in MaximumProductOfWordLengths.java and RemoveDuplicatesFromSortedArray.java

Hi,

I have found two bugs in MaximumProductOfWordLengths.java (leetcode/bit-manipulation/MaximumProductOfWordLengths.java) and RemoveDuplicatesFromSortedArray.java(leetcode/two-pointers/RemoveDuplicatesFromSortedArray.java).

In MaximumProductOfWordLengths.java line 20 if(words.length == 0 || words == null) if words is null, words.length will NPE

Similarly in RemoveDuplicatesFromSortedArray.java line 12 if(nums.length == 0 || nums == null) if nums is null then nums.length will NPE.

I know they are minor issues. I would still be good if you can fix them. Thanks a lot!

Heap image is misleading

The heap.png image in the readme (https://raw.githubusercontent.com/kdn251/interviews/master/images/heap.png) shows a tree that does indeed respect the heap order property. The problem is when you mention the time complexities. In order to have O(log(n)) insert / remove time you also need for your heap to be a complete binary tree. The heap in the picture is not a complete binary tree. I think it should at least be mentioned in the description that the property is only valid for such trees, otherwise it is somewhat misleading.

Add C++ solutions for CTCI

Hey there, not sure if issues are the correct place to post it, but I can add c++ solutions for some of the CTCI problems; I can submit a PR if it's required:)

leetcode/hash-table/TwoSum.java

There is a better solution for the TwoSum problem than the hashmap solution. Sure hashmap is fine and meets the desired output. however it can be completely eliminated as such. The techinque employs a pointers to track the argument array i.e. one from the begining aka head and the other one from the end aka tail. A single sweep on the array and adjusting the two pointers does the job rather nicely.

       //input array must be sorted 
       int head =0;  int tail = arr.length -1;  int k = 11;  //target sum to find

        while(head < tail) {
           int sum = arr[head] + arr[tail];
           if(sum == k)  return true; //found it !!
           else if(sum < k) ++head;
           else --tail; 
        }

UC Berkley YouTube channel removed lecture videos

UC Berkley decided to remove all of their online lecture videos (link). Since the link for the UC Berkley Data Structures lecture is broken, should we consider removing it or possible replacing it? My suggestion would be to replace it with this. Which contains all of their removed videos on archive.org. Although I don't believe there is a specific playlist for CS lectures.

I can submit a PR if this seems like something worth adding.

BFS and DFS illustration images should be in respective sections

• We have BFS and DFS images in both Breadth First Traversal and Depth First Traversal. We should have illustrations in the respective sections.

null

Hi ValidParentheses.java

else if(s.charAt(i) == ')' && !stack.isEmpty() && stack.peek() == ')') {
} else if(s.charAt(i) == ']' && !stack.isEmpty() && stack.peek() == ']') {
} else if(s.charAt(i) == '}' && !stack.isEmpty() && stack.peek() == '}') {}
this code is bug
repair:
else if (s.charAt(i) == ')' && !stack.isEmpty() && stack.peek() == '(') {
} else if (s.charAt(i) == ']' && !stack.isEmpty() && stack.peek() == '[') {
} else if (s.charAt(i) == '}' && !stack.isEmpty() && stack.peek() == '{') {}

Complexity of Dijkstra's and Prim's

Hi there,

I am not sure if I am right, but in my understanding, Prim's algorithm is very similar to Dijkstra's.

They should be both some kind of O(|E| log |V|), while using heap in the implementation.

leetcode/array/LongestConsecutiveSequence.java

LongestConsecutiveSequence

Will it be better if Line 26 while loop be like ? :

while(set.contains(current + 1)) {
    currentMax++;
    current++;
}

in C++ if I use n instead of current the output would be 7 with sample input.

Deque interface should be used instead of Stack class in sorting a stack

Hi
Stack class is used in sorting a stack u should use Deque interface instead of it because Stack has no interface, so if you know you need Stack operations you end up committing to a specific concrete class, which isn't usually a good idea.So I had make a pull request to change it #192

Add implementation of BST Iterator using queue

Add implementation of BST Iterator using queue

Incorrect (?) time complexities for Heap operations

Access and Search

I was wondering why access and search are both O(lgn) time complexity? Taking the diagram on your README for example, finding a particular value (for example 2), will involve searching through every node in the Heap. Therefore I think access and search should be both O(n).

Remove Max / Min

As pointed out in #10, remove max / min should be O(lgn) and not O(1).

I can submit a PR to fix the above issues if you like 😄

interviews/company/facebook/GroupAnagrams.java

The given solution for this can be improved by not having to sort at all.
There are 2 calls to Arrays.sort().... This can become expensive if the program input array is large over 10K. A faster solution would just be to compute the hash of each value using a prime number assigned to each letter from a-z ( can be quckly generate in code). Then for each value in the array compute hash and store it inside a map. Then to get all the grouped anagrams you lookup the map or insert whatever the case maybe. I can provide code...too

remove (min/max) heap

The complexity of remove min/max in a heap is O(log(n)) instead of O(1)

Dynamic / Memoization

I think this is missing. I would do it, but I don't have much time this week until the weekend. Worst case if no one does it, I will help out for sure! Thank you for doing this!

bitmasks

Toggle kth bit: s ^= ~(1 << k)
should be
Toggle kth bit: s ^= (1 << k)

Adding a direct link to code in directory tree in readme.md

I have been past couple time and seen the directory tree of code implementation.
So it would be good to add a relative link to the direct code.

Add Computer Science Learning Notes

https://github.com/CyC2018/CS-Notes

Could I translate this document into Chinese and share with more Chinese developers?

We have an organization of translation technology articles, and We have translated a lot of documents like jwasham/coding-interview-university. Could we translate this document into Chinese and share with more Chinese developers? We will open a PR once it's done. ❤️

About our organization: xitu/gold-miner

Rename the CTCI chapters

It's better if the chapters CTCI folder are renamed so that they're sorted numerically.

binary search tree

Hi,

I would maybe add for binary search trees that the O(log(n)) complexities are correct for the average complexities. For example if the tree has a "shape of a line" (every node has a child on the left : 10->9->8->7->6->5->4->3->2->1 then the worst case complexities will be O(n) ( search, insert, delete, access). If the values are deliberately written for the average complexities, then sorry for the disturbance :)

Kind Regards, Mark