

![](/images/blog/a-secret-israeli-operation-out-of-tigray-61ed97d3333bc05afd7fb7f9_netan-bcad75cd.jpg)
*Former Israeli PMÂ Benjamin Netanyahu who authorized the operation.*

Here's a story that slipped under the radar, not receiving  much
coverage in the western press.

A few months ago, four war criminals wanted by the Ethiopian government
escaped out of Tigray in a secret Israeli airlift operation.

  
Early last November reports emerged in the Israeli Press that Ethiopian
Prime Minister Abiy Ahmed [angrily phoned and complained to Israeli PM
Naftali Bennet about four war
criminals](https://www.google.com/url?q=https://www.timesofisrael.com/liveblog_entry/ethiopian-pm-said-to-complain-war-criminals-among-those-brought-to-israel/&sa=D&source=docs&ust=1642965154294583&usg=AOvVaw2x0kem722lurc-qushKUzM)
being among dozens of people the Israeli government evacuated out of
Tigray.  

  
Haaretz, which broke the news, described the evacuation as a ["daring
operation" which "endangered human lives and Israel's diplomatic
relations with
Ethiopia"](https://www.haaretz.com/israel-news/.premium.HIGHLIGHT-israel-secretly-brought-dozens-of-ethiopians-then-discovered-most-weren-t-jewish-1.10362179),
insinuating that Israel may have entered Tigray without the knowledge of
Ethiopian officials.  

  
Israel's Interior Minister, Ayelet Shaked, described the individuals as
["61
Tigres"](https://13tv.co.il/item/news/politics/politics/shaked-interview-1425810/)
in an interview following the news reports.

So, what are we to make of the PM's accusation that some war criminals
are among these "61 Tigres"?    

  
Hundreds of TPLF fighters and loyalists have been indicted on war crimes
charges including for the Mai Kadra massacre.

In Nov 2020, a TPLF youth off-shoot called Samri singled out Amhara
civilians and went on house-to-house raids massacring households with
axes and machetes.

  
The Ethiopian Attorney General's Office [identified 202 perpetrators of
Mai
Kadra](https://ethiopianembassy.org/a-summary-of-efforts-to-ensure-accountability-regarding-violations-of-international-humanitarian-law-and-other-legal-norms-in-the-regional-state-of-tigray-may-21-2021/)
last May and announced the arrest of 23 of them.

The office indicated the whereabouts of the rest remained unknown, with
most believed to have fled to Sudan.  

  
The PM's reaction suggests that the Ethiopian government was blindsided
by the operation.

What's strange about this operation is that it came at the request of
one man named Saraka Siom (Seyoum), described by Haaretz as "not a
well-known figure in Israel's Tigrayan community".

  
  
Israel's own Population Authority discovered in an investigation that
Seyoum brought his "ex-wife, two boys who claimed to be his sons" and
several others who "have worked in his businesses".  

The agency accuses the government of engaging in what it calls a
"conspiracy".

  
A senior Israeli official, on the other hand, said the Population
Authority's investigation was "conducted recklessly" and denies the
charges of conspiracy.  

The official insists Israel was acting on intelligence that  Ethiopian
Jews were in imminent danger in Tigray.

  
The Population Authority disputes this and asserts the individuals
“didn’t come from the conflict zone and their lives weren’t at risk at
all".

Yet Israeli gov officials insist "regardless of whether they can
truthfully claim Jewish ancestry ... the immigrants will remain here"

  
That this operation took place with the approval of the highest levels
of the Israeli government is remarkable.

Especially, when considered in the context of other contemporaneous
reports about [Israel's refusal to sell Ethiopia UAV
drones](https://www.debka.com/israeli-diplomatic-families-leave-as-rebels-advance-on-addis-iran-gives-ethiopia-exploding-drones/)
needed to halt the TPLF's advance.  

  
There's also a surprising claim in a story by DebkaFile, an Israeli
military intelligence site, that "Israel and the Tigrayans have engaged
in contacts in the past".

We're left wondering, is there an innocent explanation for why Israel
secretly evacuated 61 people from Tigray?

  
Over the past four decades, Israel has evacuated ~100K Ethiopian Jews
known as the Beta Israel and the Falash Mura.  

Today, the Beta Israel have all migrated out of Ethiopia while ~14K
Falash Mura remain in Addis, Gonder, and Tigray awaiting immigration to
Israel.

  
These members live in Jewish Agency compounds in Ethiopia which include
a synagogue, schools, and pre-immigration preparation.

2000 Falash Mura have left Ethiopia over the past year and just recently
an additional \$46 million was earmarked by Israel to bring 3000 more.



![](/images/blog/a-secret-israeli-operation-out-of-tigray-61ed97ba54d01c85cbfeb38f_jewis-33321d93.jpg)

*Entrance to Jewish Agency compound in Gonder.*

  
It's not clear why Israel didn't vet the Jewish identity of the 61
individuals while they were in Ethiopia rather than after they arrived
in Israel.

It also seems unlikely that Ethiopian officials vetted the group for any
indication of criminality.

An Israeli official asserts that PM Bennet "received the decision about
the immigration operation as done and dusted" from the outgoing PM
Netanyahu.

Regardless of who made the call, what's clear is that "61 Tigres" were
brought to Israel instead of Falash Mura Jews.  

Former Israeli PM Benjamin Netanyahu who authorized the
operation.

  

This story leaves us with more questions than answers and the identity
of the individuals remains a mystery.  

But, before looking into the outstanding questions, here's what we know
so far:

  
(1) Individuals on Ethiopia's most wanted list are part of a group
evacuated out of Tigray by the Israeli government.

$2$ Israel's own immigration agency accuses the Bennet admin of a
"conspiracy".

$3$ An individual named "Saraka Seyoum" engaged in massive immigration
fraud.  

How did Seyoum manage to get the ear of the Netanyahu admin?

Is he the informant who tipped them about the imminent danger of Jews in
Tigray?

What businesses does he have in Tigray?

Will Ethiopia verify his business dealings?

Will he be held accountable by Israel?

  
Does he exist or is he a front-man concealing a more nefarious reason?

For what it's worth, there are no public records for this individual.

A quick Google search returns just seven results all related to this
story of the evacuation.

  
Following the PM's phone call, The Times of Israel reported that Israel
has pledged to send back some individuals under the condition that it
would first have to verify that they're indeed war criminals.

It's possible the two sides may have resolved the issue behind the
scenes.

  
But it's hard to have confidence in Israel's attempts to verify these
charges after its failure to verify that "61 Tigres" are not Falash Mura
Jews.

So, we agree with the Population Authority's conclusion that "more
remains concealed than revealed" about this operation.

> On February 2 2022 an Israeli High Court has [halted the
> immigration](https://www.haaretz.com/israel-news/.premium-high-court-halts-immigration-of-3-000-ethiopians-with-close-relatives-in-israel-1.10587089)
> of 3000 Falasha Jews due to a lawsuit from an Israeli organization
> that has challenged the process of immigration to Israel saying most
> individuals are on "unsupervised lists" and their Jewishness is not
> vetted until they arrive to Israel.


A Secret Israeli Operation out of Tigray


The Abay river tumbles out of the Ethiopian highlands from its source in
[Lake Tana](https://en.wikipedia.org/wiki/Lake_Tana) and embarks on an
800km journey through a deep gorge as large as the Grand Canyon of the
Colorado River until it makes a sharp western turn and meets the White
Nile near Khartoum, Sudan.

Ethiopia is constructing a hydroelectirc dam on this river (called Abay
in Ethiopia) at the edge of its western border with Sudan. [The Grand
Ethiopian Renaissance
Dam](https://en.wikipedia.org/wiki/Grand_Ethiopian_Renaissance_Dam)
(GERD) broke ground in 2011 and is now nearing completion.  
  
This project has been fully financed by the Ethiopian public and has
cemented itself as a monument of national pride for the country.



![](/images/blog/ethiopia-egypt-and-the-abay-river-5f1c67f00ba49abc02c535ef_gerd--5b1d6969.jpg)

*Abay River Originating From Lake Tana*

  
  
Egypt, a downstream consumer of the Nile river has opposed the
construction of this dam from the beginning. Nonetheless, that didn't
stop Ethiopia from breaking ground on the project nearly a decade ago.  
  
The dam is now at the final stages of completion and these two countries
are at a crossroads again about the filling and operation of the dam.   
  
Egypt contends that the filling of this dam will reduce its current flow
of the Nile waters. Ethiopia argues that it has the right to fully
utilize waters of the Abay river which originates in its country in Lake
Tana.  
  
Furthermore, Ethiopia believes that it has already accommodated Egypt's
concerns by agreeing to fill this dam over a prolonged course of three
to seven years.   
  
The moral, historical, economic, and legal dimensions of this dispute
collectively make it one of the most interesting and important
geopolitical issues of the 21st century and a harbinger of other climate
and resource related conflicts to come.  
  
Arriving at a long-term solution to this dispute is crucial to the
development of both these countries and Africa's economic future.


Ethiopia, Egypt and The Abay River

A Conversation with Dr. Tirusew Asefa


On October 31st, 1978 TPLF militants abducted an American helicopter pilot and triggered an international hostage crisis. What follows is the untold story of how the TPLF introduced itself to the United States \[1\].

Northern Ethiopia faced a severe locust invasion in 1978. According to a June 1978 Washington Post article, "43 swarms \[of locusts\] have been spotted in Ethiopia" and locusts were devouring "8,000 to 34,000 tons \[of vegetation\] each day". The UN's Desert Locust Control Organization of Eastern Africa was at the forefront addressing the crisis and had a fleet of 9 aircraft shared between seven countries. One of these aircraft had been stranded near the Kola Tembien region for three months and required several repairs.

At the time, George William Krois, was a 36 year old American helicopter pilot and Canadian resident flying frequent locust control missions in Tigray. George worked for Viking Helicopter Ltd., a Canadian contractor performing services for the UN. On October 30th, Krois had flown two missions ferrying mechanics to repair a UN spray aircraft that had been grounded in Abiy Adi.

![](/images/blog/the-untold-story-of-a-tplf-hostage-crisis-6120628965485dad3c6e4bda_helic-e8078bb2.jpg)
*George William Krois with his Viking Helicopter.*

According to an account given by Canadian Pilot Bill Waugh, a co-worker of Krois' at Viking Helicopter, wages for locals guarding the aircraft had been delayed for several days. Soon, locals guarding the grounded aircraft had began to grumble. Word soon started to spread of a third flight that would deliver their payments. TPLF fighters in the countryside heard these rumors and quickly moved to the area.

On the arrival of the third mission, TPLF fighters charged the helicopter, held Krois under gunpoint and ordered him to reroute and fly to a TPLF-held location. The fighters stole all the cash and also kidnapped four Ethiopian mechanics who arrived with Krois and instructed them to walk 70 kms on foot in the same direction. Krois and the TPLF fighters landed at a remote site and curious local peasants flocked toward the helicopter. TPLF told the peasants that the helicopter "was a gift from the Arabs and that there would be more" to come and loaded it on a truck and drove away.

![](/images/blog/the-untold-story-of-a-tplf-hostage-crisis-612062ea5c8d9751c5d6135a_helic-2afb6875.jpg)
*Tigrayan Peasants flocking to George's Helicopter.*

## Tigrayan Elders Enraged at TPLF

In Abiy Adi, Tigrayans were enraged by the abduction, fearing the UN would suspend the highly effective Locust Control Program in their community. The head of the UN's Locust Control Program in Addis, a man by the name of Mulugetta Bizuneh heard the news of the abduction and immediately dispatched locals from Abiy Adi to search for the TPLF fighters in different directions, on foot, to try to contact the guerrillas and secure the release of his staff.

After a few days of searching, on the 5th of November, large crowds of residents and church leaders finally found the TPLF fighters in the countryside. The crowd, who had travelled a long distance, demanded the TPLF release George Krois and the four Ethiopians.

The TPLF rebuffed their demands and told the crowd that the captives were "agents of the Ethiopian government". The crowds forcefully protested and argued that the captives were civil servants helping their community battle locust swarms.

When the uproar from the crowd wouldn't relent, the TPLF agreed to hold a detailed deliberation under the condition that church leaders leave. The crowds strongly objected. Then TPLF leaders began a one hour lecture explaining their discomfort with crosses and church leaders.

![](/images/blog/the-untold-story-of-a-tplf-hostage-crisis-612064d53f212f12f8cbfe63_churc-3293b7e4.jpg)
*Ethiopian Orthodox Church Leader with a Cross.*

At last, the sides agreed to have a meeting in which church leaders were cast to one side and villagers to another. The TPLF, then proceeded to deliver another two hour lecture, this time about the goal of its movement as described in its manifesto. The crowd, then became very agitated.

The meeting adjourned without a discussion on the captives. The evening arrived and the frustrated crowd spent the night in the cold outdoors. The next morning the people were restless and hungry. And yet again the TPLF subjected them to another three hours of political lectures.

After testing the limit of the crowd's patience, on November 7th, the TPLF released the four Ethiopian detainees. George Krois, the American pilot, was nowhere to be found. The TPLF said he would be released "very soon" and sent the crowd and Ethiopian captives back to Abiy Adi.

## The Americans and Canadians Informed

By this time, UN Locust Control Head, Mulugeta informed the US Ambassador Fred Chapin of Krois' abduction. Ambassador Chapin dispatched a cable to US Secretary of State Cyrus Vance to officially notify the State Department of the abduction of an American citizen by the TPLF.

![](/images/blog/the-untold-story-of-a-tplf-hostage-crisis-6120739d770f02af6741c20c_cyrus-2fbf367b.png)
*Fred Chapin, left, (Ambassador to Ethiopia) and Cyrus Vance, right, Secretary of State 1977–80*

Secretary Vance then promptly made plans to notify Krois' father in California. Unfamiliar with the TPLF at this time, he sent a cable back to Ambassador Chapin inquiring: if they "could make a point that any publicity TPLF garners from the kidnapping would be bad? Or would TPLF care as long as they got publicity?"

Ambassador Chapin received the cable and looped in the Canadians which had a stake in Krois' release since Krois was a Canadian resident with a wife in Toronto.

Both determined to coordinate plans and "to hold the story as tightly as possible" to starve the TPLF of any publicity.

## American Call on a Friend

Lacking a direct point of contact with the TPLF, the American Ambassador in Sudan, Donald Bergus, appealed to the Sudanese Government of Jaafar Nimeiry. Nimeiry, a close US and Egyptian ally, was providing financial support and a headquarters in Khartoum to the TPLF \[3\].

![](/images/blog/the-untold-story-of-a-tplf-hostage-crisis-61207403770f024c6a41c26d_jafar-cc9e568b.png)
*Jaafar Nimeiry (left), Sudanese President 1971–85, Donald Bergus (right) US Ambassador to Sudan, 1977–80*

Ambassador Bergus phoned General Omar Al-Tayeb, head of the Sudanese State Security under Nimeiry, and pressed him to approach TPLF representatives in Khartoum to negotiate Krois' release. After meeting TPLF reps in Khartoum, General Omar reported: "TPLF want money or material assistance of some kind before release of Krois".

Omar told TPLF of US policy prohibiting ransom of any kind for release of hostages and that any donation would be made "under the table".

Ambassador Bergus then sent a cable to the State Department to update Secretary of State Vance about the TPLF's demands as relayed by General Omar. Bergus then waited for next steps from the State Department.

Meanwhile, the Canadians also hatched a plan of their own.

## The Canadians Call on a Friend

The Canadian strategy involved reaching out to the British, who dealt with TPLF hostage-takers two years earlier when they ambushed and fired bullets on a Land Rover carrying a British family, including a 5 and 8 year old, and took the family hostage for 3 months demanding \$1M in ransom \[2\].

![](/images/blog/the-untold-story-of-a-tplf-hostage-crisis-61206757c8b80c4075538adf_Scree-b2abed6e.png)
*Sep 7 1978 NY Times Article about abduction of British Family by TPLF.*

British officials reached out to their TPLF contacts and reported the following:

"An official of the British embassy who negotiated Tyler family release was telephoned by TPLF rep late this morning. He refused to meet TPLF at embassy but instead set up meeting this evening".

After meeting in secret with the TPLF rep, the British official notified the Canadians that the rep said unless a ransom was given "Krois would continue to be held to draw attention to the TPLF cause" and that "his group was immune to pressure applied by governments".

Back in Washington, Secretary Vance emphatically rejected the TPLF ransom demand, and updated his ambassadors in Addis and Khartoum affirming that "there is no question of USG paying ransom and TPLF will only damage its public image by continuing to hold innocents hostage".

He added, "we should use as many channels as possible to bring pressure to bear on TPLF, embassy should therefore again ask governments to make another strong effort to persuade TPLF to release Krois immediately and without condition".

TPLF reps would not budge. They warned a French contact "Krois is well but that he will be kept as long as necessary 'six months or a year' to bring western interlocutors to their senses".

The contact also noted that although a clear ransom demand had not been made yet, "figure being contemplated is thought to be approximately \$100,000 or \$200,000 in cash".

## TPLF Tries to Win Over Krois' Mother

Now early one morning, TPLF reps approached a Red Cross official in Khartoum by the name of Fred Isler and demanded that he deliver three letters \[4\] addressed to Mrs. Beverely Krois (George Krois' mother in Toronto) to the Canadian embassy to send to Mrs. Krois.

Isler accepted the first two letters which were letters from George to his mother describing his situation, but according to a mid-November cable, "Isler refused to accept a third letter which was a propagandistic explanation from TPLF to Mrs. Krois" justifying Krois' captivity.

Isler "told TPLF Krois was not a POW but a civilian who'd been kidnapped. He said @ICRC wouldn't be party to a case of kidnapping except to carry humane messages. TPLF then took back letter from Krois to his mother because they wanted it and their letter to reach her at same time."

In the letter Isler refused, TPLF wrote to Mrs. Krois "the inconvenience of one man for an indefinite period of time" is a worthwhile price to pay for "five million Tigreans".

They also complained, stating "for the last hundred years the Amhara nation dominated us".

Though TPLF ultimately pulled back the letters, the gesture presumably was an attempt to demonstrate a degree of good faith. In 1976, a British man kidnapped by the TPLF remarked that he "had to suck water from cactuses to keep going" on a 500 mile march under armed TPLF guards.

## Canadians Want UN Involved, Americans Unconvinced

By December, the one month mark of Krois' abduction had passed. US and Canadian officials were still no closer to securing Krois' release as when they had started.

The Canadians proposed that the UN Secretary General make a public appeal to the TPLF on humanitarian grounds.

![](/images/blog/the-untold-story-of-a-tplf-hostage-crisis-61207451415c590de7aa2ce7_waldh-6c9fec1a.png)
*Kurt Waldheim, UN Secretary General 1972–81*

Ambassador Chapin and the Americans were unconvinced arguing "an appeal on humanitarian grounds would, in any case, fall on deaf ears. The TPLF has clearly shown itself to be a politically unsophisticated group, not concerned with the adverse nature of the publicity it might get."

In Washington, Deputy Secretary of State Warren Christopher had now taken over the Krois' file. (Christopher would become Secretary of State under Bill Clinton). Christopher was displeased with the Sudanese effort so far and called for more "aggressive" pressure against the Sudanese.

![](/images/blog/the-untold-story-of-a-tplf-hostage-crisis-61206c2fe15fa7568ed939c8_warre-41ee67d2.jpg)
*Deputy Secretary of State Christopher (under Jimmy Carter). Secretary of State under Bill Clinton*

Soon enough, the Sudanese feeling the heat, reassured the US Ambassador in Khartoum that the matter was now personally being handled by Sudanese President Nimeiry and promised renewed pressure would be applied on the TPLF leadership in Khartoum.

Sudanese authorities would then summon TPLF reps in Khartoum. What exactly happened next is unclear. The details of the exchange remain classified. It's possible the Sudanese threatened the TPLF with expulsion or the Eritreans who had leverage on the TPLF made them fold.

It's also unclear whether any of the TPLF's ransom demands were met "under the table" by the Sudanese officials. The Sudanese promised the TPLF a press conference in Khartoum and requested US officials send media reps to the press conference. The US would grudgingly accept.

After more than 2 months of a dizzying diplomatic frenzy and 70 days under TPLF captivity, George Krois would finally be a free man on January 9 after the TPLF handed him to Sudanese authorities in Khartoum. A week later he boarded a flight to Toronto and reunited with his wife.

![](/images/blog/the-untold-story-of-a-tplf-hostage-crisis-61206c63bc5a478f0dcaa38a_Scree-6bcea9fc.png)
*Jan 10 NY Times Article on release of George Krois*

President Nimeiry received a letter of thanks from President Jimmy Carter for his efforts. Carter wrote: "I would like to express my gratitude for your government's efforts in bringing about the safe release of Mr. George William Krois by the Tigre Peoples Liberation Front".

## Aftermath

The Krois affair was one of more than a dozen documented hostage incidents involving the TPLF throughout the 1970s and 1980s. These incidents led to the TPLF's designation as a Tier III organization under United States law.

The TPLF also received its promised press conference with western media, where its representatives stated "they were anxious to call attention of world opinion to plight of Tigrean people who were fighting a fascist government."

Only a year after securing Krois' release, President Carter would find himself confronting another hostage crisis — this time in Iran — one he could not keep under wraps and which would ultimately contribute to his losing the 1980 election.

Despite their rocky beginning, the TPLF and the United States would forge a closer relationship in the late 1980s. Ethiopia expelled Ambassador Chapin and the Americans in July 1980, and the US wouldn't regain a foothold in the country until facilitating a TPLF-led transition of power in 1991.

---

## Notes

1. The US had been aware of efforts to create a "Tigray Liberation Front" at least since April 1975, which is two months after TPLF's official founding.
2. British Surgeon Lindsey Taylor was on vacation with his wife and his 8 and 5 year old children when TPLF fighters ambushed his vehicle and kidnapped the family. This story on the Sunday Times recounts this event and also an additional TPLF kidnapping.
3. Incidentally, just like today, in 1977–78 while Ethiopia was preoccupied with war with Somalia, Nimeiry's troops invaded fertile lands of Ethiopian farmers in Gonder and in later years, according to a statement by the Ethiopian Border Affairs Committee, TPLF leaders promised Nimeiry that they would abrogate the 1902 Border Treaty if they took power in Ethiopia.
4. Here's the full content of the TPLF letter sent to Mrs. Krois.

*© 2026 Eliezer Abate. All rights reserved.*


The Untold Story of a TPLF Hostage Crisis


![](/images/blog/binary-search-609c9e97e0ccb1d020cc91db_Scree-57f0d5dc.png)
*Loop condition to check first value larger than the target.*



![](/images/blog/binary-search-609c7695f9519a29155c65c3_Scree-fa15ca61.png)
*Binary Search (first infindPivotthen insearch)*

#### Introduction

Suppose a group of 100 people are in a line and they are standing from
shortest to tallest where the shortest person is on the left side and
the tallest person is on the right side. You want to join the line but
to do so you must honor the rules of the line and find a position where
the person to your left is shorter than you and the person to your right
is taller than you and insert yourself the middle. Of course if you are
the shortest you can simply go to the far left and if you are the
tallest to the right without having to do much work. But like most
people, if you are somewhere in between, you need to do some
searching.  

One approach to find where you belong is to begin from the shortest
person and one by one move to the right until the right conditions are
satisfied. Although this approach works it is not the most efficient. A
better approach would be to find the person at the middle of the line
and compare your height to that person. If you are taller than that
person you know that you can eliminate searching through all people to
the left. Similarly if you are shorter than the middle person you can
eliminate searching through the taller half of the line on the right
side.  
  
The binary search algorithm works exactly this way. Binary search is
used to find an element in a sorted array and to do so the algorithm
first finds the middle element and based on the result it eliminates one
half of the array which is irrelevant to it. It continues this process
until the element is found or it determines the element does not
exist.   

#### An Example

*Problem Description*

An integer array *nums* is sorted in ascending order and contains
**distinct** values. We rotate the array **k** positions to the right.
Your task is to determine if a value **target** belongs to the array and
return the index at which it's located. If target is not in the array,
we should return -1. For example if we had an initial array
\[1,2,3,4,5\] if we rotate it by k=2, it becomes \[4,5,1,2,3\] and
target = 1. In this case target is located at index 3.  
  
The key insight to to solving this problem is to find the pivot element
first in O(logN) time doing a binary search. The pivot element is the
single element which is greater than the element to its right. If the
array is not rotated at all the pivot element is the last element. Then
after finding the pivot element we need to determine whether the target
value falls to the left or to the right of the array and perform binary
search to find it.  
  
The code follows below:

Binary Search (first in findPivot then in
search)

Observe in the above example we had *L

Loop condition to check first value larger than the
target.

#### Practice Problems

**EASY**

○ [Kth Missing Positive
Number](https://leetcode.com/problems/kth-missing-positive-number/)

**MEDIUM**

○ [Capacity to Ship Packages in N
Days](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/)

○ [Koko Eating
Bananas](https://leetcode.com/problems/koko-eating-bananas/)

○ [Find the Smallest Divisor Given
Threshold](https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/)  
○ [Search in Rotated Sorted
Array](https://leetcode.com/problems/search-in-rotated-sorted-array)

○ [Minimum Number of Days to Make m
Bouquets](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/)

○ [Longest Increasing
Subsequence](https://leetcode.com/problems/longest-increasing-subsequence)

○ [Divide Two
Integers](https://leetcode.com/problems/divide-two-integers)

○ [Find K Closest
Elements](https://leetcode.com/problems/find-k-closest-elements)

○ [4Sum II](https://leetcode.com/problems/4sum-ii)

○ [Kth Smallest Element in
BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst)

**HARD**

○ [Median of Two Sorted
Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays)

○ [Maximum Profit in Job
Scheduling](https://leetcode.com/problems/maximum-profit-in-job-scheduling)

○ [Count of Smaller Number After
Self](https://leetcode.com/problems/count-of-smaller-numbers-after-self)

○ [Divide Chocolate](https://leetcode.com/problems/divide-chocolate/)

○ [Minimize Max Distance to Gas
Station](https://leetcode.com/problems/minimize-max-distance-to-gas-station/)

○ [Split Array Largest
Sum](https://leetcode.com/problems/split-array-largest-sum/)


Binary Search


![](/images/blog/bit-manipulation-60986f09088fb25e9d689cc9_Scree-96dc9156.png)

#### Introduction

Technical interviews at large tech companies such as Facebook, Google,
Netflix etc … will test your understanding of fundamental Computer
Science techniques.   

Bit manipulation questions come up frequently and are intended to test
one’s fluency with working with unary bit operators such as: ^ (xor), \|
(or), & (and), \\> (right shift), ~ (not).  
  
For example to check if the *3rd* bit of the integer 7 is set (7 is
represented as 0111 in binary), all we have to do is the
following: (0111) & (1 \ 3 neighbors dies
- A dead cell with 3 live neighbors becomes alive  

This question asks us to compute the next state of the matrix *without*
utilizing another matrix. 



![](/images/blog/bit-manipulation-60986e4b49833285ad021878_game--804d6480.jpg)

*Applying above rules to 4 x 3 matrix*

  
The key insight to solve this problem is to realize that each cell
utilizes exactly a single bit to store information even though each cell
is made up of 32-bit integers. Thus we can solve this problem by storing
the next state in the second least significant bit position and when we
are done processing every cell we can shift the value in the second bit
back to the least significant bit and return the answer in the original
matrix we were given. The solution follows below.

Observe that in line 19 *n* the number of neighbors and we perform a
bitwise OR (\|) with the value. If we have a live cell denoted by the
integer 1, 01 then the bitwise or of n=2, 10 or n=3 11 and 1 will always
be three and we set the second bit by adding 2. For a dead cell, 00, we
set the second bit only if the count is n=3, 11 which will result in a
value of three when we do 00 \| 11.  
  
Finally we move the second bit values to the first bit and place the
matrix in its final position.

#### Some Bit Tricks

Set ith bit: num \|= num & (1 \<\< i)

Clear ith bit: num &= ~(1 \<\< i)

Clear least significant set bit: num &= num-1

#### Practice Problems

**EASY**

○ [Hamming Distance](https://leetcode.com/problems/hamming-distance/)

○ [Single Number](https://leetcode.com/problems/single-number)

○ [Missing Number](https://leetcode.com/problems/missing-number/)

○ [Majority Element](https://leetcode.com/problems/majority-element)
(hint: try bit by bit construction)

○ [Reverse Bits](https://leetcode.com/problems/reverse-bits/)

**MEDIUM**

○ [Game of Life](https://leetcode.com/problems/game-of-life) (hint: see
example above)

○ [Maximum XOR of Two Numbers in an
Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array)
(hint: try bit by bit construction)

○ [Counting Bits](https://leetcode.com/problems/counting-bits)

○ [Single Number II](https://leetcode.com/problems/single-number-ii)

○ [Subsets](https://leetcode.com/problems/subsets)

○ [Repeated
DNA Sequences](https://leetcode.com/problems/repeated-dna-sequences/)

○ [Single Number III](https://leetcode.com/problems/single-number-iii/)

○ [Sum of Two
Integers](https://leetcode.com/problems/sum-of-two-integers/)

**HARD**

○ [Minimum One Bit Operations to Make Integers
Zero](https://leetcode.com/problems/minimum-one-bit-operations-to-make-integers-zero)

To learn more about Bit Manipulation refer to the following [excellent
post](https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently).


Bit Manipulation


#### Introduction

There are a class of problems in technical interviews that will ask you
to design a typically known game or data structure using object oriented
principles. You may be asked to design a data structure like a Hash Map
or an LRU cache or simulate a game like Tic Tac Toe or a system like a
Browser's history functionality.

#### An Example

Design Tic Tac Toe. You have to implement a class named *TicTacToe*
which will take an integer n representing an nxn grid and you need to
implement a method called *move* that will take a row, column and player
that will place an item. The player id is either 1 or 2 and the move
method will return the winner everytime it's called. If there is no
winner it returns 0 otherwise it will return either player 1 or 2.

The key insight to realize for this problem is that a tic tac toe game
can only be won if a player places an item entirely in a row, column or
one of the two diagonals. So we only need to keep track of the number of
placements by each player for each row, column, diagonal, and
*antidiagonal.* One clever way to do this is to keep for arrays of size
N and if player 1 places an item add 1 to the respective
row,column,diagonal, or antidiagonal or if player 2 places an item add
-1. If at anypoint any of these four arrays contains total value of size
N for a row,column, diagonal or antidiagonal, then the player that just
placed the item is the winner. The code follows below: 



![](/images/blog/design-x-609dadfaae19b93085715ce7_Scree-91c095c9.png)

*TitTacToe solution*

#### Practice Problems

**EASY**

○ [Design HashMap](https://leetcode.com/problems/design-hashmap)

**MEDIUM**

○ [Design an Underground
System](https://leetcode.com/problems/design-underground-system)

○ [Design Hit Counter](https://leetcode.com/problems/design-hit-counter)

○ [Design Tic-Tac-Toe](https://leetcode.com/problems/design-tic-tac-toe)

○ [Design Browser
History](https://leetcode.com/problems/design-browser-history)

○ [Design a
Leaderboard](https://leetcode.com/problems/design-a-leaderboard)****

**HARD**

○ [Design In-Memory File
System](https://leetcode.com/problems/design-in-memory-file-system)

○ [Design Excel Sum
Formula](https://leetcode.com/problems/design-excel-sum-formula)


Design X


![](/images/blog/dfs-bfs-60a68bbe6631805ee5c78743_Scree-536c8658.png)
*BFSÂ solution*

#### Introduction

Depth First Search and Breath First Search are extremely common graph
traversal algorithms. The main difference is that in BFS visits nodes of
the same level one at the same time, whereas DFS follows a node through
the rabbit hole until the node no longer has any neighbors to visit.
You'll typically perform DFS or BFS when the problem statement has a
2D matrix that requires non-obvious navigation, or a binary tree. There
are also other deceptive inputs that initially seem like they require
simple array processing or two-pointer processing but can only be
answered via DFS/BFS. The example that follows will illustrate this.

#### An Example

*Problem Statement*

Given a string s that contains parentheses and letters, remove the
minimum number of invalid parentheses to make the input string valid.

Return *all the possible results*. You may return the answer in **any
order**.

*BFS Algorithm*

The key to this problem is to realize that we will need to remove a
single open or close parentheses from *every possible position* and
check to see if the newly formed string is a valid parentheses. If we go
about removing 1 parentheses the first time from all possible positions,
then another (which makes a total of two), then another on the third
round, we can treat this like a BFS problem.

The code follows below:

BFS solution

The problem can also be solved via DFS. They key thing to remember is
that we need to remove the minimum amount of characters until we
encounter a valid parentheses. So we need to keep the track of the
running minimum value so that our other depth first traversals don't go
to deeper levels than the minimum we have encountered. The solution
follows below:



![](/images/blog/dfs-bfs-60a68d54375aadeea6662dfc_Scree-73cb7e1a.png)

*DFS Solution*

#### Practice Problems

**MEDIUM**

○ [Number of Islands](https://leetcode.com/problems/number-of-islands)

○ [Letter Combinations of a Phone
Number](https://leetcode.com/problems/course-schedule-ii)

○ [Course Schedule II](https://leetcode.com/problems/course-schedule-ii)

○ [Course Schedule](https://leetcode.com/problems/course-schedule)

○ [Pacific Atlantic Water
Flow](https://leetcode.com/problems/pacific-atlantic-water-flow)

○ [Minesweeper](https://leetcode.com/problems/minesweeper)

○ [Populating Next Right Pointers in Each Node
II](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii)

○ [Construct Binary Tree from Inorder and Postorder
Traversal](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal)

**HARD**

○ [Longest Increasing Path in a
Matrix](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/)

○ [Binary Tree Maximum Path
Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum)

○ [Remove Invalid
Parentheses](https://leetcode.com/problems/remove-invalid-parentheses/)

○ [Concatenated
Words](https://leetcode.com/problems/concatenated-words/)

○ [Recover Binary Search
Tree](https://leetcode.com/problems/recover-binary-search-tree/)


DFS & BFS


#### Introduction

There are a lot of interesting basic math questions that make for good
algorithm questions. Most of these questions don't require any
specialized knowledge except for elementary school level math, but they
will require careful thinking to answer correctly.

#### An Example

Count the number of primes less than a non-negative number n. The naive
way to solve this problem would be to check each number and test whether
it is divisible by any other number other than 1. But there is a better
algorithm called the sieve of Eratosthenes named after Eratosthenes of
Alexandria. The idea is to initially declare an array of booleans called
primes and set every value between 0 - n to true as 'probably prime'.
Then we set 1 and 0 to false. Then we consider all factors of the number
less than its square root. Then beginning with 2 (which is set to true
as a prime) we cross out all multiples of two as non-prime. We do this
with 3 and all numbers until we hit out end condition,



![](/images/blog/math-609ddb3d4b9317ff784d32cd_Scree-e498fa2c.png)

*Sieve of Eratosthenes*

#### Practice Problems

**EASY**

○ [Reverse Integer](https://leetcode.com/problems/reverse-integer/)

○ [Count Primes](https://leetcode.com/problems/count-primes)

**MEDIUM**

○ [Add Two Numbers](https://leetcode.com/problems/add-two-numbers)

○ [Divide Two
Integers](https://leetcode.com/problems/divide-two-integers)

○ [Fraction to Recurring
Decimal](https://leetcode.com/problems/fraction-to-recurring-decimal)

**HARD**

○ [Basic Calculator](https://leetcode.com/problems/basic-calculator)


Math


![](/images/blog/sliding-window-60a1acf057a0d42067b63c82_Scree-86b7b504.png)
*Longest Continuous Subarray with Absolute Diff Less Than or Equal to Limit*

#### Introduction

Sliding window problems require you to keep a fixed size window that
satisfies a certain criteria and shift or slide the window as soon as a
violation is encountered.

#### A Few Examples

*Problem*

Given an array of integers *A* and an integer *limit*, return the size
of the longest **non-empty** subarray such that the absolute difference
between any two elements of this subarray is less than or equal to
*limit.*

*Algorithm*

The key idea is to maintain an ordered
[multiset](http://www.cplusplus.com/reference/set/multiset/) of elements
and compare the max and the min values to see if they exceed limit. Each
time we encounter a violation we will decrease the window size by one
beginning from the left hand side. The gap of the largest possible
subarray we have seen will remain and at the end the array size - our
ending left pointer (i) will give us the answer.

Longest Continuous Subarray with Absolute Diff Less Than or
Equal to Limit

*Problem*

Given an array of integers nums and an integer k. A continuous subarray
is called **nice** if there are k odd numbers on it. Return *the number
of* ***nice*** *sub-arrays*.

*Algorithm*

There are several problems that will ask you to find the number of
continuous subarrays containing k properties (odd \#s in this example).
The key insight to remember here is that to arrive at *exactly* k items
which satisfy a certain property, we just have to count the total length
of continuous subarrays which satisfy *atmost* k elements and those that
satisfy at most k-1 elements and take the difference between two. Where
the at most k-1 and the at most k differ means we have exclusive
subarrays that only work for the *exactly k case.* Solution follows
below:



![](/images/blog/sliding-window-60a2ba52eaf39962458b7074_Scree-b81a0896.png)

*exactly(k) = atmost(k) - atmost(k-1)*

#### Practice Problems

**MEDIUM**

[Minimum size subarray
sum](https://leetcode.com/problems/minimum-size-subarray-sum/)

[Binary Subarrays with
Sum](https://leetcode.com/problems/binary-subarrays-with-sum/)

[Max Consecutive Ones
III](https://leetcode.com/problems/max-consecutive-ones-iii/)

[Count Number of Nice
Subarrays](https://leetcode.com/problems/count-number-of-nice-subarrays/)

[Number of Substrings Containing All Three
Characters](https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/)

[Replace the Substring for Balanced
String](https://leetcode.com/problems/replace-the-substring-for-balanced-string/)

[Fruit Into Baskets](https://leetcode.com/problems/fruit-into-baskets/)

**HARD**

[Shortest Subarray with Sum at least
K](https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/)

[Subarrays with K Different
Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/)

[Constrained Subsequence
Sum](https://leetcode.com/problems/constrained-subsequence-sum/)


Sliding Window


#### Introduction

In typical interviews you will rarely encounter problems that will
directly ask you to sort an array of integers. You might, however,
encounter a question that asks you to sort a linked list. Thus it’s
important to become familiar with the techniques used in common sorting
algorithms.  
  
Usually sorting creeps its head in when it is *an intermediate* step in
a multi-step process to solve a problem. At other times the problem
statement will make clear that you are dealing with a sorted array and
you should use that information to help you arrive at an optimal
solution. If the input array you are dealing with is already sorted then
that’s a big hint you should probably consider binary search before
considering a less optimal linear time solution.   
  

#### O(N) algorithms 

*Counting Sort*

Counting sort works by counting the frequency of each unique item and
then outputting the items in order. If an item occurs k times , we'll
place it k consecutive times. We will assume that we know the ordering
of the unique items. For example if we have items 0 - 6, we know 0 



![](/images/blog/sorting-609adee6386d8046fd5ab293_Scree-bad9e051.png)

*Insertion Sort.*

*

![](/images/blog/sorting-609af1195fa3314d173a4ee6_Scree-c18a02ed.png)

*Selection Sort**

Selection sort also uses the same principle as insertion sort and keeps
a partially sorted array to the left of the item currently being
processed. While in insertion sort we continually modify the partially
sorted array by inserting a new element somewhere in between its
smallest and largest value, in selection sort the partially sorted items
are in their final position.

We front load the work and each time try to find the smallest value to
the right and adding it as the next item in the partially sorted array
to our left. This contrasts with insertion sort where we never examine
the items to the right of the value we are processing.

Selection Sort

*

![](/images/blog/sorting-609af6573b6872bdb4c39fe6_Scree-f315d57e.png)

*Bubble Sort**

Bubble sort will keep a partially sorted array on the far right hand
side. Assuming we want to sort in ascending order we will continually
bubbling the largest items to the right by finding the largest item seen
so far and move it to the right, then the second largest item and so
forth. Once we have processed all elements our final array will be
sorted. For bubble sort the partial sort is on the right hand side and
thus its different from selection sort and insertion sort in this
manner. It is similar to the selection sort though in that the partially
sorted items in the right are in their final position.

Bubble Sort

  

#### O(NLogN) Algorithms

Merge Sort (Todo)

Quick Sort (Todo)

Heap Sort (Todo)

#### Other Notes

A sorting algorithm is **stable** if two elements in the input array
with identical keys appear in the same order when the sorted output is
processed. Heapsort and Quicksort algorithms are unstable, whereas merge
sort and insertion sort are. The key takeaway is stability only matters
when the input array contains duplicate values.

Check out the following tool to see a
[visualization](https://visualgo.net/en/sorting) your favorite sorting
algorithms.


Sorting


##### [ ](https://www.allthingsdistributed.com/)

##### Classic Papers

Paper
Topic
Authors
What is it?

[Amazon Dynamo](https://www.cs.cornell.edu/courses/cs5414/2017fa/papers/dynamo.pdf)
Distributed Storage
Amazon
A highly available distributed data store built for
Amazon's massive scale.

[Big Table](https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf)
Distributed Storage
Google
A distributed storage system for managing structured
data that is designed to scale to a very large size: petabytes of data
across thousands of commodity servers

[Google File System](https://pdos.csail.mit.edu/6.824/papers/gfs.pdf)
Distributed Storage
Google
A scalable distributed file system for large
distributed data-intensive applications

[Memcache at Facebook](https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final170_update.pdf)
Distributed Storage
Facebook
How Facebook leverages memcached as a building block
to construct and scale a distributed key-value store that supports the
world’s largest social network.

[Cassandra](https://www.cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf)
Distributed Storage
Facebook
A distributed storage system for managing very large
amounts of structured data spread out across many commodity servers,
while providing highly available service with no single point of
failure.

[Spanner](https://pdos.csail.mit.edu/6.824/papers/spanner.pdf)
Distributed Storage
Google
A scalable, multi-version, globallydistributed, and
synchronously-replicated database.

[Map Reduce](https://pdos.csail.mit.edu/6.824/papers/mapreduce.pdf)
Distributed Processing
Google
A programming model and an associated implementation
for processing and generating large data sets

[Spark](https://pdos.csail.mit.edu/6.824/papers/zaharia-spark.pdf)
Distributed Processing
UC Berkeley
A distributed memory abstraction that lets
programmers perform in-memory computations on large clusters in a
fault-tolerant manner

[Apache Kafka](https://cs.uwaterloo.ca/~ssalihog/courses/papers/netdb11-final12.pdf)
Distributed Messaging
LinkedIn
A distributed messaging system for collecting and
delivering high volumes of log data with low latency

[Raft](https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf)
Distributed Consensus
Stanford
A consensus algorithm for managing a replicated log.
[See MIT Lecture for more.](https://www.youtube.com/watch?v=64Zp3tzNbpE&amp;t=88s)

[TAO](https://www.usenix.org/system/files/conference/atc13/atc13-bronson.pdf)
Architecture
Facebook
A simple data model and API tailored for serving
Facebook's massive social graph, and TAO, its implementation.

[Zookeeper](https://pdos.csail.mit.edu/6.824/papers/zookeeper.pdf)
Architecture
Yahoo
A service for coordinating processes of distributed
applications.

[Google Search](http://infolab.stanford.edu/~backrub/google.html)
Architecture
Stanford
Sergey and Larry Page's The Anatomy of a
Hypertextual Web Search Engine Describing Google's Early
Architecture.

[Bitcoin](https://pdos.csail.mit.edu/6.824/papers/bitcoin.pdf)
Architecture
Satoshi Nakomoto
The White Paper that introduced Bitcoin to the
world.

[CAP Theorem](https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed/)
Reflections
Eric Brewer
Eric Brewer Reflecting on the CAP Theorem.

##### Good Systems Blogs

[All Things Distributed](https://www.allthingsdistributed.com/) by
Werner Vogels

[High Scalability](http://highscalability.com/) by Todd Hoff

[On Digital Money](http://www.ignaciomas.com/) by Ignacio Mas

[Irrational Exuberance](https://lethain.com/) by Will Larson

##### Aggregated Resources

[System Design
Primer](https://github.com/donnemartin/system-design-primer#index-of-system-design-topics)
by Donne Martin (comprehensive guide)

[Cracking the System Design
Interview](https://tianpan.co/notes/2016-02-13-crack-the-system-design-interview)
by Tian Pan (Good practical examples)

##### Videos

[Whats App](https://www.youtube.com/watch?v=LJx6mUEFAqQ) - A Reflection
on Building Whats App Server

##### To Understand a new Systems Design Ask:

- What is it? 
- Why was it invented? 
- How does it work?


Systems Design Resources


#### Introduction

A topological sort of a directed acyclic graph (DAG) is a linear
ordering of all the nodes of the graph such that *a comes before b* if
the edge *a-\>b* exists in the DAG. A DAG will always have one or
possibly more topologically sorted orderings.  

Figure1: Directed Acyclic Graph

Consider the DAG above. One possible topological sort for this DAG
is: A, B, C, D, E, F, G, H, I. Observe that for any pair of characters
(p1, p2) in ordering (A, B, C, D, E, F, G, H, I) p1 comes before p2.  
  
In a typical technical interview you will most likely encounter a
question that asks you to determine whether a topological ordering is
possible for a graph rather than generating the ordering itself.
Furthermore, the graph will not be given to you as a variable, you'll
need to infer that the problem is a topological sort problem by paying
close attention to the problem description.

#### An Example

> **There are a total of N courses you have to take, labeled from 0 to
> N - 1. You are given an array prerequisites where prereq\[i\] = \[ai,
> bi\] indicates that you **must** take course bi first if you want to
> take course ai. For example, the pair \[0, 1\], indicates that to take
> course 0 you have to first take course 1. Return true if you can
> finish all courses. Otherwise, return false.



![](/images/blog/topological-sort-6099a9af4c166e5d4e774de5_dag-84d1361b.png)
*Figure1:Â Directed Acyclic Graph*

The key to solving this problem is to understand that prerequisites
*cannot* be cyclic. For example if course A is a prereq to course B and
course B is a prereq to course C then course C cannot be a prereq to
course A otherwise we have a cycle and we would not be able to take any
of the courses.

This problem can be modeled as a directed acyclic graph where the
courses, 0, 1, 2, ..., N-1 are the nodes in the graph and an edge exists
from a -\> b iff a is a prerequisite of b.

For our case, the way our input is given \[ai, bi\] indicates that
course bi must be taken before course ai so we need to be careful and
make sure that we have bi -\> ai in the graph we construct.  
  
*Algorithm & Code*

- construct a directed graph using the prerequisites array (may be
  cyclic or acylic. we don't know yet)
- we determine all the *in* degrees for each node and store them in an
  array
- we loop through our array and store all our *0 degree* nodes in a
  queue
- while our queue is not empty we remove the front element and for all
  neighbors of the node we decrease their in degree
- the above action simulates the removal of the node and all its
  corresponding edges from the graph
- if there are neighbor nodes with an in degree of 0 we place them in
  the queue
- while we do this we keep track of how many nodes we have processed
- at the end of this operation if we haven't processed all nodes, then
  there must be a cycle in the graph



![](/images/blog/topological-sort-6099af444fc3ce6b12cfe256_Scree-839fb272.png)

*Topological Sort (Kahn's Algorithm)*

The above algorithm where we remove nodes and decrease in-degrees is
called Kahn's algorithm. There is also a way to determine whether a we
can topologically sort a directed graph using a depth first first
approach. The key idea is to have two arrays, one which determines if a
node has been visited, and another which determines whether a node is in
a current dfs path.

Then for each unvisited node we perform dfs. If on entry we find that
the node is on the current dfs path, that means we just encountered a
cycle and the graph is not a directly acyclic graph. If on the other
hand if the node *is not* on the current path, but has been visited
before then we can confidently return true to the question of whether
the graph is acyclic because a previous dfs search has already told us
the graph is acyclic. Then if we get past both these checks, we mark
both visted and on current path to true and perform dfs on the neighbors
of the node. If at any point we find a cyclic path we stop the loop and
return early. Otherwise we reset to onCurrentPath to false and return
true. The code follows below.



![](/images/blog/topological-sort-6099b4520d9873470d3ac717_Scree-147db435.png)

*Topological Sort using Depth First Search*

Note if we actually wanted to track the linear ordering, all we have to
do is add an additional parameter for a list that can track the nodes as
we enter the dfs. Then at the end of every successful acyclic path, we
push the node to the list. It's important to *make sure* though to
reverse the list at the end of the process because we will be visiting
the most "dependent" node at the very end. Also the *onCurrentPath*
check should precede the visited check in this scenario because only
when a node IS NOT on a current path but is visited can we be sure that
it's acyclic.

#### Practice Problems

**MEDIUM**

○ [Course Schedule](https://leetcode.com/problems/course-schedule/)

○ [Course Schedule II](https://leetcode.com/problems/course-schedule-ii)

**HARD**

○ [Alien Dictionary](https://leetcode.com/problems/alien-dictionary/)

○ [Longest Increasing Path in a
Matrix](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/)


Topological Sort


#### Introduction

Two pointer problems require you to use two (or more) pointers whose
values shift one at a time. These problems are similar to sliding window
problems but unlike sliding window problems which usually have a fixed
window size that moves from right to left or left to right, two pointer
problems don't usually keep a fixed window. Two pointers problems can be
some of the trickest problems to intuit so it's important to put in the
reps and do as many problems as possible.

#### A Couple Examples

*Problem*

Given two sorted integer arrays *nums1* and *nums2*, merge *nums2* into
*nums1* as one sorted array.

The number of elements initialized in *nums1* and *nums2* are m and n
respectively. You may assume that *nums1* has a size equal to m + n such
that it has enough space to hold additional elements from *nums2*.

*Algorithm*

The main trick required to solve this problem is to recognize that we
need to solve it from right to left so that we don't overwrite the
values in *nums1.* If we have one pointer at m-1 and another at n-1, and
a final pointer at m+n-1 and work from right to left comparing values
one at a time and placing the larger value at the right, then once both
the right and left pointer reach 0 we know we will have processed all
elements and the array will be in sorted order.



![](/images/blog/two-pointers-609ed69028c08210061c7511_Scree-5ed43bab.png)

*Example of three pointers.*

*Problem*

Given an integer array nums sorted in **non-decreasing** order, return
*an array of* ***the squares of each number*** *sorted in non-decreasing
order*.

*Algorithm*

This problem would require an *unchanged* array if the numbers are all
positive. The only hiccup comes from the fact that the smallest value in
the original array could have the largest square in the new array. For
example if we had \[-4,2,1\] the square of these values would be
\[1,4,16\]. So we use two pointers one on the far left and one on the
right hand and compare the squares of each one by one and place the
largest value on the far right in a new array.



![](/images/blog/two-pointers-609ef115b8c5224ee8b57b6b_Scree-cb722d50.png)

*Two pointers.*

#### Practice Problems

**EASY**

○ [Merge Sorted
Array](https://leetcode.com/problems/merge-sorted-array/)

○ [Squares of a Sorted
Array](https://leetcode.com/problems/squares-of-a-sorted-array/)

○ [Backspace String
Compare](https://leetcode.com/problems/backspace-string-compare/)

**MEDIUM**

○ [Longest Substring Without Repeating
Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters)

○ [Container With Most
Water](https://leetcode.com/problems/container-with-most-water)

○ [Partition Labels](https://leetcode.com/problems/partition-labels)

○ [Longest Repeating Character
Replacement](https://leetcode.com/problems/longest-repeating-character-replacement)

○ [Sort Colors](https://leetcode.com/problems/sort-colors)

○ [Three Sum Closest](https://leetcode.com/problems/3sum-closest/)

**HARD**

○ [Trapping Rain
Water](https://leetcode.com/problems/trapping-rain-water/)


Two Pointers


Array problems are many and can be some of the trickiest in the
business. There are many problems that seek the maximum or minimum value
of subarrays and subsequences and there could be many ways to solve a
problem. Problems with arrays can be solved with Dynamic Programming,
Two Pointers, Sliding Window or using a data structure such as a Hash
Map or a Heap. Below are some problems categorized by problem solving
strategy.

| Problem | Strategy | Description |
|----|----|----|
| [Maximum Size Subarray Sum Equals K](https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/) | HashMap | Find maximum length subarray whose sum equals to K. |
| [Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/) | HashMap | Find total number of subarrays whose sum equals to K. |
| [Contiguous Array](https://leetcode.com/problems/contiguous-array/) | HashMap | Find maximum length subarray with equal numbers of 1's and 0's. |
| [Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/) | Visualize | Find largest product of any subarray. |
| [Maximum Subarray](https://leetcode.com/problems/maximum-subarray/) | Visualize | Find largest sum of any subarray.  |
| [Maximum Product of Three Numbers](https://leetcode.com/problems/maximum-product-of-three-numbers/) | Visualize | Find maximum product of three numbers in array. |


Arrays


![](/images/blog/union-find-609c219e25d3736b060925f1_Scree-5ea35024.png)

#### Introduction

Imagine you’re back in elementary school and its recess and you and your
friends have chosen captains to form teams. No single player can belong
to more than one team and at some point after you have played some games
some players can switch teams. What if someone came while you guys are
on break and wanted to know to which team a player belonged to?  
  
The Union Find data structure was invented by Bernard Galler and Michael
Fischer to efficiently determine which non-overlapping group and item
belongs to (for ex. which team a player belongs to) and to quickly join
two items into a single group (i.e. the captain selects you into his
team). It has the following two operations:

  

- join(item A, item B) -\> joins two items together
- find(item) -\> group it belongs to

#### How It Works

Like many other data structures, the union find data structure is
modeled as a tree, but like the common heap implementation the tree
operations are performed on an array. The key to the union find data
structure is assigning a representative value as an id to each disjoint
(non-overlapping) group.   

We allocate an array to store the representative id of the *immediate*
parent of each of our N items. Initially each item belongs to its own
group the parent\[i\] = i. We will also allocate an array to store the
*rank* (which is the height of a tree beginning at the node itself) for
each item.

  
Then if we want to join two items into the same group, we first have to
check to see if they’re already in the same group. If they are not, then
we will assign the *root* of the item with the smaller rank to be a
direct child of the root of the item with the larger rank so as not to
increase the maximum rank between the two items. If the two items have
exactly the same rank, we can arbitrarily choose one item and assign it
as the parent of the other.  
  
For the find operation we will walk back parents until we land on the
root node. And as we walk back we can reduce the distance for our next
search by assigning to each descendent of the root node, the root node
as its parent, so next time we call find we can immediately find it.
This is called *path compression*. The implementation of the data
structure follows below: 

The key thing to observe is that in the recursive *find* function above
we'll continue to call find on the parent until the parent becomes
itself while setting the parent of any descendants of the root to the
root. The path compression allows us to achieve a worst case
O(LogN) time for the find and join operations (In fact they are slightly
faster than O(LogN). You can read more
[here](https://www.semanticscholar.org/paper/Efficiency-of-a-Good-But-Not-Linear-Set-Union-Tarjan/449230e4ebcf6ba071636e07cdca76ef85213a43)).
This is how we compress the path. It's usually the case that if a
problem can be solved using the Union Find data structure, then it can
alternatively be solved using BFS or DFS as well. It's good to practice
all three approaches.

#### Practice Problems

**MEDIUM**

○ [Number of Islands](https://leetcode.com/problems/number-of-islands/)

○ [Number of
Provinces](https://leetcode.com/problems/number-of-provinces/)

○ [Accounts Merge](https://leetcode.com/problems/accounts-merge/)

○ [Evaluate Division](https://leetcode.com/problems/evaluate-division/)

**HARD**

○ [Longest Consecutive
Sequence](https://leetcode.com/problems/longest-consecutive-sequence)


Union Find


[Skunkworks](https://www.amazon.com/Skunk-Works-Personal-Memoir-Lockheed/dp/0316743003)
is a riveting memoir by Ben Rich about his years working at Lockheed’s
top-secret Skunkworks program first as an engineer, then as the head of
the organization for close to twenty years. In this first-person
account, we get to peek into the brilliant mind of a manager and a group
of enterprising engineers, chemists, physicists and all-around doers
that made the impossible possible and produced some of America’s most
iconic military aircraft from the U2 spy plane to the record-setting


![](/images/blog/book-review-skunkworks-604bffef3fdf20d110204df1_sr-71-49d98330.jpg)

*SR-71 Blackbird* which blazed at three times the speed of sound.  

In the first half of the book Rich chronicles the story of Kelly
Johnson, the formidable and charismatic chief engineer who founded the
program. Johnson is a larger-than-life figure that reminds one of the
legendary UCLA basketball coach John Wooden who left an impression on
his players that extended far beyond the basketball court. Similarly,
the lessons and fear that Johnson instilled in his employees is palpable
throughout Rich’s words and the accounts of other employees, pilots,
generals, and Secretaries of State who are profiled in the book.



Indeed one of the highlights of the books is we get to hear from some of
the most towering figures of the Cold War from former National Security
Advisor Zbigniew Brzezinski to Secretary of State William Perry about
how crucial a role the Skunkworks team played in ensuring America’s
military advantage during the era.  
  
We also get to peek inside the Pentagon’s bureaucracy and its Byzantine
rules and regulations which made life somewhat frustrating for both Rich
and Johnson. Despite their stellar record, the team ran into the same
issues that most of us run into in the corporate world today from
inflated egos, unexpected change of direction from the top, and
backbiting characters.  
  
The pace at which most of the planes got built is truly astonishing.
Most of the planes that were took less than 24 months from conception to
prototype. The focus, grit, ingenuity, and high degree of excellence
that was expected of SkunkWorks employees can be credited for this rapid
and prolific output which didn’t sacrifice quality.  
  
My biggest takeaway from this book is that we should be fearless about
tackling challenges that may seem uncomfortable or unknown at first.
Most of the projects that the Skunkworks team undertook were zero-to-one
projects that had never been done before. The team had mastered the
fundamentals in each of their endeavors and was able to improvise to
create products that revolutionized the game.


Book Review: SkunkWorks


> "I've always said that I wanted to be remembered as a player that
> didn't waste a moment ... didn't waste a day." - Kobe Bryant

The skies over Southern California were unusually overcast on the
morning of Sunday January 26 2020. I had arrived in the area around
midnight after an eighteen hour drive from Washington state. That
morning, I decided to accompany my family to church. My good friend
Yafet was preaching and I attended his service along with my brother. In
the middle of the service, my brother who was sitting next to me, had
the blankest stare that I had ever seen on his face. He looked at me,
and said, “Kobe died”. 

Kobe who? Not Kobe Bryant! It couldn’t be. How? What happened? What do
you mean he died? I couldn’t believe it. I opened up my phone and my
heart dropped as soon as the internet confirmed what I hoped was cruel
joke. The shock and unsettling that followed wouldn’t subside for days
and still stings to this day on the one year anniversary of his passing.
On this day, I want to offer a note of gratitude to Kobe Bean Bryant. 

Kobe you were an artist and a marvelous basketball player. You gave
everything to the game you loved and showed all of us what giving your
absolute best looks like. You came to the NBA as an 18 year old boy and
left as a legend. Despite your God-given talents, you weren’t satisfied
for one second. You wanted to be the best. While your peers spent their
summers relaxing, you were up at 3am honing your craft. Day after day.

You were clutch like no other player I’ve seen. With the game on the
line the entire league knew there was no one better to have the ball;
double teams, triple teams, didn’t matter! You wanted the ball and you
delivered *every time*. Your ability to focus under pressure and execute
were superhuman. 

Your obsession with perfection and becoming the best version of yourself
raised the level of everyone around you. Regardless of our profession,
you reminded us to focus on the fundamentals, put in the the time, go
deep, and to become craftsmen rather than going through the motions.
[*Mamba
mentality*](https://www.amazon.com/Mamba-Mentality-How-Play/dp/0374201234)
wasn’t confined to the world of basketball. You were an inspiration to
an entire generation of athletes and admirers of art and excellence. 

You deconstructed what greatness looks like in a way mere mortals can
understand. We know your greatness came at a great cost in time. Yet you
managed to be an exceptional and loving father to your daughters. 

You were not a perfect man. You made mistakes as a young man but you
didn’t make excuses. You owned up to it. Your contrition on the public
stage at the tender age of 24 was courageous and honorable to both man
and God. Most of us will never know what it feels like to be publicly
shamed and reviled by millions of people as you were at that time. Yet
you channeled all your energy to drop forty, fifty points a game and
thrill many millions more than those that cursed you.

You showed us what staying grounded looks like regardless of how wealthy
you got. You left nothing on the table and inspired all of us to give
our very best until we put our sneakers, pens, cameras, or scalpels up.
Dropping 60 points in your very last game! Really?

You have a special place in our hearts & will be forever missed. Your
spirit carries on. Your example and dedication inspires hundreds of
millions of people around the world. Congratulations on a life
well-lived. We were lucky to be alive when you played basketball.

  
*Rest In Peace*


Thank you Kobe


This essay is a retrospective about my journey founding a food discovery
startup called idk over the course of the past of 2019. I have written
the tldr of the major lessons I took away right below, and if you’re
interested in the longer form narrative, keep reading, hopefully you’ll
find other useful nuggets.

  

TLDR: 

  

- Have one founder, (hopefully the CEO), whose sole responsibility is to
  raise money so that your startup can get off the ground. 
- Start thinking about potential investment partners as early as you
  think about a startup and prepare for the long haul (6months -
  12months) of fundraising. 
- As a first-time founder with no-exit, realize that 9/10 investors will
  look at you skeptically and so make sure either your product blows
  them away, you have revenue numbers to show off, or engagement numbers
  to show off. 
- If you decide to self-fund, make sure you have at least 12 months of
  living expenses covered -- among your founding team -- so that you put
  yourself in a position to make solid headway with your product. 

  

Over the course of 2019, I worked on a startup called idk. I began
working on this project when I got together with my co-founder, who was
a childhood friend of mine. We both had grand ambitions about succeeding
in technology and becoming very rich. Other than this grand ambition, we
did not have a clear-cut idea of what to build, how to raise money, and
how to monetize the product we were building.  
  
It seems obvious, in hindsight, that these should have been topics that
we should have spent considerable time breaking down, but because of our
preternatural bias towards action, we felt that if we continued to
build, talk to users, and just keep making progress day by day, that
these issues would resolve themselves. Or more likely, we felt that we
would have a better mental model and framework with which we can come up
with solutions to the questions above.  
  
I went to Stanford and studied Computer Science as an undergrad.
Everyone in Silicon Valley and beyond knows that countless tech
entrepreneurs came out of this storied institution and founded iconic
companies from Google to Snap to endless others. Still, as an undergrad,
I was focused on obtaining the technical skills necessary to build these
companies. I had mistakenly believed that all it took to build great
technology companies was technical prowess. Basically the idea that I
can build a great software product with the CS skills that I was
learning, and commercialize that product and make a lot of money.  
  
Part of the reason that I had this mistaken belief was because I knew
that having great technical chops was *necessary* to build a great
software startup and that those who did not have these technical skills
had no chance succeeding in founding a technology startup. Most of the
widely heralded founders and CEOs that I observed in the tech press I
was consuming -- from Zuck, to Sergey and Larry, to Jeff Bezos and Elon
-- were all highly technical people with a software background at some
point in their lives. So I had this conviction that there would be
absolutely no way to make it in technology as a startup founder unless
one had experience building software at some point in their lives.  
  
Furthermore, from reading dozens of
[essays](http://www.paulgraham.com/articles.html) from Paul Graham, I
picked up the idea that traditional business-minded, MBA types, were
held in disdain by the tech community. So I was committed to not having
a business co-founder when I pursued my tech startup at some point. My
plan was to pursue an enterprise or B2B unglamorous startup that was
very product and software heavy. 

  

However, when I got together with my co-founder in March of 2019, he had
a very consumer-centric mobile app idea and it became clear to me that
he hadn’t even explored the realm of non-consumer ideas. He was even
more of a novice than I was. He had never seen how products are actually
built in a startup or software setting and so he came with a layman’s
understanding of what was possible. His background was in door-to-door
sales selling copiers to local businesses on foot.  
  
I hadn’t obviously built my own startup before, but I had built software
projects with teams composed of product managers, designers, data
analysts, and many top-notch engineers at some of the top companies in
Silicon Valley and I had a good sense of what was technically required
to get our product off the ground into a usable stage.  
  
We were first-time founders and convinced that we needed to get the
product live out to users before we had any shot at raising money from
angel investors and early stage venture capitalists. So we built and
built and built some more for about five months and we launched our
first product to public users in September of 2019. During our launch
day, we had about four-hundred people download and use our app, mostly
people that my co-founder knew from social media.  
  
We had a toast to celebrate our first launch, and immediately several
things started becoming very clear about our business. First, we
realized that we were geographically limited. Our food discovery app
only served people in a particular geographical location at a time. It
was not a photo-sharing app that can be used by anybody anywhere in the
world. So even though we were getting downloads from across the United
States, we knew that the usability of our app was limited only to folks
living in the southern California area. 

  

Secondly, we now wanted to know what it took to raise money. I had
talked to friends that had raised money without getting as far into a
launch as we had gotten and had the idea that all we needed was to just
check off a bunch of checklists and thresholds and we would eventually
become acceptable to investors. I was conditioned to having this
mistaken idea from my experience getting into college or other highly
competitive programs where the application was clearcut and all one had
to do was make sure she meets all the pre-specified criteria.  
  
But I soon realized that the venture capital world was different. The
entrepreneur not only had to go out and sell the product, but more
importantly she has to relentlessly hustle and sell her vision to a
peculiar group of people who hear ideas and pitches hundreds and
sometimes thousands of times a year. Finding the door and connections to
decision-makers that can potentially invest in your company is actually
intentionally *not* clear cut at all.  
  
At this point it became abundantly clear that raising money was going to
be difficult no matter how much we improved our product. The investors
and accelerators we ended up meeting all wanted to see significant
traction in the way of users or revenue. As our personal savings were
dwindling down with no investor’s in sight, the rate of our product
iterations also began to suffer. We were concerned that we were going to
run out of runway, we didn’t have any investor meetings lined up, and
our product was getting stale to our users and we were spending lots of
money on paid traffic in order to satisfy the whims of a potential angel
investor who wanted to see 10000 users before he can make a decision to
invest. Just like a guy trying too hard to woo an attractive girl, we
began to reek of desperation and to see the writing on the wall.  
  
IDK did not work out because we couldn’t figure out how to pursue
building the product while providing for our living expenses. In other
words, we ran out of money -- *our own* money.  
  

Like most people, I thought if we got a product out, that would signal
to investors that we were ahead of most of our early stage competition
and investment dollars would follow. But that was actually quite
foolish. Investors are more than anything looking for a battle-tested
team, social validation from other investors or notable accelerators,
and a history of getting impressive things accomplished. To be clear,
having the technical chops necessary to get your product out is a
*necessary* condition, but not a *sufficient* one to impress the
investorati. So my advice to my current and previous self would be to
focus more on getting the overall vision, and storyline, and investor
connection set up right, before hunkering down and writing the first
line of code.


Archive

Start here

All posts